Arborele B - B-tree

B-copac
Tip	Arborele (structura datelor)
Inventat	1970
Inventat de	Rudolf Bayer , Edward M. McCreight
Complexitatea timpului în notația O mare
Algoritm In medie Cel mai rău caz Spaţiu O ( n ) O ( n ) Căutare O (jurnal n ) O (jurnal n ) Introduce O (jurnal n ) O (jurnal n ) Șterge O (jurnal n ) O (jurnal n )

În informatică , arborele B este o structură de date a arborelui auto-echilibrată care menține datele sortate și permite căutări, acces secvențial, inserții și ștergeri în timp logaritmic . Arborele B generalizează arborele de căutare binar , permițând noduri cu mai mult de doi copii. Spre deosebire de alți arbori binari de căutare auto-echilibrați , arborele B este potrivit pentru sistemele de stocare care citesc și scriu blocuri relativ mari de date, cum ar fi discurile. Este frecvent utilizat în baze de date și sisteme de fișiere .

Origine

Arborii B au fost inventați de Rudolf Bayer și Edward M. McCreight în timp ce lucrau la Boeing Research Labs , în scopul gestionării eficiente a paginilor index pentru fișiere mari cu acces aleatoriu. Presupunerea de bază a fost că indicii ar fi atât de voluminoși încât doar bucăți mici de copac ar putea încapea în memoria principală. Lucrarea lui Bayer și McCreight, Organizarea și întreținerea unor indici mari ordonați , a fost difuzată pentru prima dată în iulie 1970 și publicată ulterior în Acta Informatica .

Bayer și McCreight nu au explicat niciodată ce înseamnă, dacă este ceva, B : Boeing , echilibrat , larg , stufos și Bayer au fost sugerate. McCreight a spus că „cu cât te gândești mai mult la ce înseamnă B din copacii B, cu atât înțelegi mai bine copacii B”.

Definiție

Conform definiției lui Knuth, un copac B de ordinul m este un copac care îndeplinește următoarele proprietăți:

1. Fiecare nod are cel mult m copii.
2. Fiecare nod non-frunză (cu excepția rădăcinii) are cel puțin ⌈ m / 2⌉ noduri copil.
3. Rădăcina are cel puțin doi copii dacă nu este un nod frunze.
4. Un nod fără frunze cu k copii conține k - 1 chei.
5. Toate frunzele apar la același nivel și nu conțin informații.

Cheile fiecărui nod intern acționează ca valori de separare care împart subarborii săi. De exemplu, dacă un nod intern are 3 noduri copil (sau subarburi), atunci acesta trebuie să aibă 2 taste: a ₁ și a ₂ . Toate valorile din subarbore va fi cel mai din stânga mai puțin de un ₁ , toate valorile din subarbore din mijloc va fi între un ₁ și un ₂ , și toate valorile din subarbore va fi mai mare din dreapta decât un ₂ .

Noduri interne

Nodurile interne sunt toate nodurile, cu excepția nodurilor frunze și a nodului rădăcină. Ele sunt de obicei reprezentate ca un set ordonat de elemente și indicatori pentru copii. Fiecare nod intern contine un maxim de U copii și un minim de L copii. Astfel, numărul de elemente este întotdeauna cu 1 mai mic decât numărul de indicatori copii (numărul de elemente este între L -1 și U -1). U trebuie să fie fie 2 L, fie 2 L −1; prin urmare, fiecare nod intern este cel puțin pe jumătate plin. Relația dintre U și L implică faptul că două noduri pe jumătate pline pot fi unite pentru a face un nod legal, iar un nod complet poate fi împărțit în două noduri legale (dacă există spațiu pentru a împinge un element în sus în părinte). Aceste proprietăți fac posibilă ștergerea și inserarea de noi valori într-un arbore B și ajustarea arborelui pentru a păstra proprietățile arborelui B.

Nodul rădăcină

Numărul de copii al nodului rădăcină are aceeași limită superioară ca și nodurile interne, dar nu are limită inferioară. De exemplu, atunci când există mai puțin de L -1 elemente în întregul copac, rădăcina va fi singurul nod din copac fără copii deloc.

Noduri de frunze

În terminologia lui Knuth, nodurile frunze nu conțin nicio informație. Nodurile interne care se află la un nivel deasupra frunzelor sunt ceea ce ar fi numit „frunze” de către alți autori: aceste noduri stochează doar cheile (cel mult m -1 și cel puțin m / 2-1 dacă nu sunt rădăcina) și indicatori către noduri care nu conțin informații.

Un copac B de adâncime n +1 poate conține aproximativ U de ori mai multe articole decât un copac B de adâncime n , dar costul operațiunilor de căutare, inserare și ștergere crește odată cu adâncimea copacului. Ca și în cazul oricărui copac echilibrat, costul crește mult mai încet decât numărul de elemente.

Unii copaci echilibrați stochează valori numai la nodurile frunzei și utilizează diferite tipuri de noduri pentru nodurile frunzei și nodurilor interne. Arborii B păstrează valori în fiecare nod din arbore, cu excepția nodurilor frunze.

Diferențe de terminologie

Literatura despre copacii B nu este uniformă în terminologia sa.

Bayer și McCreight (1972), Comer (1979) și alții definesc ordinea arborelui B ca numărul minim de chei dintr-un nod non-rădăcină. subliniază că terminologia este ambiguă, deoarece numărul maxim de taste nu este clar. Un arbore de comandă 3 B poate conține maximum 6 taste sau maximum 7 taste. Knuth (1998) evită problema prin definirea ordinii pentru a fi numărul maxim de copii (care este cu unul mai mult decât numărul maxim de taste).

