R+ stablo

R+ stablo je metod za pregled podataka koristeći lokaciju, često (x, y) koordinate, a često i za lokacije na površini Zemlje. Pretraživanje za jedan broj je rešen problem; pretraživanje 2 ili više, i zahtev za lokacijama koje su blizu u x i y pravcima zahteva korišćenje „lukavijih“ algoritama.

U osnovi, R+ stablo je stablo strukture podataka, varijanta R stabla, koje se koristi za indeksiranje prostornih informacija.

Razlika između R+ i R stabala

R+ stabla su kompromis između R-stabla i KD-stabla: one izbegavaju preklapanje unutrašnjih čvorova ubacivanjem objekta u više listova, ako je potrebno. Pokrivenost je cela oblast koja pokriva sve srodne kvadrate. Preklapanje je cela oblast koja se nalazi u dva ili više čvorova. Minimalna pokrivenost smanjuje količinu praznog prostora koji je pokriven čvorovima R stabla. Minimalno preklapanje smanjuje skup puteva pretrage do listova (što je čak bitnije za vreme pristupanja nego za minimalnu pokrivenost). Efikasna pretraga zahteva minimalnu pokrivenost i preklapanje.

R+ stabla se razlikuju od R stabala po:

• Za čvorove se ne garantuje da će biti bar pola popunjeni
• Stavke bilo kog unutrašnjeg čvora se ne preklapaju
• Identifikacija objekta može da se čuva u više od jednog list-čvora

Prednosti

• Pošto se čvorovi ne preklapaju jedni sa drugima, postižu se bolje performanse, jer su svi prostorni regioni pokriveni sa najviše jednim čvorom.
• Ide se jednim putem i manje čvorova se posećuje nego u R stablu.

Mane

• Pošto se kvadrati dupliraju, R+ stablo može biti veće od R stabla koje je napravljeno na osnovu istih podataka.
• Konstrukcija i održavanje R* stabla je mnogo komplikovanije od konstrukcije i održavanja R stabla i njegovih drugih varijanti.

Literatura

• Härder, Theo; Rahm, Erhard (2007). Datenbanksysteme. (2., überarb. Aufl. izd.). Berlin [etc.]: Gardners Books. str. 285, 286. ISBN 978-3-540-42133-7. 
• T. Sellis, N. Roussopoulos, and C. Faloutsos. „The R+-Tree: A dynamic index for multi-dimensional objects”. CiteSeerX 10.1.1.45.3272 . CS1 održavanje: Višestruka imena: spisak autora (veza). In VLDB, 1987.