Arbre-B

Exemple d'arbre B.

En les ciències de la computació, els arbres-B o B-arbres són estructures de dades d'arbre que es troben comunament en les implementacions de bases de dades i sistemes d'arxius. Els arbres B mantenen les dades ordenades i les insercions i eliminacions es realitzen en temps logarítmic amortitzat.

Definició

La idea després dels arbres-B és que els nodes interns han de tenir un nombre variable de nodes fill dins d'un rang predefinit. Quan s'insereix o s'elimina una dada de l'estructura, la quantitat de nodes fill varia dins d'un node. Perquè seguisca mantenint-se el nombre de nodes dins del rang *predefinido, els nodes interns s'ajunten o es parteixen. Atès que es permet un rang variable de nodes fill, els arbres-B no necessiten rebalancejar-se tan freqüentment com els arbres binaris de recerca acte-balandrejants, però d'altra banda poden balafiar memòria, perquè els nodes no romanen totalment ocupats. Els límits superior i inferior en el nombre de nodes fill són definits per a cada implementació en particular. Per exemple, en un arbre-B 2-3 (Sovint simplement dit arbre 2-3), cada node només pot tenir 2 o 3 nodes fills.

Un arbre-B es manté balancejat perquè requereix que tots els nodes fulla es troben a la mateixa altura.

Els arbres B tenen avantatges substancials sobre altres implementacions quan el temps d'accés als nodes excedeix al temps d'accés entre nodes. Aquest cas es dona usualment quan els nodes es troben en dispositius d'emmagatzematge secundari com els discos rígids. AL maximitzar el nombre de nodes fill de cada node intern, l'altura de l'arbre decreix, les operacions per a balancejar-lo es redueixen, i augmenta l'eficiència. Usualment aquest valor es col·loca de forma tal que cada node ocupe un bloc de disc, o una grandària anàloga en el dispositiu. Mentre que els arbres B 2-3 poden ser útils en la memòria principal i, a més, més fàcils d'explicar, si la grandària dels nodes s'ajusten per a cabre en un bloc de disc, el resultat pot ser un arbre B 129-513.

Els creadors de l'arbre B, Rudolf Bayer i Ed McCreight, no han explicat el significat de la lletra B del seu nom. Es creu que la B és de balancejat, atès que tots els nodes fulla es mantenen al mateix nivell en l'arbre. La B també pot referir-se a Bayer, o a Boeing, perquè els seus creadors treballaven en el Boeing Scientific Research Labs en eixe llavors.

Definició breu

B-arbre és un arbre de recerca que pot estar buit o aquell els nodes del qual poden tenir diversos fills, existint una relació d'ordre entre ells, tal com mostra el dibuix.

Un arbre-B d'ordre M (el màxim nombre de fills que pot tenir cada node) és un arbre que satisfà les següents propietats:

1. Cada node té com a màxim M fills.
2. Cada node (excepte arrel i fulles) té com a mínim M/2 fills.
3. L'arrel té almenys 2 fills si no és un node fulla.
4. Tots els nodes fulla apareixen al mateix nivell.
5. Un node no fulla amb k fills conté k-1 elements emmagatzemats.
6. Els fills que pengen de l'arrel (r1, · · · *rm) han de complir certes condicions :
   1. El primer té valor menor que r1
   2. . El segon té valor major que r1 i menor que r2, etc.
   3. L'últim fill té major que rm.

Altura: El millor i el pitjor cas

En el millor dels casos, l'altura d'un arbre-B és:

$log_{M}n$

En el pitjor dels casos, l'altura d'un arbre-B és:

$log_{\left({\frac {M}{2}}\right)}n$

On M és el nombre màxim de fills que pot tenir un node.

Estructura dels nodes

Cada element d'un node intern actua com un valor separador, que ho divideix en subarbres. Per exemple, si un node intern té tres nodes fill, ha de tenir dos valors separadors o elements a₁ i a₂. Tots els valors del subarbre esquerre han de ser menors a a₁, tots els valors del subarbre del centre han d'estar entre a₁ i a₂, i tots els valors del subarbre dret han de ser majors a a₂. Els nodes interns d'un arbre B, és a dir els nodes que no són fulla, usualment es representen com un conjunt ordenat d'elements i punters als fills. Cada node intern conté un màxim de O fills i, amb excepció del node arrel, un mínim de L fills. Per a tots els nodes interns exceptuant l'arrel, el nombre d'elements és un menys que el nombre de punters a nodes. El nombre d'elements es troba entre L-1 i O-1. El nombre O ha de ser 2L o 2L-1, és a dir, cada node intern està almenys a mitjan omplir. Aquesta relació entre O i L implica que dos nodes que estan a mitjan omplir poden ajuntar-se per a formar un node legal, i un node ple pot dividir-se en dos nodes legals (si és que hi ha lloc per a pujar un element al node pare). Aquestes propietats fan possible que l'arbre B s'ajuste per a preservar les seues propietats davant la inserció i eliminació d'elements.

