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 ₀, I ₁,..., I _d-1), kde I_i je interval [ a_i,b_i] 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 m₁ bude oznaΦovat parametr, pro kter² platφ m _{1 £} m /2. Minimßlnφ poΦet nßslednφk∙ uzlu R-stromu bude m ₁.

R-strom je tedy m-ßrnφ strom, kter² mß nßsledujφcφ vlastnosti:

• Ka₧d² jeho nelistov² uzel mß n nßslednφk∙, n Î < m₁, m> ,
• ka₧d² listov² uzel obsahuje n indexov²ch zßznam∙ n Î < m₁, 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 é log_mEù -1, nejhorÜφ hodnota zapln∞nφ uzlu l je m₁/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.