B-strom
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
B-strom je druh stromu. Je specifický tím, že má řád a limity na maximální (), i minimální () 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.
B-strom řádu n je takový strom, který splňuje tyto vlastnosti:
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.
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 k1 a k2, které budou uzel rozdělovat. Všechny hodnoty které jsou menší než k1 musí být uloženy v levém podstromu, hodnoty které jsou větší než k1 a menší než k2 musí být uloženy v prostředním podstromu, a konečně všechny hodnoty větší než k2 musí být v pravém podstromu. Na tyto podstromy jsou samozřejmě v uzlu uloženy ukazatele.
B-stromem stupně n rozumíme strom, splňující následující podmínky:
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 :
Písmenka ki v něm zastupují klíče, písmenka ci 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ů.
Vyhledávání v B-stromu je velice jednoduché. Rozdělíme ho do několika kroků:
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 c2 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.
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.
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.
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íč k3, 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 k3') a původní uzel se rozpadne na dva, tak jak bylo napsáno výše.
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ů:
Při vymazávání z nelistových položek si musíme dát pozor, abychom neponičili strukturu stromu:
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.
Pokud chceme spojit dva uzly, musíme v zásadě provést 2 kroky:
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.
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 k1 se přesune do levého podstromu jako odkaz napravo od posledního klíče.
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.