Arborele B

Reprezentarea unui copac B.

Un copac B (în engleză : copac B ) este o structură de date care permite localizarea rapidă a fișierelor ( înregistrări sau chei), în special în baze de date , reducând de câte ori are nevoie un utilizator pentru a accesa memoria în care sunt salvate datele . Ele derivă din copacii de căutare binari , deoarece fiecare cheie aparținând subarborelui stâng al unui nod are o valoare mai mică decât orice cheie aparținând subarborelui din dreapta acestuia; în plus, structura lor garantează echilibrul lor: pentru fiecare nod, înălțimile subarborelui drept și stâng diferă cu mai mult de o unitate. Acesta este principalul avantaj al arborelui B și vă permite să efectuați operațiuni de inserare, ștergere și căutare în timpi amortizați logaritmic.

Acestea sunt adesea utilizate în contextul bazelor de date , deoarece permit accesul la noduri în mod eficient atât dacă sunt disponibile în memoria centrală (printr-un cache ), cât și dacă sunt prezente doar în memoria de masă.

Definiție

Un copac B este un copac înrădăcinat (a cărui rădăcină poate fi denumită $root[T]$ ${\ displaystyle root [T]}$ $rădăcină [T]$ ) care îndeplinește următoarele proprietăți:

Fiecare nod $X$ {\ displaystyle x} $X$ are următoarele atribute:
- $n[x]$ ${\ displaystyle n [x]}$ $n [x]$ , numărul de taste stocate în $X$ ${\ displaystyle x}$ $X$
- indicând cu $key_{i}[x]$ ${\ displaystyle key_ {i} [x]}$ $cheie_ {i} [x]$ tasta a i-a a nodului $X$ ${\ displaystyle x}$ $X$ da ai $key_{1}[x]\leq key_{2}[x]\leq ...\leq key_{n[x]}[x]$ ${\ displaystyle key_ {1} [x] \ leq key_ {2} [x] \ leq ... \ leq key_ {n [x]} [x]}$ $key_ {1} [x] \ leq key_ {2} [x] \ leq ... \ leq key _ {{n [x]}} [x]$
- $leaf[x]$ ${\ displaystyle leaf [x]}$ $frunza [x]$ este o valoare booleană care poate lua valoare ${\mbox{true}}$ ${\ displaystyle {\ mbox {true}}}$ ${\ mbox {true}}$ dacă nodul $X$ ${\ displaystyle x}$ $X$ este o frunză, ${\mbox{false}}$ ${\ displaystyle {\ mbox {false}}}$ ${\ mbox {false}}$ in caz contrar.
Fiecare nod intern are $n[x]+1$ ${\ displaystyle n [x] +1}$ $n [x] +1$ indicii $c_{1}[x],c_{2}[x],...,c_{n[x]+1}[x]$ ${\ displaystyle c_ {1} [x], c_ {2} [x], ..., c_ {n [x] +1} [x]}$ $c_ {1} [x], c_ {2} [x], ..., c _ {{n [x] +1}} [x]$ copiilor săi.
Merita $c_{1}[x]\leq key_{1}[x]\leq c_{2}[x]\leq key_{2}[x]\leq ...\leq key_{n[x]}[x]\leq c_{n[x]+1}[x]$ ${\ displaystyle c_ {1} [x] \ leq key_ {1} [x] \ leq c_ {2} [x] \ leq key_ {2} [x] \ leq ... \ leq key_ {n [x] } [x] \ leq c_ {n [x] +1} [x]}$ $c_ {1} [x] \ leq key_ {1} [x] \ leq c_ {2} [x] \ leq key_ {2} [x] \ leq ... \ leq key _ {{n [x]} } [x] \ leq c _ {{n [x] +1}} [x]$
Toate frunzele au aceeași adâncime (arborele este complet echilibrat )
Numărul de chei pe nod este limitat în partea de sus și de jos. $t$ $\geq$ $2$ {\ displaystyle t \ geq 2} $t \ geq 2$ este gradul minim al arborelui
- Fiecare nod conține cel puțin $t-1$ ${\ displaystyle t-1}$ $t-1$ cheie
- Fiecare nod conține cel mult $2t-1$ ${\ displaystyle 2t-1}$ $2t-1$ cheie

