Co je to strom B +?
B + Tree je primárně využívána pro provádění dynamické indexování na více úrovních. Ve srovnání s B-stromem ukládá strom B + datové ukazatele pouze na listové uzly stromu, díky čemuž je vyhledávání přesnější a rychlejší.
V tomto výukovém programu B + Tree se naučíte:
- Co je to strom B +?
- Pravidla pro strom B +
- Proč používat B + Tree
- B + strom vs. B strom
- Vyhledávací operace
- Operace vložení
- Smazat operaci
Pravidla pro strom B +
Zde jsou základní pravidla pro B + Tree.
- Listy se používají 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ž interní uzel, je sledován bod jen na jeho levé straně.
- Pokud je hodnota cílového klíče větší nebo rovna vnitřnímu uzlu, je sledován bod jen na jeho pravé straně.
- Kořen má minimálně dvě děti.
Proč používat B + Tree
Tady jsou důvody pro použití stromu B +:
- Klíč se primárně používá k podpoře vyhledávání tím, že nasměruje na správný list.
- B + Tree používá "faktor naplnění" ke správě zvětšení a zmenšení stromu.
- Ve stromech B + lze na stránku paměti snadno umístit mnoho klíčů, protože nemají data spojená s vnitřními uzly. Proto bude rychle přistupovat k datům stromu, která jsou v listovém uzlu.
- Komplexní úplné prohledá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.
B + strom vs. B strom
Zde jsou hlavní rozdíly mezi stromy B + a B
| B + strom | B Strom |
| Vyhledávací klávesy lze opakovat. | Vyhledávací klíče nemohou být nadbytečné. |
| Data se ukládají pouze na listové uzly. | Jak listové uzly, tak interní uzly mohou ukládat data |
| Díky datům uloženým v listovém uzlu je vyhledávání přesnější a rychlejší. | Hledá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 uzlu listu. | Odstranění prvků je složitý a časově náročný proces. |
| Propojené listové uzly umožňují efektivní a rychlé vyhledávání. | Nelze propojit uzly listu. |
Vyhledávací operace
Ve stromu B + 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.
Platí následující vyhledávací algoritmus:
- Chcete-li najít požadovaný záznam, musíte provést binární vyhledávání v dostupných záznamech ve stromu.
- V případě přesné shody s vyhledávacím klíčem se odpovídající záznam vrátí uživateli.
- V případě, že přesný klíč není nalezen při hledání v nadřazeném, aktuálním nebo listovém uzlu, zobrazí se uživateli „zpráva nenalezena“.
- Proces vyhledávání lze znovu spustit a získat tak lepší a přesnější výsledky.
Algoritmus vyhledávací operace
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živateli se zobrazí odpovídající záznam nastavený na přesný klíč; jinak se uživateli zobrazí neúspěšný pokus.
Operace vložení
Pro operaci vložení je použitelný následující algoritmus:
- 50 procent prvků v uzlech je přesunuto do nového listu pro uložení.
- Nadřazený prvek nového listu je přesně spojen s minimální hodnotou klíče a novým umístěním ve stromu.
- Rozdělte nadřazený uzel na více míst pro případ, že bude plně využit.
- Pro lepší výsledky je nyní středový klíč přidružen k uzlu nejvyšší úrovně daného listu.
- Dokud nebude nalezen uzel nejvyšší úrovně, pokračujte v iteraci procesu vysvětleného ve výše uvedených krocích.
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čí prvek a úspěšně jej vloží do požadovaného uzlu listu.
Výše uvedený ukázkový příklad stromu B + je vysvětlen v následujících krocích:
- Nejprve máme 3 uzly a první 3 prvky, které jsou 1, 4 a 6, jsou přidány na příslušných místech v uzlech.
- Další hodnota 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 prvek ukazatele.
- Nyní je vytvořena pravá hierarchie stromu a zbývající datové hodnoty jsou odpovídajícím způsobem upraveny tak, že budete mít na paměti příslušná pravidla stejná nebo větší než hodnoty proti uzlům klíč – hodnota vpravo.
Smazat operaci
Složitost postupu mazání ve stromu B + převyšuje složitost funkce vkládání a vyhledávání.
Při odstraňování prvku ze stromu B + je použitelný následující algoritmus:
- Nejprve musíme ve stromu najít listovou položku, která obsahuje klíč a ukazatel. , odstraňte položku listu ze Stromu, pokud List splňuje přesné podmínky 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 Leaf minimální počet položek a nelze jej odstranit.
- Ostatní propojené uzly vpravo a vlevo mohou uvolnit jakékoli položky a poté je přesunout na List. Pokud tato kritéria nejsou splněna, měli by kombinovat listový uzel a jeho propojený uzel v hierarchii stromu.
- Po sloučení listového uzlu s jeho sousedy vpravo nebo vlevo budou odstraněny položky hodnot v listovém uzlu nebo propojeném sousedovi směřující k uzlu nejvyšší úrovně.
Výše uvedený příklad ilustruje postup odebrání prvku ze stromu B + určitého pořadí.
- 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, nikoli na umístění indexu. Proto může být prvek odstraněn bez ovlivnění pravidel mazání, což je hodnota klíčového minima.
- Ve výše uvedeném příkladu musíme odstranit 31 ze stromu.
- Musíme najít instance 31 v indexu a listu.
- Vidíme, že 31 je k dispozici na úrovni uzlů Index i Leaf. Proto jej odstraníme z obou případů.
- 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 jedinou přítomnou hodnotou a stane se indexem.
Smazat 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 :
Klíč „K“ je odstraněn a klíče jsou v případě potřeby vypůjčeny od sourozenců pro úpravu hodnot vn a jeho nadřazených uzlech.
Souhrn:
- B + Tree je samovyvažující 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 načíst úplná nebo částečná data, protože procházení propojené stromové struktury je efektivní.
- Stromová struktura B + roste a zmenšuje se zvyšováním / snižováním počtu uložených záznamů.
- Ukládání dat na listové uzly a následné větvení vnitřních uzlů evidentně zkracuje výšku stromu, což snižuje operace vstupu a výstupu disku a nakonec spotřebovává mnohem méně místa na úložných zařízeních.