# 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 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é

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

Citováno z „http://cs.wikipedia.org../../../b/-/s/B-strom.html“

Kategorie: Počítačové pahýly | Datové struktury

##### Views

- Článek
- Diskuse
- Aktuální verze

##### Hledání

##### V jiných jazycích

- Deutsch
- English
- Español
- Français
- Italiano
- 日本語
- 한국어
- Lietuvių
- Polski
- Português
- Српски / Srpski
- Svenska
- 中文