Před pochopením B strom a B+ strom rozdíly, měli bychom znát B strom a B+ strom samostatně.
Co je strom B?
B strom je samovyrovnávací strom a je to strom m-cest, kde m definuje pořadí stromu. Bstrom je zobecněním Binární vyhledávací strom ve kterém uzel může mít více než jeden klíč a více než dva potomky v závislosti na hodnotě m . Ve stromu B jsou data specifikována v seřazeném pořadí s nižšími hodnotami v levém podstromu a vyššími hodnotami v pravém podstromu.
číst ze souboru csv v jazyce Java
Vlastnosti B stromu
Vlastnosti stromu B jsou následující:
- Ve stromu B musí být všechny listové uzly na stejné úrovni, zatímco v případě binárního stromu mohou být listové uzly na různých úrovních.
Pojďme pochopit tuto vlastnost na příkladu.
Ve výše uvedeném stromu nejsou všechny listové uzly na stejné úrovni, ale mají maximálně dvě děti. Proto můžeme říci, že výše uvedený strom je a binární strom ale ne strom B.
- Pokud má Bstrom řád m, pak každý uzel může mít maximálně m V případě minimálních potomků mají listové uzly nula potomků, kořenový uzel má dva potomky a vnitřní uzly mají strop m/2.
- Každý uzel může mít maximálně (m-1) klíčů. Pokud je například hodnota m 5, pak maximální hodnota klíčů je 4.
- Kořenový uzel má minimálně jeden klíč, zatímco všechny ostatní uzly kromě kořenového uzlu mají (strop m/2 mínus - 1) minimální klíč.
- Pokud provádíme vkládání do B stromu, pak se uzel vždy vkládá do listového uzlu.
Předpokládejme, že chceme vytvořit B strom řádu 3 vložením hodnot od 1 do 10.
Krok 1: Nejprve vytvoříme uzel s 1 hodnotou, jak je uvedeno níže:
Krok 2: Dalším prvkem je 2, který následuje po 1, jak je uvedeno níže:
Krok 3: Dalším prvkem je 3 a vkládá se za 2, jak je znázorněno níže:
Protože víme, že každý uzel může mít maximálně 2 klíče, rozdělíme tento uzel prostřednictvím prostředního prvku. Prostřední prvek je 2, takže se přesune ke svému nadřazenému prvku. Uzel 2 nemá žádného rodiče, takže se stane kořenovým uzlem, jak je znázorněno níže:
Krok 4: Dalším prvkem je 4. Protože 4 je větší než 2 a 3, bude přidán za 3, jak je znázorněno níže:
Krok 5: Dalším prvkem je 5. Protože 5 je větší než 2, 3 a 4, bude přidán za 4, jak je uvedeno níže:
Protože víme, že každý uzel může mít maximálně 2 klíče, rozdělíme tento uzel prostřednictvím prostředního prvku. Prostřední prvek je 4, takže se přesune do svého rodiče. Rodičem je uzel 2; proto se za 2 přidá 4, jak je uvedeno níže:
Krok 6: Dalším prvkem je 6. Protože 6 je větší než 2, 4 a 5, bude 6 následovat po 5, jak je uvedeno níže:
Krok 7: Dalším prvkem je 7. Protože 7 je větší než 2, 4, 5 a 6, bude 7 následovat po 6, jak je uvedeno níže:
Protože víme, že každý uzel může mít maximálně 2 klíče, rozdělíme tento uzel prostřednictvím prostředního prvku. Prostřední prvek je 6, takže se přesune ke svému nadřazenému prvku, jak je znázorněno níže:
Ale 6 nelze přidat po 4, protože uzel může mít maximálně 2 klíče, takže tento uzel rozdělíme prostředním prvkem. Prostřední prvek je 4, takže se přesune do svého rodiče. Protože uzel 4 nemá žádného rodiče, uzel 4 se stane kořenovým uzlem, jak je znázorněno níže:
Co je to strom B+?
The B+ strom je také známý jako pokročilý samovyvážený strom, protože každá cesta od kořene stromu k listu stromu má stejnou délku. Zde stejná délka znamená, že všechny uzly listů se vyskytují na stejné úrovni. Nestane se tak, že by se některé z listových uzlů vyskytovaly na třetí úrovni a některé z nich na druhé úrovni.
Index stromu B+ je považován za víceúrovňový index, ale stromová struktura B+ není podobná sekvenčním souborům víceúrovňového indexu.
Proč se používá strom B+?
Strom B+ se používá k velmi efektivnímu ukládání záznamů tím, že se záznamy ukládají indexovaným způsobem pomocí indexované struktury stromu B+. Díky víceúrovňovému indexování je přístup k datům rychlejší a jednodušší.
B+ stromová struktura uzlu
Struktura uzlů stromu B+ obsahuje ukazatele a hodnoty klíčů znázorněné na obrázku níže:
Jak můžeme pozorovat ve výše uvedené struktuře uzlů stromu B+, obsahuje n-1 klíčových hodnot (k1do kn-1) a n ukazatelů (str1hornín).
Hodnoty vyhledávacích klíčů, které jsou umístěny v uzlu, jsou udržovány v seřazeném pořadí. Pokud tedy i
Omezení na různé typy uzlů
Nechť 'b' je pořadí stromu B+.
Nelistový uzel
Nechť 'm' představuje počet potomků uzlu, pak vztah mezi pořadím stromu a počtem dětí může být reprezentován jako:
Nechť k představuje hodnoty klíče hledání. Vztah mezi pořadím stromu a vyhledávacím klíčem může být reprezentován jako:
Protože víme, že počet ukazatelů se rovná hodnotám vyhledávacích klíčů plus 1, takže matematicky to lze zapsat jako:
java stack
Počet ukazatelů (nebo dětí) = počet vyhledávacích kláves + 1
Proto by maximální počet ukazatelů byl 'b' a minimální počet ukazatelů by byl stropní funkcí b/2.
Listový uzel
Listový uzel je uzel, který se vyskytuje na poslední úrovni stromu B+ a každý listový uzel používá ke vzájemnému propojení pouze jeden ukazatel, aby byl zajištěn sekvenční přístup na úrovni listu.
V listovém uzlu je maximální počet dětí:
Maximální počet vyhledávacích klíčů je:
Kořenový uzel
Maximální počet potomků v případě kořenového uzlu je: b
Minimální počet dětí je: 2
Speciální případy ve stromu B+
Případ 1: Pokud je kořenový uzel jediným uzlem ve stromu. V tomto případě se kořenový uzel stane listovým uzlem.
V tomto případě je maximální počet potomků 1, tj. samotný kořenový uzel, zatímco minimální počet potomků je b-1, což je stejné jako u listového uzlu.
Reprezentace listového uzlu ve stromu B+
Na obrázku výše je '.' představuje ukazatel, zatímco 10, 20 a 30 jsou klíčové hodnoty. Ukazatel obsahuje adresu, na které je uložena hodnota klíče, jak je znázorněno na obrázku výše.
Příklad stromu B+
Na obrázku výše uzel obsahuje tři hodnoty klíče, tj. 9, 16 a 25. Ukazatel, který se objeví před 9, obsahuje hodnoty klíče menší než 9 reprezentované ki. Ukazatel, který se objeví před 16, obsahuje klíčové hodnoty větší nebo rovné 9, ale menší než 16 reprezentované kj. Ukazatel, který se objeví před 25, obsahuje klíčové hodnoty větší nebo rovné 16, ale menší než 25 reprezentované kn.
Rozdíly mezi stromem B a stromem B+
Níže jsou uvedeny rozdíly mezi stromem B a stromem B+:
| B strom | B+ strom |
|---|---|
| Ve stromu B jsou všechny klíče a záznamy uloženy v interních i listových uzlech. | Ve stromu B+ jsou klíče indexy uložené ve vnitřních uzlech a záznamy jsou uloženy v listových uzlech. |
| Ve stromu B nelze klíče opakovaně ukládat, což znamená, že nedochází k duplikaci klíčů nebo záznamů. | Ve stromu B+ může být výskyt klíčů redundantní. V tomto případě jsou záznamy uloženy v koncových uzlech, zatímco klíče jsou uloženy v interních uzlech, takže v interních uzlech mohou být přítomny redundantní klíče. |
| V Bstromu nejsou listové uzly vzájemně propojeny. | Ve stromu B+ jsou listové uzly vzájemně propojeny, aby poskytovaly sekvenční přístup. |
| V Btree není vyhledávání příliš efektivní, protože záznamy jsou uloženy buď v listových nebo interních uzlech. | Ve stromu B+ je vyhledávání velmi efektivní nebo rychlejší, protože všechny záznamy jsou uloženy v listových uzlech. |
| Mazání vnitřních uzlů je velmi pomalé a časově náročný proces, protože musíme vzít v úvahu také potomka odstraněného klíče. | Mazání ve stromu B+ je velmi rychlé, protože všechny záznamy jsou uloženy v listových uzlech, takže nemusíme brát v úvahu potomka uzlu. |
| V Btree není sekvenční přístup možný. | Ve stromu B+ jsou všechny listové uzly navzájem propojeny pomocí ukazatele, takže je možný sekvenční přístup. |
| V Btree se provádí čím více štípacích operací, díky čemuž se výška zvyšuje ve srovnání s šířkou, | Strom B+ má větší šířku ve srovnání s výškou. |
| V Btree má každý uzel alespoň dvě větve a každý uzel obsahuje nějaké záznamy, takže pro získání dat nemusíme procházet až do listových uzlů. | Ve stromu B+ obsahují interní uzly pouze ukazatele a listové uzly obsahují záznamy. Všechny listové uzly jsou na stejné úrovni, takže musíme procházet až k listovým uzlům, abychom získali data. |
| Kořenový uzel obsahuje alespoň 2 až m dětí, kde m je pořadí stromu. | Kořenový uzel obsahuje alespoň 2 až m dětí, kde m je pořadí stromu. |