Arbre-B

Erro al crear miniatura:

Eixemple d'arbre B.

En les ciències de la computació, els arbres-B o B-arbres són estructures de senyes d'arbre que es troben comunament en les implementacions de bases de senyes i sistemes d'archius. De la mateixa manera que els arbres binaris de busca, són arbres balancejats de busca, pero cada nodo pot posseir més de dos fills. Els arbres B mantenen les senyes ordenades i les insercions i eliminacions es realisen en temps logarítmic amortisat.

Definició

L'idea despuix dels arbres-B és que els nodos interns deuen tindre un número variable de nodos fill dins d'un ranc predefinit. Quan s'inserta o s'elimina una senya de l'estructura, la cantitat de nodos fill varia dins d'un nodo. Per a que seguixca mantenint-se el número de nodos dins del ranc predefinit, els nodos interns es junten o es partixen. Ya que es permet un ranc variable de nodos fill, els arbres-B no necessiten rebalancearse tan freqüentment com els arbres binaris de busca auto-balanceables. Pero, per un atre costat, poden desperdiciar memòria, perque els nodos no permaneixen totalment ocupats. Els llímits (un de superior i un atre inferior) en el número de nodos fill són definits per a cada implementació en particular. Per eixemple, en un arbre-B 2-3 (A sovint simplement cridat arbre 2-3 ), cada nodo només pot tindre 2 o 3 nodos fills.

Un arbre-B es manté balancejat perque requerix que tots els nodos full es troben a la mateixa altura.

Els arbres B tenen ventages substancials sobre atres implementacions quan el temps d'accés als nodos excedix al temps d'accés entre nodos. Este cas es dona usualment quan els nodos es troben en dispositius d'almagasenament secundari com els discs rígits. En maximizar el número de nodos fill de cada nodo intern, l'altura de l'arbre decreix, les operacions per a balancejar-ho es reduïxen, i aumenta l'eficiència. Usualment este valor es coloca de forma tal que cada nodo ocupe un bloc de disc, o un tamany anàlec en el dispositiu. Mentres que els arbres B 2-3 poden ser útils en la memòria principal, i ademés més fàcils d'explicar, si el tamany dels nodos s'ajusta 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, ya que tots els nodos full es mantenen al mateix nivell en l'arbre. La B també pot referir-se a Bayer, o a Boeing, perque els seus creadors treballaven en els Boeing Scientific Research Labs per eixe llavors.

Definició tècnica

B-arbre és un arbre de busca que pot estar buit o aquell els nodos del qual poden tindre varis fills, existint una relació d'orde entre ells, tal com mostra el dibuix.

Un arbre-B d'orde M (el màxim número de fills que pot tindre cada nodo) és un arbre que satisfà les següents propietats:

1. Cada nodo té com a màxim M fills.
2. Cada nodo (llevat raïl) té com a mínim (M)/2 claus.
3. La raïl té a lo manco 2 fills si no és un nodo full. (segons M)
4. Tots els nodos full apareixen al mateix nivell.
5. Un nodo no full en k fills conté k-1 elements almagasenats.
6. Els fills que pengen de la raïl (r1, ···, rm) tenen que 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é valor major que rm.

Notes

Cada nodo tindrà sempre entre L i O fills inclosos en una excepció: El nodo raïl deu tindre entre 2 i O fills. En atres paraules, la raïl està exenta de la restricció del llímit inferior. Açò permet a l'arbre sostindre un chicotet número d'elements. Un nodo raïl en un sol fill no tindria sentit, ya que podríem afegir-li-ho a la raïl. Un nodo raïl sense fills és també innecessari, ya que un arbre sense fills se sol representar sense raïl.

Multi-modo:combinar i dividir

És possible modificar l'algoritme anterior, quan tractem de trobar més elements per a un nodo al que li falten, examinem als germans, i si algun té més del valor mínim de números, reordenamos els valors dels germans d'un extrem a un atre per a reblir al mínim el nodo al que li falten. De la mateixa manera, quan un nodo es dividix, els elements extra poden ser moguts prop, per eixemple a germans menys poblats; o la divisió pot donar lloc a un número de germans, redistribuint els elements entre ells en lloc de dividir un nodo.

En la pràctica, l'us més comú dels arbres-B implica mantindre els nodos una memòria secundària, a on serà llent accedir a un nodo que no haja segut usat en anterioritat. Utilisant solament divisions i combinacions, disminuïm el número de nodos que es necessiten per a la majoria de situacions comunes, pero podrien ser útils en unes atres.

Relació entre O i L

És casi universal el dividir nodos elegint un element mig i creant dos nous nodos. Açò llimita la relació entre L i O. Si intentem insertar un element dins d'un nodo en O elements, açò comporta una redistribució de O elements. Un d'estos, l'intermig, serà traslladat al nodo pare, i els restants seran dividits equitativament, en la mida de lo possible, entre els dos nous nodos.

Per eixemple, en un arbre-B 2-3, afegint un element a un nodo que ya conté 3 fills, i per tant 2 valors separadores (pares), dona lloc a 3 valors (els dos separadores i el nou valor). El valor mig es convertix en el nou separador (pare), i els atres valors es fan independents i en 2 fills. Per lo general, si O és impar, cada u dels nous nodos tenen (O+2)/2 fills. Si O és parell, uns té O/2 fills i l'atre O/2+1.

Si un nodo està complet i es dividix exactament en 2 nodos, L deu tindre un tamany permés, lo suficient chicotet, una volta q el nodo ha segut dividixc. També és possible dividir nodos complets en més de dos nodos nous. Elegint dividir un nodo en més de 2 nodos nous requerirà un valor més chicotet per a L per al mateix valor de O. Com a L es fa més chicotet, açò permet que hi haja més espai sense usar en els nodos. Açò disminuirà la freqüència de divisió de nodos, pero de la mateixa manera aumentarà la cantitat de memòria que es necessita per a almagasenar el mateix número de valors, i el número de nodos que tenen que ser examinats per a una operació particular.

Accés concurrent

Lehman i Yao nos varen mostrar que, unint els blocs d'arbres en cada nivell en una busca al següent nivell (en una estructura d'arbre a on els permissos, de llectura dels blocs de l'arbre, es poden evitar perque l'arbre descendix des de la raïl fins als fulls per busca i inserció), els permissos d'escritura solament es requerixen quan un bloc de l'arbre és modificat. Minimisar els permissos a un nodo colgante simple solament durant la seua modificació, ajuda a maximizar l'accés concurrent per múltiples usuaris. Esta senya es té en conte en bases de senyes com, per eixemple, ISAM (Métodos Indexats d'Accés Seqüencial).

Vore també

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