B TREE în Structura datelor: Căutare, Inserare, Ștergere OperaExemplu

Reguli pentru B-Tree

Iată reguli importante pentru crearea B_Tree

• Toate frunzele vor fi create la același nivel.
• B-Tree este determinat de un număr de grade, care se mai numește și „ordine” (specificat de un actor extern, cum ar fi un programator), denumit

  m

  mai departe. Valoarea a

  m

  depinde de dimensiunea blocului de pe disc pe care se află în principal datele.

• Subarborele din stânga al nodului va avea valori mai mici decât partea dreaptă a subarborelui. Aceasta înseamnă că nodurile sunt, de asemenea, sortate în ordine crescătoare de la stânga la dreapta.
• Numărul maxim de noduri copil, un nod rădăcină, precum și nodurile sale secundare pe care le pot conține sunt calculate prin această formulă:

  m – 1

  De exemplu:

  m = 4
  max keys: 4 – 1 = 3
  

• Fiecare nod, cu excepția root, trebuie să conțină cheile minime ale

  [m/2]-1

  De exemplu:

  m = 4
  min keys: 4/2-1 = 1
  

• Numărul maxim de noduri copil pe care un nod le poate avea este egal cu gradul său, adică

  m

• Copiii minimi pe care un nod îi poate avea este jumătate din ordin, care este m/2 (se ia valoarea plafonului).
• Toate cheile dintr-un nod sunt sortate în ordine crescătoare.

De ce să folosiți B-Tree

Iată motivele utilizării B-Tree

• Reduce numărul de citiri efectuate pe disc
• B Arborele pot fi ușor optimizați pentru a-și ajusta dimensiunea (adică numărul de noduri copii) în funcție de dimensiunea discului
• Este o tehnică special concepută pentru manipularea unei cantități mari de date.
• Este un algoritm util pentru baze de date și sisteme de fișiere.
• O alegere bună pentru a opta când vine vorba de citirea și scrierea unor blocuri mari de date

Istoria arborelui B

• Datele sunt stocate pe disc în blocuri, aceste date, atunci când sunt aduse în memoria principală (sau RAM) se numesc structură de date.
• În cazul datelor uriașe, căutarea unei înregistrări pe disc necesită citirea întregului disc; aceasta crește timpul și consumul de memorie principală datorită frecvenței mari de acces la disc și dimensiunii datelor.
• Pentru a depăși acest lucru, sunt create tabele de index care salvează referința de înregistrare a înregistrărilor pe baza blocurilor în care se află. Acest lucru reduce drastic timpul și consumul de memorie.
• Deoarece avem date uriașe, putem crea tabele de indexare pe mai multe niveluri.
• Indexul pe mai multe niveluri poate fi proiectat folosind B Tree pentru a păstra datele sortate într-un mod de auto-echilibrare.

Caută OperaTION

Operația de căutare este cea mai simplă operație de pe B Tree.

Se aplică următorul algoritm:

• Lăsați cheia (valoarea) să fie căutată prin „k”.
• Începeți să căutați de la rădăcină și parcurgeți recursiv în jos.
• Dacă k este mai mică decât valoarea rădăcinii, căutați subarborele din stânga, dacă k este mai mare decât valoarea rădăcinii, căutați subarborele din dreapta.
• Dacă nodul are k găsit, pur și simplu returnați nodul.
• Dacă k nu este găsit în nod, parcurgeți în jos până la copil cu o cheie mai mare.
• Dacă k nu se găsește în arbore, returnăm NULL.

Insera OperaTION

Deoarece B Tree este un arbore cu auto-echilibrare, nu puteți forța inserarea unei chei în orice nod.

Se aplică următorul algoritm:

• Rulați operația de căutare și găsiți locul potrivit de inserare.
• Introduceți noua cheie în locația potrivită, dar dacă nodul are deja un număr maxim de chei:
• Nodul, împreună cu o cheie nou introdusă, se va despărți de elementul din mijloc.
• Elementul din mijloc va deveni părintele pentru celelalte două noduri copil.
• Nodurile trebuie să rearanjeze cheile în ordine crescătoare.

