B-medis

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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

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 sąvybė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).

[taisyti] 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 maksimalus 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.