Termenul frunză este, de asemenea, inconsistent. Bayer și McCreight (1972) au considerat nivelul frunzei ca fiind cel mai scăzut nivel de taste, dar Knuth a considerat că nivelul frunzei este cu un nivel sub tastele cele mai mici. Există multe opțiuni posibile de implementare. În unele modele, frunzele pot deține întreaga înregistrare a datelor; în alte modele, frunzele pot conține doar indicii pentru înregistrarea datelor. Aceste alegeri nu sunt fundamentale pentru ideea unui copac B.

Pentru simplitate, majoritatea autorilor presupun că există un număr fix de chei care se încadrează într-un nod. Presupunerea de bază este că dimensiunea cheii este fixă ​​și dimensiunea nodului este fixă. În practică, pot fi folosite taste cu lungime variabilă.

Descriere informală

În arborii B, nodurile interne ( fără frunze ) pot avea un număr variabil de noduri copil în cadrul unui interval predefinit. Când datele sunt inserate sau eliminate dintr-un nod, numărul său de noduri copil se modifică. Pentru a menține domeniul predefinit, nodurile interne pot fi unite sau împărțite. Deoarece este permisă o gamă largă de noduri, arborii B nu au nevoie de reechilibrare la fel de frecvent ca alți arbori de căutare auto-echilibrați, dar pot pierde puțin spațiu, deoarece nodurile nu sunt complet pline. Limitele inferioare și superioare ale numărului de noduri copil sunt de obicei fixate pentru o anumită implementare. De exemplu, într-un arbore 2-3 (uneori denumit 2-3 arbore B ), fiecare nod intern poate avea doar 2 sau 3 noduri copil.

Fiecare nod intern al unui arbore B conține un număr de chei. Cheile acționează ca valori de separare care îi împart subarborii . De exemplu, dacă un nod intern are 3 noduri copil (sau subarburi), atunci acesta trebuie să aibă 2 taste: și . Toate valorile din subarborele din stânga vor fi mai mici decât , toate valorile din subarborele din mijloc vor fi între și și toate valorile din subarborele din dreapta vor fi mai mari decât . ${\ displaystyle a_ {1}}$${\ displaystyle a_ {2}}$${\ displaystyle a_ {1}}$${\ displaystyle a_ {1}}$${\ displaystyle a_ {2}}$${\ displaystyle a_ {2}}$

De obicei, numărul de taste este ales pentru a varia între și , unde este numărul minim de taste, și este gradul minim sau factorul de ramificare al arborelui. În practică, tastele ocupă cel mai mult spațiu într-un nod. Factorul 2 va garanta că nodurile pot fi împărțite sau combinate. Dacă un nod intern are chei, atunci adăugarea unei chei la acel nod poate fi realizată prin împărțirea nodului cheii ipotetice în două noduri cheie și mutarea cheii care ar fi fost în mijloc la nodul părinte. Fiecare nod divizat are numărul minim necesar de chei. În mod similar, dacă un nod intern și vecinul său au fiecare chei, atunci o cheie poate fi ștearsă din nodul intern prin combinarea acestuia cu vecinul său. Ștergerea cheii ar face ca nodul intern să aibă chei; aderarea la vecin ar adăuga chei plus încă o cheie adusă de la părintele vecinului. Rezultatul este un nod complet de chei. ${\ displaystyle d}$${\ displaystyle 2d}$${\ displaystyle d}$${\ displaystyle d + 1}$${\ displaystyle 2d}$${\ displaystyle 2d + 1}$${\ displaystyle d}$${\ displaystyle d}$${\ displaystyle d-1}$${\ displaystyle d}$${\ displaystyle 2d}$

Numărul de ramuri (sau noduri copil) dintr-un nod va fi cu mai mult decât numărul de chei stocate în nod. Într-un arbore B 2-3, nodurile interne vor stoca fie o cheie (cu două noduri copil), fie două taste (cu trei noduri copil). Un copac B este uneori descris cu parametrii - sau pur și simplu cu cea mai mare ordine de ramificare ,. ${\ displaystyle (d + 1)}$${\ displaystyle (2d + 1)}$${\ displaystyle (2d + 1)}$

Un arbore B este menținut echilibrat după inserare prin împărțirea unui nod potențial supraumplut, de chei, în frați cu două chei și inserarea cheii de valoare medie în părinte. Adâncimea crește numai atunci când rădăcina este împărțită, menținând echilibrul. În mod similar, un arbore B este menținut echilibrat după ștergere prin fuzionarea sau redistribuirea cheilor între frați pentru a menține minimul -key pentru nodurile non-rădăcină. O fuziune reduce numărul de chei din părinte, forțându-l potențial să fuzioneze sau să redistribuie cheile cu frații săi și așa mai departe. Singura modificare a adâncimii are loc atunci când rădăcina are doi copii, de și (tranzitorii) chei, caz în care cei doi frați și părinte sunt fuzionați, reducând adâncimea cu unul. ${\ displaystyle 2d + 1}$${\ displaystyle d}$${\ displaystyle d}$${\ displaystyle d}$${\ displaystyle d-1}$

Această adâncime va crește încet pe măsură ce elementele sunt adăugate copacului, dar o creștere a adâncimii generale este rară și are ca rezultat ca toate nodurile frunzelor să fie încă un nod mai departe de rădăcină.

