Р стабло

Р стабло је метод за преглед података користећи локацију, често (x, y) координате, а често и за локације на површини Земље. Претраживање за један број је решен проблем; претраживање 2 или више, и захтев за локацијама које су близу у x и y правцима захтева коришћење „лукавијих“ алгоритама.

У основи, Р стабло је стабло структуре података, варијанта Р стабла, које се користи за индексирање просторних информација.

Разлика између Р и Р стабала

Р стабла су компромис између Р-стабла и КД-стабла: оне избегавају преклапање унутрашњих чворова убацивањем објекта у више листова, ако је потребно. Покривеност је цела област која покрива све сродне квадрате. Преклапање је цела област која се налази у два или више чворова.^[1] Минимална покривеност смањује количину празног простора који је покривен чворовима Р стабла. Минимално преклапање смањује скуп путева претраге до листова (што је чак битније за време приступања него за минималну покривеност). Ефикасна претрага захтева минималну покривеност и преклапање.

Р стабла се разликују од Р стабала по:

За чворове се не гарантује да ће бити бар пола попуњени
Ставке било ког унутрашњег чвора се не преклапају
Идентификација објекта може да се чува у више од једног лист-чвора

Предности

Пошто се чворови не преклапају једни са другима, постижу се боље перформансе, јер су сви просторни региони покривени са највише једним чвором.
Иде се једним путем и мање чворова се посећује него у Р стаблу.

Мане

Пошто се квадрати дуплирају, Р стабло може бити веће од Р стабла које је направљено на основу истих података.
Конструкција и одржавање Р* стабла је много компликованије од конструкције и одржавања Р стабла и његових других варијанти.

Референце

^ Härder & Rahm 2007, стр. 285, 286.

Литература

Härder, Theo; Rahm, Erhard (2007). Datenbanksysteme. (2., überarb. Aufl. изд.). Berlin [etc.]: Gardners Books. стр. 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 . . In VLDB, 1987.

[FOOTNOTEHärderRahm2007285,_286-1] Härder & Rahm 2007, стр. 285, 286.

[1]