prev up next

Problemstellung

Ein Sekundär-Index ist in der Lage, alle Records mit $x_1 \leq a \leq x_2$ zu finden. Nun heißt die Aufgabe: Finde alle Records mit $x_1 \leq a_1 \leq x_2$ und $y_1 \leq a_2 \leq y_2 , \ldots $

Beispiel
für mehrdimensionale Bereichsabfrage:
Gesucht sind alle Personen mit der Eigenschaft

Alter zwischen 20 und 30 Jahre alt
Einkommen zwischen 2000 und 3000 Euro
PLZ zwischen 40000 und 50000

Im folgenden betrachten wir (wegen der einfacheren Veranschaulichung) nur den 2-dimensionalen Fall. Diese Technik ist auf beliebige Dimensionen verallgemeinerbar.


Abbildung 5.1: Fläche mit Datenpunkten

Abbildung 5.1 zeigt eine zweidimensionale Fläche mit Datenpunkten sowie ein Query-Rechteck, gegeben durch vier Geraden.

Die Aufgabe besteht darin, alle Punkte zu ermitteln, die im Rechteck liegen. Hierzu bieten sich zwei naheliegende Möglichkeiten an:

Es ist offensichtlich, daß trotz kleiner Trefferzahl ggf. lange Laufzeiten auftreten können. Dagegen ist für die 1-dimensionale Suche bekannt: Der Aufwand beträgt O($k + \log n$) bei $k$ Treffern in einem Suchbaum mit $n$ Knoten.


prev up next