Arborii B au avantaje substanțiale față de implementările alternative atunci când timpul de accesare a datelor unui nod depășește cu mult timpul petrecut procesând acele date, deoarece atunci costul accesării nodului poate fi amortizat pe mai multe operațiuni din cadrul nodului. Acest lucru se întâmplă de obicei atunci când datele nodului sunt în stocarea secundară, cum ar fi unitățile de disc . Prin maximizarea numărului de chei din cadrul fiecărui nod intern , înălțimea arborelui scade și numărul accesurilor scumpe la noduri este redus. În plus, reechilibrarea arborelui are loc mai rar. Numărul maxim de noduri copil depinde de informațiile care trebuie stocate pentru fiecare nod copil și de dimensiunea unui bloc de disc complet sau de o dimensiune analogă în stocarea secundară. În timp ce 2-3 arbori B sunt mai ușor de explicat, arborii B practici care utilizează stocare secundară au nevoie de un număr mare de noduri copil pentru a îmbunătăți performanța.

Variante

Termenul arborele B se poate referi la un design specific sau se poate referi la o clasă generală de modele. În sens restrâns, un copac B stochează cheile în nodurile sale interne, dar nu trebuie să stocheze acele chei în înregistrările din frunze. Clasa generală include variații precum arborele B + , arborele B ^* și arborele B ^{* +} .

• În arborele B + , copiile cheilor sunt stocate în nodurile interne; cheile și înregistrările sunt stocate în frunze; în plus, un nod frunză poate include un indicator către următorul nod frunză pentru a accelera accesul secvențial.
• Arborele B ^* echilibrează mai multe noduri interne învecinate pentru a menține nodurile interne mai dens. Această variantă asigură că nodurile non-rădăcină sunt cel puțin 2/3 pline în loc de 1/2. Deoarece cea mai costisitoare parte a operației de introducere a nodului în arborele B este împărțirea nodului, arborii B ^* sunt creați pentru a amâna operația de împărțire cât mai mult posibil. Pentru a menține acest lucru, în loc să împărțiți imediat un nod când acesta se umple, cheile sale sunt partajate cu un nod de lângă acesta. Această operațiune de deversare este mai puțin costisitoare de realizat decât divizarea, deoarece necesită doar deplasarea tastelor între nodurile existente, nu alocarea memoriei pentru unul nou. Pentru inserare, se verifică mai întâi dacă nodul are spațiu liber în el și, dacă da, noua cheie este doar introdusă în nod. Cu toate acestea, dacă nodul este plin (are m - 1 taste, unde m este ordinea arborelui ca număr maxim de pointeri către subarburi dintr-un nod), trebuie verificat dacă fratele potrivit există și are spațiu liber . Dacă fratele potrivit are j < m - 1 taste, atunci cheile sunt redistribuite între cele două noduri fratele cât mai uniform posibil. În acest scop, tastele m - 1 din nodul curent, noua cheie introdusă, o cheie din nodul părinte și cheile j din nodul frate sunt văzute ca o matrice ordonată de taste + m + j + 1 . Matricea devine împărțită la jumătate, astfel încât ⌊ ( m + j + 1) / 2 ⌋ cele mai mici chei rămâne în nodul curent, tasta următoare (mijloc) este introdus în părinte și du - te la restul frate dreapta. (Tasta nou introdusă ar putea ajunge în oricare dintre cele trei locuri.) Situația în care fratele drept este plin, iar stânga nu este analogă. Când ambele noduri frate sunt pline, atunci cele două noduri (nodul curent și un frate) sunt împărțite în trei și încă o tastă este deplasată în sus în arbore, către nodul părinte. Dacă părintele este plin, atunci operația de vărsare / împărțire se propagă către nodul rădăcină. Ștergerea nodurilor este oarecum mai complexă decât inserarea.
• Arborele B ^{* +} combină caracteristicile principale ale arborelui B + și B ^* împreună.
• Arborii B pot fi transformați în arbori statistici de ordine pentru a permite căutări rapide pentru a N-a înregistrare în ordine cheie, sau numărarea numărului de înregistrări între oricare două înregistrări și diverse alte operații conexe.

Utilizarea arborelui B în bazele de date

Este timpul să căutați un fișier sortat

De obicei, algoritmii de sortare și căutare au fost caracterizați de numărul de operații de comparație care trebuie efectuate folosind notația de ordine . O căutare binară a unui tabel cu sortat N înregistrări, de exemplu, se poate face în aproximativ ⌈ log ₂ N ⌉ comparații. Dacă tabelul ar avea 1.000.000 de înregistrări, atunci ar putea fi localizată o înregistrare specifică cu cel mult 20 de comparații: ⌈ log ₂ (1.000.000) ⌉ = 20 .

Bazele de date mari au fost păstrate istoric pe unitățile de disc. Timpul pentru citirea unei înregistrări pe o unitate de disc depășește cu mult timpul necesar pentru a compara tastele odată ce înregistrarea este disponibilă. Timpul pentru citirea unei înregistrări de pe o unitate de disc implică un timp de căutare și o întârziere de rotație. Timpul de căutare poate fi de la 0 la 20 sau mai multe milisecunde, iar întârzierea de rotație este în medie de aproximativ jumătate din perioada de rotație. Pentru o unitate de 7200 RPM, perioada de rotație este de 8,33 milisecunde. Pentru o unitate precum Seagate ST3500320NS, timpul de căutare track-to-track este de 0,8 milisecunde, iar timpul mediu de căutare a citirii este de 8,5 milisecunde. Pentru simplitate, presupunem că citirea de pe disc durează aproximativ 10 milisecunde.

