B-strom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. února 2015; kontroly vyžadují 46 úprav .

B-strom (vyslovováno v ruštině jako B-strom ) je datová struktura , vyhledávací strom. Z hlediska vnější logické reprezentace - vyvážený , vysoce rozvětvený strom . Často se používá k ukládání dat do externí paměti.

Použití B-stromů bylo poprvé navrženo R. Bayerem a E. McCreightem v roce 1970 .

Vyvážený znamená, že délky libovolných dvou cest od kořene k listům se neliší o více než jednu.

Větvení stromu je vlastnost každého uzlu stromu odkazovat na velký počet následných uzlů.

Z hlediska fyzické organizace je B-strom reprezentován jako multilistová struktura paměťových stránek, to znamená, že každý uzel stromu odpovídá paměťovému bloku (stránce). Vnitřní a listové stránky mají obvykle jinou strukturu.

Aplikace

Struktura B-stromu se používá k uspořádání indexů v mnoha moderních DBMS .

B-strom lze použít ke strukturování (indexování) informací na pevném disku (obvykle metadata). Doba přístupu k libovolnému bloku na pevném disku je velmi dlouhá (řádově milisekundy), protože je určena rychlostí rotace disku a pohybu hlavy. Proto je důležité snížit počet uzlů skenovaných při každé operaci. Použití vyhledávání v seznamu pokaždé k nalezení náhodného bloku by mohlo vést k nadměrnému počtu přístupů na disk kvůli nutnosti postupně procházet všemi jeho prvky předcházejícími danému, zatímco hledání v B-stromu kvůli vlastnostem rovnováhu a vysoké větvení, může výrazně snížit počet takových operací.

Relativně jednoduchá implementace algoritmů a existence hotových knihoven (včetně těch pro C ) pro práci se strukturou B-stromu činí takovou organizaci paměti oblíbenou v široké škále programů, které pracují s velkým množstvím dat.

Struktura a principy konstrukce

B-strom je strom, který splňuje následující vlastnosti:

Klíče v každém uzlu jsou obvykle objednány pro snadný přístup. Kořen obsahuje od 1 do 2t-1 klíčů. Jakýkoli jiný uzel obsahuje klíče od t-1 do 2t-1. Listy nejsou výjimkou z tohoto pravidla. Zde t je parametr stromu, který je alespoň 2 (a obvykle nabývá hodnot od 50 do 2000 [1] ).
Listy nemají potomky. Jakýkoli jiný uzel obsahující klíče , …, , obsahuje potomky. V čem $K_1$ $K_n$ $n+1$
1. První potomek a všechny jeho potomky obsahují klíče z intervalu $(-\infty, K_1)$
2. Pro i-té dítě a všechny jeho potomky obsahují klíče z intervalu $2\le i\le n$ $(K_{i-1}, K_i)$
3. $(n+1)$ -th child a všechny jeho potomky obsahují klíče z intervalu $(K_n,\infty)$
Hloubka všech listů je stejná.

Vlastnost 2 lze uvést různě: každý uzel B-stromu, kromě listů, lze považovat za uspořádaný seznam, ve kterém se střídají klíče a ukazatele na potomky.

Hledat

Pokud je klíč obsažen v kořenovém adresáři, je nalezen. V opačném případě určíme interval a přejdeme k odpovídajícímu potomkovi. opakujeme.

Přidání klíče

Strom potomků určitého uzlu budeme nazývat podstrom skládající se z tohoto uzlu a jeho potomků.

Nejprve definujme funkci, která přidá klíč K do potomka stromu uzlu x. Po provedení funkce bude ve všech předávaných uzlech, snad kromě samotného uzlu x, méně než , ale ne méně než , klíčů. $2t-1$ $t-1$

Pokud x není list,
1. Určíme interval, kde má být K. Nechť y je odpovídající potomek.
2. Rekurzivně přidejte K do potomka y.
3. Pokud je uzel y plný, to znamená, že obsahuje klíče, rozdělíme ho na dva. Uzel obdrží první z klíčů y a první ze svých potomků a uzel obdrží poslední z klíčů y a poslední ze svých potomků. Medián klíčů uzlu y jde do uzlu x a ukazatel na y v uzlu x je nahrazen ukazateli na uzly a . $2t-1$ $y_1$ $t-1$ $t$ $y_2$ $t-1$ $t$ $y_1$ $y_2$
Pokud je x list, stačí tam přidat klíč K.

