Abans d'entendre arbre B i Arbre B+ diferències, hauríem de conèixer l'arbre B i l'arbre B+ per separat.
Què és l'arbre B?
arbre B és un arbre d'autoequilibri, i és un arbre m-way on m defineix l'ordre de l'arbre. Btree és una generalització de la Arbre de cerca binària en què un node pot tenir més d'una clau i més de dos fills segons el valor de m . A l'arbre B, les dades s'especifiquen en un ordre ordenat amb valors més baixos al subarbre esquerre i valors més alts al subarbre dret.
convertir string a date
Propietats de l'arbre B
Les propietats de l'arbre B són les següents:
- A l'arbre B, tots els nodes fulla han d'estar al mateix nivell, mentre que, en el cas d'un arbre binari, els nodes fulla poden estar a diferents nivells.
Entenem aquesta propietat a través d'un exemple.
A l'arbre anterior, tots els nodes de les fulles no estan al mateix nivell, però tenen el màxim de dos fills. Per tant, podem dir que l'arbre anterior és a arbre binari però no un arbre B.
- Si l'arbre B té un ordre de m, aleshores cada node pot tenir un màxim de m En el cas dels fills mínims, els nodes fulla tenen zero fills, el node arrel té dos fills i els nodes interns tenen un sostre de m/2.
- Cada node pot tenir un màxim de claus (m-1). Per exemple, si el valor de m és 5, el valor màxim de les claus és 4.
- El node arrel té com a mínim una clau, mentre que tots els altres nodes excepte el node arrel tenen (sostre de m/2 menys - 1) claus mínimes.
- Si realitzem la inserció a l'arbre B, aleshores el node sempre s'insereix al node fulla.
Suposem que volem crear un arbre B d'ordre 3 inserint valors de l'1 al 10.
Pas 1: Primer, creem un node amb 1 valor com es mostra a continuació:
Pas 2: El següent element és 2, que ve després de l'1 com es mostra a continuació:
Pas 3: El següent element és 3 i s'insereix després de 2 tal com es mostra a continuació:
Com sabem que cada node pot tenir 2 claus com a màxim, dividirem aquest node per l'element central. L'element central és 2, de manera que es mou al seu pare. El node 2 no té cap pare, de manera que es convertirà en el node arrel tal com es mostra a continuació:
Pas 4: El següent element és 4. Com que 4 és més gran que 2 i 3, s'afegirà després del 3 com es mostra a continuació:
Pas 5: El següent element és 5. Com que 5 és més gran que 2, 3 i 4, s'afegirà després de 4 com es mostra a continuació:
Com sabem que cada node pot tenir 2 claus com a màxim, dividirem aquest node per l'element central. L'element central és 4, de manera que es mou al seu pare. El pare és el node 2; per tant, s'afegiran 4 després de 2 tal com es mostra a continuació:
Pas 6: El següent element és 6. Com que 6 és més gran que 2, 4 i 5, per tant, 6 vindrà després de 5 com es mostra a continuació:
Pas 7: El següent element és 7. Com que 7 és més gran que 2, 4, 5 i 6, 7 vindrà després de 6 tal com es mostra a continuació:
Com sabem que cada node pot tenir 2 claus com a màxim, dividirem aquest node per l'element central. L'element central és 6, de manera que es mou al seu pare com es mostra a continuació:
Però, 6 no es poden afegir després de 4 perquè el node pot tenir 2 claus com a màxim, de manera que dividirem aquest node per l'element central. L'element central és 4, de manera que es mou al seu pare. Com que el node 4 no té cap pare, el node 4 es convertirà en un node arrel tal com es mostra a continuació:
Què és un arbre B+?
El Arbre B+ també es coneix com un arbre autoequilibrat avançat perquè cada camí des de l'arrel de l'arbre fins a la fulla de l'arbre té la mateixa longitud. Aquí, la mateixa longitud significa que tots els nodes de fulla es troben al mateix nivell. No passarà que alguns dels nodes de la fulla es produeixin al tercer nivell i alguns d'ells al segon nivell.
Un índex d'arbre B+ es considera un índex multinivell, però l'estructura d'arbre B+ no és similar als fitxers seqüencials d'índex multinivell.
Per què s'utilitza l'arbre B+?
S'utilitza un arbre B+ per emmagatzemar els registres de manera molt eficient emmagatzemant els registres de manera indexada mitjançant l'estructura indexada de l'arbre B+. A causa de la indexació multinivell, l'accés a les dades es fa més ràpid i fàcil.
Estructura de nodes d'arbre B+
L'estructura de nodes de l'arbre B+ conté punters i valors clau que es mostren a la figura següent:
Com podem observar a l'estructura del node d'arbre B+ anterior que conté n-1 valors clau (k1a kn-1) i n punters (pàg1superiorn).
Els valors de clau de cerca que es col·loquen al node es mantenen ordenats. Així, si i
Restricció a diversos tipus de nodes
Sigui 'b' l'ordre de l'arbre B+.
Node sense fulla
Sigui 'm' el nombre de fills d'un node, llavors la relació entre l'ordre de l'arbre i el nombre de fills es pot representar com:
Sigui k representa els valors de la clau de cerca. La relació entre l'ordre de l'arbre i la clau de cerca es pot representar com:
Com que sabem que el nombre de punters és igual als valors de la clau de cerca més 1, per tant, matemàticament, es pot escriure com:
Nombre de punters (o fills) = Nombre de tecles de cerca + 1
Per tant, el nombre màxim de punters seria 'b' i el nombre mínim de punters seria la funció de sostre de b/2.
Node de fulla
Un node fulla és un node que es produeix a l'últim nivell de l'arbre B+, i cada node fulla utilitza només un punter per connectar-se entre ells per proporcionar l'accés seqüencial al nivell de fulla.
Al node fulla, el nombre màxim de fills és:
El nombre màxim de claus de cerca és:
Node arrel
El nombre màxim de fills en el cas del node arrel és: b
El nombre mínim de nens és: 2
Casos especials en arbre B+
Cas 1: Si el node arrel és l'únic node de l'arbre. En aquest cas, el node arrel es converteix en el node fulla.
En aquest cas, el nombre màxim de fills és 1, és a dir, el propi node arrel, mentre que el nombre mínim de fills és b-1, que és el mateix que el d'un node fulla.
Representació d'un node fulla a l'arbre B+
A la figura anterior, '.' representa el punter, mentre que els 10, 20 i 30 són els valors clau. El punter conté l'adreça on s'emmagatzema el valor de la clau, tal com es mostra a la figura anterior.
Exemple d'arbre B+
arquitectura de Linux
A la figura anterior, el node conté tres valors clau, és a dir, 9, 16 i 25. El punter que apareix abans de 9, conté els valors clau inferiors a 9 representats per ki. El punter que apareix abans de 16, conté els valors clau superiors o iguals a 9 però inferiors a 16 representats per kj. El punter que apareix abans de 25, conté els valors clau superiors o iguals a 16 però inferiors a 25 representats per kn.
Diferències entre l'arbre B i l'arbre B+
A continuació es mostren les diferències entre l'arbre B i l'arbre B+:
| arbre B | Arbre B+ |
|---|---|
| A l'arbre B, totes les claus i registres s'emmagatzemen tant als nodes interns com a les fulles. | A l'arbre B+, les claus són els índexs emmagatzemats als nodes interns i els registres s'emmagatzemen als nodes fulla. |
| A l'arbre B, les claus no es poden emmagatzemar repetidament, el que significa que no hi ha duplicació de claus o registres. | A l'arbre B+, pot haver-hi redundància en l'aparició de les claus. En aquest cas, els registres s'emmagatzemen als nodes fulla, mentre que les claus s'emmagatzemen als nodes interns, de manera que les claus redundants poden estar presents als nodes interns. |
| A l'arbre B, els nodes de fulla no estan vinculats entre si. | A l'arbre B+, els nodes fulla estan enllaçats entre si per proporcionar l'accés seqüencial. |
| A Btree, la cerca no és molt eficient perquè els registres s'emmagatzemen en fulles o nodes interns. | A l'arbre B+, la cerca és molt eficient o més ràpida perquè tots els registres s'emmagatzemen als nodes fulla. |
| La supressió dels nodes interns és molt lenta i un procés que requereix molt de temps, ja que també hem de tenir en compte el fill de la clau suprimida. | La supressió a l'arbre B+ és molt ràpida perquè tots els registres s'emmagatzemen als nodes fulla, de manera que no hem de tenir en compte el fill del node. |
| A Btree, l'accés seqüencial no és possible. | A l'arbre B+, tots els nodes fulla estan connectats entre si mitjançant un punter, de manera que és possible l'accés seqüencial. |
| A Btree, com més es realitza el nombre d'operacions de divisió a causa de les quals augmenta l'alçada en comparació amb l'amplada, | L'arbre B+ té més amplada en comparació amb l'alçada. |
| A Btree, cada node té almenys dues branques i cada node conté alguns registres, de manera que no necessitem recórrer fins als nodes fulla per obtenir les dades. | A l'arbre B+, els nodes interns només contenen punters i els nodes full contenen registres. Tots els nodes de fulla estan al mateix nivell, de manera que hem de recórrer fins als nodes de fulla per obtenir les dades. |
| El node arrel conté almenys de 2 a m fills, on m és l'ordre de l'arbre. | El node arrel conté almenys de 2 a m fills, on m és l'ordre de l'arbre. |