Naiv, deci, timpul de localizare a unei înregistrări dintr-un milion ar dura 20 de lecturi de disc de 10 milisecunde pe disc citit, adică 0,2 secunde.

Momentul nu va fi atât de rău, deoarece înregistrările individuale sunt grupate împreună într-un bloc de disc . Un bloc de disc ar putea avea 16 kilobyte. Dacă fiecare înregistrare are 160 de octeți, atunci 100 de înregistrări ar putea fi stocate în fiecare bloc. Timpul de citire a discului de mai sus a fost de fapt pentru un bloc întreg. Odată ce capul discului este în poziție, unul sau mai multe blocuri de disc pot fi citite cu puțină întârziere. Cu 100 de înregistrări pe bloc, ultimele șase comparații nu trebuie să citească pe disc - comparațiile se află în ultimul bloc de disc citit.

Pentru a accelera căutarea, primele 13-14 comparații (care au necesitat fiecare acces la disc) trebuie accelerate.

Un index accelerează căutarea

Un index de arbore B creează o structură de arbore pe mai multe niveluri care descompune o bază de date în blocuri sau pagini de dimensiuni fixe. Fiecare nivel al acestui arbore poate fi utilizat pentru a lega acele pagini printr-o locație de adresă, permițând unei pagini (cunoscute sub numele de nod sau pagină internă) să se refere la altul cu pagini frunze la cel mai jos nivel. O pagină este de obicei punctul de plecare al arborelui sau „rădăcina”. Aici ar începe căutarea unei anumite chei, traversând o cale care se termină într-o frunză. Majoritatea paginilor din această structură vor fi pagini frunză care în cele din urmă se referă la rânduri specifice de tabel.

O îmbunătățire semnificativă a performanței poate fi făcută cu un B-arbore de index . Deoarece fiecare nod (sau pagină internă) poate avea mai mult de doi copii, un index al arborelui B va avea de obicei o înălțime mai mică (distanța de la rădăcină până la cea mai îndepărtată frunză) decât un arbore de căutare binar. În exemplul de mai sus, citirile inițiale pe disc au restrâns intervalul de căutare cu un factor de doi. Acest lucru poate fi îmbunătățit substanțial prin crearea unui index auxiliar care conține prima înregistrare din fiecare bloc de disc (uneori numit index rar ). Acest index auxiliar ar fi 1% din dimensiunea bazei de date originale, dar poate fi căutat mai rapid. Găsirea unei intrări în indexul auxiliar ne-ar spune ce bloc să căutăm în baza de date principală; după căutarea în indexul auxiliar, ar trebui să căutăm doar acel bloc al bazei de date principale - la un cost de încă un disc citit. Indicele ar conține 10.000 de intrări, deci ar fi nevoie de cel mult 14 comparații. La fel ca baza de date principală, ultimele șase comparații din indexul auxiliar ar fi pe același bloc de disc. Indexul ar putea fi căutat în aproximativ opt lecturi de disc, iar înregistrarea dorită ar putea fi accesată în 9 lecturi de disc.

Trucul creării unui index auxiliar poate fi repetat pentru a face un index auxiliar la indexul auxiliar. Asta ar face un indice aux-aux care ar avea nevoie doar de 100 de intrări și s-ar încadra într-un singur bloc de disc.

În loc să citim 14 blocuri de disc pentru a găsi înregistrarea dorită, trebuie doar să citim 3 blocuri. Această blocare este ideea de bază din spatele creării arborelui B, unde blocurile de disc completează o ierarhie de niveluri pentru a compune indexul. Citirea și căutarea primului (și singurului) bloc al indexului aux-aux care este rădăcina arborelui identifică blocul relevant din indexul aux în nivelul de mai jos. Citirea și căutarea acelui bloc index indică blocul relevant de citit, până când nivelul final, cunoscut sub numele de nivel frunze, identifică o înregistrare în baza de date principală. În loc de 150 de milisecunde, avem nevoie de doar 30 de milisecunde pentru a obține înregistrarea.

Indicii auxiliari au transformat problema de căutare de la o căutare binară care necesită aproximativ log ₂ N disc citește la unul care necesită doar log _b N disc citește unde b este factorul de blocare (numărul de intrări per bloc: b = 100 înregistrări per bloc în nostru exemplu; jurnal ₁₀₀ 1.000.000 = 3 citiri).

În practică, dacă baza de date principală este căutată frecvent, indexul aux-aux și o mare parte din indexul auxiliar pot să se afle într-un cache de disc , deci nu ar suporta citirea unui disc. Arborele B rămâne implementarea standard a indexului în aproape toate bazele de date relaționale și multe baze de date nerelationale le folosesc și ele.

Inserții și ștergeri

Dacă baza de date nu se modifică, atunci compilarea indexului este ușor de realizat, iar indexul nu trebuie schimbat niciodată. Dacă există modificări, atunci gestionarea bazei de date și a indexului acesteia devine mai complicată.

Ștergerea înregistrărilor dintr-o bază de date este relativ ușoară. Indexul poate rămâne același, iar înregistrarea poate fi doar marcată ca ștearsă. Baza de date rămâne în ordine sortată. Dacă există un număr mare de ștergeri, atunci căutarea și stocarea devin mai puțin eficiente.

