B-strom

B-strom je druh stromu. Je specifický tím, že má řád $n$ a limity na maximální ( $n$ ), i minimální ( $\left\lceil {\frac {n}{2}}\right\rceil$ ) 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 čase. Tato struktura je často používána v aplikacích, kdy není celá struktura uložena v operační 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 1 001, můžeme do něj uložit miliardu klíčů (obsahuje milion uzlů) a ke každé položce se dostaneme maximálně po dvou diskových operacích.

B-strom je speciální případ (a,b)-stromu, který poskytuje větší volnost ve volbě minimálního a maximálního počtu potomků než B-strom.

Autoři algoritmu, Rudolf Bayer a Ed McCreight, nikdy nevysvětlili, co v názvu znamená písmeno B. Nejčastěji se předpokládá, že znamená balanced (v angličtině vyvážený), jelikož všechny listy jsou na stejné úrovni stromu. B může být také první písmeno jména Bayer, případně Boeing, oba totiž v té době pracovali ve výzkumném ústavu této firmy.

Základní informace

B-strom řádu n je takový strom, který splňuje tyto vlastnosti:

Všechny listy (tj. uzly které nemají žádné potomky) jsou na stejné úrovni (ve stejné hloubce).
Všechny vnitřní uzly kromě kořene mají maximálně n a minimálně $\left\lceil {\frac {n}{2}}\right\rceil$ potomků.
Kořen má nejvýše n potomků, spodní hranice není omezena.

Pokud chceme vložit nebo smazat data (klíče) z uzlu, změní se tím počet potomků tohoto uzlu. Aby se dodržel rozsah daný řádem stromu, vnitřní uzly se v případě potřeby rozdělují či slučují. Protože počet potomků každého uzlu je omezený, není potřeba vyvažovat tento strom tak často jako jiné typy automaticky vyvažovaných stromů. Jelikož strom je málokdy zcela zaplněný, musíme počítat s tím, že může docházet k nevyužití veškeré obsazené paměti (většinou to ale není překážkou).

Strom je vyvažován požadavkem, aby byly všechny listy na stejné úrovni. Tato hloubka pozvolna logaritmicky roste s tím, jak do stromu přidáváme další data, nebo klesá spolu s vymazáváním dat ze stromu.

Princip uložení dat

Data jsou ve stromu uložena jako setříděné hodnoty, které rozdělují strom na jednotlivé podstromy. Například pokud nějaký uzel má tři potomky, musí být v tomto uzlu uloženy dva klíče k₁ a k₂, které budou uzel rozdělovat. Všechny hodnoty které jsou menší než k₁ musí být uloženy v levém podstromu, hodnoty které jsou větší než k₁ a menší než k₂ musí být uloženy v prostředním podstromu, a konečně všechny hodnoty větší než k₂ musí být v pravém podstromu. Na tyto podstromy jsou samozřejmě v uzlu uloženy ukazatele.

List tedy obsahuje $\left\lceil {\frac {n}{2}}\right\rceil -1$ 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 má maximálně n−1 klíčů a nemusí mít žádné potomky – v tom případě je pak zároveň listem.

Formální definice

B-stromem stupně n rozumíme strom, splňující následující podmínky:

Kořen má nejméně dva potomky, pokud není listem
Každý uzel kromě kořene a listu má nejméně $\left\lceil {\frac {n}{2}}\right\rceil$ a nejvýše n potomků.
Každý uzel kromě kořene má nejméně $\left\lceil {\frac {n}{2}}\right\rceil -1$ a nejvýše n−1 položek.
Všechny cesty od kořene k listům jsou stejně dlouhé
Data v uzlu jsou organizována tak, aby logicky vytvářela posloupnost $p_{0},k_{1},p_{1},k_{2},p_{2}\ldots$ , kde k označují klíčové atributy ukládaných dat, takové, že pro ně jde zavést relace uspořádání <, a $p_{i}$ označují odkazy na podstromy. Pro každé $k_{i},k_{j},i<j$ je $k_{i}<k_{j}$
Pro každé k v podstromě odpovídajícím odkazu $p_{i-1}$ , platí $k<k_{i}$
Pro každé k v podstromě odpovídajícím odkazu $p_{i}$ , platí $k>k_{i}$

Operace se stromem

S B-stromem jsou definová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 :

Definovaný B-strom

Písmenka k_i v něm zastupují klíče, písmenka c_i 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í

Vyhledávání v B-stromu je velice jednoduché. Rozdělíme ho do několika kroků:

Načteme celý uzel (v případě, že začínáme s hledáním, je to kořen)
Prohledáváme v tomto uzlu zleva doprava všechny klíče, dokud nenalezneme hodnotu klíče, která je stejná nebo větší než požadovaná hodnota.
1. Pokud je hodnota tohoto klíče stejná s hledanou, skočíme na krok číslo 4.
2. Pokud je hodnota tohoto klíče větší a aktuální uzel není listem, zapamatujeme si ukazatel vlevo od tohoto klíče. Pokud je aktuální uzel zároveň listem, skočíme na krok číslo 5 (není již kde vyhledávat).
V případě, že máme z minulého kroku ukazatel, následujeme ho a pokračujeme krokem jedna. V případě, že ukazatel není k dispozici, znamená to, že musíme následovat ukazatel, který je nejvíce vpravo (hledaná hodnota je větší než klíč s největší hodnotou v tomto uzlu).
Nalezli jsme požadovanou hodnotu, končíme.

