B+ Tree je rozšířením B Tree, které umožňuje efektivní operace vkládání, mazání a vyhledávání.
Ve stromu B mohou být klíče a záznamy uloženy v interních i listových uzlech. Zatímco ve stromu B+ mohou být záznamy (data) uloženy pouze na listových uzlech, zatímco interní uzly mohou ukládat pouze hodnoty klíče.
Listové uzly stromu B+ jsou propojeny ve formě jednoduše propojených seznamů, aby byly vyhledávací dotazy efektivnější.
B+ Tree slouží k uložení velkého množství dat, která nelze uložit do hlavní paměti. Vzhledem k tomu, že velikost hlavní paměti je vždy omezena, jsou interní uzly (klíče pro přístup k záznamům) stromu B+ uloženy v hlavní paměti, zatímco listové uzly jsou uloženy v sekundární paměti.
Vnitřní uzly stromu B+ se často nazývají indexové uzly. B+ strom řádu 3 je znázorněn na následujícím obrázku.
Výhody B+ Tree
- Záznamy lze načíst stejným počtem přístupů na disk.
- Výška stromu zůstává vyrovnaná a menší ve srovnání se stromem B.
- K datům uloženým ve stromu B+ můžeme přistupovat sekvenčně i přímo.
- K indexování se používají klíče.
- Rychlejší vyhledávací dotazy, protože data jsou uložena pouze na listových uzlech.
Strom B VS Strom B+
| SN | B strom | B+ strom |
|---|---|---|
| 1 | Tlačítka vyhledávání nelze opakovaně ukládat. | Mohou být přítomny redundantní vyhledávací klíče. |
| 2 | Data mohou být uložena v listových uzlech i vnitřních uzlech | Data mohou být uložena pouze na listových uzlech. |
| 3 | Vyhledávání některých dat je pomalejší proces, protože data lze nalézt na interních uzlech i na listových uzlech. | Vyhledávání je poměrně rychlejší, protože data lze nalézt pouze na listových uzlech. |
| 4 | Mazání vnitřních uzlů je tak složité a časově náročné. | Odstranění nebude nikdy složitý proces, protože prvek bude vždy odstraněn z koncových uzlů. |
| 5 | Listové uzly nelze propojit. | Listové uzly jsou propojeny, aby byly operace vyhledávání efektivnější. |
Vložení do B+ stromu
Krok 1: Vložte nový uzel jako listový uzel
Krok 2: Pokud list nemá požadované místo, rozdělte uzel a zkopírujte prostřední uzel do dalšího indexového uzlu.
Krok 3: Pokud uzel indexu nemá požadované místo, rozdělte uzel a zkopírujte prostřední prvek na další stránku indexu.
Příklad:
Vložte hodnotu 195 do stromu B+ řádu 5 znázorněného na následujícím obrázku.
195 bude vložen do pravého podstromu 120 za 190. Vložte jej na požadované místo.
Uzel obsahuje větší než maximální počet prvků, tedy 4, proto jej rozdělte a umístěte střední uzel až k nadřazenému.
Nyní indexový uzel obsahuje 6 potomků a 5 klíčů, což porušuje vlastnosti stromu B+, proto jej musíme rozdělit, jak je znázorněno následovně.
Smazání ve stromu B+
Krok 1: Odstraňte klíč a data z listů.
Krok 2: pokud listový uzel obsahuje méně než minimální počet prvků, sloučte uzel dolů s jeho sourozencem a odstraňte klíč mezi nimi.
Krok 3: pokud indexový uzel obsahuje méně než minimální počet prvků, slučte uzel se sourozencem a přesuňte klíč dolů mezi ně.
Příklad
Odstraňte klíč 200 ze stromu B+ znázorněného na následujícím obrázku.
200 je přítomno v pravém podstromu 190, po 195. smažte jej.
Sloučte dva uzly pomocí 195, 190, 154 a 129.
Nyní je prvek 120 jediným prvkem přítomným v uzlu, který porušuje vlastnosti stromu B+. Proto jej musíme sloučit pomocí 60, 78, 108 a 120.
Nyní se výška stromu B+ sníží o 1.