Inserările pot fi foarte lente într-un fișier secvențial sortat, deoarece trebuie făcut spațiu pentru înregistrarea inserată. Introducerea unei înregistrări înainte de prima înregistrare necesită deplasarea tuturor înregistrărilor în jos una. O astfel de operație este prea scumpă pentru a fi practică. O soluție este să lăsați niște spații. În loc să împacheteze dens toate înregistrările într-un bloc, blocul poate avea spațiu liber pentru a permite inserțiile ulterioare. Aceste spații ar fi marcate ca și cum ar fi înregistrări „șterse”.

Atât inserțiile, cât și ștergerile sunt rapide atât timp cât spațiul este disponibil pe un bloc. Dacă o inserție nu se potrivește pe bloc, atunci trebuie găsit un spațiu liber pe un bloc din apropiere, iar indicii auxiliari trebuie reglați. Speranța este că este disponibil suficient spațiu în apropiere, astfel încât o mulțime de blocuri nu trebuie să fie reorganizate. Alternativ, pot fi utilizate unele blocuri de disc în afara secvenței.

Avantajele utilizării arborelui B pentru baze de date

Arborele B folosește toate ideile descrise mai sus. În special, un copac B:

• păstrează cheile în ordine sortată pentru parcurgerea secvențială
• folosește un index ierarhic pentru a minimiza numărul de citiri pe disc
• folosește blocuri parțial pline pentru a accelera inserțiile și ștergerile
• menține indicele echilibrat cu un algoritm recursiv

În plus, un copac B minimizează deșeurile, asigurându-se că nodurile interioare sunt cel puțin pe jumătate pline. Un copac B poate gestiona un număr arbitrar de inserări și ștergeri.

Cel mai bun caz și cel mai rău caz înălțimi

Fie h ≥ –1 înălțimea arborelui clasic B (vezi Arborele (structura datelor) § Terminologia pentru definiția înălțimii arborelui). Fie n ≥ 0 numărul de intrări din arbore. Fie m numărul maxim de copii pe care îl poate avea un nod. Fiecare nod poate avea cel mult m -1 taste.

Se poate arăta (de exemplu prin inducție) că un copac B de înălțime h cu toate nodurile sale complet umplute are n = m ^{h +1} –1 intrări. Prin urmare, cea mai bună înălțime a cazului (adică înălțimea minimă) a unui copac B este:

${\ displaystyle h _ {\ mathrm {min}} = \ lceil \ log _ {m} (n + 1) \ rceil -1}$

Fie numărul minim de copii pe care un nod intern (non-rădăcină) îl poate avea. Pentru un copac B obișnuit,${\ displaystyle d}$${\ displaystyle d = \ left \ lceil m / 2 \ right \ rceil.}$

Comer (1979) și Cormen și colab. (2001) oferă cel mai rău caz înălțimea (înălțimea maximă) a unui copac B ca.

${\ displaystyle h _ {\ mathrm {max}} = \ left \ lfloor \ log _ {d} {\ frac {n + 1} {2}} \ right \ rfloor.}$

Algoritmi

Căutare

Căutarea este similară căutării într-un arbore de căutare binar. Începând de la rădăcină, arborele este parcurs recursiv de sus în jos. La fiecare nivel, căutarea își reduce câmpul vizual la indicatorul copil (subarborele) al cărui interval include valoarea căutării. Intervalul unui subarbore este definit de valorile sau cheile conținute în nodul său părinte. Aceste valori limită sunt, de asemenea, cunoscute sub numele de valori de separare.

Căutarea binară este de obicei (dar nu neapărat) utilizată în noduri pentru a găsi valorile de separare și arborele copil de interes.

Inserare

Toate inserțiile încep de la un nod frunză. Pentru a insera un element nou, căutați arborele pentru a găsi nodul frunzei în care ar trebui adăugat noul element. Introduceți noul element în acel nod cu următorii pași:

1. Dacă nodul conține mai puțin decât numărul maxim permis de elemente, atunci este loc pentru noul element. Introduceți noul element în nod, păstrând elementele nodului ordonate.
2. În caz contrar, nodul este plin, împărțiți-l uniform în două noduri, astfel încât:
   1. O singură mediană este aleasă dintre elementele frunzei și elementul nou.
   2. Valorile mai mici decât mediana sunt introduse în noul nod stâng și valorile mai mari decât mediana sunt introduse în noul nod drept, mediana acționând ca o valoare de separare.
   3. Valoarea de separare este inserată în părintele nodului, ceea ce poate determina divizarea ei și așa mai departe. Dacă nodul nu are părinte (adică, nodul era rădăcina), creați o nouă rădăcină deasupra acestui nod (mărind înălțimea arborelui).

Dacă împărțirea merge până la rădăcină, se creează o nouă rădăcină cu o singură valoare separator și doi copii, motiv pentru care limita inferioară a mărimii nodurilor interne nu se aplică rădăcinii. Numărul maxim de elemente pe nod este U -1. Când un nod este divizat, un element se mută la părinte, dar se adaugă un element. Deci, trebuie să fie posibil să împărțim numărul maxim U -1 de elemente în două noduri legale. Dacă acest număr este impar, atunci U = 2 L și unul dintre noile noduri conține ( U −2) / 2 = L −1 elemente și, prin urmare, este un nod legal, iar celălalt conține încă un element și, prin urmare, este legal și. Dacă U −1 este par, atunci U = 2 L −1, deci există 2 L −2 elemente în nod. Jumătate din acest număr este L -1, care este numărul minim de elemente permise pe nod.

