Indeks przestrzenny

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Indeks przestrzenny (ang. spatial index) – indeks używany przez przestrzenne bazy danych w celu optymalizacji zapytań przestrzennych. Indeksy używane przez bazy danych innych typów nie nadają się do efektywnej obsługi dodatkowych, geometrycznych typów danych. Przykładowo, nie mogą efektywnie wskazać, jak daleko są rozmieszczone względem siebie dwa punkty i czy punkty zawierają się w wybranym obszarze w przestrzeni. Najczęściej używane metody indeksowania to:

Zapytanie przestrzenne (ang. spatial query) - jest specjalnym typem zapytania bazodanowego obsługiwane przez geograficzne bazy danych. Zapytania takie różnią się od zapytań SQL kilkoma ważnymi rzeczami. Dwa najważniejsze rzeczy to:Drzewo ósemkowe (ang. octree) to stosowana w grafice komputerowej struktura danych będąca drzewem, używana do przestrzennego podziału trójwymiarowej przestrzeni na mniejsze, regularne części.
  • Siatka (indeks przestrzenny),
  • Porządek Z (krzywa),
  • Drzewa czwórkowe,
  • Drzewa ósemkowe,
  • UB-drzewa,
  • R-drzewa - Najczęściej wybierana metoda indeksowania danych przestrzennych. Obiekty geometryczne (wielokąty, linie i punkty) są grupowane przy użyciu algorytmu minimalnej obwiedni prostokątnej (ang. Minimum Bounding Rectangle, MBR). Obiekty są dodawane do MBR, do indeksu wskazującego na najmniejszy przyrost wielkości dodawanych obiektów,
  • Drzewo kd,
  • Drzewo BVH,
  • Drzewo przedziałowe - w przypadku zapytań jednowymiarowych,
  • Zobacz też[ | edytuj kod]

  • krzywa Hilberta
  • 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 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".Drzewo kd (skrót od drzewa k-wymiarowego) – struktura danych używana do dzielenia przestrzeni. Drzewa kd są przydatne w tworzeniu struktur w niektórych zastosowaniach takich jak wyszukiwanie najbliższych sąsiadów lub znajdywanie punktów w prostokątnych obszarach (w czasie O ( n + k ) {displaystyle O({sqrt {n}}+k)} , gdzie n {displaystyle n} to całkowita liczba punktów, k {displaystyle k} - liczba znalezionych punktów).




    Warto wiedzieć że... beta

    Drzewo czwórkowe (ang. quadtree) to w informatyce struktura danych będąca drzewem, używana do podziału dwuwymiarowej przestrzeni na mniejsze części, dzieląc ją na cztery równe ćwiartki, a następnie każdą z tych ćwiartek na cztery itd.
    Drzewo brył ograniczających (ang. bound volume hierarchy, BVH) – struktura danych do przechowywania i szybkiego wykonywania zapytań na temat obiektów w przestrzeni trójwymiarowej. Najczęściej stosowana w grafice komputerowej do akceleracji algorytmu śledzenie promieni (ray tracing) oraz w symulacjach fizyki ciał do akceleracji detekcji kolizji (np. w grach komputerowych).

    Reklama