Avantajele copacilor B

B-Trees aduce avantaje puternice în ceea ce privește viteza și eficiența față de implementările alternative atunci când majoritatea nodurilor se află în memoria secundară, de exemplu pe un hard disk. Prin maximizarea numărului de noduri copil pentru fiecare nod, înălțimea arborelui este redusă, operația de echilibrare este necesară mai rar și, prin urmare, crește eficiența. În general, acest număr este setat în așa fel încât fiecare nod să ocupe un întreg grup de sectoare: astfel, deoarece operațiunile de nivel scăzut accesează discul pe cluster, numărul de accesări la acesta este minimizat. Acestea oferă performanțe excelente atât în ceea ce privește operațiunile de căutare, cât și de actualizare, deoarece ambele pot fi realizate cu complexitate logaritmică și prin utilizarea unor proceduri destul de simple. Pe ele este, de asemenea, posibilă efectuarea procesării secvențiale a arhivei primare fără a fi necesară reorganizarea acesteia.

Structura nodului

Este indicat cu $R.$ ${\ displaystyle R}$ $R.$ ordinea pomului. Iată o simplificare a structurii nodului pentru un B-Tree implementat în C ++.

 struct bNode
{
  int nKeys ; // nivel de umplere nod
 
  bNode * RefPage [ 2 * R + 1 ]; // vector de indicatori către nodurile copil
 
  tipoChiave K [2 * R]; // vector comandat de chei 2 * R;
 
  lung RefInfo [ 2 * R ]; // vector de indicatori pentru arhivarea informațiilor
 
};

Înălțimea unui copac B.

Presupunând că numărul de chei al unui B-Tree este egal cu $n$ ${\ displaystyle n}$ $n$ iar gradul său minim este $t\geq 2$ ${\ displaystyle t \ geq 2}$ $t \ geq 2$ , inaltimea $h$ ${\ displaystyle h}$ $h$ , în cel mai rău caz, va fi

$h\leq \log _{t}{n+1 \over 2}$ ${\ displaystyle h \ leq \ log _ {t} {n + 1 \ peste 2}}$ $h \ leq \ log _ {t} {n + 1 \ peste 2}$

La urma urmei, dacă un B-Tree are înălțime $h$ ${\ displaystyle h}$ $h$ , este evident că numărul nodurilor sale este minim dacă rădăcina conține o cheie și toate celelalte noduri conțin $t-1$ ${\ displaystyle t-1}$ $t-1$ chei: veți avea, în acest fel, $2$ ${\ displaystyle 2}$ $2$ noduri la adâncimea 1, $2t$ ${\ displaystyle 2t}$ $2t$ noduri la adâncimea 2, $2t^{2}$ ${\ displaystyle 2t ^ {2}}$ $2t ^ {2}$ la adâncimea 3 și așa mai departe. Fix $h$ ${\ displaystyle h}$ $h$ înălțimea Arborelui B va avea ca la adâncimea h să fie $2t^{h}-1$ ${\ displaystyle 2t ^ {h} -1}$ $2t ^ {h} -1$ noduri. Deci, numărul de taste va fi

$n\geq 1+2(t-1)\sum _{i=1}^{h}t^{i-1}=2t^{h}-1$ ${\ displaystyle n \ geq 1 + 2 (t-1) \ sum _ {i = 1} ^ {h} t ^ {i-1} = 2t ^ {h} -1}$ $n \ geq 1 + 2 (t-1) \ sum _ {{i = 1}} ^ {h} t ^ {{i-1}} = 2t ^ {h} -1$

Crearea unui copac B.

Operația de creare a unui B-Tree (inițial fără chei) necesită doar crearea unui nod rădăcină.

 B-Tree-Create (T)
 alocați un nou nod x
 n [x] ← 0
 frunza [x] ← ADEVĂRAT
 scrie nodul x pe disc
 rădăcină [T] ← x

Operațiuni principale

