Ce este un copac B +?
Un arbore B + este utilizat în principal pentru implementarea indexării dinamice pe mai multe niveluri. În comparație cu B-Tree, B + Tree stochează indicatoarele de date numai la nodurile frunze ale Tree, ceea ce face ca procesul de căutare să fie mai precis și mai rapid.
În acest tutorial B + Tree, veți învăța:
- Ce este un copac B +?
- Reguli pentru B + Tree
- De ce să folosiți B + Tree
- B + Tree vs. B Tree
- Operațiunea de căutare
- Operațiunea de inserare
- Ștergeți operațiunea
Reguli pentru B + Tree
Iată regulile esențiale pentru B + Tree.
- Frunzele sunt folosite pentru a stoca înregistrările de date.
- A fost stocat în nodurile interne ale Arborelui.
- Dacă o valoare a cheii țintă este mai mică decât nodul intern, atunci se urmărește punctul din partea stângă.
- Dacă o valoare a cheii țintă este mai mare sau egală cu nodul intern, atunci se urmărește punctul din dreapta sa.
- Rădăcina are cel puțin doi copii.
De ce să folosiți B + Tree
Iată, sunt motive pentru utilizarea arborelui B +:
- Cheile sunt utilizate în primul rând pentru a ajuta căutarea, direcționând către frunza corespunzătoare.
- B + Tree folosește un „factor de umplere” pentru a gestiona creșterea și scăderea unui copac.
- În copacii B +, numeroase taste pot fi plasate cu ușurință pe pagina de memorie, deoarece nu au datele asociate cu nodurile interioare. Prin urmare, va accesa rapid datele arborelui care se află pe nodul frunzei.
- O scanare completă completă a tuturor elementelor este un copac care are nevoie de o singură trecere liniară, deoarece toate nodurile frunze ale unui copac B + sunt legate între ele.
B + Tree vs. B Tree
Iată principalele diferențe dintre B + Tree vs. B Tree
| Arborele B + | B Copac |
| Tastele de căutare pot fi repetate. | Cheile de căutare nu pot fi redundante. |
| Datele sunt salvate numai pe nodurile frunze. | Atât nodurile frunze, cât și nodurile interne pot stoca date |
| Datele stocate pe nodul frunzei fac căutarea mai precisă și mai rapidă. | Căutarea este lentă datorită 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ă mult timp. |
| Nodurile frunze conectate fac căutarea eficientă și rapidă. | Nu puteți lega nodurile frunze. |
Operațiunea de căutare
În B + Tree, căutarea este una dintre cele mai simple proceduri de executat și de a obține rezultate rapide și precise din acesta.
Se aplică următorul algoritm de căutare:
- Pentru a găsi înregistrarea necesară, trebuie să executați căutarea binară pe înregistrările disponibile în Arborele.
- Î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ăutare în nodul părinte, curent sau frunze, atunci se afișează utilizatorului un „mesaj care nu a fost găsit”.
- Procesul de căutare poate fi relansat pentru rezultate mai bune și mai precise.
Algoritmul operației de căutare
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Ieșire :
Înregistrarea potrivită setată cu cheia exactă este afișată utilizatorului; în caz contrar, o încercare eșuată este afișată utilizatorului.
Operațiunea de inserare
Următorul algoritm este aplicabil pentru operația de inserare:
- 50 la sută din elementele din noduri sunt mutate într-o nouă frunză pentru stocare.
- Părintele noului Leaf este legat cu precizie de valoarea cheie minimă și de o nouă locație în Tree.
- Î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ă iterați procesul explicat în pașii de mai sus.
Inserați algoritmul de operație
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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.
Ieșire :
Algoritmul va determina elementul și îl va insera cu succes în nodul frunzei dorit.
Exemplul exemplar B + Tree 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țiile corespunzătoare 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 pointer.
- Acum, se creează o ierarhie dreaptă a unui arbore, iar valorile de date rămase sunt ajustate corespunzător, ținând cont de regulile aplicabile egale sau mai mari decât valorile față de nodurile cheie-valoare din dreapta.
Ștergeți operațiunea
Complexitatea procedurii de ștergere din arborele B + depășește 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ă localizăm o intrare de frunză în Arborele care ține cheia și indicatorul. , ștergeți intrarea frunzei din copac dacă frunza îndeplinește condițiile exacte de ștergere a înregistrării.
- În cazul în care nodul frunzei îndeplinește doar factorul satisfăcător de a fi pe jumătate plin, atunci operațiunea 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 Leaf. Dacă aceste criterii nu sunt îndeplinite, atunci acestea ar trebui să combine nodul frunzei și nodul legat al acestuia în ierarhia arborelui.
- La îmbinarea nodului frunzei cu vecinii săi din dreapta sau din stânga, intrările de valori din nodul frunzei sau vecinul legat care indică nodul de nivel superior sunt șterse.
Exemplul de mai sus ilustrează procedura de eliminare a unui element din Arborele B + al unei anumite ordine.
- În primul rând, locațiile exacte ale elementului care trebuie șters sunt identificate în Arborele.
- Aici elementul care trebuie șters poate fi identificat cu precizie 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 copac.
- Trebuie să localizăm instanțele de 31 în Index și Leaf.
- Putem vedea că 31 este disponibil atât la nivelul nodului Index, cât și la nivelul Leaf. Prin urmare, îl ștergem din ambele instanțe.
- Dar, trebuie să completăm indicele care indică 42. Acum ne vom uita la copilul potrivit sub 25 și vom lua valoarea minimă și o vom plasa ca un index. Deci, 42 fiind singura valoare prezentă, va deveni indicele.
Șterge algoritmul operației
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Ieșire :
Cheia „K” este ștearsă, iar cheile sunt împrumutate de la frați pentru ajustarea valorilor în n și a nodurilor părinte, dacă este necesar.
Rezumat:
- B + Tree este o structură de date auto-echilibrată pentru executarea unor căutări exacte și mai rapide, inserarea și ștergerea procedurilor pe date
- Putem prelua cu ușurință date complete sau date parțiale, deoarece parcurgerea structurii arborelui 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 frunze și ramificarea ulterioară a nodurilor interne scurtează evident înălțimea arborelui, ceea ce reduce operațiunile de intrare și ieșire a discului, consumând în cele din urmă mult mai puțin spațiu pe dispozitivele de stocare.