Arborele B în structura de date: Căutare, Inserare, Ștergere

Ce este un arbore B?

B Arborele este o structură de date autoechilibrată bazată pe un set specific de reguli pentru căutarea, inserarea și ștergerea datelor într-un mod mai rapid și eficient din punct de vedere al memoriei. Pentru a realiza acest lucru, se respectă următoarele reguli pentru a crea un arbore B.

Un arbore B este un tip special de arbore într-o structură de date. În 1972, această metodă a fost introdusă pentru prima dată de McCreight și Bayer, care au numit-o arbore de căutare pe căi multiple echilibrate în înălțime. Acesta vă ajută să păstrați datele sortate și permite diverse operațiuni precum inserarea, căutarea și ștergerea într-un timp mai scurt.

Reguli pentru B-Tree

Iată câteva reguli importante pentru crearea unui arbore B:

• Toate frunzele vor fi create la același nivel.
• Un arbore B este determinat de un număr de grade, numit ș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 chei pe care un nod rădăcină, precum și nodurile sale copil, le poate conține se calculează cu această formulă: m − 1. De exemplu:

  m = 4
  max keys: 4 − 1 = 3

• Fiecare nod, cu excepția nodului rădăcină, trebuie să conțină un număr minim de chei de [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 pentru utilizarea unui B-Tree:

• Reduce numărul de citiri efectuate pe disc.
• Arborii B pot fi ușor optimizați 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 mari de date.
• Este un algoritm util pentru baze de date și sisteme de fișiere.
• O alegere bună de făcut 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 introduse în memoria principală (sau RAM), se numesc structură de date.
• În cazul unor date voluminoase, căutarea unei singure înregistrări pe disc necesită citirea întregului disc; acest lucru crește timpul și consumul de memorie principală din cauza frecvenței mari de acces la disc și a dimensiunii datelor.
• Pentru a depăși acest lucru, se creează tabele de index care salvează referința înregistrărilor pe baza blocurilor în care se află. Acest lucru reduce drastic consumul de timp și memorie.
• Deoarece avem date uriașe, putem crea tabele de indexare pe mai multe niveluri.
• Un index multi-nivel poate fi proiectat folosind un arbore B pentru keeping datele sortate într-un mod autoechilibrat.

Căutare OperaTION

Operația de căutare este cea mai simplă operație pe un arbore B. Se aplică următorul algoritm:

• Fie cheia (valoarea) care urmează a fi căutată „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, se caută în subarborele din stânga; dacă k este mai mare decât valoarea rădăcinii, se caută în 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

Întrucât un arbore B este un arbore autoechilibrat, nu poț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.

În exemplul de mai sus:

• Căutați poziția corespunzătoare în nod pentru cheie.
• Introduceți cheia în nodul țintă și verificați dacă există reguli.
• După inserare, nodul are mai mult sau egal cu numărul minim de chei, care este 1? În acest caz, da, are. Verificați următoarea regulă.
• După inserare, nodul are mai mult decât numărul maxim de chei, care este 3? În acest caz, nu, nu are. 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 diviza, iar cheia din mijloc va deveni nodul rădăcină al restului celor două noduri.
• În cazul unui număr par de chei, nodul din mijloc va fi selectat prin polarizare stânga sau dreapta.

În exemplul de mai sus:

• Nodul are mai puține chei decât numărul maxim.
• 1 este introdus lângă 3, dar regula ordinii crescătoare este încălcată.
• Pentru a remedia acest lucru, cheile sunt sortate.

În mod similar, 13 și 2 pot fi inserate cu ușurință în nod, deoarece îndeplinesc regula „chei mai mici decât numărul maxim” pentru noduri.

În exemplul de mai sus:

• Nodul are chei egale cu cheile maxime.
• Cheia este introdusă în nodul țintă, dar încalcă regula numărului maxim de chei.
• 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ț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.
• Se aplică trei condiții în funcție de locația cheii țintă, așa cum se explică în secțiunile următoare.

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

• Target se află în nodul frunză, mai mult de chei minime. Ștergerea acestei opțiuni nu va încălca proprietatea arborelui B.
• Target se află în nodul frunză și are noduri cheie minime. Ștergerea acesteia va încălca proprietatea arborelui B.
• Nodul țintă poate împrumuta o cheie de la nodul imediat stâng sau de la nodul imediat drept (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ă către părinte, valoarea maximă a nodului părinte va fi transferată către nodul țintă, iar valoarea țintă este eliminată.
• Target se află în nodul frunză, dar niciun frate nu are mai mult decât numărul minim de chei: căutați cheia, fuzionați cu frații și minimul de noduri părinte, totalul cheilor va fi acum mai mare decât minimul, iar cheia țintă va fi înlocuită cu minimul unui nod părinte.

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

• Alegeți fie un predecesor în ordine, fie un succesor în ordine.
• În cazul unui predecesor în ordine, va fi selectată cheia maximă din subarborele său din stânga.
• În cazul unui succesor în ordine, va fi selectată cheia minimă din subarborele său din dreapta.
• Dacă predecesorul în ordine al cheii țintă are mai multe chei decât numărul minim de chei, numai atunci poate înlocui cheia țintă cu numărul maxim de chei a predecesorului în ordine.
• Dacă predecesorul cheii țintă în ordine 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 subarboreleui predecesor în ordine.
• Dacă, după ștergere, ținta are mai puțin de cheile 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 preluată de țintă, dar cu nodurile cu valoarea maximă a fratelui.

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

Diagrama de mai sus prezintă diferite cazuri ale operației de ștergere într-un arbore B. Acest arbore B 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. În timp ce numărul minim și maxim de chei pe care le poate avea orice nod sunt 2 și respectiv 4.

În exemplul de mai sus:

• Nodul țintă are cheia țintă de șters.
• Nodul țintă are mai multe chei decât numărul minim de chei.
• Pur și simplu ștergeți cheia.

În exemplul de mai sus:

• Nodul țintă are chei egale cu cheile minime, deci nu îl putem ș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 (fratele stâng), deoarece nu are niciun succesor în ordine (fratele drept).
• Valoarea maximă a predecesorului în ordine 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 din succesorul său în ordine.

• Nodul țintă va împrumuta o cheie de la un frate imediat, în acest caz, succesorul în ordine (fratele din dreapta), deoarece predecesorul său în ordine (fratele din stânga) are chei egale cu numărul minim de chei.
• 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 sa nodului țintă. Prin urmare, este necesară fuzionarea. Vedeți procedura de ștergere a unei astfel de chei:

• Fuzionați nodul țintă cu oricare dintre frații săi imediati, împreună cu cheia părinte.
• Cheia din nodul părinte este selectată, acesta fiind situat între cele două noduri care se îmbină.
• Ștergeți cheia țintă din nodul îmbinat.

Șterge Operațiune Pseudo Code

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
    }
}

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

Întrebări frecvente