Pereiti prie turinio

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

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.

  1. JUOZAPAVIČIUS, Algimantas. Duomenų struktūros ir efektyvūs algoritmai. Vilnius: TEV, 2007, 108 p. ISBN 978-9955-680-87-1.