Prieš supratimą B medis ir B+ medis skirtumus, turėtume žinoti B medį ir B+ medį atskirai.
Kas yra B medis?
B medis yra savaime balansuojantis medis, ir tai yra m formos medis, kur m apibrėžia medžio tvarką. Btree yra apibendrinimas Dvejetainės paieškos medis kuriame mazgas gali turėti daugiau nei vieną raktą ir daugiau nei du vaikus, priklausomai nuo reikšmės m . B medyje duomenys nurodomi surūšiuota tvarka, kai kairiajame pomedžio reikšmės yra mažesnės, o dešiniajame – didesnės.
dvejetainių medžių rūšys
B medžio savybės
Toliau pateikiamos B medžio savybės:
- B medyje visi lapų mazgai turi būti tame pačiame lygyje, o dvejetainio medžio atveju lapų mazgai gali būti skirtinguose lygiuose.
Supraskime šią savybę per pavyzdį.
Aukščiau pateiktame medyje visi lapų mazgai nėra viename lygyje, tačiau jie turi daugiausiai du vaikus. Todėl galime teigti, kad aukščiau minėtas medis yra a dvejetainis medis bet ne B medis.
- Jei Btree eilės tvarka yra m, tai kiekvienas mazgas gali turėti daugiausiai m Mažiausių vaikų atveju lapų mazgai turi nulį vaikų, šaknies mazgas turi du vaikus, o vidinių mazgų lubos yra m/2.
- Kiekvienas mazgas gali turėti maksimalų (m-1) raktą. Pavyzdžiui, jei m reikšmė yra 5, tada maksimali raktų reikšmė yra 4.
- Šakninis mazgas turi mažiausiai vieną raktą, o visi kiti mazgai, išskyrus šakninį mazgą, turi (m/2 minus – 1) minimalius raktus.
- Jei atliekame įterpimą į B medį, tai mazgas visada įterpiamas į lapo mazgą.
Tarkime, kad norime sukurti 3 eilės B medį, įterpdami reikšmes nuo 1 iki 10.
1 žingsnis: Pirmiausia sukuriame mazgą su 1 reikšme, kaip parodyta toliau:
2 žingsnis: Kitas elementas yra 2, kuris ateina po 1, kaip parodyta toliau:
3 veiksmas: Kitas elementas yra 3 ir įterpiamas po 2, kaip parodyta toliau:
Kaip žinome, kiekvienas mazgas gali turėti ne daugiau kaip 2 raktus, todėl šį mazgą padalinsime per vidurinį elementą. Vidurinis elementas yra 2, todėl jis perkeliamas į pirminį elementą. 2 mazgas neturi pirminio, todėl jis taps šakniniu mazgu, kaip parodyta toliau:
4 veiksmas: Kitas elementas yra 4. Kadangi 4 yra didesnis nei 2 ir 3, jis bus pridėtas po 3, kaip parodyta toliau:
5 veiksmas: Kitas elementas yra 5. Kadangi 5 yra didesnis nei 2, 3 ir 4, jis bus pridėtas po 4, kaip parodyta toliau:
Kaip žinome, kiekvienas mazgas gali turėti ne daugiau kaip 2 raktus, todėl šį mazgą padalinsime per vidurinį elementą. Vidurinis elementas yra 4, todėl jis perkeliamas į pirminį elementą. Pirminis yra 2 mazgas; todėl po 2 bus pridėta 4, kaip parodyta toliau:
6 veiksmas: Kitas elementas yra 6. Kadangi 6 yra didesnis nei 2, 4 ir 5, tai 6 bus po 5, kaip parodyta toliau:
7 veiksmas: Kitas elementas yra 7. Kadangi 7 yra didesnis nei 2, 4, 5 ir 6, tai 7 bus po 6, kaip parodyta toliau:
Kaip žinome, kiekvienas mazgas gali turėti ne daugiau kaip 2 raktus, todėl šį mazgą padalinsime per vidurinį elementą. Vidurinis elementas yra 6, todėl jis perkeliamas į pirminį elementą, kaip parodyta toliau:
Tačiau 6 negalima pridėti po 4, nes mazgas gali turėti ne daugiau kaip 2 raktus, todėl šį mazgą padalinsime per vidurinį elementą. Vidurinis elementas yra 4, todėl jis perkeliamas į pirminį elementą. Kadangi 4 mazgas neturi pirminio, 4 mazgas taps šakniniu mazgu, kaip parodyta toliau:
Kas yra B+ medis?
The B+ medis Taip pat žinomas kaip pažangus savaime subalansuotas medis, nes kiekvienas kelias nuo medžio šaknies iki medžio lapo yra vienodo ilgio. Čia toks pat ilgis reiškia, kad visi lapų mazgai yra tame pačiame lygyje. Taip neatsitiks, kad dalis lapų mazgų atsirastų trečiame lygyje, o dalis – antrame lygyje.
B+ medžio indeksas laikomas kelių lygių indeksu, tačiau B+ medžio struktūra nėra panaši į kelių lygių indeksų nuoseklius failus.
Kodėl naudojamas B+ medis?
B+ medis naudojamas norint labai efektyviai saugoti įrašus, įrašus išsaugant indeksuotu būdu, naudojant B+ medžio indeksuotą struktūrą. Dėl kelių lygių indeksavimo duomenų prieiga tampa greitesnė ir lengvesnė.
B+ medžio mazgo struktūra
B+ medžio mazgo struktūroje yra rodyklės ir pagrindinės reikšmės, parodytos toliau esančiame paveikslėlyje:
Kaip matome aukščiau pateiktoje B+ medžio mazgo struktūroje, joje yra n-1 rakto reikšmės (k1į kn-1) ir n rodyklės (p1į pn).
Paieškos rakto reikšmės, esančios mazge, laikomos surūšiuota tvarka. Taigi, jei i
Įvairių tipų mazgų apribojimas
Tegul „b“ yra B+ medžio tvarka.
Ne lapų mazgas
Tegul „m“ reiškia mazgo vaikų skaičių, tada ryšį tarp medžio eilės ir vaikų skaičiaus galima pavaizduoti taip:
Tegu k reiškia paieškos rakto reikšmes. Ryšys tarp medžio tvarkos ir paieškos rakto gali būti pavaizduotas taip:
Kadangi žinome, kad rodyklių skaičius yra lygus paieškos rakto reikšmėms plius 1, todėl matematiškai jį galima parašyti taip:
Rodyklės (arba vaikų) skaičius = paieškos klavišų skaičius + 1
Todėl didžiausias rodyklių skaičius būtų „b“, o mažiausias rodyklių skaičius būtų b/2 lubų funkcija.
Lapų mazgas
Lapo mazgas yra mazgas, esantis paskutiniame B+ medžio lygyje, o kiekvienas lapo mazgas naudoja tik vieną žymeklį, kad galėtų prisijungti vienas prie kito, kad užtikrintų nuoseklią prieigą lapo lygyje.
Lapo mazge didžiausias vaikų skaičius yra:
Didžiausias paieškos klavišų skaičius yra:
Šakninis mazgas
Didžiausias vaikų skaičius šakninio mazgo atveju yra: b
Minimalus vaikų skaičius: 2
Ypatingi atvejai B+ medyje
1 atvejis: Jei šaknies mazgas yra vienintelis medžio mazgas. Šiuo atveju šaknies mazgas tampa lapo mazgu.
Šiuo atveju didžiausias vaikų skaičius yra 1, t. y. pats šaknies mazgas, o mažiausias vaikų skaičius yra b-1, kuris yra toks pat kaip lapo mazgo.
Lapo mazgo vaizdavimas B+ medyje
Aukščiau pateiktame paveikslėlyje „. reiškia žymeklį, o 10, 20 ir 30 yra pagrindinės reikšmės. Rodyklėje yra adresas, kuriame saugoma rakto reikšmė, kaip parodyta aukščiau esančiame paveikslėlyje.
B+ medžio pavyzdys
Parsisiųsti youtube su vlc
Aukščiau pateiktame paveikslėlyje mazge yra trys pagrindinės reikšmės, t.i. Rodyklėje, kuri rodoma prieš 16, yra pagrindinės reikšmės, didesnės arba lygios 9, bet mažesnės nei 16, pažymėtos kj. Rodyklėje, kuri rodoma prieš 25, yra pagrindinės reikšmės, didesnės arba lygios 16, bet mažesnės nei 25, pavaizduotos kn.
Skirtumai tarp B medžio ir B+ medžio
Toliau pateikiami skirtumai tarp B medžio ir B+ medžio:
| B medis | B+ medis |
|---|---|
| B medyje visi raktai ir įrašai saugomi tiek vidiniuose, tiek lapų mazguose. | B+ medyje raktai yra indeksai, saugomi vidiniuose mazguose, o įrašai saugomi lapų mazguose. |
| B medyje raktai negali būti pakartotinai saugomi, o tai reiškia, kad nėra raktų ar įrašų dubliavimo. | B+ medyje raktai gali būti pertekliniai. Šiuo atveju įrašai saugomi lapų mazguose, o raktai – vidiniuose mazguose, todėl vidiniuose mazguose gali būti perteklinių raktų. |
| Btree lapų mazgai nėra susieti vienas su kitu. | B+ medyje lapų mazgai yra susieti vienas su kitu, kad būtų užtikrinta nuosekli prieiga. |
| Btree paieška nėra labai efektyvi, nes įrašai saugomi lapų arba vidiniuose mazguose. | B+ medyje paieška yra labai efektyvi arba greitesnė, nes visi įrašai saugomi lapų mazguose. |
| Vidinių mazgų ištrynimas yra labai lėtas ir daug laiko reikalaujantis procesas, nes taip pat turime atsižvelgti į ištrinto rakto antrinį elementą. | Ištrynimas B+ medyje yra labai greitas, nes visi įrašai yra saugomi lapų mazguose, todėl mums nereikia atsižvelgti į mazgo antrį. |
| Btree nuosekli prieiga negalima. | B+ medyje visi lapų mazgai yra sujungti vienas su kitu per žymeklį, todėl galima nuosekli prieiga. |
| Btree atliekama daugiau skaidymo operacijų, dėl kurių aukštis didėja, palyginti su pločiu, | B+ medis turi didesnį plotį nei aukštis. |
| „Btree“ kiekvienas mazgas turi bent dvi šakas ir kiekviename mazge yra keletas įrašų, todėl mums nereikia pereiti iki lapų mazgų, kad gautume duomenis. | B+ medyje vidiniuose mazguose yra tik rodyklės, o lapų mazguose yra įrašai. Visi lapų mazgai yra tame pačiame lygyje, todėl norėdami gauti duomenis turime pereiti iki lapų mazgų. |
| Šaknies mazgas turi mažiausiai nuo 2 iki m vaikų, kur m yra medžio tvarka. | Šaknies mazgas turi mažiausiai nuo 2 iki m vaikų, kur m yra medžio tvarka. |