Un algoritm alternativ acceptă o singură trecere în jos a copacului de la rădăcină la nodul unde va avea loc inserarea, împărțind orice noduri complete întâlnite pe drum în mod preventiv. Acest lucru previne necesitatea de a reaminti nodurile părinte în memorie, ceea ce poate fi costisitor dacă nodurile se află pe un spațiu de stocare secundar. Cu toate acestea, pentru a utiliza acest algoritm, trebuie să putem să trimitem un element părintelui și să împărțim restul de elemente U -2 în două noduri legale, fără a adăuga un element nou. Acest lucru necesită U = 2 L mai degrabă decât U = 2 L -1, ceea ce explică de ce unele manuale impun această cerință în definirea arborilor B.

Ștergere

Există două strategii populare de ștergere dintr-un copac B.

1. Localizați și ștergeți elementul, apoi restructurați arborele pentru a-și păstra invarianții, SAU
2. Faceți o singură trecere în jos a copacului, dar înainte de a introduce (vizita) un nod, restructurați arborele astfel încât, odată ce cheia care trebuie ștearsă să fie întâlnită, să poată fi ștearsă fără a declanșa necesitatea unei restructurări ulterioare.

Algoritmul de mai jos folosește fosta strategie.

Există două cazuri speciale de luat în considerare atunci când ștergeți un element:

1. Elementul dintr-un nod intern este un separator pentru nodurile sale copil
2. Ștergerea unui element poate pune nodul său sub numărul minim de elemente și copii

Procedurile pentru aceste cazuri sunt în ordine mai jos.

Ștergerea dintr-un nod frunză

1. Căutați valoarea de șters.
2. Dacă valoarea se află într-un nod frunză, pur și simplu ștergeți-o din nod.
3. În cazul în care are loc o deversare, reechilibrați arborele așa cum este descris în secțiunea „Reechilibrare după ștergere” de mai jos.

Ștergerea dintr-un nod intern

Fiecare element dintr-un nod intern acționează ca o valoare de separare pentru doi subarburi, de aceea trebuie să găsim un înlocuitor pentru separare. Rețineți că cel mai mare element din subarborele din stânga este încă mai mic decât separatorul. La fel, cel mai mic element din subarborele din dreapta este încă mai mare decât separatorul. Ambele elemente se află în noduri frunze și oricare dintre ele poate fi noul separator pentru cele două subarburi. Algoritmic descris mai jos:

1. Alegeți un separator nou (fie cel mai mare element din subarborele din stânga, fie cel mai mic element din subarborele din dreapta), scoateți-l din nodul frunze în care se află și înlocuiți elementul de șters cu noul separator.
2. Pasul anterior a șters un element (noul separator) dintr-un nod frunză. Dacă acel nod frunză este acum deficitar (are mai puțin decât numărul necesar de noduri), atunci reechilibrează arborele începând de la nodul frunzei.

Reechilibrarea după ștergere

Reechilibrarea începe de la o frunză și se îndreaptă spre rădăcină până când arborele este echilibrat. Dacă ștergerea unui element dintr-un nod a adus-o sub dimensiunea minimă, atunci unele elemente trebuie redistribuite pentru a aduce toate nodurile la minimum. De obicei, redistribuirea implică mutarea unui element dintr-un nod frate care are mai mult decât numărul minim de noduri. Acea operațiune de redistribuire se numește rotație . Dacă niciun frate nu poate salva un element, atunci nodul deficient trebuie să fie fuzionat cu un frate. Combinarea face ca părintele să piardă un element separator, astfel încât părintele poate deveni deficitar și poate avea nevoie de reechilibrare. Fuziunea și reechilibrarea pot continua până la rădăcină. Deoarece numărul minim de elemente nu se aplică rădăcinii, transformarea rădăcinii în singurul nod deficitar nu este o problemă. Algoritmul pentru reechilibrarea arborelui este după cum urmează:

• Dacă fratele drept al nodului deficitar există și are mai mult decât numărul minim de elemente, atunci rotiți la stânga
  1. Copiați separatorul de la părinte la capătul nodului deficitar (separatorul se deplasează în jos; nodul deficient are acum numărul minim de elemente)
  2. Înlocuiți separatorul din părinte cu primul element al fratelui drept (fratele drept pierde un nod, dar are cel puțin numărul minim de elemente)
  3. Arborele este acum echilibrat
• În caz contrar, dacă fratele stâng al nodului deficitar există și are mai mult decât numărul minim de elemente, atunci rotiți la dreapta
  1. Copiați separatorul de la părinte la începutul nodului deficitar (separatorul se deplasează în jos; nodul deficient are acum numărul minim de elemente)
  2. Înlocuiți separatorul din părinte cu ultimul element al fratelui stâng (fratele stâng pierde un nod, dar are cel puțin numărul minim de elemente)
  3. Arborele este acum echilibrat
• În caz contrar, dacă ambii frați imediați au doar numărul minim de elemente, atunci fuzionează cu un frate care își separă separatorul de la părintele lor
  1. Copiați separatorul la capătul nodului din stânga (nodul din stânga poate fi nodul deficitar sau poate fi fratele cu numărul minim de elemente)
  2. Mutați toate elementele de la nodul drept la nodul stâng (nodul stâng are acum numărul maxim de elemente, iar nodul drept - gol)
  3. Eliminați separatorul din părinte împreună cu copilul drept gol (părintele pierde un element)
     • Dacă părintele este rădăcina și acum nu are elemente, atunci eliberați-l și faceți din nodul fuzionat noua rădăcină (arborele devine mai superficial)
     • În caz contrar, dacă părintele are mai puțin decât numărul necesar de elemente, reechilibrați părintele

