B-arborele

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 24 februarie 2015; verificările necesită 46 de modificări .

B-tree (pronunțat în rusă ca B-tree ) este o structură de date , un arbore de căutare. Din punctul de vedere al reprezentării logice externe - un arbore echilibrat , foarte ramificat . Adesea folosit pentru a stoca date în memoria externă.

Utilizarea arborilor B a fost propusă pentru prima dată de R. Bayer și E. McCreight în 1970 .

Echilibrat înseamnă că lungimile oricăror două căi de la rădăcină la frunze diferă cu cel mult unul.

Ramificarea unui arbore este proprietatea fiecărui nod de arbore de a se referi la un număr mare de noduri descendente.

Din punct de vedere al organizării fizice, arborele B este reprezentat ca o structură multilistă a paginilor de memorie, adică fiecărui nod al arborelui îi corespunde un bloc de memorie (pagină). Paginile interioare și cele cu frunze au de obicei o structură diferită.

Aplicație

Structura B-tree este utilizată pentru a organiza indecși în multe SGBD-uri moderne .

Un arbore B poate fi folosit pentru a structura (indexa) informații pe un hard disk (de obicei metadate). Timpul de acces la un bloc arbitrar de pe un hard disk este foarte lung (de ordinul milisecundelor), deoarece este determinat de viteza de rotație a discului și de mișcarea capului. Prin urmare, este important să se reducă numărul de noduri scanate la fiecare operație. Folosirea unei căutări în listă de fiecare dată pentru a găsi un bloc aleatoriu ar putea duce la un număr excesiv de accesări pe disc din cauza necesității de a trece secvențial prin toate elementele sale premergătoare celui dat, în timp ce căutarea în arborele B, datorită proprietăților lui echilibru și ramificare ridicată, pot reduce semnificativ numărul de astfel de operațiuni.

Implementarea relativ simplă a algoritmilor și existența unor biblioteci gata făcute (inclusiv cele pentru C ) pentru lucrul cu structura B-tree fac ca o astfel de organizare a memoriei să fie populară într-o mare varietate de programe care lucrează cu cantități mari de date.

Structura și principiile construcției

Un arbore B este un arbore care satisface următoarele proprietăți:

