Problemstellung

Ein Sekundär-Index ist in der Lage, alle Records mit x₁ $\leq$ a $\leq$ x₂ zu finden. Nun heißt die Aufgabe: Finde alle Records mit x₁ $\leq$ a₁ $\leq$ x₂ und y₁ $\leq$ a₂ $\leq$ y₂,...

Beispiel

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

Alter zwischen 20 und 30 Jahre alt

Einkommen zwischen 2000 und 3000 DM

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.

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:

• Projektion durchführen auf x oder y mit binärer Suche über vorhandenen Index, danach sequentiell durchsuchen, d.h. zunächst werden G,F,C,D,E ermittelt, danach bleibt F übrig
• Projektion durchführen auf x und Projektion durchführen auf y , anschließend Durchschnitt bilden.

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.