B TREE în structura datelor: Căutare, inserare, ștergere Exemplu de operație

Cuprins:

Anonim

Ce este un copac B?

Arborele B este o structură de date de auto-echilibrare bazată pe un set specific de reguli pentru căutarea, inserarea și ștergerea datelor într-un mod mai rapid și eficient în memorie. Pentru a realiza acest lucru, sunt urmate următoarele reguli pentru a crea un arbore B.

Un copac B este un tip special de copac într-o structură de date. În 1972, această metodă a fost introdusă pentru prima dată de McCreight, iar Bayer a denumit-o Height Balanced m-way Search Tree. Vă ajută să păstrați datele sortate și să permiteți diverse operațiuni precum inserarea, căutarea și ștergerea în mai puțin timp.

În acest tutorial B-Tree, veți învăța:

  • Ce este un copac B?
  • De ce să folosiți B-Tree
  • Istoria Arborelui B.
  • Operațiunea de căutare
  • Operațiunea de inserare
  • Ștergeți operațiunea

Reguli pentru B-Tree

Aici sunt reguli importante pentru crearea B_Tree

  • Toate frunzele vor fi create la același nivel.
  • Arborele B este determinat de un număr de grade, care este, de asemenea, numit „ordine” (specificat de un actor extern, precum un programator), denumit 
    m
    încolo. Valoarea a 
    m
    depinde de dimensiunea blocului de pe discul pe care se află în principal datele.
  • Subarborele stâng al nodului va avea valori mai mici decât partea dreaptă a subarborelui. Aceasta înseamnă că și nodurile sunt 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 copil pot fi conținute sunt calculate prin această formulă: 
    m - 1
    De exemplu: 
    m = 4max keys: 4 - 1 = 3

  • Fiecare nod, cu excepția rădăcinii, trebuie să conțină chei minime de 
    [m/2]-1
    De exemplu: 
    m = 4min keys: 4/2-1 = 1
  • Numărul maxim de noduri copil pe care le poate avea un nod este egal cu gradul său, care este 
    m
  • Numărul minim de copii pe care îl poate avea un nod este jumătate din ordin, care este m / 2 (se ia valoarea plafonului).
  • Toate tastele dintr-un nod sunt sortate în ordine crescătoare.

De ce să folosiți B-Tree

Iată, sunt motive pentru utilizarea B-Tree

  • Reduce numărul de citiri efectuate pe disc
  • Copacii B pot fi optimizați cu ușurință pentru a-și ajusta dimensiunea (adică numărul de noduri copil) în funcție de dimensiunea discului
  • Este o tehnică special concepută pentru manipularea unei cantități voluminoase de date.
  • Este un algoritm util pentru baze de date și sisteme de fișiere.
  • O alegere bună pentru a opta atunci 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 unor date imense, căutarea unei înregistrări pe disc necesită citirea întregului disc; acest lucru mărește consumul de timp și de memorie principală datorită frecvenței ridicate a accesului la disc și a dimensiunii datelor.
  • Pentru a depăși acest lucru, sunt create tabele index care salvează referința înregistrărilor înregistrărilor pe baza blocurilor în care se află. Acest lucru reduce drastic timpul și consumul de memorie.
  • Deoarece avem date imense, putem crea tabele de indexuri pe mai multe niveluri.
  • Indexul pe mai multe niveluri poate fi proiectat folosind B Tree pentru păstrarea datelor sortate într-un mod de auto-echilibrare.

Operațiunea de căutare

Operațiunea 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ă cu „k”.
  • Începeți să căutați din rădăcină și parcurgeți recursiv în jos.
  • Dacă k este mai mic decât valoarea rădăcină, căutați subarborele din stânga, dacă k este mai mare decât valoarea rădăcină, căutați subarborele din dreapta.
  • Dacă nodul are k găsit, pur și simplu întoarceți nodul.
  • Dacă k nu se găsește în nod, treceți în jos către copil cu o cheie mai mare.
  • Dacă k nu este găsit în copac, returnăm NULL.

Operațiunea de inserare

Deoarece arborele B este un arbore auto-echilibrat, nu puteți forța introducerea unei chei în orice nod.

Se aplică următorul algoritm:

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

BACSIS

Următorul nu este adevărat despre algoritmul de inserare:

Deoarece nodul este plin, prin urmare se va împărți, apoi va fi inserată o nouă valoare

În exemplul de mai sus:

  • Căutați cheia în poziția corespunzătoare din nod
  • Introduceți cheia în nodul țintă și verificați dacă există reguli
  • După inserare, are nodul mai mult decât egal cu un număr minim de taste, care este 1? În acest caz, da, da. Verificați următoarea regulă.
  • După inserare, are nodul mai mult de un număr maxim de taste, 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 taste
  • Nodul se va împărți, iar cheia din mijloc va deveni nodul rădăcină al celor două noduri restante.
  • În cazul numărului par de taste, nodul din mijloc va fi selectat prin părtinire stângă sau părtinire dreaptă.

