mały|400px|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. 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ż drzewo kd drzewo czwórkowe drzewo ósemkowe drzewo BVH
Przypisy
Linki zewnętrzne Biblioteka Boost.Geometry zawierająca implementację R-drzewa
Kategoria:Bazy danych R-drzewo