B-strom

Z Wikipedie, otevřené encyklopedie

B-strom je stromová datová struktura, používaná pro uchovávání dat a vyhledávání v nich. Operace přidání, vyjmutí i vyhledávání probíhají v logaritmicky omezeném čase. Tato struktura je často využívána pro databázové aplikace. B-strom je speciální případ (a,b)-stromu, který poskytuje větší volnost ve volbě minimálního a maximálního počtu potomků.

[editovat] Základní popis

V principu se jedná o (n + 1)-ární strom, kde jednotlivé uzly obsahují maximálně n klíčů a maximálně n + 1 ukazatelů na podstromy nižší úrovně. Všechny větve stromu jsou stejně dlouhé (ale nikoliv nutně stejně široké). Všechny uzly s výjimkou kořenového uzlu obsahují minimálně n \over 2 klíčů.

[editovat] Formální definice

B-stromem stupně n rozumíme strom, splňující následující podmínky:

  • Kořen má nejméně dva potomky, pokud není listem
  • Každý uzel kromě kořene a listu má nejméně \left \lceil \frac{n}{2} \right \rceil -1 a nejvýše n potomků.
  • Všechny cesty od kořene k listům jsou stejně dlouhé
  • Data v uzlu jsou organizována tak, aby logicky vytvářela posloupnost p_0, k_1, p_1, k_2, p_2 \ldots, kde k označují klíčové atributy ukládaných dat, takové, že pro ně jde zavést relace uspořádání <, a pi označují odkazy na podstromy. Pro každé ki,kj,i < j je ki < kj
  • Pro každé k v podstromě odpovídajícím odkazu pi − 1, platí k < ki
  • Pro každé k v podstromě odpovídajícím odkazu pi, platí k > ki

[editovat] Podívejte se také