Els nodes fulla tenen la mateixa restricció sobre el nombre d'elements, però no tenen fills, i per tant manquen de punters.

El node arrel té límit superior de nombre de fills, però no té límit inferior. Per exemple, si haguera menys de L-1 elements en tot l'arbre, l'arrel seria l'únic node de l'arbre, i no tindria fills.

Un arbre B d'altura n+1 pot contenir O vegades per elements més que un arbre B de profunditat n, però el cost en la recerca, inserció i eliminació creix amb l'altura de l'arbre. Com tot arbre balancejat, el creixement del cost és més lent que el del nombre d'elements.

Alguns arbres balancejats guarden valors només en els nodes fulla, i per tant els seus nodes interns i nodes fulla són de diferent tipus. Els arbres B guarden valors en cada node, i poden utilitzar la mateixa estructura per a tots els nodes. No obstant això, com els nodes fulla no tenen fills, una estructura especial per a aquests millora el funcionament.

Algorismes

Recerca

La recerca és similar a la dels arbres binaris. Es comença en l'arrel, i es recorre l'arbre cap avall, escollint el subnode d'acord amb la posició relativa del valor cercat respecte als valors de cada node. Típicament s'utilitza la recerca binària per a determinar aquesta posició relativa.

Procediment

exemple2 inserció en arbre B

1. . Situar-se en el node arrel.
2. (*). Comprovar si conté la clau a cercar.
   1. . Oposada fi de procediment.
   2. . No oposada:
      1. Si és fulla no existeix la clau.
      2. En altre cas el node actual és el fill que correspon:
         1. . La clau a cercar k < k1 :fill esquerre.
         2. . La clau a cercar k > ki i k < ki+1 fill i-èsim.

1. 1. 1. 1. . Tornar a pas 2(*).

Inserció

Totes les insercions es fan en els nodes fulla.

1. Realitzant una recerca en l'arbre, es troba el node fulla en el qual hauria de situar-se el nou element.
2. Si el node fulla té menys elements que el màxim nombre d'elements legals, llavors hi ha lloc per a un més. Inserisca el nou element en el node, respectant l'ordre dels elements.
3. D'altra forma, el node ha de ser dividit en dos nodes. La divisió es realitza de la següent manera:
   1. S'escull el valor mitjà entre els elements del node i el nou element.
   2. Els valors menors que el valor mitjà es col·loquen en el nou node esquerre, i els valors majors que el valor mitjà es col·loquen en el nou node dret; el valor mitjà actua com a valor separador.
   3. El valor separador s'ha de col·locar en el node pare, el que pot provocar que el pare siga dividit en dos, i així successivament.

Si les divisions de nodes pugen fins a l'arrel, es crea una nova arrel amb un únic element com valor separador, i dos fills. És per açò pel que la cota inferior de la grandària dels nodes no s'aplica a l'arrel. El màxim nombre d'elements per node és O-1. Així que ha de ser possible dividir el nombre màxim d'elements U-1 en dos nodes legals. Si aquest nombre anara imparell, llavors O=2L, i cadascun dels nous nodes tindrien (O-2)/2 = L-1 elements, i per tant serien nodes legals. Si O-1 fos parell, O=2L-1, de manera que hauria 2L-2 elements en el node. La meitat d'aquest nombre és L-1, que és el nombre mínim d'elements permesos per node.

Un algorisme millorat admet una sola passada per l'arbre des de l'arrel, fins al node on la inserció tinga lloc, dividint tots els nodes que estiguen plens trobats al seu pas.Açò evita la necessitat de tornar a carregar en memòria els nodes pares, que poden ser cars si els nodes es troben en una memòria secundària.No obstant això, per a usar aquest algorisme millorat, hem de ser capaços d'enviar un element al node pare i dividir la resta O-2 elements en 2 nodes legals, sense afegir un nou element.Açò requereix que O=2L en lloc de O=L-1,el que explica per quin alguns llibres de text imposen aquest requisit en la definició d'arbres-B.

Eliminació

L'eliminació d'un element és directa si no es requereix correcció per a garantir les seues propietats. Hi ha dues estratègies populars per a eliminar un node d'un arbre B.

• localitzar i eliminar l'element, i després corregir, o

• fer una única passada de dalt a baix per l'arbre, però cada vegada que es visita un node, reestructurar l'arbre perquè quan es trobe l'element a ser esborrat, puga eliminar-se sense necessitat de continuar reestructurant

