B+ Tree ir B Tree paplašinājums, kas ļauj veikt efektīvas ievietošanas, dzēšanas un meklēšanas darbības.
B kokā atslēgas un ierakstus var saglabāt gan iekšējos, gan lapu mezglos. Savukārt B+ kokā ierakstus (datus) var saglabāt tikai lapu mezglos, savukārt iekšējie mezgli var saglabāt tikai galvenās vērtības.
string to itn
B+ koka lapu mezgli ir savstarpēji saistīti atsevišķi saistītu sarakstu veidā, lai padarītu meklēšanas vaicājumus efektīvākus.
B+ Tree izmanto, lai saglabātu lielu datu apjomu, ko nevar saglabāt galvenajā atmiņā. Sakarā ar to, ka galvenās atmiņas apjoms vienmēr ir ierobežots, B+ koka iekšējie mezgli (ierakstu piekļuves atslēgas) tiek saglabāti galvenajā atmiņā, bet lapu mezgli tiek glabāti sekundārajā atmiņā.
B+ koka iekšējos mezglus bieži sauc par indeksa mezgliem. 3. kārtas B+ koks ir parādīts nākamajā attēlā.
B+ koka priekšrocības
- Ierakstus var ienest vienādās diska piekļuves reižu skaitā.
- Koka augstums paliek līdzsvarots un mazāks nekā B kokam.
- Mēs varam piekļūt B+ kokā saglabātajiem datiem gan secīgi, gan tieši.
- Atslēgas tiek izmantotas indeksēšanai.
- Ātrāki meklēšanas vaicājumi, jo dati tiek glabāti tikai lapu mezglos.
B koks VS B+ koks
| SN | B Koks | B+ koks |
|---|---|---|
| 1 | Meklēšanas taustiņus nevar atkārtoti saglabāt. | Var būt liekas meklēšanas atslēgas. |
| 2 | Datus var glabāt lapu mezglos, kā arī iekšējos mezglos | Datus var glabāt tikai lapu mezglos. |
| 3 | Dažu datu meklēšana ir lēnāks process, jo datus var atrast gan iekšējos mezglos, gan lapu mezglos. | Meklēšana ir salīdzinoši ātrāka, jo datus var atrast tikai lapu mezglos. |
| 4 | Iekšējo mezglu dzēšana ir tik sarežģīta un laikietilpīga. | Dzēšana nekad nebūs sarežģīts process, jo elements vienmēr tiks dzēsts no lapas mezgliem. |
| 5 | Lapu mezglus nevar savienot kopā. | Lapu mezgli ir savienoti kopā, lai padarītu meklēšanas darbības efektīvākas. |
Ievietošana B+ kokā
1. darbība: Ievietojiet jauno mezglu kā lapas mezglu
2. darbība: Ja lapai nav nepieciešamas vietas, sadaliet mezglu un kopējiet vidējo mezglu uz nākamo indeksa mezglu.
3. darbība: Ja indeksa mezglam nav nepieciešamās vietas, sadaliet mezglu un kopējiet vidējo elementu uz nākamo rādītāja lapu.
Piemērs :
Ievietojiet vērtību 195 B+ kokā pēc 5. kārtas, kas parādīts nākamajā attēlā.
195 tiks ievietots labajā apakškokā 120 pēc 190. Ievietojiet to vajadzīgajā vietā.
Mezglā ir lielāks par maksimālo elementu skaitu, t.i., 4, tāpēc sadaliet to un novietojiet vidējo mezglu līdz vecākajam mezglam.
pavedienu sinhronizācija
Tagad indeksa mezglā ir 6 bērni un 5 atslēgas, kas pārkāpj B+ koka īpašības, tāpēc mums tas ir jāsadala, kā parādīts šādi.
Dzēšana B+ kokā
1. darbība: Izdzēsiet atslēgu un datus no lapām.
2. darbība: ja lapas mezglā ir mazāks par minimālo elementu skaitu, sapludiniet mezglu ar tā brāli un izdzēsiet starp tiem esošo atslēgu.
3. darbība: ja indeksa mezglā ir mazāks par minimālo elementu skaitu, sapludiniet mezglu ar brāli un pārvietojiet taustiņu uz leju starp tiem.
Piemērs
Izdzēsiet atslēgu 200 no B+ koka, kas parādīts nākamajā attēlā.
200 atrodas 190 labajā apakškokā, pēc 195. dzēst to.
Apvienojiet abus mezglus, izmantojot 195, 190, 154 un 129.
Tagad elements 120 ir vienīgais mezglā esošais elements, kas pārkāpj B+ koka īpašības. Tāpēc mums tas ir jāapvieno, izmantojot 60, 78, 108 un 120.
Tagad B+ koka augstums tiks samazināts par 1.
