B+ Tree er en utvidelse av B Tree som tillater effektiv innsetting, sletting og søkeoperasjoner.
I B Tree kan nøkler og poster både lagres i interne så vel som bladnoder. Mens i B+-treet kan poster (data) bare lagres på bladnodene mens interne noder bare kan lagre nøkkelverdiene.
Bladnodene til et B+-tre er koblet sammen i form av en enkeltlenkede lister for å gjøre søkene mer effektive.
B+ Tree brukes til å lagre store mengder data som ikke kan lagres i hovedminnet. På grunn av det faktum at størrelsen på hovedminnet alltid er begrenset, lagres de interne nodene (nøkler for å få tilgang til poster) til B+-treet i hovedminnet, mens bladnoder lagres i sekundærminnet.
De interne nodene til B+-treet kalles ofte indeksnoder. Et B+-tre av størrelsesorden 3 er vist i følgende figur.
Fordeler med B+ Tree
- Poster kan hentes i like antall disktilganger.
- Høyden på treet forblir balansert og mindre sammenlignet med B-treet.
- Vi kan få tilgang til dataene som er lagret i et B+-tre sekvensielt så vel som direkte.
- Nøkler brukes til indeksering.
- Raskere søk ettersom dataene bare lagres på bladnodene.
B-tre VS B+-tre
| SN | B tre | B+ tre |
|---|---|---|
| 1 | Søketaster kan ikke lagres gjentatte ganger. | Redundante søkenøkler kan være tilstede. |
| 2 | Data kan lagres i bladnoder så vel som interne noder | Data kan kun lagres på bladnodene. |
| 3 | Å søke etter noen data er en langsommere prosess siden data kan bli funnet på interne noder så vel som på bladnodene. | Søking er relativt raskere ettersom data bare finnes på bladnodene. |
| 4 | Sletting av interne noder er så komplisert og tidkrevende. | Sletting vil aldri være en kompleks prosess siden element alltid vil bli slettet fra bladnodene. |
| 5 | Bladnoder kan ikke kobles sammen. | Bladnoder er knyttet sammen for å gjøre søkeoperasjonene mer effektive. |
Innsetting i B+ Tree
Trinn 1: Sett inn den nye noden som en bladnode
java-verdi av streng
Steg 2: Hvis bladet ikke har nødvendig plass, del noden og kopier den midterste noden til neste indeksnode.
Trinn 3: Hvis indeksnoden ikke har nødvendig plass, del noden og kopier midtelementet til neste indeksside.
Eksempel:
Sett inn verdien 195 i B+-treet av orden 5 vist i følgende figur.
195 vil bli satt inn i høyre undertre av 120 etter 190. Sett den inn i ønsket posisjon.
Noden inneholder mer enn det maksimale antallet elementer, dvs. 4, del den derfor opp og plasser mediannoden opp til overordnet.
Nå inneholder indeksnoden 6 barn og 5 nøkler som bryter med B+-treegenskapene, derfor må vi dele den, vist som følger.
Sletting i B+-tre
Trinn 1: Slett nøkkel og data fra bladene.
Steg 2: hvis bladnoden inneholder mindre enn minimum antall elementer, slå sammen noden med søsken og slett nøkkelen mellom dem.
Trinn 3: hvis indeksnoden inneholder mindre enn minimum antall elementer, slå sammen noden med søsken og flytt ned tasten mellom dem.
Eksempel
Slett nøkkelen 200 fra B+-treet vist i følgende figur.
200 er til stede i det høyre undertreet av 190, etter 195. slett det.
Slå sammen de to nodene ved å bruke 195, 190, 154 og 129.
Nå er element 120 det eneste elementet tilstede i noden som bryter B+ Tree-egenskapene. Derfor må vi slå den sammen ved å bruke 60, 78, 108 og 120.
Nå vil høyden på B+ treet reduseres med 1.