Notă : Operațiunile de reechilibrare sunt diferite pentru copacii B + (de exemplu, rotația este diferită deoarece părintele are copie a cheii) și arborele B ^* (de exemplu, trei frați sunt îmbinați în doi frați).

Acces secvențial

În timp ce bazele de date proaspăt încărcate tind să aibă un comportament succesiv bun, acest comportament devine din ce în ce mai dificil de menținut pe măsură ce o bază de date crește, rezultând provocări de I / O și performanță mai aleatorii.

Construcția inițială

Un caz special obișnuit este adăugarea unei cantități mari de date pre-sortate într-un arbore B gol inițial. Deși este foarte posibil să efectuați pur și simplu o serie de inserții succesive, inserarea datelor sortate are ca rezultat un arbore compus aproape în întregime din noduri pe jumătate pline. În schimb, un algoritm special de „încărcare în bloc” poate fi utilizat pentru a produce un arbore mai eficient cu un factor de ramificare mai mare.

Când intrarea este sortată, toate inserțiile se află la marginea din dreapta a arborelui și, în special, de fiecare dată când un nod este divizat, ni se garantează că nu vor mai avea loc inserții în jumătatea stângă. Când încărcăm în bloc, profităm de acest lucru și, în loc să împărțim uniform nodurile supraîncărcate, le împărțim cât mai inegal posibil: lăsați nodul stâng complet plin și creați un nod drept cu chei zero și un copil (cu încălcarea B-ului obișnuit) reguli de copac).

La sfârșitul încărcării în vrac, arborele este compus aproape în întregime din noduri complet pline; numai nodul din dreapta de pe fiecare nivel poate fi mai mic decât plin. Deoarece aceste noduri pot fi, de asemenea, mai puțin de jumătate pline, pentru a restabili regulile normale ale arborelui B, combinați astfel de noduri cu frații lor stângi (plin garantat) și împărțiți tastele pentru a produce două noduri cel puțin pe jumătate pline. Singurul nod căruia îi lipsește un frate stâng complet este rădăcina, căreia i se permite să fie mai puțin de jumătate plină.

În sistemele de fișiere

Pe lângă utilizarea sa în baze de date, arborele B (sau § Variante ) este utilizat și în sistemele de fișiere pentru a permite accesul rapid aleatoriu la un bloc arbitrar într-un anumit fișier. Problema de bază este transformarea adresei blocului de fișiere într-o adresă de disc (sau poate într-o direcție a cilindrului ). ${\ displaystyle i}$

Unele sisteme de operare necesită utilizatorului să aloce dimensiunea maximă a fișierului atunci când este creat fișierul. Fișierul poate fi alocat ca blocuri de disc adiacente. În acest caz, pentru a converti adresa blocului de fișier într-o adresă a blocului de disc, sistemul de operare adaugă pur și simplu adresa blocului de fișiere la adresa primului bloc de disc care constituie fișierul. Schema este simplă, dar fișierul nu poate depăși dimensiunea creată. ${\ displaystyle i}$${\ displaystyle i}$

Alte sisteme de operare permit creșterea unui fișier. Este posibil ca blocurile de disc rezultate să nu fie adiacente, deci maparea blocurilor logice la blocurile fizice este mai implicată.

MS-DOS , de exemplu, a folosit un tabel simplu de alocare a fișierelor (FAT). FAT are o intrare pentru fiecare bloc de disc, iar acea intrare identifică dacă blocul său este utilizat de un fișier și dacă da, care bloc (dacă există) este următorul bloc de disc al aceluiași fișier. Deci, alocarea fiecărui fișier este reprezentată ca o listă legată în tabel. Pentru a găsi adresa discului blocului de fișiere , sistemul de operare (sau utilitarul discului) trebuie să urmeze secvențial lista legată a fișierului din FAT. Mai rău, pentru a găsi un bloc de disc gratuit, acesta trebuie să scaneze secvențial FAT. Pentru MS-DOS, aceasta nu a fost o penalizare uriașă, deoarece discurile și fișierele erau mici, iar FAT avea puține intrări și lanțuri de fișiere relativ scurte. În sistemul de fișiere FAT12 (utilizat pe dischete și hard diskuri timpurii), nu existau mai mult de 4.080 de intrări, iar FAT ar fi de obicei rezident în memorie. Pe măsură ce discurile au devenit mai mari, arhitectura FAT a început să se confrunte cu penalități. Pe un disc mare care utilizează FAT, poate fi necesar să efectuați citiri pe disc pentru a afla locația pe disc a unui bloc de fișiere care trebuie citit sau scris. ${\ displaystyle i}$

TOPS-20 (și eventual TENEX ) a folosit un arbore de nivel 0 până la 2, care are similitudini cu un arbore B. Un bloc de disc avea 512 cuvinte pe 36 de biți. Dacă fișierul se încadrează într-un bloc de cuvinte 512 (2 ⁹ ), atunci directorul de fișiere ar indica acel bloc fizic de disc. Dacă fișierul se încadrează în 2 ¹⁸ cuvinte, atunci directorul ar indica un index auxiliar; cele 512 de cuvinte ale acelui index ar fi fie NULL (blocul nu este alocat) sau ar indica adresa fizică a blocului. Dacă fișierul se încadrează în 2 ^{27 de} cuvinte, atunci directorul ar indica un bloc care deține un index aux-aux; fiecare intrare ar fi NUL sau ar indica un index auxiliar. În consecință, blocul de disc fizic pentru un fișier de 2 ^{27 de} cuvinte ar putea fi localizat în două lecturi de disc și citite pe al treilea.