În exemplul de mai sus:

  • Nodul are mai puține chei max
  • 1 este inserat lângă 3, dar regula de ordine crescătoare este încălcată
  • Pentru a remedia problema, cheile sunt sortate

În mod similar, 13 și 2 pot fi inserate cu ușurință în nod, deoarece îndeplinesc regula mai mică decât tastele maxime pentru noduri.

În exemplul de mai sus:

  • Nodul are taste egale cu max.
  • Cheia este inserată în nodul țintă, dar încalcă regula cheilor max.
  • Nodul țintă este împărțit, iar tasta de mijloc prin părtinire stângă este acum părintele noilor noduri copil.
  • 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ți operațiunea

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

Se aplică următorul algoritm:

  • Rulați operațiunea de căutare și găsiți cheia țintă în noduri
  • Trei condiții aplicate pe baza locației cheii țintă, așa cum se explică în secțiunile următoare

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

  • Ținta se află în nodul frunzei, mai mult decât tastele min.
    • Ștergerea acestui lucru nu va încălca proprietatea lui B Tree
  • Ținta este în nodul frunzei, are noduri cheie min
    • Ștergerea acestui lucru va încălca proprietatea lui B Tree
    • Nodul țintă poate împrumuta cheia de la nodul stâng imediat sau nodul drept imediat (frate)
    • Fratele va spune da dacă are mai mult de un număr minim de taste
    • 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 va elimina valoarea țintă
  • Ținta se află în nodul frunzei, dar niciun frate nu are mai mult de un număr minim de taste
    • Căutați cheia
    • Îmbinați-vă cu frații și cu minimul 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

  • Fie alegeți, în ordinea predecesorului sau în ordinea succesorului
  • În cazul predecesorului în ordine, va fi selectată cheia maximă din subarborele din stânga
  • În cazul succesorului în ordine, va fi selectată cheia minimă din subarborele din dreapta
  • Dacă predecesorul în ordine a cheii țintă are mai mult decât tastele min, numai atunci poate înlocui cheia țintă cu maximul predecesorului în ordine.
  • Dacă predecesorul în ordine a cheii țintă nu are mai mult de chei min, căutați cheia minimă a succesorului în ordine.
  • Dacă predecesorul și succesorul cheii țintă au ambele mai puține chei min, atunci combinați predecesorul și succesorul.

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

  • Înlocuiți cu elementul maxim al subarborelui predecesor în ordine
  • Dacă, după ștergere, ținta are mai puține chei min, atunci nodul țintă va împrumuta valoarea maximă de la fratele său prin părintele fratelui său.
  • 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 copil pe care le poate avea orice nod este 3, iar numărul maxim de noduri copil pe care le poate avea orice nod este 5. Întrucât numărul minim și maxim de taste 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 chei minime
  • Pur și simplu ștergeți cheia

În exemplul de mai sus:

  • Nodul țintă are chei egale cu cheile minime, deci nu îl puteți ș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, predecesorul în ordine (frate stâng), deoarece nu are un succesor în ordine (frate dreapta)
  • Valoarea maximă a predecesorului inorder va fi transferată către părinte, iar părintele va transfera valoarea maximă către nodul țintă (vezi diagrama de mai jos)

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

  • Nodul țintă va împrumuta o cheie de la un frate imediat, în acest caz, succesorul în ordine (frate dreapta), deoarece predecesorul în ordine (frate stâng) 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ă poată da cheia nodului țintă. Prin urmare, fuziunea este necesară.

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

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

Ștergeți operațiunea Pseudo Code

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

Ieșire :

Cel mai mare element este șters din Arborele B.

Rezumat:

  • Arborele B este o structură de date auto-echilibrată pentru o mai bună căutare, inserare și ștergere a datelor de pe disc.
  • Arborele B este reglementat de gradul specificat
  • B Tastele și nodurile arborelui sunt aranjate în ordine crescătoare.
  • Operația de căutare a Arborelui B 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țiunea de inserare a Arborelui B este destul de detaliată, ceea ce găsește mai întâi o poziție adecvată de inserare pentru cheia țintă, o introduce, evaluează validitatea Arborelui B în raport cu diferite cazuri și apoi restructurează nodurile Arborelui B în consecință.
  • Operațiunea de ștergere a Arborelui B caută mai întâi cheia țintă care trebuie ștearsă, o șterge, evaluează validitatea pe baza mai multor cazuri, cum ar fi cheile minime și maxime ale nodului țintă, fraților și părintelui.