Pred pochopením B strom a B+ strom rozdiely by sme mali poznať B strom a B+ strom oddelene.
Čo je to strom B?
B strom je samovyvažovací strom a je to m-cestný strom, kde m definuje poradie stromu. Btree je zovšeobecnením Binárny vyhľadávací strom v ktorom môže mať uzol viac ako jeden kľúč a viac ako dve potomky v závislosti od hodnoty m . V strome B sú údaje špecifikované v zoradenom poradí s nižšími hodnotami v ľavom podstrome a vyššími hodnotami v pravom podstrome.
reťazec v char java
Vlastnosti B stromu
Nasledujú vlastnosti stromu B:
- V strome B musia byť všetky uzly listov na rovnakej úrovni, zatiaľ čo v prípade binárneho stromu môžu byť uzly listov na rôznych úrovniach.
Poďme pochopiť túto vlastnosť na príklade.
Vo vyššie uvedenom strome nie sú všetky uzly listov na rovnakej úrovni, ale majú maximálne dve deti. Preto môžeme povedať, že vyššie uvedený strom je a binárny strom ale nie B strom.
- Ak má Bstrom rádovo m, potom každý uzol môže mať maximálne m V prípade minimálnych detí majú listové uzly nula detí, koreňový uzol má dve deti a vnútorné uzly majú strop m/2.
- Každý uzol môže mať maximálne (m-1) kľúčov. Ak je napríklad hodnota m 5, maximálna hodnota kľúčov je 4.
- Koreňový uzol má minimálne jeden kľúč, zatiaľ čo všetky ostatné uzly okrem koreňového majú (strop m/2 mínus - 1) minimálne kľúče.
- Ak vykonávame vkladanie do B stromu, tak uzol je vždy vložený do listového uzla.
Predpokladajme, že chceme vytvoriť strom B rádu 3 vložením hodnôt od 1 do 10.
Krok 1: Najprv vytvoríme uzol s 1 hodnotou, ako je uvedené nižšie:
Krok 2: Ďalším prvkom je 2, ktorý nasleduje po 1, ako je uvedené nižšie:
Krok 3: Ďalší prvok je 3 a vkladá sa za 2, ako je znázornené nižšie:
Keďže vieme, že každý uzol môže mať maximálne 2 kľúče, rozdelíme tento uzol cez stredný prvok. Stredný prvok je 2, takže sa presunie k svojmu rodičovi. Uzol 2 nemá žiadneho rodiča, takže sa stane koreňovým uzlom, ako je uvedené nižšie:
Krok 4: Ďalším prvkom je 4. Keďže 4 je väčšie ako 2 a 3, pridá sa za 3, ako je uvedené nižšie:
Krok 5: Ďalším prvkom je 5. Keďže 5 je väčšie ako 2, 3 a 4, pridá sa za 4, ako je uvedené nižšie:
Keďže vieme, že každý uzol môže mať maximálne 2 kľúče, rozdelíme tento uzol cez stredný prvok. Stredný prvok je 4, takže sa presunie k svojmu rodičovi. Rodičom je uzol 2; preto sa za 2 pridá 4, ako je uvedené nižšie:
Krok 6: Ďalším prvkom je 6. Keďže 6 je väčšie ako 2, 4 a 5, 6 bude nasledovať po 5, ako je uvedené nižšie:
Krok 7: Ďalším prvkom je 7. Keďže 7 je väčšie ako 2, 4, 5 a 6, 7 bude nasledovať po 6, ako je uvedené nižšie:
Keďže vieme, že každý uzol môže mať maximálne 2 kľúče, rozdelíme tento uzol cez stredný prvok. Stredný prvok je 6, takže sa presunie k svojmu rodičovi, ako je znázornené nižšie:
6 však nemožno pridať po 4, pretože uzol môže mať maximálne 2 kľúče, takže tento uzol rozdelíme cez stredný prvok. Stredný prvok je 4, takže sa presunie k svojmu rodičovi. Keďže uzol 4 nemá žiadneho rodiča, uzol 4 sa stane koreňovým uzlom, ako je uvedené nižšie:
Čo je to strom B+?
The B+ strom je tiež známy ako pokročilý samovyvážený strom, pretože každá cesta od koreňa stromu po list stromu má rovnakú dĺžku. Tu rovnaká dĺžka znamená, že všetky uzly listov sa vyskytujú na rovnakej úrovni. Nestane sa tak, že niektoré z listových uzlov sa vyskytnú na tretej úrovni a niektoré z nich na druhej úrovni.
Index stromu B+ sa považuje za viacúrovňový index, ale stromová štruktúra B+ nie je podobná viacúrovňovým indexovým sekvenčným súborom.
Prečo sa používa strom B+?
Strom B+ sa používa na veľmi efektívne ukladanie záznamov tým, že sa záznamy ukladajú indexovaným spôsobom pomocou indexovanej štruktúry stromu B+. Vďaka viacúrovňovému indexovaniu je prístup k údajom rýchlejší a jednoduchší.
B+ stromová štruktúra uzla
Štruktúra uzla stromu B+ obsahuje ukazovatele a hodnoty kľúčov zobrazené na obrázku nižšie:
Ako môžeme vidieť vo vyššie uvedenej štruktúre uzlov stromu B+, že obsahuje n-1 kľúčových hodnôt (k1do kn-1) a n ukazovateľov (s1na pn).
Hodnoty vyhľadávacích kľúčov, ktoré sú umiestnené v uzle, sa uchovávajú v zoradenom poradí. Ak teda i
Obmedzenie rôznych typov uzlov
Nech 'b' je poradie B+ stromu.
Nelistový uzol
monitor s katódovou trubicou
Nech „m“ predstavuje počet detí uzla, potom vzťah medzi poradím stromu a počtom detí môže byť reprezentovaný ako:
Nech k predstavuje hodnoty kľúča vyhľadávania. Vzťah medzi poradím stromu a kľúčom vyhľadávania môže byť reprezentovaný ako:
Keďže vieme, že počet ukazovateľov sa rovná hodnotám kľúča vyhľadávania plus 1, takže matematicky to možno zapísať ako:
Počet ukazovateľov (alebo detí) = počet vyhľadávacích kláves + 1
Preto by maximálny počet ukazovateľov bol „b“ a minimálny počet ukazovateľov by bol stropnou funkciou b/2.
Listový uzol
Listový uzol je uzol, ktorý sa vyskytuje na poslednej úrovni stromu B+ a každý listový uzol používa iba jeden ukazovateľ na vzájomné prepojenie, aby sa zabezpečil sekvenčný prístup na úrovni listu.
V listovom uzle je maximálny počet detí:
Maximálny počet vyhľadávacích kľúčov je:
Koreňový uzol
Maximálny počet detí v prípade koreňového uzla je: b
Minimálny počet detí je: 2
Špeciálne prípady v strome B+
Prípad 1: Ak je koreňový uzol jediným uzlom v strome. V tomto prípade sa koreňový uzol stáva listovým uzlom.
V tomto prípade je maximálny počet detí 1, t. j. samotný koreňový uzol, zatiaľ čo minimálny počet detí je b-1, čo je rovnaký počet ako listový uzol.
Reprezentácia listového uzla v B+ strome
Na obrázku vyššie „.“ predstavuje ukazovateľ, zatiaľ čo 10, 20 a 30 sú kľúčové hodnoty. Ukazovateľ obsahuje adresu, na ktorej je uložená hodnota kľúča, ako je znázornené na obrázku vyššie.
Príklad stromu B+
Na obrázku vyššie obsahuje uzol tri kľúčové hodnoty, t. j. 9, 16 a 25. Ukazovateľ, ktorý sa objaví pred 9, obsahuje kľúčové hodnoty menšie ako 9 reprezentované ki. Ukazovateľ, ktorý sa objaví pred 16, obsahuje kľúčové hodnoty väčšie alebo rovné 9, ale menšie ako 16 reprezentované kj. Ukazovateľ, ktorý sa objaví pred 25, obsahuje kľúčové hodnoty väčšie alebo rovné 16, ale menšie ako 25 reprezentované kn.
Rozdiely medzi stromom B a stromom B+
Nasledujú rozdiely medzi stromom B a stromom B+:
| B strom | B+ strom |
|---|---|
| V strome B sú všetky kľúče a záznamy uložené v interných aj listových uzloch. | V strome B+ sú kľúče indexy uložené vo vnútorných uzloch a záznamy sú uložené v listových uzloch. |
| V strome B nie je možné opakovane ukladať kľúče, čo znamená, že nedochádza k duplicite kľúčov alebo záznamov. | V strome B+ môže byť výskyt kľúčov nadbytočný. V tomto prípade sú záznamy uložené v listových uzloch, zatiaľ čo kľúče sú uložené vo vnútorných uzloch, takže vo vnútorných uzloch môžu byť prítomné redundantné kľúče. |
| V Bstrome nie sú listové uzly navzájom prepojené. | V strome B+ sú listové uzly navzájom prepojené, aby poskytli sekvenčný prístup. |
| V Btree nie je vyhľadávanie veľmi efektívne, pretože záznamy sú uložené buď v listových alebo interných uzloch. | V strome B+ je vyhľadávanie veľmi efektívne alebo rýchlejšie, pretože všetky záznamy sú uložené v listových uzloch. |
| Odstránenie interných uzlov je veľmi pomalý a časovo náročný proces, pretože musíme brať do úvahy aj potomka odstráneného kľúča. | Odstránenie v strome B+ je veľmi rýchle, pretože všetky záznamy sú uložené v listových uzloch, takže nemusíme brať do úvahy potomka uzla. |
| V Btree nie je možný sekvenčný prístup. | V strome B+ sú všetky listové uzly navzájom prepojené pomocou ukazovateľa, takže je možný sekvenčný prístup. |
| V Btree sa vykonáva čím viac štiepacích operácií, čím sa zvyšuje výška v porovnaní so šírkou, | Strom B+ má väčšiu šírku v porovnaní s výškou. |
| V Btree má každý uzol aspoň dve vetvy a každý uzol obsahuje nejaké záznamy, takže na získanie údajov nemusíme prechádzať do listových uzlov. | V strome B+ obsahujú interné uzly iba ukazovatele a listové uzly obsahujú záznamy. Všetky listové uzly sú na rovnakej úrovni, takže na získanie údajov musíme prejsť až po listové uzly. |
| Koreňový uzol obsahuje najmenej 2 až m detí, kde m je poradie stromu. | Koreňový uzol obsahuje najmenej 2 až m detí, kde m je poradie stromu. |