B+ TREE: Căutați, Inserați și ștergeți OperaExemplu

Ce este un arbore B+?

A B+ Arborele este utilizat în principal pentru implementarea indexării dinamice pe mai multe niveluri. În comparație cu B- Tree, B+ Tree stochează indicatorii de date numai la nodurile frunze ale Arborelui, ceea ce face ca procesul de căutare să fie mai precis și mai rapid.

Reguli pentru B+ Tree

Iată regulile esențiale pentru B+ Tree.

• Frunzele sunt folosite pentru stocarea înregistrărilor de date.
• Este stocat în nodurile interne ale Arborelui.
• Dacă valoarea cheii țintă este mai mică decât nodul intern, atunci punctul din partea stângă este urmat.
• Dacă o valoare cheie țintă este mai mare sau egală cu nodul intern, atunci punctul din partea dreaptă este urmat.
• Rădăcina are minim doi copii.

De ce să folosiți B+ Tree

Iată motivele pentru care utilizați B+ Tree:

• Cheile sunt utilizate în principal pentru a ajuta căutarea prin direcționarea către Frunza potrivită.
• B+ Tree folosește un „factor de umplere” pentru a gestiona creșterea și scăderea unui copac.
• În arborii B+, numeroase chei pot fi plasate cu ușurință pe pagina de memorie deoarece nu au datele asociate nodurilor interioare. Prin urmare, va accesa rapid datele arborelui care se află pe nodul frunză.
• O scanare completă completă a tuturor elementelor este un arbore care are nevoie de o singură trecere liniară, deoarece toate nodurile frunze ale unui arbore B+ sunt legate între ele.

Arborele B+ vs. Arborele B

Iată principalele diferențe dintre B+ Tree și B Tree

B+ Arborele	B Arborele
Tastele de căutare pot fi repetate.	Cheile de căutare nu pot fi redundante.
Datele sunt salvate doar pe nodurile frunzelor.	Atât nodurile frunză, cât și nodurile interne pot stoca date
Datele stocate pe nodul frunză fac căutarea mai precisă și mai rapidă.	Căutarea este lentă din cauza datelor stocate pe Leaf și nodurile interne.
Ștergerea nu este dificilă, deoarece un element este eliminat doar dintr-un nod frunză.	Ștergerea elementelor este un proces complicat și care necesită timp.
Nodurile de frunze legate fac căutarea eficientă și rapidă.	Nu puteți lega nodurile frunzelor.

Caută OperaTION

În B+ Tree, o căutare este una dintre cele mai ușoare proceduri de executat și de a obține rezultate rapide și precise din ea.

Se aplică următorul algoritm de căutare:

• Pentru a găsi înregistrarea necesară, trebuie să executați căutare binară pe înregistrările disponibile în Arbore.
• În cazul unei potriviri exacte cu cheia de căutare, înregistrarea corespunzătoare este returnată utilizatorului.
• În cazul în care cheia exactă nu este localizată de căutarea în nodul părinte, curent sau frunză, atunci utilizatorului i se afișează un „mesaj negăsit”.
• Procesul de căutare poate fi reluat pentru rezultate mai bune și mai precise.

Caută OperaAlgoritmul de țiune

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

producție:

Înregistrarea potrivită stabilită cu cheia exactă este afișată utilizatorului; în caz contrar, o încercare eșuată este afișată utilizatorului.

Insera OperaTION

Următorul algoritm este aplicabil pentru operația de inserare:

• 50 la sută din elementele din noduri sunt mutate într-o nouă frunză pentru depozitare.
• Părintele noii frunze este legat cu exactitate cu valoarea minimă a cheii și cu o nouă locație în arbore.
• Împărțiți nodul părinte în mai multe locații în cazul în care este utilizat pe deplin.
• Acum, pentru rezultate mai bune, cheia centrală este asociată cu nodul de nivel superior al acelei frunze.
• Până când nodul de nivel superior nu este găsit, continuați să repetați procesul explicat în pașii de mai sus.

