B-medis
B-medis tai besibalansuojančių medžio tipo duomenų struktūrų grupė, naudojama informatikoje. Ji buvo 1972 pristatyta Rudolfo Bayerio ir E. M. McCreigo. B-medyje įterpimas ir pašalinimas gali būti realizuotas O (lg n), kur n – lentelės įrašų numeris.[1]
B-medžiai pasižymi tuo kad laikas vidinių elementų apdorojimui yra žymiai mažesnis už laiką reikalingą perrinkti viršūnėms. Dėl šios savybės ši duomenų struktūra yra dažniausiai naudojama duomenų bazių ir failų sistemų realizacijai. Tokiu atveju pasirenkamas aukštos eilės B-medis, kurio viršūnė saugoma operatyvioje atmintyje, o didesnė dalis pomedžių saugoma antrinėje atminties laikmenoje (pavyzdžiui, kietajame diske).
Savybės redaguoti
B-medis dažniausiai apibrėžiamas duomenų elementų ir kiekvienos viršūnės maksimaliu galimų vaikų skaičiumi. Jei tartume, kad L yra mažiausias šiame medyje galimas viršūnės vaikų skaičius, tai didžiausias vaikų skaičius būtų 2L, o duomenų elementų kiekvienoje viršūnėje nuo L-1 iki 2L-1.
Paprasčiausias B-medžio variantas – 2-3-4 medis, kuriame kiekviena viršūnė gali turėti 2, 3 ar 4 vaikus ir atitinkamai 1, 2 ar 3 duomenų elementus.
Šaltiniai redaguoti
- ↑ JUOZAPAVIČIUS, Algimantas. Duomenų struktūros ir efektyvūs algoritmai. Vilnius: TEV, 2007, 108 p. ISBN 978-9955-680-87-1.
Nuorodos redaguoti
- Bajerio medis Archyvuota kopija 2008-06-09 iš Wayback Machine projekto..
.png){kind=small}
|
Šis straipsnis apie programavimą yra nebaigtas. Jūs galite prisidėti prie Vikipedijos papildydami šį straipsnį. |