R-stablo |
R-stabla su stabla strukture podataka slična
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
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.
