B+ strom: Porovnání verzí

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

*Všechny [[Strom (datová struktura)#Uzly ve stromu|uzly]] kromě kořene mají maximálně ''nN'' a minimálně ''nN/2'' potomků (přesněji:<math>\left \lceil \frac{n}{2} \right \rceil -1 </math>).

*[[Strom (datová struktura)#Kořen stromu|Kořen]] má nejvýše ''nN'' potomků, spodní hranice není omezena.

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

* Maximální počet uložených záznamů je <math>nN = bB^hH</math>

* Minimální počet klíčů je <math>2(bB/2)^{hH-1}</math>

* Místo požadované pro uložení stromu je <math>O(nN)</math>

* Vložení záznamu do stromu vyžaduje v nejhorším případě <math>O(\log_bnlog_BN)</math> operací

* Vyhledání záznamu v nejhorším případě vyžaduje <math>O(\log_bnlog_BN)</math> operací

* Vymazání (dříve nalezeného) záznamu v nejhorším případě vyžaduje <math>O(\log_bnlog_BN)</math> operací

* Vyhledání více položek v rámci zadaného rozsahu trvá v nejhorším případe <math>O(\log_bnlog_BN+kK)</math> operací (''kK'' je zde počet položek vyskytujících se v dotazovaném rozsahu)

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ímypracujícími s rozsahy typu ''vrať všechny záznamy kde plat je mezi 10000-2000''. 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.

'''B+ strom''' Jeje 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 ''bB'', do '''B+ stromu''' se uloží počet klíčů který je roven násobku ''bB'' a čtení celého bloku dat je velice efektivní oproti [[Binární vyhledávací strom|binárnímu vyhledávacímu stromu]] (což je odpovídající blokově neorientovaná alternativa).