Р+ стабло
Р+ стабло је метод за преглед података користећи локацију, често (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.
