Čo je to strom B +?
B + Tree je primárne využívaná pre vykonávanie dynamické indexovanie na viacerých úrovniach. V porovnaní s stromom B-Tree ukladá strom B + dátové ukazovatele iba do listových uzlov stromu, čo robí vyhľadávanie presnejším a rýchlejším.
V tomto výučbe stromu B + sa dozviete:
- Čo je to strom B +?
- Pravidlá pre strom B +
- Prečo používať B + Tree
- Strom B + strom B
- Vyhľadávacia operácia
- Vložiť operáciu
- Operácia odstránenia
Pravidlá pre strom B +
Tu sú základné pravidlá pre strom B +.
- Listy sa používajú na ukladanie dátových záznamov.
- Uložilo sa to do vnútorných uzlov stromu.
- Ak je cieľová hodnota kľúča menšia ako interný uzol, potom sa sleduje bod len na jeho ľavej strane.
- Ak je cieľová hodnota kľúča väčšia alebo rovnaká ako interný uzol, bude nasledovať bod vpravo od jeho pravej strany.
- Koreň má minimálne dve deti.
Prečo používať B + Tree
Tu sú dôvody pre použitie stromu B +:
- Kľúče sa primárne používajú na uľahčenie vyhľadávania nasmerovaním na správny list.
- Strom B + používa na riadenie prírastku a úbytku stromu „faktor naplnenia“.
- V stromoch B + možno na stránku pamäte ľahko umiestniť početné kľúče, pretože nemajú údaje spojené s vnútornými uzlami. Preto bude rýchlo pristupovať k údajom stromu, ktoré sú v uzle listu.
- Komplexným úplným skenovaním všetkých prvkov je strom, ktorý potrebuje iba jeden lineárny priechod, pretože všetky listové uzly stromu B + sú navzájom spojené.
Strom B + strom B
Tu sú hlavné rozdiely medzi stromom B + a stromom B.
| Strom B + | B Strom |
| Klávesy vyhľadávania je možné opakovať. | Kľúče vyhľadávania nemôžu byť nadbytočné. |
| Údaje sa ukladajú iba do uzlov listov. | Listové uzly aj vnútorné uzly môžu ukladať údaje |
| Vďaka údajom uloženým v listovom uzle je vyhľadávanie presnejšie a rýchlejšie. | Vyhľadávanie je pomalé z dôvodu údajov uložených v Leaf a vnútorných uzloch. |
| Vymazanie nie je ťažké, pretože prvok sa odstráni iba z uzla listu. | Vymazanie prvkov je komplikovaný a časovo náročný proces. |
| Prepojené listové uzly umožňujú efektívne a rýchle vyhľadávanie. | Nemôžete prepojiť listové uzly. |
Vyhľadávacia operácia
V strome B + je vyhľadávanie jedným z najjednoduchších postupov na vykonanie a získanie rýchlych a presných výsledkov.
Použiteľný je nasledujúci vyhľadávací algoritmus:
- Ak chcete nájsť požadovaný záznam, musíte vykonať binárne vyhľadávanie v dostupných záznamoch v strome.
- V prípade presnej zhody s vyhľadávacím kľúčom sa používateľovi vráti zodpovedajúci záznam.
- V prípade, že presný kľúč nie je nájdený pri vyhľadávaní v nadradenom, aktuálnom alebo listovom uzle, potom sa používateľovi zobrazí „správa nenájdená“.
- Proces vyhľadávania je možné znova spustiť, aby ste dosiahli lepšie a presnejšie výsledky.
Vyhľadávací operačný algoritmus
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Výstup :
Užívateľovi sa zobrazí priradený záznam nastavený na presný kľúč; inak sa používateľovi zobrazí neúspešný pokus.
Vložiť operáciu
Pre operáciu vloženia je použiteľný nasledujúci algoritmus:
- 50 percent prvkov v uzloch sa presunie na nový list na uloženie.
- Rodič nového listu je presne spojený s minimálnou hodnotou kľúča a novým umiestnením v strome.
- Rozdelte nadradený uzol na viac miest pre prípad, že bude plne využitý.
- Pre lepšie výsledky je teraz stredový kľúč priradený k uzlu najvyššej úrovne daného listu.
- Kým sa nenájde uzol najvyššej úrovne, pokračujte v opakovaní procesu vysvetleného vo vyššie uvedených krokoch.
Vložte operačný algoritmus
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.
Výstup :
Algoritmus určí prvok a úspešne ho vloží do požadovaného uzla listu.
Vyššie uvedený príklad ukážky stromu B + je vysvetlený v nasledujúcich krokoch:
- Najskôr máme 3 uzly a prvé 3 prvky, ktoré sú 1, 4 a 6, sa pridajú na príslušné miesta v uzloch.
- Ďalšou hodnotou v rade údajov je 12, ktoré musia byť súčasťou Stromu.
- Aby ste to dosiahli, rozdeľte uzol a pridajte 6 ako ukazovateľový prvok.
- Teraz je vytvorená pravá hierarchia stromu a zvyšné hodnoty údajov sa zodpovedajúcim spôsobom upravia tak, že sa pamätajú na príslušné pravidlá rovnaké alebo väčšie ako hodnoty pre uzly kľúč - hodnota vpravo.
Operácia odstránenia
Zložitosť postupu odstránenia v strome B + prekonáva zložitosť funkcie vkladania a vyhľadávania.
Pri odstraňovaní prvku zo stromu B + je použiteľný nasledujúci algoritmus:
- Najskôr musíme nájsť stromový záznam, ktorý obsahuje kláves a ukazovateľ. , odstráňte listový záznam zo Stromu, ak List spĺňa presné podmienky vymazania záznamu.
- V prípade, že listový uzol spĺňa iba uspokojivý faktor polovičného zaplnenia, je operácia dokončená; inak má uzol Leaf minimálne položky a nemožno ho vymazať.
- Ostatné prepojené uzly vpravo a vľavo môžu uvoľniť ľubovoľné položky a potom ich presunúť na list. Ak tieto kritériá nie sú splnené, mali by spojiť listový uzol a jeho prepojený uzol v stromovej hierarchii.
- Po zlúčení listového uzla s jeho susedmi vpravo alebo vľavo sa odstránia položky hodnôt v listovom uzle alebo v prepojenom susednom bode smerujúcom na uzol najvyššej úrovne.
Vyššie uvedený príklad ilustruje postup odstránenia prvku zo stromu B + konkrétnej objednávky.
- Najskôr sú v strome identifikované presné umiestnenia prvku, ktorý sa má vymazať.
- Tu je možné prvok, ktorý sa má vymazať, presne identifikovať iba na úrovni listov, a nie na indexovom umiestnení. Preto je možné prvok vymazať bez ovplyvnenia pravidiel mazania, čo je hodnota kľúča minimálneho minima.
- Vo vyššie uvedenom príklade musíme zo stromu vymazať 31.
- Musíme nájsť inštancie 31 v indexe a liste.
- Vidíme, že 31 je k dispozícii na úrovni indexu aj úrovne uzla Leaf. Preto ho z obidvoch prípadov odstránime.
- Musíme však vyplniť index ukazujúci na 42. Teraz sa pozrieme na správne dieťa do 25 rokov a vezmeme minimálnu hodnotu a umiestnime ju ako index. Takže 42, ktorá je jedinou prítomnou hodnotou, sa stane indexom.
Odstrániť operačný algoritmus
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Výstup :
Kľúč „K“ sa vymaže a kľúče si v prípade potreby požičajú od súrodencov na úpravu hodnôt vn a jeho nadradených uzloch.
Zhrnutie:
- B + Tree je samovyvažujúca dátová štruktúra na vykonávanie presného a rýchlejšieho vyhľadávania, vkladania a mazania údajov
- Môžeme ľahko načítať úplné alebo čiastočné údaje, pretože prechod cez prepojenú stromovú štruktúru je efektívny.
- Stromová štruktúra B + rastie a zmenšuje sa so zvyšovaním / znižovaním počtu uložených záznamov.
- Ukladanie dát do listových uzlov a následné rozvetvenie vnútorných uzlov evidentne skracuje výšku stromu, čo znižuje operácie vstupu a výstupu disku a v konečnom dôsledku zaberá oveľa menej miesta na úložných zariadeniach.