Es poden donar dos problemes a l'eliminar elements: primer, l'element pot ser un separador d'un node intern. Segon, pot succeir que a l'esborrar l'element nombre d'elements del node quede sota la cota mínima. Aquests problemes es tracten a continuació en ordre.

Eliminació en un node fulla

• Cerque el valor a eliminar.
• Si el valor es troba en un node fulla, s'elimina directament la clau, possiblement deixant-lo amb molt pocs elements; pel que es requeriran canvis addicionals en l'arbre.

eliminar clau 20 d'un node intern

Eliminació en un node intern

Cada element d'un node intern actua com valor separador per a dos *subárboles, i quan aqueix element és eliminat, poden succeir dos casos. En el primer, tant el fill esquerre com el dret tenen el nombre mínim d'elements, L-1. Poden llavors fondre's en un únic node amb 2L-2 elements, que és un nombre que no excedeix O-1 i per tant és un node legal. Llevat que se sàpia que aquest arbre B en particular no té dades duplicades, també s'ha d'eliminar l'element en qüestió (recursivament) del nou nodet.

En el segon cas, un dels dos nodes fills tenen un nombre d'elements major que el mínim. Llavors s'ha de trobar un nou separador per a aquests dos subarbres. Note que el major element de l'arbre esquerre és el major element que és menor que el separador. De la mateixa forma, el menor element del subarbre dret és el menor element que és major que el separador. Ambdós elements es troben en nodes fulla, i qualsevol dels dos pot ser el nou separador.

• Si el valor es troba en un node intern, esculla un nou separador (pot ser el major element del subarbre esquerre o el menor element del subarbre dret), elimine'l del node fulla que es troba, i reemplace l'element a eliminar pel nou separador.
• Com s'ha eliminat un element d'un node fulla, s'ha de tractar aquest cas de manera equivalent.

Rebalanceig després de l'eliminació

Si a l'eliminar un element d'un node fulla el node s'ha quedat amb menys elements que el mínim permès, alguns elements s'han de redistribuir. En alguns casos el canvi duu la deficiència al node pare, i la redistribució s'ha d'aplicar iterativament cap amunt de l'arbre, potser fins i tot fins a l'arrel. Atès que la cota mínima en el nombre d'elements no s'aplica a l'arrel, el problema desapareix quan arriba a aquesta.

L'estratègia consisteix a trobar un germà per al node deficient que tinga més del mínim nombre d'elements i redistribuir els elements entre els germans perquè tots tinguen més del mínim. Açò també canvia els separadors del node pare.

• Si el node germà immediat de la dreta del node deficient té més del mínim nombre d'elements, esculla el valor mitjà entre el separador i ambdós germans com nou separador i col·loque'l en el pare.
• Redistribuïsca els elements restants en els nodes fill dret i esquerre.
• Redistribuïsca els subarbres dels dos nodes. Els subarbres són trasplantats per complet, i no s'alteren si es mouen a un altre node pare, i açò pot fer-se mentre els elements es redistribueixen.
• Si el node germà immediat de la dreta del node deficient té el mínim nombre d'elements, examine el node germà immediat de l'esquerra.
• Si els dos nodes germans immediats tenen el mínim nombre d'elements, creu un nou node amb tots els elements del node deficient, tots els elements d'un dels seus germans, col·locant el separador del pare entre els elements dels dos nodes germans fosos.

• Elimine el separador del pare, i reemplace els dos fills que separava pel nou node fos.

• Si aqueixa acció deixa al nombre d'elements del pare per sota del mínim, repetisca aquests passos en el nou node deficient, llevat que siga l'arrel, ja que no té cota mínima en el nombre d'elements.

Construcció Inicial

En aplicacions, és freqüentment útil construir un arbre-B per a representar un gran nombre de dades existents i després actualitzar-lo de forma creixent usant operacions *Standard dels arbres-B. En aquest cas, la manera més eficient per a construir l'arbre-B inicial no seria inserir tots els elements en el conjunt inicial successivament, si no construir el conjunt inicial de nodes fulla directament des de l'entrada, i després construir els nodes interns a partir d'aquest conjunt. Inicialment, totes les fulles excepte l'última tenen un element més, el qual serà utilitzat per a construir els nodes interns.

Per exemple, si els nodes fulla tenen una grandària màxima de 4 i el conjunt inicial és d'enters des de l'1 al 24, hem de construir inicialment

