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ě 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ě 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 , kde k označují klíčové atributy ukládaných dat, takové, že pro ně jde zavést relace uspořádání <, a p_i označují odkazy na podstromy. Pro každé k_i,k_j,i < j je k_i < k_j
• Pro každé k v podstromě odpovídajícím odkazu p_{i − 1}, platí k < k_i
• Pro každé k v podstromě odpovídajícím odkazu p_i, platí k > k_i

[editovat] Podívejte se také

• AVL-strom
• Hashovací tabulka
• (a,b)-strom

Tento článek o počítačích je pahýl. Můžete pomoci Wikipedii tím, že jej vhodně rozšíříte.