Ukázka vyhledávání v B-stromu
Nenalezli jsme požadovanou hodnotu, končíme.

Příklad: Hledáme klíč s hodnotou číslo 9 v B-stromu na obrázku vpravo. Prohledáváme všechny hodnoty v uzlu, dokud nenarazíme na hodnotu, která je větší než 9. Touto hodnotou je číslo 13. Následujeme ukazatel c₂ na potomka a dostaneme se tak do dalšího uzlu. Pokud by již tento uzel byl listem, číslo 9 by v případě, že by se ve stromu vyskytovalo bylo v tomto uzlu. Pokud by tento uzel nebyl listem, mohli bychom pokračovat stejným způsobem.

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ě hloubce stromu.

Operace vkládání

Pokud přidáváme data do stromu, může nastat několik možností. V ideálním případě se požadovaná data vejdou do správného uzlu. V tomto případě je pouze vložíme do tohoto správného uzlu (ten nalezneme obdobným vyhledávacím algoritmem vyhledávání) a nemusíme již dělat žádnou dodatečnou manipulaci se stromem.

Rozpadání uzlu

Pokud je uzel moc plný (má n−1 klíčů), je nezbytné ho rozdělit na dva uzly. Tato operace se provede tak, že se vybere prostřední klíč z tohoto potenciálně přeplněného uzlu a ten se přemístí do svého rodiče. Vytvoří se nový uzel, do kterého přesuneme všechny klíče vpravo od toho prostředního. Klíče vlevo od prostředního zůstávají v původním uzlu.

Samozřejmě, že pokud přidáváme klíč do rodiče, musíme zkontrolovat, jestli se do něj vejde a pokud ne, musíme ho rozdělit stejným způsobem. Pokud se takovýmto postupem dostaneme až do kořene, musíme vytvořit nový kořen s pouze jednou položkou, která nám původní kořen rozdělí na dvě části.

Ukázka rozpadnutí jednoho uzlu ve dva

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₃, 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₃') a původní uzel se rozpadne na dva, tak jak bylo napsáno výše.

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ů:

Pokud je v listu dost klíčů na to, aby i po vymazání jednoho klíče splňoval definici B-stromu, můžeme rovnou daný klíč vyjmout.
Pokud by po odebrání jednoho klíče již tento uzel nesplňoval definici B-stromu, musíme provést některé dodatečné změny. Pokud má sourozenecký uzel minimální počet klíčů, můžeme tyto dva sourozenecké uzly spojit. Pokud má sourozenecký uzel více klíčů než je minimální počet, můžeme z tohoto sourozeneckého uzlu jeden klíč přesunout, poté pak bude mít náš uzel dostatečný počet klíčů.

Při vymazávání z nelistových položek si musíme dát pozor, abychom neponičili strukturu stromu:

Pří mazání klíče z nelistové položky nejprve tento klíč najdeme, smažeme ho a na jeho místo přesuneme jeho prvního následovníka (jelikož víme jak jsou data ve stromu uložena, tak to již není problém). Musíme si samozřejmě dát pozor aby při odebírání nebyl v některém uzlu nedostatečný počet klíčů, teď již však máme aparát na to, abychom to mohli napravit.

Je vidět že tato implementace mazaní není jednoprůchodová, vždy nejprve vymažeme zadaný klíč a poté uvádíme strom do vyváženého stavu. Je možné postupovat i jiným způsobem, kdy při procházení uzlů provedeme úpravu struktury stromu tak, abychom mohli po nalezení vymazávané položky ji rovnou odstranit bez dalších operací a kontrol.

Operace spojení uzlů

Ukázka spojení dvou uzlů v jeden

Pokud chceme spojit dva uzly, musíme v zásadě provést 2 kroky:

Přesuneme všechny klíče z pravého sourozence do levého, tento pravý podstrom následně zrušíme.
Do tohoto společného potomka následně přesuneme i klíč který je odděloval v rodiči (na ilustrativním obrázku zelený klíč k₁)

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.

Operace přesunutí klíče

Ukázka přesunutí klíče z jednoho uzlu do druhého

Přesunutí klíče z jednoho sourozence do druhého – uvažujme přesunutí klíče z pravého podstromu do levého, tak jak je to znázorněno na obrázku.

Ve skutečnosti se daný klíč nepřesune do svého levého sourozeneckého uzlu, ale do svého rodiče; v tomto rodiči nahradí klíč který doteď odděloval tyto dva sourozence a ten se zase posune do levého sourozence. Lépe je to vidět na obrázku.

Poznámka: Opět si musíme uvědomit, že při přesouvání klíčů v nelistových uzlech musíme dát pozor na správné přesunutí také všech odkazů na potomky. V uvažovaném případě například odkaz na levý podstrom zeleného klíče k₁ se přesune do levého podstromu jako odkaz napravo od posledního klíče.

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+.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu B-strom na Wikimedia Commons
Vizualizace B-stromu