B+ Tree is een uitbreiding van B Tree die efficiënte invoeg-, verwijder- en zoekbewerkingen mogelijk maakt.
In B Tree kunnen sleutels en records zowel in de interne als in de bladknooppunten worden opgeslagen. Terwijl in de B+-boom records (gegevens) alleen op de bladknooppunten kunnen worden opgeslagen, terwijl interne knooppunten alleen de sleutelwaarden kunnen opslaan.
De bladknooppunten van een B+-boom zijn met elkaar verbonden in de vorm van afzonderlijk gekoppelde lijsten om de zoekopdrachten efficiënter te maken.
B+ Tree wordt gebruikt om de grote hoeveelheid gegevens op te slaan die niet in het hoofdgeheugen kunnen worden opgeslagen. Vanwege het feit dat de grootte van het hoofdgeheugen altijd beperkt is, worden de interne knooppunten (sleutels voor toegang tot records) van de B+-boom opgeslagen in het hoofdgeheugen, terwijl bladknooppunten worden opgeslagen in het secundaire geheugen.
De interne knooppunten van de B+-boom worden vaak indexknooppunten genoemd. Een B+-boom van orde 3 wordt weergegeven in de volgende afbeelding.
Voordelen van B+ Boom
- Records kunnen worden opgehaald bij een gelijk aantal schijftoegangen.
- De hoogte van de boom blijft in balans en lager dan bij de B-boom.
- We hebben zowel sequentieel als direct toegang tot de gegevens die in een B+-boom zijn opgeslagen.
- Voor indexering worden sleutels gebruikt.
- Snellere zoekopdrachten omdat de gegevens alleen op de bladknooppunten worden opgeslagen.
B-boom VS B+-boom
| SN | B Boom | B+ Boom |
|---|---|---|
| 1 | Zoeksleutels kunnen niet herhaaldelijk worden opgeslagen. | Er kunnen redundante zoeksleutels aanwezig zijn. |
| 2 | Gegevens kunnen zowel in bladknooppunten als in interne knooppunten worden opgeslagen | Gegevens kunnen alleen op de bladknooppunten worden opgeslagen. |
| 3 | Het zoeken naar bepaalde gegevens is een langzamer proces, omdat gegevens zowel op interne knooppunten als op de bladknooppunten kunnen worden gevonden. | Zoeken gaat relatief sneller omdat gegevens alleen op de bladknooppunten kunnen worden gevonden. |
| 4 | Het verwijderen van interne knooppunten is zo ingewikkeld en tijdrovend. | Verwijdering zal nooit een ingewikkeld proces zijn, omdat elementen altijd uit de bladknooppunten worden verwijderd. |
| 5 | Bladknooppunten kunnen niet aan elkaar worden gekoppeld. | Leaf-knooppunten zijn met elkaar verbonden om de zoekoperaties efficiënter te maken. |
Invoeging in B+ Boom
Stap 1: Voeg het nieuwe knooppunt in als een bladknooppunt
Stap 2: Als het blad geen vereiste ruimte heeft, splitst u het knooppunt en kopieert u het middelste knooppunt naar het volgende indexknooppunt.
Stap 3: Als het indexknooppunt niet over de vereiste ruimte beschikt, splitst u het knooppunt en kopieert u het middelste element naar de volgende indexpagina.
Voorbeeld :
Voer de waarde 195 in de B+-boom van volgorde 5 in, weergegeven in de volgende afbeelding.
195 wordt na 190 in de rechter subboom van 120 ingevoegd. Voeg deze op de gewenste positie in.
Het knooppunt bevat meer dan het maximale aantal elementen, d.w.z. 4. Splits het daarom op en plaats het middenknooppunt bij de ouder.
Nu bevat het indexknooppunt 6 kinderen en 5 sleutels die de B+ boomeigenschappen schenden. Daarom moeten we het splitsen, zoals hieronder weergegeven.
Verwijdering in B+ Boom
Stap 1: Verwijder de sleutel en gegevens van de bladeren.
Stap 2: als het bladknooppunt minder dan het minimumaantal elementen bevat, voeg dan het knooppunt samen met zijn broer of zus en verwijder de sleutel ertussen.
Stap 3: als het indexknooppunt minder dan het minimumaantal elementen bevat, voeg het knooppunt dan samen met het broertje of zusje en verplaats de sleutel ertussenin.
Voorbeeld
Verwijder sleutel 200 uit de B+-boom, weergegeven in de volgende afbeelding.
200 is aanwezig in de rechter subboom van 190, na 195. verwijder het.
Voeg de twee knooppunten samen door 195, 190, 154 en 129 te gebruiken.
Nu is element 120 het enige element dat aanwezig is in het knooppunt en dat de B+ Tree-eigenschappen schendt. Daarom moeten we het samenvoegen door 60, 78, 108 en 120 te gebruiken.
Nu wordt de hoogte van de B+-boom met 1 verlaagd.