TIP	Următoarele nu sunt adevărate despre algoritmul de inserare: Deoarece nodul este plin, se va împărți și apoi va fi inserată o nouă valoare

În exemplul de mai sus:

• Căutați cheia în poziția corespunzătoare în nod
• Introduceți cheia în nodul țintă și verificați dacă există reguli
• După inserare, nodul are mai mult decât egal cu un număr minim de chei, care este 1? În acest caz, da, așa este. Verificați următoarea regulă.
• După inserare, nodul are mai mult de un număr maxim de chei, care este 3? În acest caz, nu, nu. Aceasta înseamnă că arborele B nu încalcă nicio regulă, iar inserarea este completă.

În exemplul de mai sus:

• Nodul a atins numărul maxim de chei
• Nodul se va împărți, iar cheia din mijloc va deveni nodul rădăcină al celorlalte două noduri.
• În cazul unui număr par de taste, nodul din mijloc va fi selectat prin polarizare la stânga sau la dreapta.

În exemplul de mai sus:

• Nodul are mai puțin de chei maxime
• 1 este introdus lângă 3, dar se încalcă regula de ordine crescătoare
• Pentru a remedia acest lucru, cheile sunt sortate

În mod similar, 13 și 2 pot fi inserate cu ușurință în nod, deoarece îndeplinesc mai puțin decât regula maximă de chei pentru noduri.

În exemplul de mai sus:

• Nodul are chei egale cu cheile maxime.
• Cheia este introdusă în nodul țintă, dar încalcă regula cheilor maxime.
• Nodul țintă este împărțit, iar cheia din mijloc prin polarizarea stângă este acum părintele noilor noduri secundare.
• Noile noduri sunt aranjate în ordine crescătoare.

În mod similar, pe baza regulilor și cazurilor de mai sus, restul valorilor pot fi inserate cu ușurință în arborele B.

Șterge OperaTION

Operația de ștergere are mai multe reguli decât operațiunile de inserare și căutare.

Se aplică următorul algoritm:

• Rulați operația de căutare și găsiți cheia țintă în noduri
• Trei condiții aplicate în funcție de locația cheii țintă, așa cum este explicat în secțiunile următoare

Dacă cheia țintă se află în nodul frunză

• Target este în nodul frunză, mai mult decât tastele min.
• Ștergerea acesteia nu va încălca proprietatea B Tree
• Target este în nodul frunză, are noduri cheie min
• Ștergerea acestui lucru va încălca proprietatea B Tree
• Target nodul poate împrumuta cheia de la nodul imediat din stânga sau din nodul imediat din dreapta (frate)
• va spune fratele da dacă are mai mult decât numărul minim de chei
• Cheia va fi împrumutată de la nodul părinte, valoarea maximă va fi transferată unui părinte, valoarea maximă a nodului părinte va fi transferată la nodul țintă și eliminați valoarea țintă
• Target se află în nodul frunză, dar niciun frați nu are mai mult de un număr minim de chei
• Căutați cheia
• Îmbinați cu frații și cu minimumul de noduri părinte
• Cheile totale vor fi acum mai mult de min
• Cheia țintă va fi înlocuită cu minimul unui nod părinte

Dacă cheia țintă se află într-un nod intern

• Alegeți fie predecesor în ordine, fie succesor în ordine
• În cazul predecesorului în ordine, cheia maximă din subarborele din stânga va fi selectată
• În cazul succesorului în ordine, cheia minimă din subarborele din dreapta va fi selectată
• Dacă predecesorul în ordine al cheii țintă are mai mult decât tastele minime, numai atunci poate înlocui cheia țintă cu maximul predecesorului în ordine
• Dacă predecesorul în ordine al cheii țintă nu are mai mult de chei minime, căutați cheia minimă a succesorului în ordine.
• Dacă predecesorul și succesorul în ordine ale cheii țintă au ambele mai puține chei minime, atunci îmbinați predecesorul și succesorul.

