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.