B+ Tree yra B Tree plėtinys, leidžiantis efektyviai atlikti įterpimo, trynimo ir paieškos operacijas.
B medyje raktai ir įrašai gali būti saugomi tiek vidiniuose, tiek lapų mazguose. Tuo tarpu B+ medyje įrašai (duomenys) gali būti saugomi tik lapų mazguose, o vidiniai mazgai gali saugoti tik pagrindines reikšmes.
B+ medžio lapų mazgai yra susieti atskirai susietų sąrašų forma, kad paieškos užklausos būtų veiksmingesnės.
B+ medis naudojami dideliam duomenų kiekiui, kurių negalima išsaugoti pagrindinėje atmintyje, saugoti. Dėl to, kad pagrindinės atminties dydis visada yra ribotas, B+ medžio vidiniai mazgai (įrašų prieigos raktai) yra saugomi pagrindinėje atmintyje, o lapų mazgai – antrinėje atmintyje.
Vidiniai B+ medžio mazgai dažnai vadinami indekso mazgais. Toliau esančiame paveikslėlyje parodytas 3 eilės B+ medis.
B+ medžio privalumai
- Įrašai gali būti paimti vienodu prieigų prie disko skaičiumi.
- Medžio aukštis išlieka subalansuotas ir mažesnis, palyginti su B medžiu.
- Duomenis, saugomus B+ medyje, galime pasiekti nuosekliai ir tiesiogiai.
- Raktai naudojami indeksavimui.
- Greitesnės paieškos užklausos, nes duomenys saugomi tik lapų mazguose.
B medis VS B+ medis
| SN | B Medis | B+ medis |
|---|---|---|
| 1 | Paieškos klavišai negali būti pakartotinai saugomi. | Gali būti perteklinių paieškos raktų. |
| 2 | Duomenys gali būti saugomi lapų mazguose ir vidiniuose mazguose | Duomenys gali būti saugomi tik lapų mazguose. |
| 3 | Kai kurių duomenų paieška yra lėtesnė, nes duomenis galima rasti tiek vidiniuose, tiek lapų mazguose. | Paieška yra palyginti greitesnė, nes duomenis galima rasti tik lapų mazguose. |
| 4 | Vidinių mazgų ištrynimas yra toks sudėtingas ir atima daug laiko. | Ištrynimas niekada nebus sudėtingas procesas, nes elementas visada bus ištrintas iš lapų mazgų. |
| 5 | Lapų mazgai negali būti susieti kartu. | Lapų mazgai yra susieti kartu, kad paieškos operacijos būtų efektyvesnės. |
Įterpimas į B+ medį
1 žingsnis: Įdėkite naują mazgą kaip lapo mazgą
2 žingsnis: Jei lape nėra reikiamos vietos, padalinkite mazgą ir nukopijuokite vidurinį mazgą į kitą indekso mazgą.
3 veiksmas: Jei indekso mazge nėra reikiamos vietos, padalinkite mazgą ir nukopijuokite vidurinį elementą į kitą rodyklės puslapį.
Pavyzdys :
Įveskite reikšmę 195 į B+ 5 eilės medį, parodytą toliau pateiktame paveikslėlyje.
195 bus įterptas į dešinįjį 120 pomedį po 190. Įdėkite jį į norimą vietą.
Mazge yra didesnis nei maksimalus elementų skaičius, ty 4, todėl padalinkite jį ir padėkite vidurinį mazgą iki pirminio.
Dabar indekso mazge yra 6 vaikai ir 5 raktai, kurie pažeidžia B+ medžio savybes, todėl turime jį padalinti, kaip parodyta taip.
Ištrynimas B+ medyje
1 žingsnis: Ištrinkite raktą ir duomenis iš lapų.
2 žingsnis: jei lapo mazge yra mažiau nei minimalus elementų skaičius, sujunkite mazgą su jo broliu ir ištrinkite tarp jų esantį raktą.
3 veiksmas: jei indekso mazge yra mažiau nei minimalus elementų skaičius, sujunkite mazgą su seserimi ir perkelkite klavišą žemyn tarp jų.
Pavyzdys
Ištrinkite raktą 200 iš B+ medžio, parodyto kitame paveikslėlyje.
200 yra dešiniajame 190 pomedyje, po 195. ištrinti.
Sujunkite du mazgus naudodami 195, 190, 154 ir 129.
Dabar elementas 120 yra vienintelis mazge esantis elementas, kuris pažeidžia B+ medžio savybes. Todėl turime jį sujungti naudodami 60, 78, 108 ir 120.
Dabar B+ medžio aukštis bus sumažintas 1.
