Înainte de a înțelege arborele B și arbore B+ diferențe, ar trebui să cunoaștem arborele B și arborele B+ separat.
Ce este arborele B?
arborele B este un arbore cu auto-echilibrare și este un arbore m-way unde m definește ordinea arborelui. Btree este o generalizare a Arborele de căutare binar în care un nod poate avea mai mult de o cheie și mai mult de doi copii, în funcție de valoarea lui m . În arborele B, datele sunt specificate într-o ordine sortată având valori mai mici în subarborele din stânga și valori mai mari în subarborele din dreapta.
cum să dezactivezi modul dezvoltator Android
Proprietățile arborelui B
Următoarele sunt proprietățile arborelui B:
- În arborele B, toate nodurile frunzelor trebuie să fie la același nivel, în timp ce, în cazul unui arbore binar, nodurile frunzei pot fi la niveluri diferite.
Să înțelegem această proprietate printr-un exemplu.
În arborele de mai sus, toate nodurile frunzelor nu sunt la același nivel, dar au cel mai mult doi copii. Prin urmare, putem spune că arborele de mai sus este a arbore binar dar nu un arbore B.
- Dacă Btree are un ordin de m, atunci fiecare nod poate avea un maxim de m În cazul copiilor minime, nodurile frunză au zero copii, nodul rădăcină are doi copii, iar nodurile interne au un plafon de m/2.
- Fiecare nod poate avea maxim (m-1) chei. De exemplu, dacă valoarea lui m este 5, atunci valoarea maximă a tastelor este 4.
- Nodul rădăcină are minim o cheie, în timp ce toate celelalte noduri, cu excepția nodului rădăcină, au (plafon de m/2 minus - 1) chei minime.
- Dacă efectuăm inserarea în arborele B, atunci nodul este întotdeauna inserat în nodul frunză.
Să presupunem că vrem să creăm un arbore B de ordinul 3 inserând valori de la 1 la 10.
Pasul 1: Mai întâi, creăm un nod cu 1 valoare, așa cum se arată mai jos:
Pasul 2: Următorul element este 2, care vine după 1, după cum se arată mai jos:
Pasul 3: Următorul element este 3 și este inserat după 2 după cum se arată mai jos:
După cum știm că fiecare nod poate avea maximum 2 chei, așa că vom împărți acest nod prin elementul din mijloc. Elementul din mijloc este 2, deci se mută la părintele său. Nodul 2 nu are niciun părinte, așa că va deveni nodul rădăcină, așa cum se arată mai jos:
Pasul 4: Următorul element este 4. Deoarece 4 este mai mare decât 2 și 3, va fi adăugat după 3 așa cum se arată mai jos:
Pasul 5: Următorul element este 5. Deoarece 5 este mai mare decât 2, 3 și 4, va fi adăugat după 4 așa cum se arată mai jos:
După cum știm că fiecare nod poate avea maximum 2 chei, așa că vom împărți acest nod prin elementul din mijloc. Elementul din mijloc este 4, deci se mută la părintele său. Părintele este nodul 2; prin urmare, 4 vor fi adăugate după 2, după cum se arată mai jos:
Pasul 6: Următorul element este 6. Deoarece 6 este mai mare decât 2, 4 și 5, deci 6 va veni după 5, așa cum se arată mai jos:
Pasul 7: Următorul element este 7. Deoarece 7 este mai mare decât 2, 4, 5 și 6, deci 7 va veni după 6, după cum se arată mai jos:
După cum știm că fiecare nod poate avea maximum 2 chei, așa că vom împărți acest nod prin elementul din mijloc. Elementul din mijloc este 6, așa că se mută la părintele său, așa cum se arată mai jos:
Dar, 6 nu poate fi adăugat după 4 deoarece nodul poate avea maximum 2 chei, așa că vom împărți acest nod prin elementul din mijloc. Elementul din mijloc este 4, deci se mută la părintele său. Deoarece nodul 4 nu are niciun părinte, nodul 4 va deveni un nod rădăcină, după cum se arată mai jos:
Ce este un arbore B+?
The arbore B+ este cunoscut și ca un copac autoechilibrat avansat, deoarece fiecare cale de la rădăcina copacului până la frunza copacului are aceeași lungime. Aici, aceeași lungime înseamnă că toate nodurile frunzelor apar la același nivel. Nu se va întâmpla ca unele dintre nodurile frunzelor să apară la nivelul al treilea, iar unele dintre ele la nivelul al doilea.
Un index arbore B+ este considerat un index pe mai multe niveluri, dar structura arborescentă B+ nu este similară cu fișierele secvențiale cu index pe mai multe niveluri.
De ce este folosit arborele B+?
Un arbore B+ este folosit pentru a stoca înregistrările foarte eficient prin stocarea înregistrărilor într-o manieră indexată folosind structura indexată a arborelui B+. Datorită indexării pe mai multe niveluri, accesarea datelor devine mai rapidă și mai ușoară.
Structura nodului arbore B+
Structura de noduri a arborelui B+ conține indicatori și valori cheie prezentate în figura de mai jos:
După cum putem observa în structura nodului arborelui B+ de mai sus, că acesta conține n-1 valori cheie (k1la kn-1) și n pointeri (p1la pn).
Valorile cheii de căutare care sunt plasate în nod sunt păstrate în ordine sortată. Astfel, dacă i
Constrângere asupra diferitelor tipuri de noduri
Fie „b” ordinul arborelui B+.
Nodul fără frunze
Fie „m” reprezintă numărul de copii ai unui nod, apoi relația dintre ordinea arborelui și numărul de copii poate fi reprezentată astfel:
Fie k reprezintă valorile cheii de căutare. Relația dintre ordinea arborelui și cheia de căutare poate fi reprezentată astfel:
Deoarece știm că numărul de pointeri este egal cu valorile cheii de căutare plus 1, deci matematic, poate fi scris ca:
java string.format
Număr de indicatori (sau copii) = Număr de taste de căutare + 1
Prin urmare, numărul maxim de pointeri ar fi „b”, iar numărul minim de pointeri ar fi funcția de plafon a lui b/2.
Nodul frunzelor
Un nod frunză este un nod care apare la ultimul nivel al arborelui B+ și fiecare nod frunză folosește doar un indicator pentru a se conecta unul cu celălalt pentru a oferi acces secvenţial la nivelul frunzei.
În nodul frunză, numărul maxim de copii este:
Numărul maxim de chei de căutare este:
Nodul rădăcină
Numărul maxim de copii în cazul nodului rădăcină este: b
Numărul minim de copii este: 2
Cazuri speciale în arborele B+
Cazul 1: Dacă nodul rădăcină este singurul nod din arbore. În acest caz, nodul rădăcină devine nodul frunză.
În acest caz, numărul maxim de copii este 1, adică nodul rădăcină în sine, în timp ce numărul minim de copii este b-1, care este același cu cel al unui nod frunză.
Reprezentarea unui nod frunză în arborele B+
În figura de mai sus, '.' reprezintă indicatorul, în timp ce 10, 20 și 30 sunt valorile cheie. Pointerul conține adresa la care este stocată valoarea cheii, așa cum se arată în figura de mai sus.
Exemplu de arbore B+
În figura de mai sus, nodul conține trei valori cheie, adică 9, 16 și 25. Indicatorul care apare înainte de 9 conține valorile cheii mai mici decât 9 reprezentate prin ki. Indicatorul care apare înainte de 16, conține valorile cheii mai mari sau egale cu 9 dar mai mici de 16 reprezentate prin kj. Indicatorul care apare înainte de 25, conține valorile cheii mai mari sau egale cu 16 dar mai mici de 25 reprezentate prin kn.
Diferențele dintre arborele B și arborele B+
Următoarele sunt diferențele dintre arborele B și arborele B+:
| arborele B | arbore B+ |
|---|---|
| În arborele B, toate cheile și înregistrările sunt stocate atât în nodurile interne, cât și în cele ale frunzelor. | În arborele B+, cheile sunt indecșii stocați în nodurile interne și înregistrările sunt stocate în nodurile frunză. |
| În arborele B, cheile nu pot fi stocate în mod repetat, ceea ce înseamnă că nu există duplicare a cheilor sau a înregistrărilor. | În arborele B+, poate exista redundanță în apariția cheilor. În acest caz, înregistrările sunt stocate în nodurile frunză, în timp ce cheile sunt stocate în nodurile interne, astfel încât cheile redundante pot fi prezente în nodurile interne. |
| În Btree, nodurile frunzelor nu sunt legate între ele. | În arborele B+, nodurile frunzelor sunt legate între ele pentru a oferi acces secvenţial. |
| În Btree, căutarea nu este foarte eficientă, deoarece înregistrările sunt fie stocate în frunză, fie în noduri interne. | În arborele B+, căutarea este foarte eficientă sau mai rapidă deoarece toate înregistrările sunt stocate în nodurile frunzelor. |
| Ștergerea nodurilor interne este foarte lentă și un proces consumator de timp, deoarece trebuie să luăm în considerare și copilul cheii șterse. | Ștergerea în arborele B+ este foarte rapidă deoarece toate înregistrările sunt stocate în nodurile frunze, astfel încât nu trebuie să luăm în considerare copilul nodului. |
| În Btree, accesul secvenţial nu este posibil. | În arborele B+, toate nodurile frunzelor sunt conectate între ele printr-un pointer, astfel încât accesul secvenţial este posibil. |
| În Btree, cu cât se efectuează un număr mai mare de operațiuni de împărțire, datorită cărora înălțimea crește în comparație cu lățimea, | Arborele B+ are o lățime mai mare decât înălțimea. |
| În Btree, fiecare nod are cel puțin două ramuri și fiecare nod conține unele înregistrări, așa că nu trebuie să traversăm până la nodurile frunze pentru a obține datele. | În arborele B+, nodurile interne conțin doar pointeri, iar nodurile frunză conțin înregistrări. Toate nodurile frunză sunt la același nivel, așa că trebuie să traversăm până la nodurile frunză pentru a obține datele. |
| Nodul rădăcină conține cel puțin 2 până la m copii, unde m este ordinea arborelui. | Nodul rădăcină conține cel puțin 2 până la m copii, unde m este ordinea arborelui. |