Bajero medžiai

KAUNO TECHNOLOGIJOS UNIVERSITETAS Bajero medžiai Kaunas 2006 Turinys 1. Įvadas............................................................................................................................3 2. Bajero medžių taikymas................................................................................................3 3. Bajero medžio struktūra yra tokia.................................................................................3 4. B medžių savybės..........................................................................................................4 5. Įterpimas........................................................................................................................4 6. Jei lapas pildant tapo perpildytas, galimi šie variantai..................................................4 7. Paieška...........................................................................................................................4 8. Šalinimas........................................................................................................................5 9. Ypatingi B medžio atvejai. Dvejetainis B medis...........................................................5 10. Ypatingi B medžio atvejai. Simetrinis dvejetainis B medis........................................6 11. Naudota Literatūra.......................................................................................................6 Tikslas ♦ Susipažinti su Bajero medžių veikimo principu. ♦ Sužinoti kodėl, kaip ir kur naudojami Bajero medžiai. ♦ Išmokti pritaikyti Bajero medžius. Bajero medžiai 1. Įvadas. Sparčiai plintant bei didėjant duomenų bazėm buvo susidurta su nauja problema. Reikėjo efektyvaus paieškos algoritmo, kuris būtų optimalus naudojamos atmintinės atžvilgiu. Vieną iš tokių algoritmų 1970m. sugalvojo R.Bajeras (Rudolf Bayer) ir E.Makreitas (Edward M. McCreight). Jis buvo pavadintas Bajero (B-Tree) arba paprasčiausiai B medžiu. 2. Bajero medžių taikymas: • MySQL • IBM System R, 1976/77 (prototipas) • Oracle • IBM SQL/DS • Ingres (vėlesnės versijos) • IBM DB2 Informix • Sybase • Microsoft SQL-Server • 3. Bajero medžio struktūra yra tokia: 4. B medžių savybės: • 1. Kiekvienas puslapis išskyrus šakninį turi nuo n iki 2n elementų(n – medžio eilė). • 2. Kiekvienas puslapis gali arba turi būti lapu (t.y. neturėti palikuonių), arba turėti m+1 palikuonį(m – puslapyje esančių elementų skaičius). • 3. Visi lapai yra vieno lygio. • 4. Gana paprasti elementų įterpimo, šalinimo, paieškos algoritmai. • 5. Jeigu įrašius naują elementą puslapyje jų yra daugiau, negu leistina, tai toks puslapis tampa perpildytas. 5. Įterpimas • Naują elementą terpiame į žemiausią B-medžio lygį(lapą) taip, kad nepasikeistų rūšiavimo tvarka. • Elemento(30) įterpimo pavyzdys 6. Jei lapas pildant tapo perpildytas, galimi šie variantai: • 1. Jei kairėje esantis lapas yra neužpildytas, elementus stumiame į kairę: iš aukštesnio puslapio vieną elementą nuleidžiame į apačią, o iš perpildyto lapo kraštinį elementą perkeliame į aukštesnį lygį. Analogišku postūmiu į dešinę vieną elementą galime perstumti į gretimą lapą iš dešinės. • 2. Jei nėra galimybės elementą perstumti į gretimą lapą, kuriame naują lapą perpildyto lapo dešinėje: perpildyto lapo kairiuosius elementus paliekame, vieną vidurinį perkeliame aukštyn, o dešiniuosius perkeliame į naują lapą dešinėje. • 3. Galimas atvejis, kad elementą perkėlus į aukštesnį puslapį, vyksta puslapio perpildymas. Tokiu atveju reikia pratęsti puslapių skaidymą jau tame pačiame lygmenyje. • 4. Kraštutiniu atveju veiksmai gali pasiekti šaknį. Tokiu atveju medis paaukštės. 7. Paieška. e1 e2 e3 e4 e5 e6 … ei … em n0 n1 n2 n3 n4 n5 n6 … ni … nm 1. Jei x em, tai peršokam į puslapį nm 8. Šalinimas. • 1. Šalinant elementą iš puslapio, jis pakeičiamas leksikografiškai gretimu elementu. Gretimas elementas iš kairės randamas taip: Paeimame vieną žingsnį kairėn ir pagal dešiniąsias nuorodas leidžiamės iki lapo P ir paimame kraštinį dešinįjį elementą. • 2. Šalinant elementą iš lapo P gali būti pažeista B-medžio savybė m

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!