Cele trei operații de bază care pot fi efectuate pe un B-Tree sunt discutate mai jos:

Căutați o cheie
Introducerea unei chei (necesită operația de divizare a nodului)
Ștergere (necesită îmbinarea nodurilor)

Cercetare

Căutarea unei înregistrări a cheii k se efectuează într-un mod similar cu arborele binar , cu singura diferență că, la fiecare pas, alegerile posibile nu sunt două, ci coincid cu numărul de chei ale fiecărui nod. Loc $n[x]$ ${\ displaystyle n [x]}$ $n [x]$ numărul de chei ale unui nod generic $X$ ${\ displaystyle x}$ $X$ din Arborele B, vom avea acest lucru la fiecare nod intern $X$ ${\ displaystyle x}$ $X$ vor apărea $n[x]+1$ ${\ displaystyle n [x] +1}$ $n [x] +1$ alegeri alternative.

Căutați o cheie

Procedura de căutare este împărțită în următorii pași:

Transferul rădăcinii în memorie
Căutați K în pagina transferată: dacă este prezentă, căutarea este finalizată.
În caz contrar, dacă K este mai mic decât cheia din stânga nodului, atunci transferați pagina indicată de indicatorul din stânga (dacă nu este nulă); dacă K este mai mare decât tasta din dreapta, atunci transferați pagina indicată de indicatorul din dreapta (dacă nu este nulă); dacă este între două taste ale nodului, atunci transferați pagina indicată de pointer între cele două taste (dacă nu este nulă). Reveniți la punctul 2.
Dacă indicatorul în cauză este nul, cheia nu este prezentă.

În acest fel, numărul maxim de pagini care trebuie citite pentru căutare coincide cu înălțimea arborelui.

Procedura B-Tree-Search (x, k) caută o cheie $k$ ${\ displaystyle k}$ $k$ a Arborelui B începând de la un nod $X$ ${\ displaystyle x}$ $X$ .

 B-Tree-Search (x, k)
 i ← 1
 în timp ce i <= n [x] && k> tasta _i [x] fac
   i ← i + 1
 dacă i <= n [x] && k = cheia _i [x] atunci
   return (x, i)
 dacă frunza [x] atunci
   întoarceți NIL
 altceva
   citiți nodul c _i [x] de pe disc
   returnează B-Tree-Search (c _i [x], k)

Deoarece în procedura de căutare arborele B este traversat de-a lungul unei căi de la rădăcină la o frunză, numărul de accesări pe disc este egal cu $\Omega (h)=\Omega (\log _{t}n)$ ${\ displaystyle \ Omega (h) = \ Omega (\ log _ {t} n)}$ $\ Omega (h) = \ Omega (\ log _ {t} n)$ . În plus $n[x]<2t$ ${\ displaystyle n [x] <2t}$ $n [x] <2t$ , prin urmare, timpul de execuție al algoritmului este, în mod trivial, $O(th)=O(t\log _{t}n)$ ${\ displaystyle O (th) = O (t \ log _ {t} n)}$ $O (th) = O (t \ log _ {t} n)$ .

Inserare

Introducerea unei noi chei poate fi mai dificilă decât aceeași procedură pentru un arbore binar, deoarece este esențial să se mențină echilibrul arborelui. O operație preliminară, care trebuie implementată în mod adecvat, pentru a putea îndeplini o funcție pentru inserarea unei chei într-un Arborele B este operația de împărțire a unui nod solid. Un nod al unui B-Tree este definit ca plin dacă conține exact $2t-1$ ${\ displaystyle 2t-1}$ $2t-1$ chei: fiind plin, în timpul fazei de inserare a unei chei, nu poate, prin însăși definiția arborelui B, să fie inserat în interiorul ei. Operația de divizare se efectuează la cheia mediană $key_{t}[y]$ ${\ displaystyle key_ {t} [y]}$ $cheie_ {t} [y]$ a nodului $y$ ${\ displaystyle y}$ $y$ deplin. După împărțire, nodul complet $y$ ${\ displaystyle y}$ $y$ este împărțit în două noduri diferite fiecare cu $t-1$ ${\ displaystyle t-1}$ $t-1$ cheie. Mai exact, cheia mediană a nodului $y$ ${\ displaystyle y}$ $y$ este mutat la părintele nodului $y$ ${\ displaystyle y}$ $y$ (nu plin). Operația de împărțire a unui nod crește în mod clar înălțimea copacului.

 B-Tree-Split-Child (x, i, y)
 alocați nodul z
 frunze [z] ← frunze [y]
 n [z] ← t-1
 pentru j ← 1 până la t-1
