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:
- Každý vrchol kromě kořene obsahuje n...2n hodnot
- Když vrchol obsahuje k hodnot, potom má k+1 synů.
- 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.
- Přidávání vrcholů
- Jak zajistit, že budou listy ve stejné hladině? — Stačí, když jsou vrcholy jen zpola zaplněné.
- Co když chceme přidat hodnotu do zaplněného vrcholu, pak by vrchol obsahoval 2n+1 hodnot, takže dáme do samostatného vrcholu prostřední hodnotu (pošleme ji nahoru) a do potomků n a n vrcholů.
- Mazání
- Může nám «podtéci» vrchol (méně než n hodnot), pak se sloučí vrcholy (a propaguje se to zase nahoru, dokud to není Ok).
