B-strom: Porovnání verzí
Smazaný obsah Přidaný obsah
opravena zámena pojmů klíč a uzel, klíčů je miliarda, uzlů milion, stejný příklad Cormen Introductions to algorithms značka: editace z Vizuálního editoru |
m Robot automaticky nahradil text: (-<br style(.*?)> +{{Clear}}); kosmetické úpravy |
||
Řádek 40:
== Operace se stromem ==
S B-stromem jsou definovanány tak jako v každém jiném stromu základní operace pro vyhledávání, vkládání a mazání dat (klíčů) ze stromu. Mějme strom této struktury : [[Soubor:B-tree-definition.png|thumb|350px|left|Definovaný B-strom]]Písmenka ''k''<sub>i</sub> v něm zastupují klíče, písmenka ''c''<sub>i</sub> značí odkaz na potomky (podstromy). Tento konkrétní strom má jeden klíč v kořenu, tento klíč pak rozděluje zbytek stromu na dvě části - jednu kde jsou uloženy všechny hodnoty které jsou menší než tento klíč, a druhou kde jsou uloženy hodnoty větší. Tyto podstromy jsou pak děleny stejným způsobem do dalších podstromů.
=== Operace vyhledávání ===
Řádek 55:
'''Poznámka''': Pokud má uzel pouze tolik klíčů, že se celý vejde do primární paměti RAM, tak je pak počet diskových operací čtení, které musíme provést při vyhledávání, roven maximálně [[Strom (datová struktura)#Hloubka, Výška, Šířka, Úroveň a Cesta|hloubce stromu]].
{{Clear}}
=== Operace vkládání ===
Řádek 69:
Příklad: Máme B-strom stupně 5 tak, jako je na obrázku. Každý uzel může mít maximálně 4 klíče. Pokud do dítěte chceme uložit další hodnotu, nejde to a uzel se rozpadne. Vkládaný klíč (nemusí to být nutně klíč ''k''<sub>3</sub>, tento klíč je zeleně zvýrazněn protože je ''prostřední'') se virtuálně vloží a poté se vybere prostřední klíč (zeleně). Tento prostřední klíč se poté vloží do rodiče (označen jako ''k''<sub>3</sub>') a původní uzel se rozpadne na dva, tak jak bylo napsáno výše.
{{Clear}}
=== Operace mazání ===
Někdy je nutné vložena data ze stromu také vyjmout, k tomu slouží operace mazání. Pří mazání opět může nastat několik problémů. Nejprve musíme vždy vyhledat požadovanou hodnotu a zjistit v kterém uzlu se nacházela.
Nejjednodušší je vymazávání z listů:
Řádek 93:
'''Poznámka''': Je potřeba dát si pozor na nelistové uzly; v těchto listech musíme spolu s přesouváním klíče přesunout i odkazy na následující podstromy spolu s klíčem.
{{Clear}}
==== Operace přesunutí klíče ====
[[Soubor:B-tree-move.png|thumb|320px|right|Ukázka přesunutí klíče z jednoho uzlu do druhého]]
Řádek 105:
== Poznámka k obrázkům ==
Obrázky které jsou u tohoto článku přiloženy využívají jiné definice B-stromu, který se občas vyskytuje v zahraniční literatuře. Jedná se o definici, kdy řád stromu neurčuje maximální počet potomků, ale maximální počet položek v uzlu. To je jediná změna oproti zde uvedené definici.
;Varianty B-stromů jsou
* klíče v listech nebo klíče uvnitř,
* T je počet klíčů nebo počet pointrů,
* B*,
* B+.
| |||