Insera OperaAlgoritmul de țiune

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

producție:

Algoritmul va determina elementul și îl va introduce cu succes în nodul frunză necesar.

Exemplul de exemplu de arbore B+ de mai sus este explicat în pașii de mai jos:

• În primul rând, avem 3 noduri, iar primele 3 elemente, care sunt 1, 4 și 6, sunt adăugate în locații adecvate din noduri.
• Următoarea valoare din seria de date este 12 care trebuie făcută parte din Arborele.
• Pentru a realiza acest lucru, împărțiți nodul, adăugați 6 ca element indicator.
• Acum, se creează o ierarhie din dreapta a unui arbore, iar valorile datelor rămase sunt ajustate în consecință, ținând cont de regulile aplicabile de valori egale sau mai mari decât nodurile cheie-valoare din dreapta.

Șterge OperaTION

Complexitatea procedurii de ștergere din arborele B+ o depășește pe cea a funcționalității de inserare și căutare.

Următorul algoritm este aplicabil la ștergerea unui element din arborele B+:

• În primul rând, trebuie să găsim o intrare de frunză în Arborele care ține tasta și indicatorul. , ștergeți intrarea frunzei din Arbore dacă Frunza îndeplinește condițiile exacte de ștergere a înregistrării.
• În cazul în care nodul frunzelor îndeplinește doar factorul satisfăcător de a fi plin pe jumătate, atunci operația este finalizată; în caz contrar, nodul Leaf are intrări minime și nu poate fi șters.
• Celelalte noduri conectate din dreapta și din stânga pot elibera orice intrări, apoi le pot muta în Frunză. Dacă aceste criterii nu sunt îndeplinite, atunci ele ar trebui să combine nodul frunză și nodul său legat în ierarhia arborescentă.
• La îmbinarea nodului frunză cu vecinii săi din dreapta sau din stânga, intrările de valori din nodul frunză sau vecinul legat care indică către nodul de nivel superior sunt șterse.

Exemplul de mai sus ilustrează procedura de eliminare a unui element din arborele B+ dintr-o anumită ordine.

• În primul rând, locațiile exacte ale elementului de șters sunt identificate în arbore.
• Aici elementul de șters poate fi identificat cu exactitate doar la nivelul frunzei și nu la plasarea indexului. Prin urmare, elementul poate fi șters fără a afecta regulile de ștergere, care este valoarea cheii minime.

• În exemplul de mai sus, trebuie să ștergem 31 din Arbore.
• Trebuie să găsim instanțele lui 31 în Index și Leaf.
• Putem vedea că 31 este disponibil atât la nivel de nod Index, cât și Leaf. Prin urmare, îl ștergem din ambele instanțe.
• Dar, trebuie să umplem indexul indicând 42. Acum ne vom uita la copilul potrivit sub 25 de ani și vom lua valoarea minimă și o vom plasa ca index. Deci, 42 fiind singura valoare prezentă, va deveni indicele.

Șterge OperaAlgoritmul de țiune

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

producție:

Cheia „K” este ștearsă și cheile sunt împrumutate de la frați pentru ajustarea valorilor în n și a nodurilor părinte, dacă este necesar.

Rezumat

• B+ Tree este un auto-echilibrare structură de date pentru executarea unor proceduri precise și mai rapide de căutare, inserare și ștergere a datelor
• Putem prelua cu ușurință date complete sau date parțiale, deoarece trecerea prin structura arborescentă legată o face eficientă.
• Structura arborelui B+ crește și se micșorează odată cu creșterea/scăderea numărului de înregistrări stocate.
• Stocarea datelor pe nodurile frunză și ramificarea ulterioară a nodurilor interne scurtează evident înălțimea arborelui, ceea ce reduce operațiunile de intrare și ieșire pe disc, consumând în cele din urmă mult mai puțin spațiu pe dispozitivele de stocare.