B+ Tree este o extensie a lui B Tree care permite operațiuni eficiente de inserare, ștergere și căutare.
În arborele B, cheile și înregistrările pot fi stocate atât în nodurile interne, cât și în cele ale frunzei. În timp ce, în arborele B+, înregistrările (datele) pot fi stocate doar pe nodurile frunză, în timp ce nodurile interne pot stoca doar valorile cheie.
Nodurile frunze ale unui arbore B+ sunt legate între ele sub forma unor liste legate unic pentru a face interogările de căutare mai eficiente.
B+ Tree sunt folosite pentru a stoca o cantitate mare de date care nu pot fi stocate în memoria principală. Datorită faptului că dimensiunea memoriei principale este întotdeauna limitată, nodurile interne (cheile de acces la înregistrări) ale arborelui B+ sunt stocate în memoria principală, în timp ce nodurile frunză sunt stocate în memoria secundară.
css bold
Nodurile interne ale arborelui B+ sunt adesea numite noduri index. Un arbore B+ de ordinul 3 este prezentat în figura următoare.
Avantajele B+ Tree
- Înregistrările pot fi preluate în număr egal de accesări la disc.
- Înălțimea copacului rămâne echilibrată și mai mică în comparație cu arborele B.
- Putem accesa datele stocate într-un arbore B+ atât secvenţial cât şi direct.
- Cheile sunt folosite pentru indexare.
- Interogări de căutare mai rapide, deoarece datele sunt stocate numai pe nodurile frunzelor.
Arborele B VS Arborele B+
| SN | B Arborele | B+ Arborele |
|---|---|---|
| 1 | Cheile de căutare nu pot fi stocate în mod repetat. | Pot fi prezente chei de căutare redundante. |
| 2 | Datele pot fi stocate în nodurile frunză, precum și în nodurile interne | Datele pot fi stocate numai pe nodurile frunzelor. |
| 3 | Căutarea unor date este un proces mai lent, deoarece datele pot fi găsite atât pe nodurile interne, cât și pe nodurile frunză. | Căutarea este relativ mai rapidă, deoarece datele pot fi găsite numai pe nodurile frunzelor. |
| 4 | Ștergerea nodurilor interne este atât de complicată și consumatoare de timp. | Ștergerea nu va fi niciodată un proces complex, deoarece elementul va fi întotdeauna șters din nodurile frunze. |
| 5 | Nodurile frunzelor nu pot fi legate între ele. | Nodurile frunză sunt legate între ele pentru a face operațiunile de căutare mai eficiente. |
Inserare în B+ Tree
Pasul 1: Inserați noul nod ca nod frunză
Pasul 2: Dacă frunza nu are spațiu necesar, împărțiți nodul și copiați nodul din mijloc în următorul nod index.
Pasul 3: Dacă nodul index nu are spațiu necesar, împărțiți nodul și copiați elementul din mijloc în următoarea pagină de index.
Exemplu:
Introduceți valoarea 195 în arborele B+ de ordinul 5 prezentat în figura următoare.
convertiți obiectul java în json
195 va fi inserat în sub-arborele din dreapta al lui 120 după 190. Introduceți-l în poziția dorită.
Nodul conține mai mult decât numărul maxim de elemente, adică 4, deci împărțiți-l și plasați nodul median până la părinte.
cate saptamani intr-o luna
Acum, nodul index conține 6 copii și 5 chei care încalcă proprietățile arborelui B+, prin urmare trebuie să-l împărțim, prezentate după cum urmează.
Ștergerea în arborele B+
Pasul 1: Ștergeți cheia și datele din frunze.
Pasul 2: dacă nodul frunză conține mai puțin decât numărul minim de elemente, îmbinați nodul cu fratele său și ștergeți cheia dintre ele.
Pasul 3: dacă nodul index conține mai puțin decât numărul minim de elemente, îmbinați nodul cu fratele și mutați în jos cheia între ele.
Exemplu
Ștergeți cheia 200 din arborele B+ prezentat în figura următoare.
200 este prezent în sub-arborele din dreapta al lui 190, după 195. ștergeți-l.
Îmbină cele două noduri folosind 195, 190, 154 și 129.
Acum, elementul 120 este singurul element prezent în nod care încalcă proprietățile arborelui B+. Prin urmare, trebuie să-l îmbinăm folosind 60, 78, 108 și 120.
Acum, înălțimea arborelui B+ va fi scăzută cu 1.
jquery la clic
