Turinys

• Palyginimo diagrama
• B medžio apibrėžimas
• M eilės B-medžio savybės
• Dvejetainio medžio apibrėžimas
• Važiavimo technika
• Išvada

B medis ir dvejetainis medis yra netiesinės duomenų struktūros tipai. Nors terminai atrodo panašūs, tačiau skiriasi visais aspektais. Dvejetainis medis naudojamas, kai įrašai ar duomenys yra saugomi RAM, o ne diske, nes RAM prieigos greitis yra daug didesnis nei disko. Kita vertus, B-medis yra naudojamas, kai duomenys saugomi diske. Jis sumažina prieigos laiką sumažindamas medžio aukštį ir padidindamas šakas mazge.

Kitas skirtumas tarp B medžio ir dvejetainio medžio yra tas, kad B medžio visi jo vaiko mazgai turi būti tame pačiame lygyje, tuo tarpu dvejetainis medis neturi tokio suvaržymo. Dvejetainis medis gali turėti ne daugiau kaip 2 pogrindžius ar mazgus, tuo tarpu B-medyje M negali būti pogrindžio ar mazgo, kur M yra B-medžio eiliškumas.

1. Palyginimo diagrama
2. Apibrėžimas
3. Pagrindiniai skirtumai
4. Išvada

Palyginimo diagrama

Palyginimo pagrindas	B-medis	Dvejetainis medis
Esminis suvaržymas	Mazgas gali turėti ne daugiau kaip M vaikų mazgų (kur M yra medžio tvarka).	Mazgas gali turėti ne daugiau kaip 2 porūšius.
Naudota	Jis naudojamas, kai duomenys saugomi diske.	Jis naudojamas, kai įrašai ir duomenys saugomi RAM.
Medžio aukštis	žurnalasM N (kur m yra M krypties medžio eiliškumas)	žurnalas2 N
Taikymas	Kodo indeksavimo duomenų struktūra daugelyje DBVS.	Kodo optimizavimas, Huffmano kodavimas ir kt.

B medžio apibrėžimas

B medis yra subalansuotas M krypties medis, dar žinomas kaip subalansuotas rūšiavimo medis. Jis panašus į dvejetainį paieškos medį, kuriame mazgai yra sutvarkyti pagal įsibrovėlių perėjimą. B-medžio erdvės sudėtingumas yra O (n). Įterpimo ir ištrynimo laiko sudėtingumas yra O (log n).

B medis turi atitikti tam tikras sąlygas:

• Medžio aukštis turi būti kuo mažesnis.
• Virš medžio lapų neturėtų būti tuščių poskonių.
• Medžio lapai turi būti tokio paties lygio.
• Visuose mazguose turėtų būti mažiausiai vaikų, išskyrus palikimo mazgus.

M eilės B-medžio savybės

• Kiekviename mazge gali būti didžiausias M vaikų skaičius ir mažiausias M / 2 vaikų skaičius arba bet koks skaičius nuo 2 iki maksimalaus.
• Kiekviename mazge yra vienas raktas mažiau nei vaikams su maksimaliu M-1 raktu.
• Klavišų išdėstymas tam tikra tvarka yra mazguose. Visi kairiajame klaviše esančio papildomo gaminio klavišai yra klavišo pirmtakai, o klavišo dešinėje esantys klavišai vadinami įpėdiniais.
• Įterpiant visą mazgą, medis suskaidomas į dvi dalis, o raktas su medianine reikšme įdedamas į pagrindinį mazgą.
• Sujungimo operacija vyksta, kai mazgai ištrinami.

Dvejetainio medžio apibrėžimas

Dvejetainis medis yra medžio struktūra, turinti daugiausia du vaiko mazgų rodykles. Tai reiškia, kad aukščiausias mazgo laipsnis gali būti 2 ir gali būti ir nulio arba vieno laipsnio mazgas.

Yra tam tikri dvejetainio medžio variantai, tokie kaip griežtai dvejetainis medis, pilnas dvejetainis medis, išplėstas dvejetainis medis ir kt.

• Griežtai dvejetainis medis yra medis, kuriame kiekvienas neterminuotas mazgas turi turėti kairįjį ir dešinįjį poskyrius.
• Medis vadinamas užbaigtu dvejetainiu medžiu, kai jis patenkina sąlygą, kad turi 2 ⁱ mazgai kiekviename lygyje, kur i yra lygis.
• Dvejetainis sriegis yra dvejetainis medis, kurį sudaro arba 0 mazgų, arba 2 mazgai.

Važiavimo technika

Medžio apvažiavimas yra viena iš dažniausių medžio duomenų struktūros operacijų, kai kiekvienas mazgas sistemingai lankėsi tiksliai vieną kartą.

• Inorder - šio medžio apvažiavimas kairįjį poskiepį aplanko rekursyviai, tada aplankytas šaknies mazgas ir aplankytas paskutinis dešinysis poskyris.
• Preorer - šio medžio apvažiavimas šaknies mazgą aplanko iš pradžių, tada kairiajame poskyryje ir paskutiniame, dešiniajame, papildomame poskyryje.
• Postorder - ši technika aplanko kairįjį, tada dešinįjį, ir paskutiniame šaknies mazge.

1. B medyje maksimalus vaikų mazgų skaičius, kurį gali turėti ne galinis mazgas, yra M, kur M yra B medžio eiliškumas. Kita vertus, dvejetainis medis gali turėti ne daugiau kaip du pogrindžius ar vaiko mazgus.
2. B-medis naudojamas, kai duomenys saugomi diske, o dvejetainis medis - kai duomenys saugomi greitojoje atmintyje, pavyzdžiui, RAM.
3. Kita „B medžio“ taikymo sritis yra duomenų indeksavimo kodo indeksavimas DBVS, priešingai, „Dvejetainis medis“ naudojamas kodo optimizavimui, „huffman“ kodavimui ir kt.
4. Didžiausias B medžio aukštis yra rąstas_MN (M yra medžio tvarka). Dvejetainio medžio didžiausias aukštis yra rąstas₂N (N yra mazgų skaičius, o bazė yra 2, nes ji yra dvejetainiams).

Išvada

B-medis yra naudojamas per dvejetainį ir dvejetainį paieškos medį. Pagrindinė to priežastis yra atminties hierarchija, kai CPU yra prijungtas prie talpyklos su didelio pralaidumo kanalais, o CPU yra prijungtas prie disko per mažo pralaidumo kanalą. Dvejetainis medis naudojamas, kai įrašai saugomi RAM (mažas ir greitas), o B-medis naudojamas, kai įrašai saugomi diske (didelis ir lėtas). Taigi, naudojant B medį, o ne dvejetainį medį, žymiai sutrumpėja prieigos laikas dėl aukšto šakojimosi faktoriaus ir sumažinto medžio aukščio.