Voordat het begrepen wordt B-boom En B+ boom verschillen, moeten we de B-boom en de B+-boom afzonderlijk kennen.
Wat is de B-boom?
B-boom is een zelfbalancerende boom, en het is een m-wegboom waarbij m de volgorde van de boom definieert. Bboom is een generalisatie van de Binaire zoekboom waarin een knooppunt meer dan één sleutel en meer dan twee kinderen kan hebben, afhankelijk van de waarde van M . In de B-boom worden de gegevens gespecificeerd in een gesorteerde volgorde met lagere waarden in de linker subboom en hogere waarden in de rechter subboom.
css een afbeelding centreren
Eigenschappen van B-boom
Dit zijn de eigenschappen van de B-boom:
- In de B-boom moeten alle bladknooppunten zich op hetzelfde niveau bevinden, terwijl in het geval van een binaire boom de bladknooppunten zich op verschillende niveaus kunnen bevinden.
Laten we deze eigenschap begrijpen aan de hand van een voorbeeld.
In de bovenstaande boom bevinden alle bladknopen zich niet op hetzelfde niveau, maar ze hebben maximaal twee kinderen. Daarom kunnen we zeggen dat de bovenstaande boom een binaire boom maar geen B-boom.
- Als de Bboom de orde van m heeft, kan elk knooppunt er maximaal hebben M In het geval van minimale kinderen hebben de bladknooppunten nul kinderen, heeft de wortelknoop twee kinderen en hebben de interne knooppunten een plafond van m/2.
- Elk knooppunt kan maximaal (m-1) sleutels hebben. Als de waarde van m bijvoorbeeld 5 is, is de maximale waarde van sleutels 4.
- Het rootknooppunt heeft minimaal één sleutel, terwijl alle andere knooppunten behalve het rootknooppunt (plafond van m/2 minus - 1) minimumsleutels hebben.
- Als we invoeging in de B-boom uitvoeren, wordt het knooppunt altijd in het bladknooppunt ingevoegd.
Stel dat we een B-boom van orde 3 willen maken door waarden van 1 tot 10 in te voegen.
Stap 1: Eerst maken we een knooppunt met 1 waarde, zoals hieronder weergegeven:
Stap 2: Het volgende element is 2, dat na 1 komt, zoals hieronder weergegeven:
Stap 3: Het volgende element is 3 en wordt na 2 ingevoegd, zoals hieronder weergegeven:
Omdat we weten dat elk knooppunt maximaal 2 sleutels kan hebben, splitsen we dit knooppunt door het middelste element. Het middelste element is 2, dus het verplaatst zich naar het bovenliggende element. Knooppunt 2 heeft geen ouder, dus het wordt het hoofdknooppunt, zoals hieronder weergegeven:
Stap 4: Het volgende element is 4. Omdat 4 groter is dan 2 en 3, wordt het na de 3 toegevoegd, zoals hieronder weergegeven:
Stap 5: Het volgende element is 5. Omdat 5 groter is dan 2, 3 en 4, wordt het na 4 toegevoegd, zoals hieronder weergegeven:
Omdat we weten dat elk knooppunt maximaal 2 sleutels kan hebben, splitsen we dit knooppunt door het middelste element. Het middelste element is 4, dus het verplaatst zich naar het bovenliggende element. De ouder is knooppunt 2; daarom wordt er 4 toegevoegd na 2, zoals hieronder weergegeven:
Stap 6: Het volgende element is 6. Omdat 6 groter is dan 2, 4 en 5, komt 6 na 5, zoals hieronder weergegeven:
Stap 7: Het volgende element is 7. Omdat 7 groter is dan 2, 4, 5 en 6, komt 7 na 6, zoals hieronder weergegeven:
Omdat we weten dat elk knooppunt maximaal 2 sleutels kan hebben, splitsen we dit knooppunt door het middelste element. Het middelste element is 6, dus het verplaatst zich naar het bovenliggende element, zoals hieronder weergegeven:
Maar 6 kan niet worden toegevoegd na 4 omdat het knooppunt maximaal 2 sleutels kan hebben, dus we zullen dit knooppunt door het middelste element splitsen. Het middelste element is 4, dus het verplaatst zich naar het bovenliggende element. Omdat knooppunt 4 geen ouder heeft, wordt knooppunt 4 een hoofdknooppunt, zoals hieronder weergegeven:
Wat is een B+ boom?
De B+ boom wordt ook wel een geavanceerde, zelfbalancerende boom genoemd, omdat elk pad van de wortel van de boom tot het blad van de boom dezelfde lengte heeft. Hier betekent dezelfde lengte dat alle bladknopen op hetzelfde niveau voorkomen. Het zal niet gebeuren dat sommige bladknooppunten op het derde niveau voorkomen en sommige op het tweede niveau.
Een B+-boomindex wordt beschouwd als een index met meerdere niveaus, maar de B+-boomstructuur is niet vergelijkbaar met de sequentiële indexbestanden met meerdere niveaus.
Waarom wordt de B+ boom gebruikt?
Een B+-boom wordt gebruikt om de records zeer efficiënt op te slaan door de records op een geïndexeerde manier op te slaan met behulp van de geïndexeerde B+-boomstructuur. Dankzij de indexering op meerdere niveaus wordt de toegang tot gegevens sneller en eenvoudiger.
B+ boom Knooppuntstructuur
De knooppuntstructuur van de B+-boom bevat verwijzingen en sleutelwaarden, weergegeven in de onderstaande afbeelding:
Zoals we in de bovenstaande B+-boomknooppuntstructuur kunnen zien, bevat deze n-1 sleutelwaarden (k1naar kn-1) en n-aanwijzers (pag1bovenkantN).
De zoeksleutelwaarden die in het knooppunt zijn geplaatst, worden in gesorteerde volgorde bewaard. Dus als ik
Beperking op verschillende soorten knooppunten
Laat 'b' de volgorde van de B+ boom zijn.
Niet-bladknooppunt
vergelijkbare string
Stel dat 'm' het aantal kinderen van een knooppunt vertegenwoordigt, dan kan de relatie tussen de volgorde van de boom en het aantal kinderen worden weergegeven als:
Laat k de zoeksleutelwaarden vertegenwoordigen. De relatie tussen de volgorde van de boom en de zoeksleutel kan als volgt worden weergegeven:
Omdat we weten dat het aantal pointers gelijk is aan de zoeksleutelwaarden plus 1, kan het wiskundig gezien als volgt worden geschreven:
Aantal aanwijzers (of kinderen) = aantal zoeksleutels + 1
Daarom zou het maximale aantal pointers 'b' zijn, en het minimale aantal pointers zou de plafondfunctie van b/2 zijn.
Bladknooppunt
Een leaf-knooppunt is een knooppunt dat voorkomt op het laatste niveau van de B+-boom, en elk leaf-knooppunt gebruikt slechts één aanwijzer om met elkaar te verbinden om de sequentiële toegang op leaf-niveau te bieden.
In het bladknooppunt is het maximale aantal kinderen:
Het maximale aantal zoeksleutels is:
Wortelknooppunt
Het maximale aantal kinderen bij de rootnode is: b
Het minimum aantal kinderen is: 2
Speciale gevallen in B+ boom
Zaak 1: Als het hoofdknooppunt het enige knooppunt in de boom is. In dit geval wordt het wortelknooppunt het bladknooppunt.
In dit geval is het maximale aantal kinderen 1, dat wil zeggen het wortelknooppunt zelf, terwijl het minimumaantal kinderen b-1 is, wat hetzelfde is als dat van een bladknooppunt.
Weergave van een bladknooppunt in een B+-boom
In de bovenstaande afbeelding: '.' vertegenwoordigt de aanwijzer, terwijl de 10, 20 en 30 de sleutelwaarden zijn. De aanwijzer bevat het adres waarop de sleutelwaarde is opgeslagen, zoals weergegeven in de bovenstaande afbeelding.
Voorbeeld van een B+-boom
In de bovenstaande afbeelding bevat het knooppunt drie sleutelwaarden, namelijk 9, 16 en 25. De aanwijzer die vóór 9 verschijnt, bevat de sleutelwaarden kleiner dan 9, weergegeven door ki. De aanwijzer die vóór 16 verschijnt, bevat de sleutelwaarden groter dan of gelijk aan 9 maar kleiner dan 16, weergegeven door kj. De aanwijzer die vóór 25 verschijnt, bevat de sleutelwaarden groter dan of gelijk aan 16 maar kleiner dan 25, weergegeven door kN.
Verschillen tussen B-boom en B+-boom
Hieronder volgen de verschillen tussen de B-boom en de B+-boom:
| B-boom | B+ boom |
|---|---|
| In de B-boom worden alle sleutels en records opgeslagen in zowel interne als leaf-knooppunten. | In de B+-boom zijn sleutels de indexen die zijn opgeslagen in de interne knooppunten en worden records opgeslagen in de bladknooppunten. |
| In de B-boom kunnen sleutels niet herhaaldelijk worden opgeslagen, wat betekent dat er geen duplicatie van sleutels of records is. | In de B+-boom kan er sprake zijn van redundantie in het voorkomen van de sleutels. In dit geval worden de records opgeslagen in de bladknooppunten, terwijl de sleutels worden opgeslagen in de interne knooppunten, zodat er redundante sleutels aanwezig kunnen zijn in de interne knooppunten. |
| In de Btree zijn bladknooppunten niet met elkaar verbonden. | In de B+-boom zijn de bladknooppunten aan elkaar gekoppeld om sequentiële toegang te bieden. |
| In Btree is het zoeken niet erg efficiënt omdat de records worden opgeslagen in leaf- of interne knooppunten. | In de B+-boom is het zoeken zeer efficiënt of sneller omdat alle records in de bladknooppunten worden opgeslagen. |
| Het verwijderen van interne knooppunten is erg langzaam en een tijdrovend proces, omdat we ook rekening moeten houden met het kind van de verwijderde sleutel. | Het verwijderen in de B+-boom gaat erg snel omdat alle records worden opgeslagen in de bladknooppunten, zodat we geen rekening hoeven te houden met het kind van het knooppunt. |
| In Btree is sequentiële toegang niet mogelijk. | In de B+-boom zijn alle leaf-knooppunten met elkaar verbonden via een pointer, waardoor sequentiële toegang mogelijk is. |
| In Btree wordt het aantal splijtoperaties groter, waardoor de hoogte toeneemt in vergelijking met de breedte, | B+ boom heeft meer breedte dan hoogte. |
| In Btree heeft elk knooppunt minstens twee vertakkingen en bevat elk knooppunt enkele records, dus we hoeven niet tot aan de bladknooppunten te doorlopen om de gegevens op te halen. | In de B+-boom bevatten interne knooppunten alleen verwijzingen en bladknooppunten records. Alle bladknooppunten bevinden zich op hetzelfde niveau, dus we moeten tot aan de bladknooppunten doorlopen om de gegevens te verkrijgen. |
| Het hoofdknooppunt bevat minimaal 2 tot m kinderen, waarbij m de orde van de boom is. | Het hoofdknooppunt bevat minimaal 2 tot m kinderen, waarbij m de orde van de boom is. |