Tolesnėje pamokoje sužinosime apie B medžio duomenų struktūrą ir apsvarstysime galimybę ją vizualizuoti.

Taigi, pradėkime.

Kas yra B medis?

The B Medis yra specialus daugiakryptės paieškos medžio tipas , paprastai žinomas kaip M-way medis, kuris subalansuoja save. Dėl subalansuotos struktūros šie medžiai dažniausiai naudojami didžiulėms duomenų bazėms valdyti ir valdyti bei paieškai supaprastinti. B medyje kiekvienas mazgas gali turėti daugiausia n antrinių mazgų. B medis yra kelių lygių indeksavimo duomenų bazių valdymo sistemoje (DBVS) pavyzdys. Lapai ir vidiniai mazgai turės įrašų nuorodas. B medis yra žinomas kaip subalansuotas saugomas medis, nes visi lapų mazgai yra tame pačiame lygyje.

Ši diagrama yra B medžio pavyzdys:

Figūra 1. A B Medis su 3 tvarka

B medžio taisyklių supratimas

Toliau pateikiamos svarbios B medžio savybės:

1. Visi lapų mazgai yra tame pačiame lygyje.
2. B medžio duomenų struktūra apibrėžiama terminu minimalus laipsnis „d“. „d“ reikšmė priklauso nuo disko bloko dydžio.
3. Kiekvienas mazgas, išskyrus šaknį, turi būti sudarytas iš bent d-1 raktų. Šakninį mazgą gali sudaryti mažiausiai 1 raktas.
4. Visus mazgus (įskaitant šakninį mazgą) gali sudaryti daugiausia (2d-1) raktai.
5. Mazgo vaikų skaičius yra lygus pridedamas jame esančių raktų skaičius ir .
6. Visi mazgo raktai rūšiuojami didėjančia tvarka. Vaikas tarp dviejų klavišų k1 ir k2 susideda iš visų klavišų, atitinkamai svyruojančių tarp k1 ir k2.
7. Skirtingai nuo dvejetainio paieškos medžio, B medžio duomenų struktūra auga ir mažėja nuo šaknies. Tuo tarpu dvejetainis paieškos medis auga žemyn ir traukiasi žemyn.
8. Panašiai kaip ir kiti savaime subalansuoti dvejetainiai paieškos medžiai, B medžio duomenų struktūros sudėtingumas atliekant tokias operacijas kaip paieška, įterpimas ir trynimas yra O(log?n) .
9. Mazgas įterpiamas į B medį tik lapo mazge.

Panagrinėkime šį B medžio, kurio minimalus laipsnis 5, pavyzdį.

2 pav. A B tvarkos medis 5

Pastaba: minimalaus užsakymo vertė yra daug didesnė nei 5 praktiniuose B medžiuose.

Aukščiau pateiktoje diagramoje galime pastebėti, kad visi lapų mazgai yra tame pačiame lygyje, o visi ne lapų mazgai neturi tuščio pomedžio ir susideda iš raktų, vienu mažiau nei jų vaikų skaičius.

Nustatyta B medžio taisyklių formuluotė:

Kiekvienas B medis priklauso nuo teigiamo pastovaus sveikojo skaičiaus, žinomo kaip MINIMUMAS , kuris naudojamas norint nustatyti duomenų elementų, kuriuos galima laikyti viename mazge, skaičių.

1 taisyklė: Šaknėje gali būti tik vienas duomenų elementas (arba net nėra duomenų elementų, jei tai taip pat nėra antrinių); kiekvienas kitas mazgas turi bent MINIMUMAS duomenų elementai.

2 taisyklė: Maksimalus mazge saugomų duomenų elementų skaičius yra du kartus didesnis už reikšmę MINIMUMAS .

3 taisyklė: Kiekvieno B medžio mazgo duomenų elementai saugomi iš dalies užpildytame masyve, surūšiuotame nuo mažiausio duomenų elemento (indekse 0 ) į didžiausią duomenų elementą (galutinėje panaudotoje masyvo vietoje).

