B⁺-arborele

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 7 februarie 2022; verificarea necesită 1 editare .

Arborele B⁺ este o structură de date bazată pe un arbore B , un arbore de căutare echilibrat cu un număr variabil, dar adesea mare de copii pe nod. Un arbore B⁺ constă dintr-o rădăcină, noduri interne și frunze, rădăcina poate fi fie o frunză, fie un nod cu doi sau mai mulți copii. $n$

Inițial, structura a fost menită să stocheze date pentru căutare eficientă într-un mediu de stocare orientat pe blocuri - în special, pentru sistemele de fișiere; aplicarea se datorează faptului că, spre deosebire de arborii binari de căutare, arborii B⁺ au un factor de ramificare foarte mare (numărul de pointeri de la un nod părinte la copii este de obicei de ordinul a 100 sau mai mult), ceea ce reduce numărul de Operații I/O care necesită căutarea unui element în arbore.

O variantă a arborelui B⁺, în care toate valorile au fost stocate în nodurile frunză, a fost revizuită sistematic în 1979 [1] , observând că astfel de structuri au fost folosite de IBM în tehnologia de acces la fișiere mainframe VSAM încă cel puțin 1973.

Structura este utilizată pe scară largă în sistemele de fișiere - NTFS , ReiserFS , NSS , XFS , JFS , ReFS și BFS folosesc acest tip de arbore pentru indexarea metadatelor; BeFS folosește și arbori B⁺ pentru a stoca directoare. Sistemele de gestionare a bazelor de date relaționale, cum ar fi DB2 , Informix , Microsoft SQL Server , Oracle Database (de la versiunea 8), Adaptive Server Enterprise și SQLite acceptă acest tip de arbore pentru indici de tabel. Printre SGBD-urile NoSQL care lucrează cu modelul cheie-valoare, structura de date este implementată pentru accesul la date în CouchDB , MongoDB (când se utilizează subsistemul de stocare WiredTiger ) și Tokyo Cabinet .

Descriere

Un arbore B⁺ este un arbore de căutare echilibrat în ordine (sau grad) care satisface următoarele proprietăți: $n$ $t,$

Fiecare nod conține cel puțin o cheie; cheile din fiecare nod sunt ordonate, rădăcina conține cheile de la până la , orice alt nod conține cheile de la până la ; frunzele nu fac excepție de la această regulă. Aici , este un parametru de arbore care este de cel puțin 2 (și de obicei ia valori de la 50 la 2000, în funcție de dimensiunea cheii în raport cu dimensiunea paginii, care, la rândul său, este determinată de dimensiunea înregistrării de conținut). $unu$ $2t-1$ ${\textstyle t-1}$ ${\textstyle 2t-1}$ ${\textstyle t}$
Frunzele nu au descendenți; pentru toate celelalte noduri care conțin chei, nodul dat conține copii. în care: $K_{1},\dots,K_{n},$ $(n+1)$
- primul copil și toți copiii săi conțin chei din interval $(-\infty ,K_{1});$
- pentru al --lea copil și toți copiii săi conțin chei din interval $2 \leqslant i \leqslant n$ $i$ $(K_{i-1},K_{i});$
- $(n+1)$ -al-lea copil și toți copiii săi conțin chei din interval $(K_{n},\infty).$
Adâncimea tuturor frunzelor este aceeași.
Frunzele au o legătură către un vecin care vă permite să traversați rapid arborele în ordinea crescătoare a tastelor și legături către date.

Clădire

Construirea unui arbore B⁺ poate necesita reconstruirea structurii intermediare, acest lucru se datorează faptului că numărul de chei din fiecare nod (cu excepția rădăcinii) trebuie să fie de la până la unde este gradul (sau ordinea) arborelui. Când încercați să introduceți cheia ( )-a în nod, devine necesar să separați acest nod; cheia ( )-a, care este plasată pe nivelul adiacent al arborelui, acționează ca cheie de separare a ramurilor formate . Un caz special este împărțirea rădăcinii, deoarece în acest caz numărul de niveluri ale copacului crește. O caracteristică a despărțirii unei frunze a unui arbore B⁺ este că aceasta este împărțită în părți inegale. Împărțirea unui nod intern sau rădăcină are ca rezultat noduri cu un număr egal de chei Împărțirea unei frunze poate provoca o „reacție în lanț” a nodurilor de divizare, care se termină la rădăcină. $t$ $2t,$ $t$ $2t+1$ ${\textstyle t+1}$ $k.$

Proprietăți structura

