B+ STROM : Hledat, vkládat a mazat OperaPříklad

Co je to strom B+?

A B+ strom se primárně používá pro implementaci dynamického indexování na více úrovních. Ve srovnání s B-Stromem, B+ Tree ukládá datové ukazatele pouze na listových uzlech Stromu, díky čemuž je vyhledávání přesnější a rychlejší.

Pravidla pro strom B+

Zde jsou základní pravidla pro B+ Tree.

• Listy slouží k ukládání datových záznamů.
• Je uložen ve vnitřních uzlech Stromu.
• Pokud je hodnota cílového klíče menší než vnitřní uzel, bude následovat bod těsně na jeho levé straně.
• Pokud je hodnota cílového klíče větší nebo rovna vnitřnímu uzlu, bude následovat bod na jeho pravé straně.
• Kořen má minimálně dvě děti.

Proč používat B+ Tree

Zde jsou důvody pro použití B+ Tree:

• Klíč se primárně používá k usnadnění hledání nasměrováním na správný list.
• B+ Tree používá „faktor plnění“ pro řízení nárůstu a poklesu ve stromu.
• Ve stromech B+ lze na stránku paměti snadno umístit četné klíče, protože nemají data spojená s vnitřními uzly. Proto bude rychle přistupovat k datům stromu, která jsou na listovém uzlu.
• Komplexní úplné skenování všech prvků je strom, který potřebuje pouze jeden lineární průchod, protože všechny listové uzly stromu B+ jsou vzájemně propojeny.

Strom B+ vs. Strom B

Zde jsou hlavní rozdíly mezi stromem B+ a stromem B

B+ strom	B strom
Tlačítka vyhledávání lze opakovat.	Vyhledávací klíče nemohou být nadbytečné.
Data se ukládají pouze na listových uzlech.	Data mohou ukládat jak listové uzly, tak vnitřní uzly
Data uložená na listovém uzlu zpřesňují a zrychlují vyhledávání.	Vyhledávání je pomalé kvůli datům uloženým na Leaf a interních uzlech.
Odstranění není obtížné, protože prvek je odstraněn pouze z listového uzlu.	Odstraňování prvků je komplikovaný a časově náročný proces.
Propojené listové uzly umožňují efektivní a rychlé vyhledávání.	Listové uzly nelze propojit.

Hledat Operavání

V B+ Tree je vyhledávání jedním z nejjednodušších postupů, které lze provést a získat z něj rychlé a přesné výsledky.

Lze použít následující vyhledávací algoritmus:

• Chcete-li najít požadovaný záznam, musíte provést binární vyhledávání na dostupných záznamech ve Stromu.
• V případě přesné shody s vyhledávacím klíčem je uživateli vrácen odpovídající záznam.
• V případě, že přesný klíč není nalezen při vyhledávání v nadřazeném, aktuálním nebo koncovém uzlu, zobrazí se uživateli zpráva „nenalezena“.
• Pro lepší a přesnější výsledky lze proces vyhledávání znovu spustit.

Hledat OperaAlgoritmus

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

Výstup:

Uživateli se zobrazí odpovídající záznam nastavený s přesným klíčem; jinak se uživateli zobrazí neúspěšný pokus.

Vložit Operavání

Pro operaci vložení je použitelný následující algoritmus:

• 50 procent prvků v uzlech se přesune do nového listu pro uložení.
• Rodič nového listu je přesně propojen s minimální hodnotou klíče a novým umístěním ve Stromu.
• Rozdělte nadřazený uzel na více umístění v případě, že bude plně využit.
• Nyní, pro lepší výsledky, je středový klíč spojen s uzlem nejvyšší úrovně tohoto listu.
• Dokud nebude uzel nejvyšší úrovně nalezen, pokračujte v opakování procesu popsaného ve výše uvedených krocích.

Vložit OperaAlgoritmus

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. 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 tree
      b. 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čí prvek a úspěšně jej vloží do požadovaného listového uzlu.

Výše uvedený ukázkový příklad stromu B+ je vysvětlen v následujících krocích:

• Za prvé, máme 3 uzly a první 3 prvky, což jsou 1, 4 a 6, jsou přidány na vhodná místa v uzlech.
• Další hodnotou v řadě dat je 12, která musí být součástí stromu.
• Chcete-li toho dosáhnout, rozdělte uzel a přidejte 6 jako ukazatel.
• Nyní je vytvořena pravá hierarchie stromu a zbývající datové hodnoty jsou odpovídajícím způsobem upraveny, přičemž je třeba pamatovat na platná pravidla rovnající se nebo větší než hodnoty proti uzlům klíč-hodnota vpravo.

Vymazat Operavání

Složitost postupu odstranění ve stromu B+ překonává funkci vkládání a vyhledávání.

Při odstraňování prvku ze stromu B+ lze použít následující algoritmus:

• Nejprve musíme ve Stromu najít položku listu, která drží klíč a ukazatel. , vymažte záznam listu ze Stromu, pokud list splňuje přesné podmínky pro smazání záznamu.
• V případě, že listový uzel splňuje pouze uspokojivý faktor polovičního zaplnění, je operace dokončena; jinak má uzel List minimum položek a nelze jej odstranit.
• Ostatní propojené uzly napravo a nalevo mohou uvolnit libovolné položky a přesunout je do listu. Pokud tato kritéria nejsou splněna, měli by kombinovat listový uzel a jeho propojený uzel ve stromové hierarchii.
• Při sloučení listového uzlu s jeho sousedy napravo nebo nalevo se vymažou položky hodnot v listovém uzlu nebo propojeném sousedovi ukazujícím na uzel nejvyšší úrovně.

Výše uvedený příklad ilustruje postup odstranění prvku ze stromu B+ konkrétní objednávky.

• Nejprve jsou ve Stromu identifikována přesná umístění prvku, který má být odstraněn.
• Zde lze prvek, který má být odstraněn, přesně identifikovat pouze na úrovni listu a nikoli na umístění indexu. Prvek lze tedy odstranit, aniž by to ovlivnilo pravidla mazání, což je hodnota klíče holého minima.

• Ve výše uvedeném příkladu musíme odstranit 31 ze stromu.
• Potřebujeme najít instance 31 v Index a Leaf.
• Vidíme, že 31 je k dispozici na úrovni uzlu Index i List. Proto jej odstraníme z obou instancí.
• Musíme však vyplnit index ukazující na 42. Nyní se podíváme na správné dítě do 25 let a vezmeme minimální hodnotu a umístíme ji jako index. Takže, 42 je jediná přítomná hodnota, stane se indexem.

Vymazat OperaAlgoritmus

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) 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 node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

Výstup:

Klíč „K“ je vymazán a klíče jsou vypůjčeny od sourozenců pro úpravu hodnot v n a jeho nadřazených uzlech, pokud je to potřeba.

Shrnutí

• B+ Tree je samovyrovnávací datová struktura pro provádění přesného a rychlejšího vyhledávání, vkládání a mazání dat
• Můžeme snadno získat kompletní data nebo částečná data, protože procházení propojené stromové struktury to zefektivňuje.
• Stromová struktura B+ roste a zmenšuje se s nárůstem/snížením počtu uložených záznamů.
• Ukládání dat na listových uzlech a následné větvení vnitřních uzlů evidentně zkracuje výšku stromu, což snižuje vstupní a výstupní operace disku a v konečném důsledku spotřebuje mnohem méně místa na úložných zařízeních.