4 taisyklė: Bendras pomedžių, esančių po ne lapo mazgu, skaičius visada yra vienu daugiau nei duomenų elementų tame mazge.

• pomedis 0, pomedis 1,...

5 taisyklė: Kalbant apie bet kurį ne lapų mazgą:

1. Indekso duomenų elementas yra didesnis už visus pomedžio skaičiaus duomenų elementus i mazgo ir
2. Duomenų elementas indekse yra mažesnis už visus pomedžio skaičiaus duomenų elementus aš+1 mazgo.

6 taisyklė: Kiekvienas B medžio lapas turi tokį patį gylį. Taigi tai užtikrina, kad B medis užkirs kelią nesubalansuoto medžio problemai.

B medžio duomenų struktūros operacijos

Siekiant užtikrinti, kad atliekant operacijas nebūtų pažeista nė viena B medžio duomenų struktūros savybė, B medis gali būti padalintas arba sujungtas. Toliau pateikiamos kelios operacijos, kurias galime atlikti su B medžiu:

1. Duomenų elemento paieška B medyje
2. Duomenų elemento įterpimas į B medį
3. Duomenų elemento ištrynimas B medyje

Paieškos operacija ant B medžio

Elemento paieška B medyje yra panaši į dvejetainėje paieškos medyje. Tačiau užuot priėmęs dvipusį sprendimą (kairėje arba dešinėje), kaip dvejetainis paieškos medis, B medis kiekviename mazge priima m krypties sprendimą, kur m yra mazgo vaikų skaičius.

Veiksmai ieškant duomenų elemento B medyje:

1 žingsnis: Paieška prasideda nuo šakninio mazgo. Palyginkite paieškos elementą k su šaknimi.

1.1 veiksmas: Jei šakninis mazgas susideda iš elemento k, paieška bus baigta.

1.2 veiksmas: Jei elementas k yra mažesnis už pirmąją reikšmę šaknyje, pereisime prie kairėje esančio vaiko ir rekursyviai ieškome vaiko.

1.3.1 veiksmas: Jei šaknis turi tik du vaikus, pereisime prie dešiniojo antrinio ir rekursyviai ieškosime antrinių mazgų.

1.3.2 veiksmas: Jei šaknyje yra daugiau nei du raktai, ieškosime likusių.

2 žingsnis: Jei elementas k nerastas perėjus visą medį, tai paieškos elemento B medyje nėra.

Leiskite mums vizualizuoti aukščiau nurodytus veiksmus naudodami pavyzdį. Tarkime, kad mes norėjome ieškoti rakto k=34 šiame B medyje:

3.1 pav. Duotas B medis

1. Pirmiausia patikrinsime, ar raktas k = 34 yra šakniniame mazge. Kadangi raktas nėra šaknyje, pereisime prie jo antrinių mazgų. Taip pat galime pastebėti, kad šakninis mazgas turi du vaikus; todėl mes palyginsime reikiamą reikšmę tarp dviejų raktų.
   
   3.2 pav. Rakto k nėra šaknyje
2. Dabar, kai galime pastebėti, kad raktas k yra didesnis nei šakninis mazgas, ty 30, tęsime su dešiniuoju šaknies antruoju elementu.
   
   3.3 pav. Klavišas k > 30, pereikite prie dešiniojo vaiko
3. Dabar palyginsime raktą k su mazge esančiomis reikšmėmis, ty atitinkamai 40 ir 50. Kadangi raktas k yra mažesnis už kairįjį klavišą, ty 40, pereisime prie kairiojo mazgo antrinio.
   
   3.4 pav. Raktas k<40, move to left child< li>
4. Kadangi kairiojo 40 antrinio skaičiaus reikšmė yra 34, tai yra būtina reikšmė, galime daryti išvadą, kad raktas rastas ir paieškos operacija baigta.
   
   3.4 pav. Raktas k = 34, kairysis vaikas 40

Palyginome raktą su keturiomis skirtingomis reikšmėmis aukščiau pateiktame pavyzdyje, kol jį radome. Taigi laiko sudėtingumas, reikalingas paieškos operacijai B medyje, yra O(log?n) .

kitaip jei java