Dacă cheia țintă se află într-un nod rădăcină

• Înlocuiți cu elementul maxim al subarborelului predecesor în ordine
• Dacă, după ștergere, ținta are mai puțin de chei minime, atunci nodul țintă va împrumuta valoarea maximă de la fratele său prin intermediul părintelui fratelui.
• Valoarea maximă a părintelui va fi luată de o țintă, dar cu nodurile valorii maxime a fratelui.

Acum, să înțelegem operația de ștergere cu un exemplu.

Diagrama de mai sus afișează diferite cazuri de operație de ștergere într-un B-Tree. Acest B-Tree este de ordinul 5, ceea ce înseamnă că numărul minim de noduri copii pe care le poate avea orice nod este 3, iar numărul maxim de noduri copii pe care le poate avea orice nod este 5. În timp ce numărul minim și maxim de chei pentru orice nod pot avea sunt 2 și, respectiv, 4.

În exemplul de mai sus:

• Nodul țintă are cheia țintă de șters
• Nodul țintă are chei mai mult decât cheile minime
• Pur și simplu ștergeți cheia

În exemplul de mai sus:

• Nodul țintă are chei egale cu cheile minime, așa că nu îl poate șterge direct, deoarece va încălca condițiile

Acum, următoarea diagramă explică cum să ștergeți această cheie:

• Nodul țintă va împrumuta o cheie de la un frate imediat, în acest caz, un predecesor în ordine (frate din stânga), deoarece nu are niciun succesor în ordine (frate din dreapta)
• Valoarea maximă a predecesorului în ordine va fi transferată părintelui, iar părintele va transfera valoarea maximă la nodul țintă (vezi diagrama de mai jos)

Următorul exemplu ilustrează cum să ștergeți o cheie care are nevoie de o valoare din succesorul său în ordine.

• Nodul țintă va împrumuta o cheie de la fratele imediat, în acest caz, succesorul în ordine (fratele din dreapta) deoarece predecesorul în ordine (fratele din stânga) are chei egale cu cheile minime.
• Valoarea minimă a succesorului în ordine va fi transferată părintelui, iar părintele va transfera valoarea maximă către nodul țintă.

În exemplul de mai jos, nodul țintă nu are niciun frate care să-și poată da cheia nodului țintă. Prin urmare, este necesară fuziunea.

Consultați procedura de ștergere a unei astfel de chei:

• Îmbinați nodul țintă cu oricare dintre frații săi imediati împreună cu cheia părinte
• Cheia de la nodul părinte este selectată pentru frații între cele două noduri care fuzionează
• Ștergeți cheia țintă din nodul îmbinat

Șterge OperaPseudo cod

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

producție:

Cel mai mare element este șters din B-Tree.

Rezumat

• B Tree este o structură de date cu auto-echilibrare pentru o mai bună căutare, inserare și ștergere a datelor de pe disc.
• Arborele B este reglementat de gradul specificat
• B Cheile arborelui și nodurile sunt aranjate în ordine crescătoare.
• Operația de căutare a B Tree este cea mai simplă, care începe întotdeauna de la rădăcină și începe să verifice dacă cheia țintă este mai mare sau mai mică decât valoarea nodului.
• Operația de inserare a arborelui B este destul de detaliată, care găsește mai întâi o poziție adecvată de inserare pentru cheia țintă, o inserează, evaluează validitatea arborelui B față de diferite cazuri și apoi restructurează nodurile arborelui B în consecință.
• Operația de ștergere a arborelui B caută mai întâi cheia țintă care urmează să fie ștearsă, o șterge, evaluează validitatea pe baza mai multor cazuri, cum ar fi cheile minime și maxime ale nodului țintă, fraților și părinte.