Într-un arbore B⁺, independența programului față de structura înregistrării informaționale este ușor de realizat.
Căutarea se termină neapărat într-o foaie.
Ștergerea unei chei are avantajul că ștergerea are loc întotdeauna de pe foaie.
Alte operațiuni sunt efectuate similar arborilor B.
Arborii B⁺ necesită mai multă memorie pentru a reprezenta decât arborii B clasici.
Arborii B⁺ au capacitatea de a accesa cheile secvenţial.

Operații de bază pe o structură

Caută

Rădăcina arborelui B⁺ este punctul de plecare pentru întregul interval de valori, în care fiecare nod intern este un subinterval.

De exemplu, să presupunem că trebuie să găsim valoarea unei chei într-un arbore B⁺. Pentru a face acest lucru, căutăm un nod frunză care să conțină valoarea La fiecare nod intern, trebuie să aflăm ce nod copil ulterior să urmăm, nodul intern al arborelui B⁺ are cel mult copii, unde fiecare dintre ei reprezintă un subinterval separat. Nodul corespunzător este selectat prin căutarea valorilor cheie ale nodului: $k$ $k.$ $t$

Funcție : search ( k ) return tree_search ( k , rădăcină ); Funcție : tree_search ( k , node ) dacă nodul este o frunză, atunci returnează nodul ; comutați k do case k < k [ 0 ] return tree_search ( k , p [ 0 ]); caz k [ i ] ≤ k < k [ i + 1 ] returnează căutarea arborelui ( k , p [ i + 1 ]); caz k [ d ] ≤ k returnează căutarea arborelui ( k , p [ d + 1 ]);

(Acest pseudocod presupune că duplicatele sunt ignorate.)

Adăugarea

Pentru a adăuga o cheie nouă sau o intrare nouă, mai întâi trebuie să găsiți nodul în care doriți să le adăugați. În acest caz, algoritmul este:

Dacă nodul nu este complet umplut (numărul de elemente după inserare nu este mai mare de ), atunci adăugați o cheie (înregistrare). $2t-1,$
În caz contrar, trebuie să împărțiți nodul:
- creați un nou nod, apoi mutați jumătate din elemente din cel curent în cel nou;
- adăugați cea mai mică cheie de la noul nod și adresa acestuia (nodul) la părinte;
- dacă nodul părinte este plin, împărțiți-l în mod similar:
  - adăugați cheia din mijloc la nodul părinte;
- repetați până când nodul părinte trebuie împărțit.
Dacă rădăcina se împarte, creați o nouă rădăcină cu o cheie și două pointere (cheia care este adăugată la rădăcină este eliminată din nodul acesteia)

Arborii B, spre deosebire de copacii B⁺, se extind din partea rădăcinii, nu din frunze.

Eliminare

Pentru a șterge o cheie sau o intrare, mai întâi trebuie să găsiți nodul frunză în care se află. Algoritm pentru eliminarea dintr-un nod frunză:

Dacă nodul este cel puțin pe jumătate plin, algoritmul se termină;
Dacă nodul are mai puține elemente, atunci:
- încercați să redistribuiți elemente, adică adăugați un element de la „frate” la nod - un element cu un strămoș comun.
- dacă redistribuirea eșuează, îmbinați nodul cu „fratele”.
Dacă are loc o îmbinare, eliminați cheia sau intrarea care indică nodul la distanță sau „fratele” acestuia din nodul părinte.

Unirea se poate extinde până la rădăcină, caz în care înălțimea copacului scade.

Complexitatea computațională a operațiunilor

Complexitatea de calcul a fiecărei operații în cel mai rău caz: unde este ordinea arborelui sau a factorului de ramificare; este numărul de elemente din arborele de ramuri din nodurile arborelui. $O(\log {\frac {t}{2n))}$ $t$ $n$

Note

↑ Douglas Comer. Arborele omniprezent B-Tree // Sondajele ACM Computing. - 1979. - Iunie ( vol. 11 , nr. 2 ). - P. 121-137 . — ISSN 0360-0300 . Arhivat din original pe 17 noiembrie 2015.

Literatură

Zubov V. S., Shevchenko I. V. Capitolul 6. Căutare în arbori nebinari - arbori B // Structuri și metode de prelucrare a datelor. Atelier în mediul Delphi. - Filin, 2004. - S. 144-164. — ISBN 5-9216-0053-9 .
Donald Knuth . 4. Generarea tuturor copacilor. Istoria generației combinatorii // The Art of Programming = The Art of Computer Programming. - M. : „Williams” , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Link -uri

B⁺ Tree Visualizer - B+ Tree Visualizer

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele segmentului
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree