R-drzewo

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

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. 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 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ż