Įterpimo operacija ant B medžio

Įterpdami duomenų elementą į B medį, pirmiausia turime patikrinti, ar tas elementas medyje jau yra, ar ne. Jei duomenų elementas randamas B medyje, įterpimo operacija nevyksta. Tačiau jei taip nėra, tęsime įterpimą. Įterpiant elementą į lapo mazgą, reikia atsižvelgti į du scenarijus:

Mazgą sudaro ne daugiau nei MAKSIMALUS raktų skaičius -Raktą įdėsime į mazgą tinkamoje vietoje.Mazgas susideda iš MAKSIMALUS raktų skaičiaus -Įterpsime raktą į pilną mazgą, o tada vyks padalijimo operacija, padalijant visą mazgą į tris dalis. Antrasis arba vidutinis raktas bus perkeltas į pirminį mazgą, o pirmoji ir trečioji dalys veiks atitinkamai kaip kairysis ir dešinysis antrinis mazgas. Šis procesas bus pakartotas su pirminiu mazgu, jei jį taip pat sudaro MAKSIMALUS raktų skaičius.

Duomenų elemento įterpimo į B medį veiksmai:

1 žingsnis: Pradėsime apskaičiuodami maksimalų raktų skaičių mazge pagal B medžio tvarką.

2 žingsnis: Jei medis tuščias, paskirstomas šakninis mazgas ir mes įterpsime raktą, kuris veikia kaip šakninis mazgas.

3 veiksmas: Dabar ieškosime atitinkamo mazgo įterpimui.

4 veiksmas: Jei mazgas pilnas:

4.1 veiksmas: Duomenų elementus įterpsime didėjimo tvarka.

4.2 veiksmas: Jei duomenų elementai yra didesni už maksimalų raktų skaičių, mes padalinsime visą mazgą prie medianos.

4.3 veiksmas: Mes pastumsime vidurinį klavišą aukštyn ir padalinsime kairįjį ir dešinįjį klavišus kaip kairįjį ir dešinįjį.

5 veiksmas: Jei mazgas neužpildytas, įterpsime mazgą didėjimo tvarka.

Leiskite mums vizualizuoti aukščiau nurodytus veiksmus naudodami pavyzdį. Tarkime, kad turime sukurti 4 eilės B medį. Duomenų elementai, kuriuos reikia įterpti į B medį, yra 5, 3, 21, 11, 1, 16, 8, 13, 4 ir 9 .

1. Kadangi m yra lygus 3, didžiausias mazgo raktų skaičius = m-1 = 3-1 = 2 .
2. Pradėsime nuo įterpimo 5 tuščiame medyje.
   
   4.1 pav. Įterpimas 5
3. Dabar į medį įterpsime 3. Kadangi 3 yra mažesnis nei 5, tame pačiame mazge įterpsime 3 į kairę nuo 5.
   
   4.2 pav. Įterpimas 3
4. Dabar į medį įterpsime 21, o kadangi 21 yra didesnis nei 5, jis bus įterptas į dešinę nuo 5 tame pačiame mazge. Tačiau, kadangi žinome, kad maksimalus raktų skaičius mazge yra 2, vienas iš šių raktų bus perkeltas į aukščiau esantį mazgą, kad jis būtų padalintas. Taigi 5, vidurinis duomenų elementas, pajudės aukštyn, o 3 ir 21 taps atitinkamai kairiuoju ir dešiniuoju jo mazgais.
   
   4.3 pav. Įterpimas 21
5. Dabar atėjo laikas įterpti kitą duomenų elementą, ty 11, kuris yra didesnis nei 5, bet mažesnis nei 21. Todėl 11 bus įterptas kaip raktas kairėje mazgo, kurį sudaro 21, kaip raktas.
   
   4.4 pav. Įterpimas 11
6. Panašiai į medį įterpsime kitą duomenų elementą 1 ir, kaip matome, 1 yra mažesnis už 3; todėl jis bus įterptas kaip raktas kairėje mazgo, kurį sudaro 3, kairėje.
   
   4.5 pav. Įterpimas 1
