COMPUTERWORLD
pod kapotou
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:

  • Každý jeho nelistový uzel má n následníků, n Î < m1, m> ,
  • každý listový uzel obsahuje n indexových záznamů n Î < m1, m> ,
  • kořen má nejméně dva následníky, není-li listem,
  • všechny cesty v R-stromu jsou stejně dlouhé.

Zřejmě pro E indexových záznamů je třeba v nejhorším případě hloubka R-stromu é logm -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:

  • prostor pokrývaný kostkou z vnitřního uzlu R-stromu,
  • překrytí dvou kostek z vnitřního uzlu R-stromu.

Existují však další možnosti. Vhodným kritérium může být např.

  • minimalizace celkové plochy kostek.

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

  • paměť pro reprezentaci R-stromu.

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>