faceți tasta _j [z] ← tasta _{j + t} [y]
 dacă nu frunza [y]
apoi pentru j ← 1 la t
 faceți c_j [z] ← c _{j + t} [y]
 n [y] ← t-1
 pentru j ← n [x] +1 până la i + 1
faceți c _{j + 1} [x] ← c _j [x]
 c _{i + 1} [x] ← z
 pentru j ← n [x] până la i
faceți tasta _{j + 1} [x] ← tasta _j [x]
 tasta _i [x] ← tasta _t [y]
 n [x] ← n [x] +1
 scrieți nodurile y, z, x pe disc

Operațiunea de introducere a unei chei se realizează grație unei vizite la copac care, prin exploatarea procedurii de împărțire a nodului, împiedică introducerea acestuia într-un nod deja complet. La primul pas al procedurii de inserare se verifică dacă rădăcina arborelui B este plină: în acest caz este împărțită la înălțimea cheii mediane; acesta din urmă va deveni singura cheie a unui nou nod rădăcină; în acest moment, procedura de inserare propriu-zisă poate fi realizată prin intermediul unei funcții recursive speciale care se ocupă de introducerea cheii în poziția corectă. Dacă rădăcina arborelui, pe de altă parte, nu este plină, puteți continua direct cu inserarea. În acest scop, pot fi implementate două proceduri: B-Tree-Insert care are grijă să verifice dacă rădăcina este plină sau nu și B-Tree-Insert-Nonfull care se ocupă de efectuarea vizitei recursive a copacului pentru a insera introduceți corespondența corectă. Această ultimă procedură este invocată oricum de prima procedură, dar dacă rădăcina este plină, aceasta este divizată preliminar. Să presupunem că doriți să introduceți o cheie $k$ ${\ displaystyle k}$ $k$ într-un copac B. $T.$ ${\ displaystyle T}$ $T.$ .

 B-Tree-Insert (T, k)
 // dacă rădăcina este plină
 dacă n [r] = 2t-1
apoi alocați un nod s
 rădăcină [t] ← s // nodul s va fi noua rădăcină
 leaf [s] ← FALS
 n [s] ← 0
 c ₁ [s] ← r
 // divizarea nodului r (anterior a fost rădăcina)
 B-Copil-Split-Copil (s, 1, r)
 // apelează procedura de inserare recursivă începând cu s
 B-Tree-Insert-Nonfull (s, k)
// dacă rădăcina nu este plină
altceva
 // apelează procedura de inserare recursivă începând de la r
 B-Tree-Insert-Nonfull (r, k)

Procedura B-Tree-Insert-Nonfull introduce cheia $k$ ${\ displaystyle k}$ $k$ într-un nod $X$ ${\ displaystyle x}$ $X$ nu este plin de arborele B.

 B-Tree-Insert-Nonfull (x, k)
// dacă nodul x este o frunză
dacă frunza [x]
 atunci
  // derulați printre tastele lui x pentru a găsi poziția corectă pentru k
  în timp ce i> = 1 && k <tasta _i [x]
 do
  tasta _{i + 1} [x] ← tasta _i [x]
  i ← i-1
  // introduceți cheia
  tasta _{i + 1} [x] ← k
  // actualizare câmp n [x]
  n [x] ← n [x] +1
  scrie nodul x pe disc
 // dacă nodul x nu este o frunză, trebuie să determinăm care
 // subarborele procedează recursiv în funcție de valoarea lui k
 altceva
  în timp ce i> = 1 && k <tasta _i [x]
 do
  i ← i-1
  i ← i + 1
  // nodul a fost găsit
  citiți nodul c _i [x] de pe disc
  // dacă nodul este plin
  dacă n [c _i [x]] = 2t-1
 // împărțirea nodului
 apoi B-Tree-Split-Child (x, i, c _i [x])
  dacă k> tasta _i [x]
