B+ strom
Kategorie: Nezařazeno (celkem: 23179 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 12. srpna 2008
- Zobrazeno: 2593×
- Licence: GNU Free Documentation License
- Seznam autorů a změn
- Vyloučení odpovědnosti
Příbuzná témata
B+ strom
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 |
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:
). - Kořen má nejvýše N potomků, spodní hranice není omezena.
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 = BH
- 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(logBN) operací
- Vyhledání záznamu v nejhorším případě vyžaduje O(logBN) operací
- Vymazání (dříve nalezeného) záznamu v nejhorším případě vyžaduje O(logBN) operací
- Vyhledání více položek v rámci zadaného rozsahu trvá v nejhorším případe O(logBN + K) operací (K je zde počet položek vyskytujících se v dotazovaném rozsahu)
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.
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.
Související články
- Strom (datová struktura)
- 2-3 strom
- (a,b)-strom
- B* strom
- UB strom