B+ Tree är en förlängning av B Tree som möjliggör effektiv infogning, radering och sökoperationer.
I B Tree kan nycklar och poster både lagras i de interna och lövnoderna. I B+-trädet kan poster (data) endast lagras på lövnoderna medan interna noder endast kan lagra nyckelvärdena.
Bladnoderna i ett B+-träd är sammanlänkade i form av en enda länkad lista för att göra sökfrågorna mer effektiva.
B+ Tree används för att lagra stora mängder data som inte kan lagras i huvudminnet. På grund av det faktum att storleken på huvudminnet alltid är begränsad, lagras de interna noderna (nycklar för åtkomst av poster) i B+-trädet i huvudminnet medan lövnoder lagras i det sekundära minnet.
De interna noderna i B+-trädet kallas ofta indexnoder. Ett B+-träd av ordning 3 visas i följande figur.
Fördelar med B+ Tree
- Poster kan hämtas i lika antal diskåtkomster.
- Trädets höjd förblir balanserad och mindre jämfört med B-trädet.
- Vi kan komma åt data som lagras i ett B+-träd sekventiellt såväl som direkt.
- Nycklar används för indexering.
- Snabbare sökfrågor eftersom data endast lagras på bladnoderna.
B-träd VS B+-träd
| SN | B Träd | B+ träd |
|---|---|---|
| 1 | Söknycklar kan inte lagras upprepade gånger. | Redundanta söknycklar kan finnas. |
| 2 | Data kan lagras i bladnoder såväl som interna noder | Data kan endast lagras på bladnoderna. |
| 3 | Att söka efter vissa data är en långsammare process eftersom data kan hittas på interna noder såväl som på bladnoderna. | Sökningen är jämförelsevis snabbare eftersom data endast kan hittas på lövnoderna. |
| 4 | Borttagning av interna noder är så komplicerat och tidskrävande. | Borttagning kommer aldrig att vara en komplex process eftersom element alltid kommer att tas bort från lövnoderna. |
| 5 | Bladnoder kan inte länkas samman. | Lövnoder är sammanlänkade för att göra sökoperationerna mer effektiva. |
Insättning i B+-träd
Steg 1: Infoga den nya noden som en lövnod
Steg 2: Om bladet inte har nödvändigt utrymme, dela noden och kopiera den mellersta noden till nästa indexnod.
Steg 3: Om indexnoden inte har nödvändigt utrymme, dela noden och kopiera mittelementet till nästa indexsida.
Exempel:
Infoga värdet 195 i B+-trädet av ordning 5 som visas i följande figur.
195 kommer att infogas i det högra underträdet av 120 efter 190. Infoga det på önskad position.
Noden innehåller fler än det maximala antalet element, dvs 4, dela den därför och placera mediannoden upp till föräldern.
Nu innehåller indexnoden 6 barn och 5 nycklar som bryter mot B+-trädets egenskaper, därför måste vi dela upp den, som visas enligt följande.
Radering i B+-träd
Steg 1: Ta bort nyckeln och data från bladen.
Steg 2: om bladnoden innehåller mindre än minsta antal element, slå samman noden med dess syskon och radera nyckeln mellan dem.
Steg 3: om indexnoden innehåller mindre än minsta antal element, slå samman noden med syskonen och flytta ner tangenten mellan dem.
Exempel
Ta bort nyckeln 200 från B+-trädet som visas i följande figur.
200 finns i det högra underträdet av 190, efter 195. radera det.
Slå samman de två noderna genom att använda 195, 190, 154 och 129.
Nu är elementet 120 det enda elementet närvarande i noden som bryter mot B+ Tree-egenskaperna. Därför måste vi slå samman det genom att använda 60, 78, 108 och 120.
Nu kommer höjden på B+-trädet att minskas med 1.
