Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : B-Stromy

Matfiz: B-Stromy

B-stromy

Podle přednášky z Programování II 19. 3. 2007:

Jak reprezentovat stromy na disku

Z disku se čte typicky po blocích, takže bychom se tomu rádi přizpůsobili: Dejme tomu, že se do bloku vejdou tři záznamy, tak si vždycky uložím vrchol ze sudé úrovně s jeho potomky z liché úrovně. Tím se nám stane (v tomto konkrétním případě) z binárního stromu 4-ární, obecně n-ární.

Řešení: B-strom

B-strom (B podle Bayera) stupně n splňuje:

  1. Každý vrchol kromě kořene obsahuje n...2n hodnot
  2. Když vrchol obsahuje k hodnot, potom má k+1 synů.
  3. Všechny listy leží na stejné hladině.

Např. Nechť jsou ve vrcholu hodnoty a, b, c, d, pak jsou z něj ukazatele na podstromy s hodnotami z intervalů <a, (a,b), (b,c), (c,d), >d.