Р-стабло

Једноставан примјер Р-стабла за 2D квадрате

Р-стабла су стабла структуре података слична Б-стаблима, кориштена за приступ просторним подацима тј, за индексирање вишедимензионих информација; нпр, (X, Y) координате просторних података. Уобичајена употреба Р-стабла могла би бити: „Пронађи све музеје унутар 2 km од моје тренутне локације“.

Структуру података дјели хијерархијски просторно угнежђен, са могућим преклапањем, минимални обухватни квадрат (MBR, још познат као bounding box, тј. „квадрат (rectangle)", од чега „Р“ у Р-стаблу).

Сваки чвор Р-стабла има промјењив број улаза (до неког предефинисаног максимума). Сваким улазом унутар не-лисног чвора похрањују се два податка: начин идентификације чвора насљедника и минимална обухватна кутија свих улаза унутар чвора насљедника.

Алгоритми уноса и брисања обухватних кутија користе обухватне кутије из чворова да осигурају да су „оближњи“ елементи постављени у исти лисни чвор (поготово, нови елемент ће ићи у лисни чвор који захтијева најмање увећање обухватне кутије). Сваки улаз унутар лисног чвора похрањује два податка: начин идентификације стварног елемента податка (који, алтернативно, могу бити постављени директно у чвор), и оквирну кутију елемента податка.

Слично, алгоритми претраге (напримјер; пресјек, садржавање, најближи) користе обухватне кутије да одреде да ли да претражују унутар чвора насљедника. У том случају, већина чворова у стаблу нису никада „додирнути“ током претраге. Као Б-стабла, ово чини Р-стабла погодним за базе података, гдје чворови могу бити похрањени у меморију кад је то потребно.

Различити алгоритми могу бити искоришћени да раздвоје чворове када они постану препуни, резултујући квадратном и линеарном подтипу Р-стабла.

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

Варијанте

• Р* стабло
• Р+ стабло
• Хилбертово Р-стабло
• Приоритетно Р-стабло (ПР-стабло) - ПР-стабло има перформансе сличне најбољој познатој варијанти Р-стабла у стварним ситуацијама и релевантан распоред података, али их значајно надмашује у екстремнијим случајевима.

Алгоритам

Претрага

Улаз је квадрат претраге (Query box). Претрага је слична претрази у Б-стаблу. Почиње из корјеног чвора стабла. Сваки унутрашњи чвор садржи скуп квадрата и показивача ка одговарајућем чвору насљеднику и сваки лисни чвор садржи квадрате просторних објеката (показивач ка неком просторном објекту може бити ту). За сваки квадрат и чвору, мора бити одлучено да ли се преклапа са претражним квадратом или не. Ако да, одговарајући чвор насљедник мора такође бити претражен. Претрага се врши рекурзивно све док сви преклапајући чворови не буду заобиђени. Када је лисни чвор достигнут, садржане обухватне кутије (квадрати) се тестирају квадратом претраге и објекти (ако их има) се смјештају у резултујући скуп ако леже унутар претражног квадрата.

Уметање

За уметање објекта, стабло се пређе рекурзивно од корјеног чвора. Сви квадрати у текућем интерном чвору се испитују. Ограничење најмање покривености је упослено за уметање објеката, тј, кутија која треба најмање увећање да обухвати нови објекат је одабрана. У случају гдје више од једног квадрата испуњава тај услов, одабере се онај са најмањом површином. Уметање се наставља рекурзивно у одабраном чвору. Једном кад је достигнут лисни чвор, ако лисни чвор није пун, непосредно се умеће објекат. Ако је лисни чвор попуњен, он мора бити подијељен прије уметања. Неколико алгоритама за подјелу је предложено за добре перформансе Р-стабла.

Уметање паковања

• Sort-Tile-Recursive (STR)

• Паковано хилбертово стабло - Користи Хилбертову вриједност центра квадрата да сортира лисне чворовеи сагради стабло рекурзивно.
• најближи-X - Квадрати су сортирани на x-координатуи и чворови су креирани.

Види још

• минимални обухватни квадрат
• просторни индекс
• GiST

Литература

• Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data. R-Trees: A Dynamic Index Structure for Spatial Searching. стр. 47—57. ISBN 978-0-89791-128-3. 
• Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees: Theory and Applications, Springer. 2005. R-Trees: Theory and Applications. ISBN 978-1-85233-977-7. 
• [1] Архивирано на сајту Wayback Machine (17. април 2018) N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger (1990). „The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles”. SIGMOD Conference. 19 (2): 322—331. doi:10.1145/93605.98741. CS1 одржавање: Вишеструка имена: списак аутора (веза)] Архивирано на сајту Wayback Machine (17. април 2018)

Спољашње везе

• Р-стабло портал

• R-Trees: A Dynamic Index Structure for Spatial Searching
• Имплементације Р-стабла: Java applet Архивирано на сајту Wayback Machine (1. мај 2007), Common Lisp, .NET, Python.