Ein Sekundär-Index ist in der Lage, alle Records mit zu finden. Nun heißt die Aufgabe: Finde alle Records mit und
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 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() bei Treffern in einem Suchbaum mit Knoten.