Wikipedie

B-strom: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
→‎Formální definice: upravil jsm vzorce pro # položek/potomků podle toho co je na EN wikipedii (a toho co nás učili na MFF)
Oprava definice stromu - strom stupně n má v uzlu nejvýše n-1 položek a n potomků - dle skript z MFF UK (např zde http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/pokorny/ )
Řádek 1:
'''B-strom''' je druh [[strom (datová struktura)|stromu]]. Jeho zvláštností je, že zavádí limity na maximální (konstantou ''n''), i minimální (''<math>\left \lceil \frac{n''/}{2} \right \rceil</math>) počet potomků vrcholu. B-strom je díky této vlastnosti ''vyvážený'', operace přidání, vyjmutí i vyhledávání tedy probíhají v logaritmickém [[Asymptotická složitost|čase]]. Tato struktura je často používána v aplikacích, kdy není celá struktura uložena v paměti RAM, ale v nějaké sekundární paměti, jako je [[pevný disk]] (například [[databáze]]). Protože přístup do tohoto typu paměti je náročný na čas (hlavně vyhledání náhodné položky), snažíme se minimalizovat počet přístupů do této paměti.
 
Příklad: Máme-li B-strom hloubky 2 a počet potomků každého uzlu je 1001, můžeme do něj uložit milion klíčů a ke každé položce se dostaneme maximálně po dvou diskových operacích.
Řádek 11:
 
*Všechny [[Strom (datová struktura)#Koncové uzly|listy]] (tj.uzly které nemají žádné potomky) jsou na stejné úrovní (ve stejné [[Strom (datová struktura)#Hloubka, Výška, Šířka, Úroveň a Cesta|hloubce]]).
*Všechny [[Strom (datová struktura)#Uzly ve stromu|uzly]] kromě kořene mají maximálně ''n'' a minimálně ''n/2'' potomků (přesněji:<math>\left \lceil \frac{n}{2} \right \rceil -1 </math>) potomků.
*[[Strom (datová struktura)#Kořen stromu|Kořen]] má nejvýše ''n'' potomků, spodní hranice není omezena.
 
Řádek 22:
Data jsou ve stromu uložena jako setříděné hodnoty, které rozdělují strom na jednotlivé [[Strom (datová struktura)#Podstrom|podstromy]]. Například pokud nějaký uzel má tři potomky, musí být v tomto uzlu uloženy dva klíče ''k''<sub>1</sub> a ''k''<sub>2</sub>, které budou uzel rozdělovat. Všechny hodnoty které jsou menší než ''k''<sub>1</sub> musí být uloženy v levém podstromu, hodnoty které jsou větší než ''k''<sub>1</sub> a menší než ''k''<sub>2</sub> musí být uloženy v prostředním podstromu, a konečně všechny hodnoty větší než ''k''<sub>2</sub> musí být v pravém podstromu. Na tyto podstromy jsou samozřejmě v uzlu uloženy ukazatele.
 
*List tedy obsahuje ''<math>\left \lceil \frac{n/}{2''} \right \rceil -1</math> až ''n-1'' klíčů a neobsahuje žádný ukazatel na podstrom.
*Vnitřní uzel (tj. takový uzel, který není listem ani kořenem) obsahuje stejný počet klíčů ''k'', ale tyto klíče rozdělují potomky tohoto uzlu do ''k+1'' podstromů.
*Kořen ma maximálně ''n-1'' klíčů a nemusí mít žádné potomky - v tom případě je pak zároveň listem.
 
== Formální definice ==
Řádek 64:
 
 
Příklad: Máme B-strom stupně 5 tak, jakjako 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 virtualně 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.
 
<br style="clear: both;" />
Citováno z „https://cs.wikipedia.org/wiki/B-strom“