Sistemul de fișiere Apple HFS + , NTFS- ul Microsoft , AIX (jfs2) și unele sisteme de fișiere Linux , precum btrfs și Ext4 , folosesc arborii B.

Arborii B ^* sunt utilizați în sistemele de fișiere HFS și Reiser4 .

DragonFly BSD e CIOCAN sistem de fișiere utilizează un B modificat + -tree.

Performanţă

Un copac B crește mai lent cu creșterea cantității de date, decât liniaritatea unei liste conectate. În comparație cu o listă de sărituri , ambele structuri au aceeași performanță, dar arborele B se potrivește mai bine pentru creșterea n . Un arbore T , pentru sistemele principale de baze de date de memorie , este similar, dar mai compact.

Variații

Acces simultan

Lehman și Yao au arătat că toate blocările de citire ar putea fi evitate (și, prin urmare, accesul simultan s-a îmbunătățit mult) prin legarea blocurilor de copaci de la fiecare nivel împreună cu un „următor” indicator. Acest lucru are ca rezultat o structură de copac în care atât operațiile de inserare, cât și operațiile de căutare coboară de la rădăcină la frunză. Blocările de scriere sunt necesare numai pe măsură ce un bloc de copac este modificat. Acest lucru maximizează concurența accesului de către mai mulți utilizatori, un aspect important pentru bazele de date și / sau alte metode de stocare ISAM bazate pe arborele B. Costul asociat cu această îmbunătățire este că paginile goale nu pot fi eliminate din btree în timpul operațiunilor normale. (Cu toate acestea, consultați diverse strategii de implementare a îmbinării nodurilor și codul sursă la.)

Brevetul SUA 5283894, acordat în 1994, pare să arate o modalitate de a utiliza o „Metodă de acces meta” pentru a permite accesul simultan al arborelui B + și modificarea fără blocări. Tehnica accesează arborele „în sus” atât pentru căutări, cât și pentru actualizări prin intermediul indexurilor suplimentare în memorie care indică blocurile din fiecare nivel din memoria cache a blocurilor. Nu este necesară reorganizarea pentru ștergeri și nu există indicatori „următori” în fiecare bloc ca în Lehman și Yao.

Algoritmi paraleli

Deoarece arborii B au o structură similară cu arborii roșu-negri , algoritmi paraleli pentru copacii roșu-negri pot fi aplicați și copacilor B.

Vezi si

• Copac B +
• R-copac
• Copac roșu-negru
• 2-3 arbore
• 2–3–4 copac

Note

Referințe

General

• Bayer, R .; McCreight, E. (1972), „Organizarea și întreținerea indexurilor mari comandate” (PDF) , Acta Informatica , 1 (3): 173–189, doi : 10.1007 / bf00288683 , S2CID  29859053
• Comer, Douglas (iunie 1979), „The Ubiquitous B-Tree”, Computing Surveys , 11 (2): 123–137, doi : 10.1145 / 356770.356776 , ISSN  0360-0300 , S2CID  101673.
• Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2001), Introducere în algoritmi (ediția a doua), MIT Press și McGraw-Hill, pp. 434-454, ISBN 0-262-03293-7. Capitolul 18: Copacii B.
• Folk, Michael J .; Zoellick, Bill (1992), Structuri de fișiere (ediția a doua), Addison-Wesley, ISBN 0-201-55713-4
• Knuth, Donald (1998), Sorting and Searching , The Art of Computer Programming , Volumul 3 (Ediția a doua), Addison-Wesley, ISBN 0-201-89685-0 |volume=are text suplimentar ( ajutor ). Secțiunea 6.2.4: Arborii cu mai multe căi, pp. 481–491. De asemenea, pp. 476–477 din secțiunea 6.2.3 (Arbori echilibrați) discută despre 2-3 arbori.

Hârtii originale

• Bayer, Rudolf ; McCreight, E. (iulie 1970), Organizarea și întreținerea indicilor mari ordonați , raportul științelor matematice și informaționale nr. 20, Laboratoarele de cercetare științifică Boeing.
• Bayer, Rudolf (1971), Arborii B binari pentru memoria virtuală , Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California.

linkuri externe

• Conferința B-tree de David Scot Taylor, SJSU
• Vizualizare B-Tree (faceți clic pe „init”)
• Vizualizare animată B-Tree
• Arborele B și arborele UB pe Scholarpedia Curator: Dr. Rudolf Bayer
• B-Trees: Structuri de date echilibrate ale copacilor
• Dicționarul de algoritmi și structuri de date NIST: arborele B
• Tutorial B-Tree
• Implementarea InfinityDB BTree
• Cache Oblivious B (+) - copaci
• Dicționar de algoritmi și structuri de date intrare pentru arborele B *
• Structuri de date deschise - Secțiunea 14.2 - Arborii B , Pat Morin
• B-Arbori numărați
• B-Tree .Net, o implementare modernă, virtualizată RAM și disc

Încărcare în vrac

• Shetty, Soumya B. (2010). O implementare configurabilă de către utilizator a arborilor B (teză). Universitatea de Stat din Iowa.
• Kaldırım, Semih (28 aprilie 2015). „Organizarea fișierelor, ISAM, arborele B + și încărcare în bloc” (PDF) . Ankara, Turcia: Universitatea Bilkent . pp. 4-6.
• „ECS 165B: Implementarea sistemului de baze de date: Lectura 6” (PDF) . Universitatea din California, Davis . 9 aprilie 2010. p. 23.
• „BULK INSERT (Transact-SQL) în SQL Server 2017” . Documente Microsoft. 6 septembrie 2018.