atunci
  i ← i + 1
  // dacă nodul nu este plin sau a fost deja împărțit, puteți
  // continuați recursiv cu vizita
  B-Tree-Insert-Nonfull (c _i [x], k)

Complexitatea algoritmului de inserare într-un B-Tree trebuie evaluată în funcție de numărul de accesări pe disc atât pentru citirea nodurilor, cât și pentru scriere. Presupunând că înălțimea Arborelui B este $h$ ${\ displaystyle h}$ $h$ se execută procedura B-Tree-Insert $O(h)$ ${\ displaystyle O (h)}$ $Oh)$ accesări pe disc. Timpul de execuție este egal cu $O(th)=O(t\log _{t}n)$ ${\ displaystyle O (th) = O (t \ log _ {t} n)}$ $O (th) = O (t \ log _ {t} n)$ .

Anulare

Procedura de ștergere a unei chei este inversa procedurii de inserare a acesteia. Să presupunem că trebuie să ștergeți o cheie $k$ ${\ displaystyle k}$ $k$ dintr-un subarbore înrădăcinat $X$ ${\ displaystyle x}$ $X$ : în acest caz o procedură de ștergere este apelată recursiv pe nod $X$ ${\ displaystyle x}$ $X$ numai dacă numărul de taste al $X$ ${\ displaystyle x}$ $X$ este egal cu gradul minim al arborelui B. $t$ ${\ displaystyle t}$ $t$ . Cazurile care pot fi întâlnite atunci când doriți să ștergeți o cheie dintr-un B-Tree sunt diverse.

