R-drzewo (ang. R-tree) – 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.

Przykład R-drzewa złożonego z dwuwymiarowych prostokątów

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 R-drzewa jest przechowanie punktów reprezentujących współrzędne geograficzne restauracji lub regionów reprezentujących powierzchnie ulic, budynków, jezior, itd., a następnie wyszukanie tych, które spełniają określone kryteria. Umożliwia to znalezienie odpowiedzi na zapytania typu „znajdź 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 „znajdź najbliższą stację paliw”.

Zobacz też edytuj

Przypisy edytuj

  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 0-89791-128-8.

Linki zewnętrzne edytuj