B+ Tree és una extensió de B Tree que permet operacions eficients d'inserció, supressió i cerca.
A l'arbre B, les claus i els registres es poden emmagatzemar tant als nodes interns com a les fulles. Mentre que, a l'arbre B+, els registres (dades) només es poden emmagatzemar als nodes fulla mentre que els nodes interns només poden emmagatzemar els valors clau.
escàner java a continuació
Els nodes de fulla d'un arbre B+ estan enllaçats entre ells en forma de llistes enllaçades individualment per fer que les consultes de cerca siguin més eficients.
B+ Tree s'utilitzen per emmagatzemar la gran quantitat de dades que no es poden emmagatzemar a la memòria principal. A causa del fet que la mida de la memòria principal sempre és limitada, els nodes interns (claus per accedir als registres) de l'arbre B+ s'emmagatzemen a la memòria principal mentre que els nodes fulla s'emmagatzemen a la memòria secundària.
Els nodes interns de l'arbre B+ s'anomenen sovint nodes d'índex. A la figura següent es mostra un arbre B+ d'ordre 3.
Avantatges de B+ Tree
- Els registres es poden obtenir en el mateix nombre d'accessos al disc.
- L'alçada de l'arbre es manté equilibrada i menor en comparació amb l'arbre B.
- Podem accedir a les dades emmagatzemades en un arbre B+ tant de manera seqüencial com directament.
- Les claus s'utilitzen per a la indexació.
- Consultes de cerca més ràpides, ja que les dades només s'emmagatzemen als nodes fulla.
Arbre B VS Arbre B+
| SN | B Arbre | Arbre B+ |
|---|---|---|
| 1 | Les claus de cerca no es poden emmagatzemar repetidament. | Les claus de cerca redundants poden estar presents. |
| 2 | Les dades es poden emmagatzemar tant en nodes fulla com en nodes interns | Les dades només es poden emmagatzemar als nodes fulla. |
| 3 | La cerca d'algunes dades és un procés més lent, ja que les dades es poden trobar tant als nodes interns com als nodes full. | La cerca és relativament més ràpida, ja que les dades només es poden trobar als nodes de la fulla. |
| 4 | La supressió de nodes interns és molt complicada i requereix molt de temps. | La supressió mai serà un procés complex, ja que l'element sempre s'eliminarà dels nodes fulla. |
| 5 | Els nodes de fulla no es poden enllaçar. | Els nodes de fulla estan enllaçats entre si per fer que les operacions de cerca siguin més eficients. |
Inserció a l'arbre B+
Pas 1: Inseriu el nou node com a node fulla
Pas 2: Si la fulla no té espai necessari, dividiu el node i copieu el node central al següent node d'índex.
Pas 3: Si el node d'índex no té espai necessari, dividiu el node i copieu l'element central a la pàgina d'índex següent.
Exemple:
Inseriu el valor 195 a l'arbre B+ d'ordre 5 que es mostra a la figura següent.
195 s'inserirà al subarbre dret de 120 després de 190. Inseriu-lo a la posició desitjada.
El node conté un nombre superior al màxim d'elements, és a dir, 4, per tant, dividiu-lo i col·loqueu el node mitjà fins al pare.
Ara, el node d'índex conté 6 fills i 5 claus que infringeixen les propietats de l'arbre B+, per tant, hem de dividir-lo, que es mostra a continuació.
Supressió a l'arbre B+
Pas 1: Elimina la clau i les dades de les fulles.
Pas 2: si el node fulla conté menys del nombre mínim d'elements, fusioneu el node amb el seu germà i suprimiu la clau entre ells.
Pas 3: si el node d'índex conté menys d'un nombre mínim d'elements, fusiona el node amb el germà i mou la tecla cap avall entre ells.
Exemple
Suprimiu la clau 200 de l'arbre B+ que es mostra a la figura següent.
r en llenguatge c
200 està present al subarbre dret de 190, després de 195. suprimeix-lo.
Combina els dos nodes utilitzant 195, 190, 154 i 129.
Ara, l'element 120 és l'únic element present al node que viola les propietats de l'arbre B+. Per tant, hem de combinar-lo fent servir 60, 78, 108 i 120.
Ara, l'alçada de l'arbre B+ es reduirà en 1.
