R* стабла
Р*-стабла су варијанта Р-стабала која се користе за индексирање просторних информација. Р*-стабла имају незнатно већу цену конструкције од стандардних Р*-стабала, због могућности поновног уноса
података;али добијено дрво ће углавном имати бољe перформансе упита. Као и стандардно Р-стабло, Р*-стабло може складиштити и показивачке и просторне податке. Предложено је од стране Норберта Бекмана, Ханс–Питера Кригела, Ралфа Шнајдера, и Бернарда Сигера 1990. године.[1]
Разлике између Р*-стабала и Р-стабала
Минимизација и покривености и преклапања је круцијална за перформансе Р-стабала. Преклапање значи да у подацима упита или уметања, више од једне гране стабла мора бити проширена (услед тога што се подаци деле у секције које се могу преклапати). Минимална покривеност унапређује перформансе орезивања, што дозвољава искључивање читавих страница из претраге чешће него иначе, у пракси за упите негативног домета.
Р*-стабло покушава да смањи оба, коришћењем комбинације прерађеног чвора подељеног алгоритма и концепта насилног поновног уметања у чвор преливања. Ово је базирано на запажању да су структуре Р-стабала врло осетљиве до границе у којој се уноси убацују, за тако изграђене структуре са појединачним уносом, (радије него структуре са више уноса одједном) је већа могућност да буду суб-оптималне. Брисање, и поновно убацивање уноса помаже им да „нађу“ место у стаблу које им више одговара него оригинална локација.
Када дође до преливања чвора, део уноса бива уклоњен из чвора и поново убачен у стабло. (У циљу избегавања неодређених каскада поновног убацивања уноса узрокованим наредног преливајућег чвора, рутина поновног уметања уноса може бити позвана само једном у сваком нивоу стабла приликом уношења било којег новог уноса). Ово има ефекат производње више добро-кластерованих група уноса у чворовима, смањујући покривеност чвора. Штавише сама дељења чвора су често одложена, што проузрокује раст просечног заузимања чвора. Поновно уметање може се посматрати као метод инкременталне оптимизације стабла, изазване чвором преливања.
Перформансе
- Побољшане издељене хеуристике производе стране које су више правоугаоне, и на тај начин бољe за многе апликације
- Метод поновног уноса оптимизује постојеће стабло, али му повећава и комплексност.
- Ефикасно подржава показивачке и просторне податке истовремено.
Алгоритам и комплексност
- Р*-стабло користи исти алгоритам за брисање и упит операција као и Р-стабло.
- Приликом уноса Р*-стабло користи комбиновану стратегију. За чворове листа, преклапање је минимизовано, док за унутрашње чворове проширења и област су минимизовани.
- Приликом дељења, Р*-стабла користе тополошко дељење, које бира издељену осу базирану на параметрима, затим минимизује преклапања.
- Додатно побољшаној стратегији дељења, Р*-стабло такође покушава да избегне дељења поновним уносом објеката и подстабала у стабло, инспирисано концептом балансирајућег Б-стабла.
Очигледно, најгори случај комплексности упита и брисања су идентична Р-стаблу. Стратегија уноса код Р*-стабала је са комплекснија него линеарна стратегија дељења () Р-стабала, али мање комплексна него квадратна стратегија дељења () за страну величине од објеката и има мало утицаја на укупну сложеност. Укупна сложеност уноса још увек може да се пореди са Р-стаблима: поновна убацивања утичу највише на једну грану стабла и тако поновних уноса, у поређењу са обављањем дељења на регуларном Р-стаблу. Све у свему, сложеност Р*-стабла је иста као и код регуларног Р-стабла. Имплементација потпуног алгоритма мора решити многе специјалне случајеве, и тесне ситуације које овде нису дискутоване.