B+ strom: Porovnání verzí
Smazaný obsah Přidaný obsah
m →Podívejte se také: Odstranění hloupého odkazu na vlastní článek |
Přídání implementace, char.vlastností, historie, vše z EN wiki a z http://www.cecs.csulb.edu/~monge/classes/share/B+TreeIndexes.html |
||
Řádek 11:
*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>).
*[[Strom (datová struktura)#Kořen stromu|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 <math>n = b^h</math>
* Minimální počet klíčů je <math>2(b/2)^{h-1}</math>
* Místo požadované pro uložení stromu je <math>O(n)</math>
* Vložení záznamu do stromu vyžaduje v nejhorším případě <math>O(\log_bn)</math> operací
* Vyhledání záznamu v nejhorším případě vyžaduje <math>O(\log_bn)</math> operací
* Vymazání (dříve nalezeného) záznamu v nejhorším případě vyžaduje <math>O(\log_bn)</math> operací
* Vyhledání více položek v rámci zadaného rozsahu trvá v nejhorším případe <math>O(\log_bn+k)</math> 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ímy 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.
Tento mechanismus odkazů na následujícího sourozence je zobrazen i na obrázku červenými políčky.
== Použití B+ stromu ==
Řádek 17 ⟶ 32:
Tento systém používají pro indexování dat na disku jak [[Souborový systém|souborový systém]] [[NTFS]] pod [[Windows]], tak [[Souborový systém|souborový systém]] [[ReiserFS]] pod [[Unix]]em a [[Linux]]em, [[Souborový systém|systém]] [[XFS]] pod [[Linux]]em a [[IRIX]]em i [[Souborový systém|systém]] [[JFS2]] pod [[Linux]]em, [[OS/2]] a pod [[AIX]].
[[Relační databáze]] také často používají tento typ [[Strom (datová struktura)|stromu]] pro ukládání tabulek s indexy.
== Historie ==
B+ strom byl poprvé popsán v článku
"Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972)".
== Podívejte se také ==
Řádek 25 ⟶ 45:
* [[UB strom]]
[[Kategorie:Stromy (datové struktury)]]
[[en:B+ tree]]
| |||