5 nodes fulla contenint 5 valors cadascun (excepte l'últim que conté 4):

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24

Construirem el següent nivell cap amunt des de les fulles prenent l'últim element de cada fulla excepte l'últim. De nou, cada node excepte l'últim contindrà un valor més. En l'exemple, és suposat que els nodes interns contenen com a molt 2 valors (pel que poden tenir 3 fills). Després el següent nivell de nodes interns ens quedaria de la següent manera:

5 10 15

20

1 2 3 4

6 7 8 9

11 12 13 14

16 17 18 19

21 22 23 24

Aquest procés es continuarà fins que arribem a un nivell amb un sol node i no aquesta sobrecarregat. En el nostre exemple solament ens quedaria el nivell de l'arrel:

15

5 10

20

1 2 3 4

6 7 8 9

11 12 13 14

16 17 18 19

21 22 23 24

Notes

Cada node tindrà sempre entre L i O fills inclosos amb una excepció:

el node arrel ha de tenir entre 2 i O fills. En altres paraules, l'arrel està exempta de la restricció del límit inferior. Açò permet a l'arbre sostenir un menut nombre d'elements. Un node arrel amb un sol fill no tindria sentit, ja que podríem afegir-se'l a l'arrel. Un node arrel sense fills és també innecessari, ja que un arbre sense fills se sol representar sense arrel.

Multi-manera:combinar i dividir

És possible modificar l'algorisme anterior, quan vam tractar de trobar més elements per a un node al que li falten, vam examinar als germans, i si algun té més del valor mínim de nombres, vam reordenar els valors dels germans d'un extrem a altre per a emplenar al mínim el node al que li falten.

De la mateixa manera, quan un node es divideix, els elements extra poden ser moguts prop, per exemple a germans menys poblats; o la divisió pot donar lloc a un nombre de germans, redistribuint els elements entre ells en lloc de dividir un node.

En la pràctica, l'ús més comú dels arbres-B implica mantenir els nodes una memòria secundària, on serà lent accedir a un node que no haja estat usat amb anterioritat. Utilitzant solament divisions i combinacions, vam disminuir el nombre de nodes que es necessiten per a la majoria de situacions comunes, però podrien ser útils en unes altres.

Relació entre O i L

És quasi universal el dividir nodes triant un element mitjà i creant dos nous nodes. Açò limita la relació entre L i O. Si intentem inserir un element dins d'un node amb O elements, açò comporta una redistribució de O elements. Un d'aquests, l'intermedi, serà traslladat al node pare, i els restants seran dividits equitativament, en la mesura del possible, entre els dos nous nodes.

Per exemple, en un arbre-B 2-3, afegint un element a un node que ja conté 3 fills, i per tant 2 valors separadors (pares), dona lloc a 3 valors (els dos separadors i el nou valor). El valor mitjà es converteix en el nou separador (pare), i els altres valors es fan independents i amb 2 fills. En general, si O és imparell, cadascun dels nous nodes tenen (O+2)/2 fills. Si O és parell, uns té O/2 fills i l'altre O/2+1.

Si un node està complet i es divideix exactament en 2 nodes, L ha de tenir una grandària permesa, prou menut, una vegada q el node ha estat dividisc. També és possible dividir nodes complets en més de dos nodes nous. Triant dividir un node en més de 2 nodes nous requerirà un valor més menut per a L per al mateix valor de O.

Com L es fa més menut, açò permet que haja més espai sense usar en els nodes. Açò disminuirà la freqüència de divisió de nodes, però de la mateixa manera augmentarà la quantitat de memòria que es necessita per a emmagatzemar el mateix nombre de valors, i el nombre de nodes que han de ser examinats per a una operació particular.

Accés concurrent

Lehman i Yao ens mostraren que unint els blocs d'arbres en cada nivell, amb un punter al següent nivell, en una estructura d'arbre, on els permisos de lectura dels blocs de l'arbre es poden evitar, perquè l'arbre descendeix des de l'arrel fins a les fulles per recerca i inserció. Els permisos d'escriptura solament es requereixen quan un bloc de l'arbre és modificat. Minimitzant els permisos a un node penjant simple, solament durant la seua modificació ajuda a maximitzar l'accés concorrent per múltiples usuaris. Una dada a ser considerat en les bases de dades, per exemple i/o altre arbre basat en ISAM (Mètodes Indexats d'Accés Seqüencial) mètodes d'emmagatzematge.

Vegeu també

• Arbre
• Arbre binari
• Arbre-B+
• Partició d'espai binari
• Arbre roig-negre
• Skip list

Enllaços externs

• Exemple de funcionament de l'arbre 2-3-4 (la variant més simple d'arbre-B) Arxivat 2006-06-01 a Wayback Machine. (anglès)
• Applet d'exemple del funcionament de l'arbre B (anglès)
• Tutorial sobre arbres B Arxivat 2007-01-20 a Wayback Machine.
• «Computer Science: Indexacion Java, Estructura de Datos». [Consulta: 7 octubre 2012]. Indexació de dades amb arbre B en Java (castellà)