Dacă cheia $k$ ${\ displaystyle k}$ $k$ se află în nod $X$ ${\ displaystyle x}$ $X$ și $X$ ${\ displaystyle x}$ $X$ este o frunză, apoi ștergeți cheia $k$ ${\ displaystyle k}$ $k$ fără operațiuni ulterioare (caz banal).
Dacă cheia $k$ {\ displaystyle k} $k$ se află într-un nod intern $X$ {\ displaystyle x} $X$ atunci procedura este mai complexă. Există trei subcazuri diferite (dintre care două sunt simetrice).
- Este $y$ ${\ displaystyle y}$ $y$ fiul lui $X$ ${\ displaystyle x}$ $X$ de mai sus $k$ ${\ displaystyle k}$ $k$ ; de sine $y$ ${\ displaystyle y}$ $y$ are cel puțin $t$ ${\ displaystyle t}$ $t$ tastele pe care trebuie să le găsiți pe predecesorul $k$ ${\ displaystyle k}$ $k$ în subarborele care are ca rădăcină $y$ ${\ displaystyle y}$ $y$ ; a găsit-o pe cea din urmă și a indicat cu $k^{'}$ ${\ displaystyle k ^ {'}}$ $k ^ {{'}}$ este șters și ulterior înlocuit $k$ ${\ displaystyle k}$ $k$ cu $k^{'}$ ${\ displaystyle k '}$ $k '$ în $X$ ${\ displaystyle x}$ $X$ .
- Caz simetric cu cel precedent. Este $z$ ${\ displaystyle z}$ $z$ fiul lui $X$ ${\ displaystyle x}$ $X$ care urmează $k$ ${\ displaystyle k}$ $k$ ; de sine $z$ ${\ displaystyle z}$ $z$ are cel puțin $t$ ${\ displaystyle t}$ $t$ chei de care aveți nevoie pentru a găsi succesorul $k$ ${\ displaystyle k}$ $k$ în subarborele care are ca rădăcină $z$ ${\ displaystyle z}$ $z$ ; a găsit-o pe cea din urmă și a indicat cu $k^{'}$ ${\ displaystyle k ^ {'}}$ $k ^ {{'}}$ este șters și ulterior înlocuit $k$ ${\ displaystyle k}$ $k$ cu $k^{'}$ ${\ displaystyle k '}$ $k '$ în $X$ ${\ displaystyle x}$ $X$ .
- Lasa-i sa fie $y$ ${\ displaystyle y}$ $y$ Și $z$ ${\ displaystyle z}$ $z$ respectiv copiii care preced și reușesc $k$ ${\ displaystyle k}$ $k$ și presupune că au $t-1$ ${\ displaystyle t-1}$ $t-1$ cheie. Apoi, acestea trebuie inserate în nod $y$ ${\ displaystyle y}$ $y$ este cheia $k$ ${\ displaystyle k}$ $k$ că toate cheile din $z$ ${\ displaystyle z}$ $z$ ; în acest caz copiii din $z$ ${\ displaystyle z}$ $z$ devin copii ai $y$ ${\ displaystyle y}$ $y$ . Cu toate acestea nodul $X$ ${\ displaystyle x}$ $X$ pierde $k$ ${\ displaystyle k}$ $k$ și indicatorul către $z$ ${\ displaystyle z}$ $z$ iar nodul $y$ ${\ displaystyle y}$ $y$ devine plin. Prin urmare, este necesar să se procedeze recursiv pentru a elimina $k$ ${\ displaystyle k}$ $k$ din $y$ ${\ displaystyle y}$ $y$ .
De sine $k$ {\ displaystyle k} $k$ nu este prezent în $X$ {\ displaystyle x} $X$ atunci se determină rădăcina $c$ $the$ $[$ $X$ $]$ {\ displaystyle c_ {i} [x]} $c_ {i} [x]$ a subarborelui pe care îl conține $k$ {\ displaystyle k} $k$ . Există două sub-cazuri.
- De sine $c_{i}[x]$ ${\ displaystyle c_ {i} [x]}$ $c_ {i} [x]$ are $t-1$ ${\ displaystyle t-1}$ $t-1$ chei și un nod soră cu $t$ ${\ displaystyle t}$ $t$ tastele apoi la $c_{i}[x]$ ${\ displaystyle c_ {i} [x]}$ $c_ {i} [x]$ o cheie a tatălui $X$ ${\ displaystyle x}$ $X$ și apoi iei o cheie fie de la fratele drept, fie de la fratele stâng al $c_{i}[x]$ ${\ displaystyle c_ {i} [x]}$ $c_ {i} [x]$ . Mai târziu îl mută pe fiul potrivit de la fratele său și se potrivește $c_{i}[x]$ ${\ displaystyle c_ {i} [x]}$ $c_ {i} [x]$ .
- De sine $c_{i}[x]$ ${\ displaystyle c_ {i} [x]}$ $c_ {i} [x]$ iar frații săi au $t-1$ ${\ displaystyle t-1}$ $t-1$ se amestecă $c_{i}$ ${\ displaystyle c_ {i}}$ $Acolo}$ cu unul dintre frații săi. O cheie a $X$ ${\ displaystyle x}$ $X$ va coborî în noul nod devenind mediana sa.

Complexitatea algoritmului de ștergere în ceea ce privește accesul la disc este $O(h)$ ${\ displaystyle O (h)}$ $Oh)$ în timp ce complexitatea timpului este $O(th)=O(t\log _{t}n)$ ${\ displaystyle O (th) = O (t \ log _ {t} n)}$ $O (th) = O (t \ log _ {t} n)$ .

Variante ale arborelui B.

Există mai multe variante ale arborelui B. Cele mai frecvente trei sunt:

Arborele B +
Arborele B *
Prefixul arborelui B
Arborele predictiv B +

Copac B +

Spre deosebire de arborele B, în arborele B + toate datele sunt salvate în frunze. Nodurile interne conțin doar chei și pointeri. Toate frunzele sunt la același nivel. Nodurile de frunze sunt, de asemenea, legate între ele ca o listă pentru a facilita extragerea informațiilor. Această conexiune face, de asemenea, posibilă efectuarea de interogări pentru o serie de valori admisibile într-un mod eficient. Numărul maxim de taste dintr-o înregistrare se numește ordinea R a arborelui B +. Numărul minim de taste pentru fiecare înregistrare este R / 2. Numărul de taste care pot fi indexate folosind un copac B + este o funcție a lui R și a înălțimii copacului. Pentru un copac B + de ordinul și înălțimea h:

Numărul maxim de taste este $n^{h}$ ${\ displaystyle n ^ {h}}$ ${\ displaystyle n ^ {h}}$
Numărul minim de taste este $2(n/2)^{h-1}$ ${\ displaystyle 2 (n / 2) ^ {h-1}}$ ${\ displaystyle 2 (n / 2) ^ {h-1}}$

Dintre toate variantele arborelui B, acesta este cel mai utilizat, deoarece toate primele noduri interne pe care le poate conține memoria principală sunt păstrate pe acesta, în timp ce restul nodurilor și frunzelor sunt lăsate în memoria de masă. Aceasta permite o viteză de căutare mai mare.

Acest tip de structură se aplică în sistemul de fișiere Journaled File System , HPFS , fi sistem de fișiere , ReFS , ReiserFS și XFS .

B * copac

Un arbore B * este o structură de date dezvoltată pentru gestionarea unor cantități mari de informații, este compusă din 2 părți: directorul și arhiva.

Arhiva este alcătuită din înregistrări, fiecare dintre ele putând fi văzută ca o pereche cheie-informație.
Directorul este organizat ca un copac: frunzele conțin indexuri, adică perechile cheie-pointer care vă permit să localizați înregistrările din arhivă, în timp ce partea superioară a arborelui are singura sarcină de a conduce la identificarea rapidă a indexul care conține cheia căutată.

Varianta principală, totuși, constă în frunzele copacului, care sunt conectate între ele printr-un lanț de indicatori, astfel încât să permită o scanare secvențială a arhivei.

Acest tip de structură își găsește aplicarea în cele Reiser4 , HFS , HFS Plus și Btrfs fișier sisteme .

Prefixul arborelui B.

Prefixul arborelui B este o evoluție a arborelui B *. În prefixele arborelui B nodurile de director nu conțin neapărat chei întregi, ci separatoare generice, adică chei care ar fi putut fi private de partea lor inițială (prefixul); întreaga cheie poate fi reconstituită pornind de la separatorul corespunzător, cunoscând poziția în arborele nodului în care este conținută. Frunzele arborelui conțin în schimb chei întregi, pentru a face căutarea secvențială mai eficientă.

Arborele predictiv B +

Același subiect în detaliu: arborele predictiv B + .

Bibliografie

Renato Conte, Lumea obiectelor Vol. 2
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introducere în algoritmi . Jackson Books, 2003, ISBN 88-256-1421-7 .

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe arborele B.

linkuri externe

Semaphore Corporation - algoritmi B-tree , pe semaphorecorp.com . Adus la 18 martie 2006 (arhivat din original la 15 martie 2006) .
Peter Neubauer - Structuri de date echilibrate ale copacilor , la bluerwhite.org .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

V · D · M Structuri de date
Tipuri	Colecție · Container
Abstract	Matrice asociativă ( Multimap ) · Listă · Stivă · Coadă ( Deque ) · prioritate coadă · Septembrie ( multiset · disjoint-set )
Matrice	Matrice de biți · Tampon circular · Matrice dinamică · Masă Hash · Matrice rar
Conectați	Lista asociațiilor · Lista Linked · Lista Omite · desfășură lista inlantuita · XOR listă înlănțuită
Copaci	B-tree · binar de căutare Arbore ( Arbore AA · Arbore AVL · arbore rosu-negru · binar de căutare copac echilibrat · copac evazat ) · Heap ( Heap binar · binom Heap · Heap Fibonacci ) · Merkle copac · copac SPQR · Arbore PQ · Binar copac indexat
Grafice	Diagrama binară de decizie · Digraf aciclic · Automat finic deterministic aciclic
Împărțirea copacilor informație spatiala	Copac Quadrament · M-tree · R-arbore ( R * arbore · R + copac ) · X-tree
Lista structurilor de date