Nyní definujeme přidání klíče K do celého stromu. Písmeno R znamená kořenový uzel.

Přidejte K do potomka R.
Pokud R nyní obsahuje klíče, rozdělte jej na dva. Uzel obdrží první z klíčů R a první ze svých potomků a uzel obdrží poslední z klíčů R a poslední ze svých potomků. Medián klíčů uzlu R spadá do nově vytvořeného uzlu, který se stává kořenovým uzlem. Uzly se stávají jeho potomky . $2t-1$ $R_{1}$ $t-1$ $t$ $R_{2}$ $t-1$ $t$ $R_{1}$ $R_{2}$

Odebrání klíče

Pokud je kořen také list, to znamená, že ve stromu je pouze jeden uzel, jednoduše odstraníme klíč z tohoto uzlu. Jinak nejprve najdeme uzel obsahující klíč a pamatujeme si cestu k němu. Nechte tento uzel být . $X$

Pokud - list, odstraňte klíč odtud. Pokud v uzlu zbývá alespoň klíčů , zastavíme se. Jinak se podíváme na počet klíčů ve dvou sousedních sourozeneckých uzlech. Pokud existuje sousední pravý uzel a má alespoň klíčů, přidáme k oddělovacímu klíči mezi ním a sousedním pravým uzlem a místo tohoto klíče vložíme první klíč sousedního pravého uzlu, načež zastavíme . Pokud tomu tak není, ale existuje sousední levý uzel a má alespoň klíčů, přidáme k oddělovacímu klíči mezi ním a sousedním levým uzlem a místo tohoto klíče vložíme poslední klíč sousedního levý uzel, po kterém se zastavíme. Nakonec, pokud levý klíč selže, sloučíme uzel se sousedním levým nebo pravým uzlem a přesuneme klíč, který předtím odděloval tyto dva uzly, do sloučeného uzlu. V tomto případě mohou v nadřazeném uzlu zůstat pouze klíče . Pak, pokud se nejedná o kořen, provedeme s ním podobný postup. Pokud jsme v důsledku toho dosáhli kořene a zbývají v něm klíče od 1 do, není třeba nic dělat, protože kořen může mít méně klíčů. Pokud v kořenu nezůstal jediný klíč, vyloučíme kořenový uzel a jeho jediného potomka uděláme novým kořenem stromu. $X$ $X$ $t-1$ $t$ $X$ $t$ $X$ $X$ $t-2$ $t-1$ $t-1$

Pokud není list a K je jeho -tý klíč, odstraňte klíč zcela vpravo z podstromu potomků -tého potomka nebo naopak klíč zcela vlevo z podstromu potomků -tého potomka . Poté nahradíme klíč K dálkovým klíčem. K odstranění klíče dojde tak, jak je popsáno v předchozím odstavci. $X$ $i$ $i$ $X$ $i+1$ $X$

Hlavní výhody

Ve všech případech je užitečné využití sekundárního úložného prostoru přes 50 %. S rostoucím využitím paměti nedochází ke snížení kvality služeb.
Náhodný přístup k záznamu je realizován prostřednictvím malého počtu dílčích operací (odkazů na fyzické bloky).
Operace vkládání a mazání záznamů jsou v průměru implementovány poměrně efektivně; při zachování přirozeného pořadí klíčů pro sekvenční zpracování a také vhodného vyvážení stromu pro zajištění rychlého náhodného vzorkování.
Neměnné řazení podle klíče umožňuje efektivní dávkové zpracování.

Hlavní nevýhodou B-stromů je, že nemají efektivní prostředky pro získávání dat (tj. metodu procházení stromem) uspořádaných jinou vlastností, než je zvolený klíč.

Viz také

Hloubka první hledání
Šířka první hledání
Vyvážené (samobalanční) stromy:

Seznam datových struktur (stromů)

Poznámky

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Kapitola 18. B-stromy // Algoritmy: Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Literatura

Levitin A. V. Kapitola 7. Časoprostorový kompromis: B-stromy // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 331-339. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Kapitola 18. B-stromy // Algoritmy: Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Odkazy

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree