![]() |
![]() |
B-stromy
Stromy patří k nejobvyklejším metodám organizace dat na vnějších pamětech s přímým přístupem, protože umožňují asociativní přístup i sekvenční zpracování dat podle vzestupného (nebo sestupného) uspořádání klíčů. Představují tedy způsob implementace indexu. Na jejich statické verzi byly založeny již první implementace indexsekvenční metody v 60. letech. Dynamickou stromovou strukturou byl historický produkt IBM VSAM, ještě před objevem B-stromů, na stromech byly již v polovině 60. let založeny datové struktury dnes všeobecně známého relačního SŘBD ADABAS. Vzhledem k charakteristickým vlastnostem vnějších pamětí jsou uzly stromu tvořeny stránkami (obvykle pevné délky), do nichž se snažíme umístit co nejvíce dat. Tato data budou tvořena záznamy, podobně jako u klasického indexu, tj. < klíč, adresa> , kde klíč je hodnota atributu, podle kterého indexujeme a adresa ukazuje na uzel-následník ve stromě, případně na seznam adres záznamů, nebo přímo do primárního souboru (či databázové tabulky). Idea je jednoduchá. Lze vyjít např. z binárních vyhledávacích stromů (BVS), kde množina klíčů, např. přirozených čísel, je umístěna do uzlů stromu tak, že je zachováno uspořádání čísel. Na obr. 1 je ukázka takového stromu. Hledáme-li např. klíč 7, postupuje se z kořene stromu levou cestou, pak pravou, tj. ve 3. kroku je klíč nalezen. 9 6 11 2 7 Obr. 1 Binární vyhledávací strom Využít BVS pro indexování relací přímo nelze, protože není jednoduše zobrazitelný do stránek na disku. Navíc, pro velkou množinu klíčů, je stále moc hluboký. Např. pro 524 288 (tj. 219) by měl v lepším případě takový strom hloubku log2524 288, tj. 19, a to by při nevhodné organizaci na disku mohlo znamenat příliš mnoho čtení stránek do vnitřní paměti. Problém vyřešil v r. 1972 článek “Organization and maintenance of large ordered indices” o B-stromech pánů Bayera a McCrighta v časopise Acta Informatica. Šlo zase o hezký příklad ovlivnění teorie praxí. B-stromy totiž byly vyvinuty při řešení praktického problému - uspořádání součástek v rámci informačního systému Boeing Company. Myšlenka jejich tvůrců spočívala na zobecnění BVS, tj. použil se m-ární strom, kde každý uzel má nejvýše m následníků. Budeme dále pro zjednodušení předpokládat, že m je sudé. Protože variant definici B-stromů je více, uvedeme zde tu, která se vyskytuje v relačních SŘBD pro implementaci indexu nejčastěji. B-strom (řádu m) je m-ární strom, splňující následující omezení:
p0,(k1,p1),(k2,p2),...,(kn,pn),u kde p0,p1,...,pn jsou ukazatele na potomky, k1,k2,...,kn jsou klíče, u je nevyužitý prostor a záznamy (ki,pi) jsou uspořádány vzestupně podle klíčů, přičemž m/2 -1 £ n £ m-1.
(i) pro každé k v U(pi-1) je k £ k i, (ii) pro každé k v U(pi) je k > k i,
Z (i) plyne, že klíče ve vnitřních uzlech B-stromu jsou pouze rozhodovací, podstatná je existence klíče v listovém uzlu. Ukazatele pi v listech již ukazují do primárního souboru nebo na seznamy ukazatelů apod. Spokojme se s tím, že jde o implementačně závislou část definice B-stromu. Na obrázku 2 je B-strom s m=3, do jehož uzlu lze umístit jeden až dva klíče, z vnitřního uzlu se lze dostat dvou až třech podstromů. V grafickém vyjádření existuje ještě místo pro třetí klíč, což není v souladu s definicí. Můžeme si je však interpretovat jako nevyužité místo u z definice B-stromu. Uzly jsou očíslovány přirozenými čísly (adresy stránek), ukazatele Zi v listech ukazují na datové struktury mimo B-strom. 6 Karla - - 2 5 -
2 5 F.L .Věk - - Matka - - 0 4 - 3 1 -
0 4 Babička F.L.Věk - Karla - - Z3 Z5 - Z1 - - 3 1 Matka - - Poklad Pustina - Z0 - - Z2 Z4 Obr. 2 B-strom Samotná struktura B-stromu ovšem není to nejpodstatnější. Ke struktuře patří algoritmy operací INSERT a DELETE, které podporují to, čemu říkáme dynamika struktury. Algoritmy jsou stavěny tak, že struktura se “zvětšuje” s počtem přibývajících klíčů, či “zmenšuje” s počtem ubývajících klíčů. Důležitým pojmem zde je štěpení, resp. slévání stránek. Na obrázku 3 a) je ukázána situace před provedením operace INSERT(Babička), na 3 b) situace poté. 2 Matka - - a) před INSERT(Babička) 0 1 - -
0 1 Karla Matka - Poklad - - Z1 Z0 - Z2 - - 2 Karla Matka - b) po INSERT(Babička) 0 3 1
0 3 1 Babička Karla - Matka - - Poklad Z3 Z1 - Z0 - - Z2 Obr. 3 Vkládání do B-stromu Algoritmus INSERT hledá místo (listový uzel), kam patří vkládaný klíč a v případě, že je uzel obsazen, štěpí stránku, tj. starou nahrazuje dvojicí (stará, nová). Polovina klíčů staré stránky jde do staré, polovina do nové, dále se obě stránky musí připojit do uzlu-předchůdce. To znamená další vkládání klíče a event. další štěpení. Bylo dokázáno, že tímto způsobem se uzly obsadí v průměru ze 69%, tj. je třeba pamatovat, že v B-stromech se trochu hýří místem. Výhoda je však v malém počtu přístupů na disk. Lze si snadno spočítat, že při velikosti m řádově stovky bude mít B-strom v průměrné aplikaci hloubku 2-3. O B-stromech by se toho dalo říci ještě moc. Lze jim např. provázat listy ukazateli, což vede k tzv. B+-stromům. Umožňují získat snadno sekvenci záznamů uspořádanou dle daného klíče, aniž by se prolézal celý B-strom. Závěrem snad už jen jedno. Co znamená to B? Autoři tvrdí, že je to od “Balanced” (vyvážený). Někteří se domnívají, že se tím zvěčnil jeden z autorů. Jedno je však jisté: s “Binary” (jak se občas někdo naivně myslí) to nemá nic společného. <seznam dílů seriálu> <COMPUTERWORLD> |