7. Dabar į medį įterpsime duomenų elementą 16, kuris yra didesnis nei 11, bet mažesnis nei 21. Tačiau raktų skaičius tame mazge viršija maksimalų raktų skaičių. Todėl mazgas bus padalintas, perkeldamas vidurinį raktą į šaknį. Taigi 16 bus įterptas į dešinę nuo 5, padalinant 11 ir 21 į du atskirus mazgus.
   
   4.6 pav. Įterpimas 16
8. Duomenų elementas 8 bus įterptas kaip raktas į kairę nuo 11.
   
   4.7 pav. Įterpimas 8
9. Į medį įterpsime 13, kuris yra mažesnis nei 16 ir didesnis nei 11. Todėl 13 duomenų elementą reikia įterpti į dešinę nuo mazgo, kurį sudaro 8 ir 11. Tačiau kadangi maksimalus raktų skaičius medyje gali būti bus tik 2, įvyks padalijimas, perkeliant vidurinį duomenų elementą 11 į aukščiau esantį mazgą, o 8 ir 13 – į du atskirus mazgus. Dabar aukščiau esantį mazgą sudarys 5, 11 ir 16, o tai vėl viršija maksimalų raktų skaičių. Todėl bus dar vienas padalijimas, todėl duomenų elementas 11 bus šakninis mazgas, kurio antriniai mazgai yra 5 ir 16.
   
   4.8 pav. Įterpimas 13
10. Kadangi duomenų elementas 4 yra mažesnis nei 5, bet didesnis nei 3, jis bus įterptas į dešinę nuo mazgo, kurį sudaro 1 ir 3, o tai vėl viršys maksimalų raktų skaičių mazge. Todėl išsiliejimas vėl įvyks, perkeliant 3 į viršutinį mazgą šalia 5.
    
    4.9 pav. Įterpimas 4
11. Pagaliau duomenų elementas 9, kuris yra didesnis nei 8, bet mažesnis nei 11, bus įterptas į dešinę nuo mazgo, kurį sudaro 8 kaip raktas.
    
    4.10 pav. Įterpimas 9

Aukščiau pateiktame pavyzdyje atlikome skirtingus palyginimus. Pirmoji reikšmė buvo tiesiogiai įterpta į medį; po to kiekviena reikšmė turėjo būti lyginama su tame medyje esančiais mazgais. Įterpimo operacijos B medyje sudėtingumas priklauso nuo mazgų skaičiaus ir .

B medžio operacijos ištrynimas

Duomenų elemento ištrynimas B medyje apima tris pagrindinius įvykius:

nuo 1 iki 100 romėnų Nr

1. Ieškoma mazgo, kuriame yra ištrintinas raktas,
2. Ištrinkite raktą ir

• Jei reikia, subalansuokite medį.

Ištrinant elementą iš medžio gali atsirasti sąlyga, vadinama Underflow. Nepakankamas srautas atsiranda, kai mazgą sudaro mažiau nei minimalus raktų skaičius; jis turėtų laikyti.

Toliau pateikiami keli terminai, kuriuos reikia suprasti prieš vizualizuojant ištrynimo / pašalinimo operaciją:

Užsakymo pirmtakas:Reikšmingiausias kairiojo mazgo antrinio elemento raktas yra žinomas kaip jo eilės pirmtakas.Užsakymo įpėdinis:Mažasis raktas dešiniajame mazgo antrinėje dalyje yra žinomas kaip jo eilės įpėdinis.

Toliau pateikiami trys ryškūs ištrynimo operacijos B medyje atvejai:

1 atvejis: rakto ištrynimas / pašalinimas yra lapo mazge - Ši byla dar skirstoma į dvi skirtingas bylas:

1. Rakto ištrynimas / pašalinimas nepažeidžia minimalaus raktų skaičiaus, kurį mazgas turi turėti.

Įsivaizduokime šį atvejį naudodami pavyzdį, kai ištrinsime 32 raktą iš šio B medžio.

4.1 pav.: Lapo mazgo rakto (32) ištrynimas iš B medžio

Kaip matome, 32 išbraukimas iš šio medžio nepažeidžia aukščiau nurodytos savybės.

