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