Pogovor:B-drevo

Iz MaFiRaWiki

Naslovi razdelkov naj NE BODO PISANI Z VELIKI ČRKAMI in naj ne vsebujejo dvopičij, kadar je to nepotrebno. AndrejBauer 15:37, 8 maj 2006 (CEST)

Oj! Jz sem ti pregledala temo pa bi se neki stvari dodala:

- iskanje elementa v B-drevesih: To je v bistvu posplošitev iskanja v navadnih binarnih drevesih. Tuki namesto, da bi primerjali iskani element z enim elementom v vozlišču je potrebno iskani element primerjati z elementi v vozlišču, dokler:

  • na naletimo na iskani element,
  • ne naletimo na večji element in se zato iskanje rekurzivno nadaljuje v poddrevesu z istim indeksom,
  • ne pregledamo zadnjega elementa in se iskanje rekurzivno nadaljuje v zadnjem poddrevesu.

Pa Še primer dodaj zraven.

- mogoče bi lahko kaj povedala o časovni zahtevnosti operacij:

  • vse operacije se v najslabšem možnem primeru izvedejo v času reda O(log n). Pri tem je m konstanten (preiskovanje elementov znotraj enega vozlišča lahko izvedemo v konstantnem času)
  • če je m velik: elemente v enem vozlišču preiskujemo z bisekcijo, v času reda O(log m).

- kot zanimivost bi še povedala, da se B-drevo visokega reda m > 256 uporablja za shranjevanje velikih baz podatkov na trdem disku.--AnjaRožac 18:04, 11 maj 2006 (CEST)

"Torej ima vsako vozlišče vsaj m/2-1 ..." To v bistvu ni res, vsako vozlišče ima vsaj (m/2)-1 ključev. Oklepaje si pozabila :). Pejdi še enkrat skozi pa si to popravi, ker mislim, da to ni edini oklepaj ki ti manjka. --AnjaRožac 18:17, 11 maj 2006 (CEST)

Hvala za mnenje! Bom upoštevala tvoje opombe. Mislim pa, da ima deljenje še vedno prednost pred odštevanjem! :) --AleksandraVujasin 19:43, 11 maj 2006 (CEST)

Ja ja na to sem pozabila :). Ampak jaz bi vseeno postavila tam oklepaje (če slučajno kdo ne ve..., kot npr. jaz).

Popravila sem ti nekaj slovničnih napak. Še nekaj me moti: namesto "ekstra" bi napisala raje odveč ali več.--AnjaRožac 20:21, 11 maj 2006 (CEST)

Sem popravila. --AleksandraVujasin 21:08, 11 maj 2006 (CEST)

Pri vstaljanju elementa je napisano, da se vstavlja v notranje vozlišče največje globine. Ali je to pravilno? Meni se zdi, da se vstavlja v liste (tako je razbrati iz primerov).

Osebna orodja