R-drzewo

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Przykład R-drzewa złożonego z dwuwymiarowych prostokątów

R-drzewo – dynamiczna, zbalansowana struktura danych wspomagająca wyszukiwanie obiektów w przestrzeni wielowymiarowej. Stanowi rozwinięcie idei B-drzewa na większą liczbę wymiarów. Została zaproponowana przez Antonina Guttmana w 1984 roku[1]. R-drzewa wykorzystuje się głównie w systemach baz danych. Do opisania obiektów wielowymiarowych wykorzystywane są minimalne regiony pokrywające (ang. MBR - minimal bounding rectangle) lub inaczej pudełka okalające (ang. AABB - axis aligned bounding box). Typowym przykładem użycia może być przechowanie w R-drzewie punktów reprezentujących współrzędne restauracji lub regionów reprezentujących powierzchnie ulic, budynków, jezior, itd., a następnie wyszukanie tych, które spełniają pewne kryteria. Umożliwia to znalezienie odpowiedzi na zapytania typu "znajdz wszystkie muzea w promieniu 2 km", "znajdź wszystkie drogi znajdujące się w obszarze" (w celu wyświetlenia ich na urządzeniu służącym do nawigacji) lub "znajdz najbliższą stację paliw".

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. Guttman A.: R-Trees: A Dynamic Index Structure for Spatial Searching. W: Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. 1984, s. 47. DOI:10.1145/602259.602266. ISBN 0897911288.

Linki zewnętrzne[edytuj | edytuj kod]