B medis

B-medis tai besibalansuojančių medžio tipo duomenų struktūrų grupė, naudojama informatikoje. Ji buvo 1972 pristatyta ir . B-medyje įterpimas ir pašalinimas gali būti realizuotas O (lg n), kur n – lentelės įrašų numeris.

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 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

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

1. JUOZAPAVIČIUS, Algimantas. Duomenų struktūros ir efektyvūs algoritmai. Vilnius: TEV, 2007, 108 p. .

Nuorodos

• Bajerio medis 2008-06-09 iš Wayback Machine projekto..