![]() |
![]() |
R-stromy
Již několikrát jsme v Databázové abecedě zdůrazňovali důležitost indexace po provoz relační databáze. Podobně je tomu i u databází prostorových objektů. Vzhledem ke geometrickým vlastnostem těchto objektů a hlavně zvláštní povaze prostorových dotazů, vyžaduje taková indexace poněkud odlišný přístup. Nejznámějším technikou pro indexaci prostorových objektů jsou R-stromy navržené Guttmanem v roce 1984. R-strom představuje jednoduchou modifikaci B-stromů známých z relačních databází. Záznamy v listových uzlech R-stromu obsahují ukazatele k datovým objektům reprezentujícím prostorové objekty. Technika používá minimální ohraničující objekty, které nazýváme minimální ohraničující vícerozměrné kostky (MOVK). Databáze d-rozměrných prostorových objektů obsahuje n-tice reprezentující prostorové objekty např. pomocí jednoznačných identifikátorů a dalších event. negeometrických atributů. Vlastní indexace takových objektů je dána pomocí dvojic (I, identifikátor n-tice), přičemž I je MOVK ohraničující odpovídající prostorový objekt. Tyto záznamy budeme nazývat indexové. MOVK má tvar (I 0, I 1,..., I d-1), kde Ii je interval [ ai,bi] popisující ohraničení objektu v dimenzi i. Nelistové uzly obsahují záznamy tvaru (I, ukazatel), přičemž ukazatel ukazuje na podstrom v R-stromu takový, že I pokrývá všechny kostky, které se v něm vyskytují. Tyto záznamy budeme nazývat řídící. Na rozdíl od B-stromu není striktně dodrženo pravidlo o polovičním naplnění uzlů v nejhorším případě. Je-li R-strom m-ární strom, pak m1 bude označovat parametr, pro který platí m 1 £ m /2. Minimální počet následníků uzlu R-stromu bude m 1. R-strom je tedy m-ární strom, který má následující vlastnosti:
Zřejmě pro E indexových záznamů je třeba v nejhorším případě hloubka R-stromu é logmEù -1, nejhorší hodnota zaplnění uzlu l je m1/m. Příklad R-stromu pro m=3 ukazuje obrázek 1. R-strom je struktura dynamická, tj. je založena na štěpení stránek (pro operaci INSERT) a slévání stránek (pro operaci DELETE). Na rozdíl od B-stromů není hledání v R-stromu určeno jednou větví. Protože MOVK v jednotlivých podstromech se mohou překrývat, je možné, že existuje více než jedna možnost, jak pokračovat při prohledávání stromu z jednoho uzlu. Tím je hledání složitější a veškeré optimalizace používané při konstrukci R-stromu jsou založeny na požadavku co nejvíce separovat ohraničující kostky, aby se omezil prostor vyhledávání. Z toho plynou speciální požadavky na algoritmy typu INSERT, kde se realizují různé heuristiky nabízející víceméně uspokojivá řešení daného problému.
I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 I12 I13 I14 I15 I16 I17 I18 I19 I1
I3 I9 I4 I11 I5 I13
![]() I2 I8 I10 I14 I18 I12 I7 I19
I6 I16 I15 I7
Obr. 1 Příklad R-stromu Rozdělení záznamů do dvou uzlů bude děláno tak, aby bylo co nejméně pravděpodobné, že bude potřeba oba uzly při prohledávání zkoušet. Protože uzly jsou navštěvovány z uzlu-předchůdce, je nutné minimalizovat celkový objem kostek v uzlech. Příklad špatného a dobrého štěpení je znázorněn na obrázku 2.
Obr. 2 Špatné a dobré štěpení uzlu R-stromu Pro rozdělení uzlů je možné použít algoritmus uvažující všechny možnosti. Hledá se globální minimum, přičemž algoritmus má exponenciální složitost. Guttman uvádí další algoritmy, lineární a kvadratický, které pouze aproximují řešení. Zmíníme zde kvadratický algoritmus, který má v experimentech lepší chování než lineární. Problém je rozdělen na výběr prvních kostek do uzlů a na připojování dalších. Vyberou se takové dvě první kostky, které by měly největší mrtvý prostor, kdyby patřily do jedné skupiny. Výběr dalších kostek se řídí kritériem co nejmenšího přírůstku, přidáme-li kostku do skupiny. Taková kostka se vybere a do takové skupiny se přiřadí. Protože tento postup může vést k nerovnoměrnému zaplňování obou uzlů, zkouší se doplnit event. zbytek kostek do prázdnějšího uzlu. Při budování R-stromu dynamickým způsobem se používaly následující dva parametry, které byly minimalizovány:
Existují však další možnosti. Vhodným kritérium může být např.
tj. v dvojrozměrném prostoru obvod obdélníků. Protože nejmenší obvod má čtverec, pokrývající MOVK by mohly být čtverce (krychle). Toho lze využít v dotazech typu okno, kde okno je čtverec. Dalším parametrem je pro minimalizaci může být
Jde o to udržet nízkou hloubku R-stromu, což vede k nižší ceně dotazu. Parametry se ovšem ovlivňuje netriviálním způsobem. Např. uplatnění prvních dvou parametrů vyžaduje větší volnost v uzlech, což vede k nižšímu využití paměti. Také kostky budou méně čtvercové. Naopak použití čtverců (krychlí) vede k lepšímu seskupování, tj. k efektivněji využité paměti. Zkušenosti a analýza chování R-stromů ukázaly, že lze nalézt řadu zlepšení. Jedno z nich navrhl Greene, který při štěpení vybere jednu z os, provede řez přímkou a štěpení provádí tak, že využije skupiny kostek tak, jak je určuje dělící přímka. Více optimalizačních kritérii je zahrnuto v R* -stromech, které jsou strukturované stejně jako R-stromy, liší se pouze v algoritmech INSERT a DELETE. Obrázek 3 ukazuje danou situaci.
přeplněný uzel štěpení dle Guttmana
štěpení dle Greena šěpení v R* -stromech Obr. 3 Různé strategie štěpení uzlu R-stromu Je jasné, že R-strom slouží hlavně pro podporu prostorových dotazů. Zkuste si zadat okno ve struktuře na obrázku 1, a hledat v něm motýla. Budete-li mít štěstí, R-strom vás dovede do MOO I12. <seznam dílů seriálu> <COMPUTERWORLD> |