B+ strom

Ukázka jednoduchého B+stromu. Jednotlivé klíče 1-7 odkazují na datové položky d1-d7. Všimněte si že každý list obsahuje odkaz na následující list (červeně), umožňující velice rychlé procházení celým stromem.

B+ strom je stromová datová struktura vycházející z B-stromu umožňující rychlé vkládání, vyhledávání i mazání dat. Data jsou zpřístupněna pomocí klíčů, přičemž na rozdíl od B-stromu jsou všechna data uložena až na samém konci stromu, v listech. Klíče jsou však uloženy i ve vnitřních uzlech či v kořenu. Ostatní vlastnosti má stejné jako zmiňovaný B-strom.

B+ strom poprvé popsal Rudolf Bayer spolu s Edwardem M. McCreightem roku 1972 v „Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972)“.

Obsah

1 Vlastnosti B+ stromu
- 1.1 Charakteristické vlastnosti B+ stromu
2 Skutečná implementace B+ stromu
3 Použití B+ stromu
4 Související články

[editovat] Vlastnosti B+ stromu

Všechny listy (tj.uzly které nemají žádné potomky) jsou na stejné úrovní (ve stejné hloubce).
Data můžou být uložena pouze v listech
Všechny uzly kromě kořene mají maximálně N a minimálně N/2 potomků (přesněji: $\left \lceil \frac{n}{2} \right \rceil -1$ ).
Kořen má nejvýše N potomků, spodní hranice není omezena.

[editovat] Charakteristické vlastnosti B+ stromu

Mějme B+ strom řádu B kde vzdálenost od kořene k listům je H:

Maximální počet uložených záznamů je $N = B H$
Minimální počet klíčů je $2(B / 2) H - 1$
Místo požadované pro uložení stromu je $O (N)$
Vložení záznamu do stromu vyžaduje v nejhorším případě $O (log B N)$ operací
Vyhledání záznamu v nejhorším případě vyžaduje $O (log B N)$ operací
Vymazání (dříve nalezeného) záznamu v nejhorším případě vyžaduje $O (log B N)$ operací
Vyhledání více položek v rámci zadaného rozsahu trvá v nejhorším případe $O (log B N + K)$ operací (K je zde počet položek vyskytujících se v dotazovaném rozsahu)

[editovat] Skutečná implementace B+ stromu

Skutečný B+ strom se ve skutečnosti realizuje tak, že je vždy ve všech listech uložen kromě vlastních klíčů a hodnot také odkaz (ukazatel) na následujícího sourozence. Díky tomu je umožněna rychlejší práce s bloky souvislých dat a s dotazy pracujícími s rozsahy typu vrať všechny záznamy kde plat je mezi 10000-20000. Tento jeden ukazatel navíc v rámci každého listu nijak dramaticky nezvětšuje paměťovou náročnost na uložení stromu, ale dramaticky zvyšuje výkon např. ve zmiňovaných souborových systémech. Tento mechanismus odkazů na následujícího sourozence je zobrazen i na obrázku červenými políčky.

[editovat] Použití B+ stromu

B+ strom je dynamická struktura, která je navržena pro práci s většími bloky dat (běžně je využíván pro ukládání dat na disk v blocích). Jeho výhodou je velice rychlé získávání (čtení) souvislého bloku dat (ve srovnání s ostatními druhy stromů). Pokud máme bloky dat definované délky B, do B+ stromu se uloží počet klíčů který je roven násobku B a čtení celého bloku dat je velice efektivní oproti binárnímu vyhledávacímu stromu (což je odpovídající blokově neorientovaná alternativa).

Tento systém používají pro indexování dat na disku souborové systémy NTFS, ReiserFS, XFS a JFS2. Relační databáze také často používají tento typ stromu pro ukládání tabulek s indexy.

[editovat] Související články

Kategorie: Stromy (datové struktury)

B+ strom v jiných jazycích: Deutsch, English, Español, עברית, 한국어, Português, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/B%2B_strom“
Stránka byla naposledy upravena v Stránka byla naposledy editována 22. 4. 2008 v 14:31.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).