R-drzewo

R-drzewo

R-drzewo to dynamiczna, zbalansowana struktura danych, która wspomaga wyszukiwanie obiektów w przestrzeni wielowymiarowej. Jest rozwinięciem koncepcji B-drzewa, dostosowanym do większej liczby wymiarów. Zostało zaproponowane przez Antonina Guttmana w 1984 roku i jest powszechnie stosowane w systemach baz danych.

Opis obiektów

W R-drzewach obiekty wielowymiarowe są reprezentowane przez minimalne regiony pokrywające (MBR – minimal bounding rectangle) lub pudełka okalające (AABB – axis aligned bounding box). Dzięki temu możliwe jest efektywne przechowywanie i wyszukiwanie danych.

Przykłady zastosowań

• Przechowywanie współrzędnych geograficznych restauracji.
• Reprezentowanie powierzchni ulic, budynków, jezior itp.
• Wyszukiwanie obiektów spełniających określone kryteria, np.:
  • „Znajdź wszystkie muzea w promieniu 2 km.”
  • „Znajdź wszystkie drogi w określonym obszarze.”
  • „Znajdź najbliższą stację paliw.”

Dzięki R-drzewom możliwe jest szybkie i efektywne przeszukiwanie dużych zbiorów danych w kontekście przestrzennym, co czyni je niezwykle użytecznymi w różnych aplikacjach, takich jak systemy nawigacyjne czy bazy danych geograficznych.