R-stablo

Jednostavan primjer R-stabla za 2D kvadrate

R-stabla su stabla strukture podataka slična B-stablima, korištena za pristup prostornim podacima tj., za indeksiranje višedimenzijskih informacija; npr., (X, Y) koordinate prostornih podataka. Uobičajena upotreba R-stabla mogla bi biti: "Pronađi sve muzeje unutar 2km od moje trenutne lokacije".

Strukturu podataka dijeli hijerarhijski prostorno ugnježđen, sa mogućim preklapanjem, minimalni obuhvatni kvadrat (MBR, još poznat kao bounding box, tj. "kvadrat (rectangle)", od čega "R" u R-stablu).

Svaki čvor R-stabla ima promjenjiv broj ulaza (do nekog predefiniranog maksimuma). Svakim ulazom unutar ne-lisnog čvora pohranjuju se dva podatka: način identifikacije čvora nasljednika i minimalna obuhvatna kutija svih ulaza unutar čvora nasljednika.

Algoritmi unosa i brisanja obuhvatnih kutija koriste obuhvatne kutije iz čvorova da bi osigurali da su "obližnji" elementi postavljeni u isti lisni čvor (pogotovo, novi element će ići u lisni čvor koji zahtijeva najmanje uvećanje obuhvatne kutije). Svaki ulaz unutar lisnog čvora pohranjuje dva podatka: način identifikacije stvarnog elementa podatka (koji, alternativno, mogu biti postavljeni direktno u čvor), i okvirnu kutiju elementa podatka.

Slično, algoritmi pretrage (naprimjer; presjek, sadržavanje, najbliži) koriste obuhvatne kutije da odrede pretražuju li unutar čvora nasljednika. U tom slučaju, većina čvorova u stablu nisu nikada "dodirnuti" tijekom pretrage. Kao B-stabla, ovo čini R-stabla pogodnim za baze podataka, gdje čvorovi mogu biti pohranjeni u memoriju kad je to potrebno.

Različiti algoritmi mogu biti iskorišteni za razdvojanje čvorova kada oni postanu prepuni, rezultirajući kvadratnom i linearnom podtipu R-stabla.

R-stabla ne jamče tradicionalno dobre performanse u kriznim slučajima, ali generalno se dobro snalaze u stvarnim situacijama. Ipak, novi algoritam koji definira Prioritete u R-stablu je objavnjen 2004. godine i obećava efikasnost kao trenutno najefikasanija metoda i ima isti optimum u kriznim slučajevima.

Varijante

  • R* stablo
  • R+ stablo
  • Hilbertovo R-stablo
  • Prioritetno R-stablo (PR-stablo) - PR-stablo ima performanse slične najboljoj poznatoj varijanti R-stabla u stvarnim situacijama i relevantan raspored podataka, ali ih značajno nadmašuje u ekstremnijim slučajevima.[1]
Other Languages
čeština: R-strom
Deutsch: R-Baum
English: R-tree
español: Árbol-R
עברית: עץ R
italiano: R-tree
日本語: R木
한국어: R 트리
polski: R-drzewo
português: Árvores R
српски / srpski: Р-стабло
українська: R-дерево
中文: R树