2. Rakto ištrynimas / pašalinimas pažeidžia mažiausio raktų skaičiaus, kurį mazgas turi turėti, savybę. Šiuo atveju turime pasiskolinti raktą iš jo artimiausio brolio mazgo tvarka iš kairės į dešinę.

Pirmiausia aplankysime artimiausią kairįjį brolį. Jei kairiajame brolio mazge yra daugiau nei minimalus raktų skaičius, jis pasiskolina raktą iš šio mazgo.

Kitu atveju patikrinsime, ar skolinsimės iš artimiausio dešiniojo brolio mazgo.

Dabar įsivaizduokime šį atvejį naudodami pavyzdį, kuriame ištrinsime 31 iš aukščiau pateikto B medžio. Šiuo atveju pasiskolinsime raktą iš kairiojo brolio mazgo.

4.2 pav.: Lapo mazgo rakto (31) ištrynimas iš B medžio

Jei abu artimiausius brolių mazgus jau sudaro minimalus raktų skaičius, tada mazgą sujungsime su kairiuoju arba su dešiniuoju. Šis sujungimo procesas atliekamas per pirminį mazgą.

Pažiūrėkime dar kartą, ištrindami raktą 30 iš aukščiau esančio B medžio.

4.3 pav.: Lapo mazgo rakto (30) ištrynimas iš B medžio

2 atvejis: rakto ištrynimas / pašalinimas yra ne lapo mazge - Ši byla dar skirstoma į skirtingus atvejus:

1. Pašalintas ne lapas / vidinis mazgas pakeičiamas eilės pirmtaku, jei kairiajame antriniame mazge yra daugiau nei minimalus raktų skaičius.

Įsivaizduokime šį atvejį naudodami pavyzdį, kai ištrinsime raktą 33 iš B medžio.

4.4 pav.: Lapo mazgo rakto (33) ištrynimas iš B medžio

2. Pašalintas ne lapas / vidinis mazgas pakeičiamas eilės įpėdiniu, jei dešiniajame antriniame mazge yra daugiau nei minimalus raktų skaičius.

Jei kuris nors vaikas turi minimalų raktų skaičių, sujungsime kairįjį ir dešinįjį antrinius mazgus.

Įsivaizduokime šį atvejį, ištrindami raktą 30 iš B medžio.

4.5 pav.: Lapo mazgo rakto (30) ištrynimas iš B medžio

Sujungus, jei pirminiame mazge yra mažiau nei minimalus raktų skaičius, galima ieškoti brolių ir seserų, kaip 1 atvejis .

3 atvejis: Tokiu atveju medžio aukštis mažėja. Jei tikslinis raktas yra vidiniame mazge, o pašalinus raktą mazge atsiranda mažiau raktų (tai yra mažiau nei būtina), ieškokite eilės pirmtako ir eilės įpėdinio. Jei abu vaikai turi minimalų raktų skaičių, skolintis negalima. Tai veda prie 2 atvejis(3) , t.y. sujungiant antrinius mazgus.

Vėl ieškosime brolio ir sesers, kad galėtume pasiskolinti raktą. Tačiau jei brolį ir seserį taip pat sudaro minimalus raktų skaičius, sujungsime mazgą su seserimi kartu su pirminiu mazgu ir sutvarkysime antrinius mazgus pagal reikalavimus (didėjimo tvarka).

Įsivaizduokime šį atvejį naudodami pavyzdį, kuriame iš nurodyto B medžio ištrinsime duomenų elementą 10.

4.6 pav.: Lapo mazgo rakto (10) ištrynimas iš B medžio

Laiko sudėtingumas pirmiau pateiktuose pavyzdžiuose skiriasi priklausomai nuo vietos, iš kurios reikia ištrinti raktą. Taigi ištrynimo operacijos B medyje sudėtingumas yra toks O(log?n) .

Išvada

Šioje pamokoje mes sužinojome apie B medį ir įvairiais pavyzdžiais vaizdavome įvairias jo operacijas. Taip pat supratome kai kurias pagrindines B medžio savybes ir taisykles.