Cheile din fiecare nod sunt de obicei comandate pentru un acces ușor. Rădăcina conține de la 1 la 2t-1 chei. Orice alt nod conține chei de la t-1 la 2t-1. Frunzele nu fac excepție de la această regulă. Aici t este un parametru de arbore care este de cel puțin 2 (și de obicei ia valori de la 50 la 2000 [1] ).
Frunzele nu au descendenți. Orice alt nod care conține chei , …, , conține copii. în care $K_1$ $K_n$ $n+1$
1. Primul copil și toți copiii săi conțin chei din interval $(-\infty, K_1)$
2. Pentru , al-lea copil și toți copiii săi conțin chei din interval $2\le i\le n$ $(K_{i-1}, K_i)$
3. $(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.

Proprietatea 2 poate fi enunțată diferit: fiecare nod al arborelui B, cu excepția frunzelor, poate fi considerat ca o listă ordonată în care alternează cheile și pointerii către copii.

Caută

Dacă cheia este conținută în rădăcină, este găsită. În caz contrar, determinăm intervalul și mergem la descendentul corespunzător. Repetăm.

Adăugarea unei chei

Vom numi arborele descendenților unui anumit nod un subarboresc format din acest nod și descendenții săi.

Mai întâi, să definim o funcție care adaugă cheia K la arborele copil al nodului x. După executarea funcției, în toate nodurile trecute, cu excepția, poate, a nodului x însuși, vor exista mai puține , dar nu mai puține , taste. $2t-1$ $t-1$

Dacă x nu este o frunză,
1. Determinăm intervalul în care ar trebui să fie K. Fie y copilul corespunzător.
2. Adăugați recursiv K la arborele descendent al lui y.
3. Dacă nodul y este plin, adică conține chei, îl împărțim în două. Nodul primește prima dintre cheile y și primul dintre copiii săi, iar nodul primește ultima dintre cheile y și ultimul dintre copiii săi. Mediana cheilor nodului y merge la nodul x, iar pointerul către y la nodul x este înlocuit cu pointerii către noduri și . $2t-1$ $y_1$ $t-1$ $t$ $y_2$ $t-1$ $t$ $y_1$ $y_2$
Dacă x este o frunză, trebuie doar să adăugați cheia K acolo.

Acum să definim adăugarea cheii K la întregul arbore. Litera R reprezintă nodul rădăcină.

Adăugați K la arborele descendent al lui R.
Dacă R conține acum chei, împărțiți-l în două. Nodul primește prima dintre cheile R și primul dintre copiii săi, iar nodul primește ultima dintre cheile R și ultimul dintre copiii săi. Mediana cheilor nodului R se încadrează în nodul nou creat, care devine nodul rădăcină. Nodurile devin copiii săi . $2t-1$ $R_{1}$ $t-1$ $t$ $R_{2}$ $t-1$ $t$ $R_{1}$ $R_{2}$

Eliminarea unei chei

Dacă rădăcina este și o frunză, adică există un singur nod în arbore, pur și simplu scoatem cheia din acest nod. În caz contrar, găsim mai întâi nodul care conține cheia, amintindu-ne calea către acesta. Fie acest nod . $X$

Dacă - frunză, ștergeți cheia de acolo. Dacă au rămas cel puțin chei în nod , ne oprim aici. În caz contrar, ne uităm la numărul de chei din două noduri învecinate. Dacă există un nod învecinat din dreapta și are cel puțin chei, adăugăm la cheia de separare între acesta și nodul învecinat din dreapta, iar în locul acestei chei punem prima cheie a nodului din dreapta vecin, după care ne oprim . Dacă nu este cazul, dar există un nod din stânga vecin și are cel puțin chei, adăugăm la cheia de separare dintre acesta și nodul din stânga vecin, iar în locul acestei chei punem ultima cheie a celei vecine. nodul stâng, după care ne oprim. În cele din urmă, dacă cheia din stânga eșuează, îmbinăm nodul cu nodul din stânga sau din dreapta vecin și mutăm cheia care a separat anterior aceste două noduri în nodul îmbinat. În acest caz, numai cheile pot rămâne în nodul părinte . Apoi, dacă nu este o rădăcină, efectuăm o procedură similară cu ea. Dacă, prin urmare, am ajuns la rădăcină și au rămas de la 1 la chei în ea, nu trebuie făcut nimic, deoarece rădăcina poate avea mai puține chei. Dacă nu a mai rămas o singură cheie în rădăcină, excludem nodul rădăcină și facem singurul său copil noua rădăcină a arborelui. $X$ $X$ $t-1$ $t$ $X$ $t$ $X$ $X$ $t-2$ $t-1$ $t-1$

Dacă nu este o frunză și K este cheia sa --a, ștergeți cheia cea mai din dreapta din subarborele descendenților celui de-al --lea descendent sau, dimpotrivă, cheia cea mai din stânga din sub-arborele descendenților celui --lea descendent . După aceea, înlocuim cheia K cu cheia de la distanță. Ștergerea cheii are loc așa cum este descris în paragraful anterior. $X$ $i$ $i$ $X$ $i+1$ $X$

Principalele avantaje

În toate cazurile, utilizarea utilă a spațiului de stocare secundar este de peste 50%. Odată cu creșterea utilizării memoriei, nu există nicio scădere a calității serviciului.
Accesul aleatoriu la înregistrare este implementat printr-un număr mic de sub-operații (referiri la blocuri fizice).
În medie, operațiunile de includere și ștergere a înregistrărilor sunt implementate destul de eficient; menținând în același timp ordinea naturală a cheilor pentru prelucrarea secvențială, precum și echilibrul adecvat al arborelui pentru a asigura eșantionarea rapidă aleatorie.
Comandarea imuabilă după cheie permite procesarea eficientă a loturilor.

Principalul dezavantaj al arborilor B este că nu au un mijloc eficient de a prelua date (adică o metodă de traversare a arborilor) ordonate după o altă proprietate decât cheia aleasă.

Vezi și

Profunzime prima căutare
Lățimea prima căutare
Copaci echilibrați (auto-echilibrați):

Lista structurilor de date (arbori)

Note

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Capitolul 18. B-Trees // Algoritmi: Construcție și Analiză = Introducere în algoritmi. - Ed. a II-a. - M. : Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Literatură

Levitin A. V. Capitolul 7. Compromisul spațiu-timp: arbori B // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 331-339. — 576 p. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Capitolul 18. B-Trees // Algoritmi: Construcție și Analiză = Introducere în algoritmi. - Ed. a II-a. - M. : Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Link -uri

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