prev up next

Grid File

Als Alternative zu den Verfahren mit fester Gittergröße stellten Hinrichs und Nievergelt im Jahre 1981 das Grid File vor, welches auch bei dynamisch sich änderndem Datenbestand eine 2-Platten-Zugriffsgarantie gibt.

Erreicht wird dies (bei k-dimensionalen Tupeln) durch

Zur einfacheren Veranschaulichung beschreiben wir die Technik für Dimension k = 2. Verwendet werden dabei


Skalen und resultierende Gitterzellen

Beispiel
für ein Lookup mit x = 100, y = 1000:
Suche in Skala x den letzten Eintrag < x. Er habe den Index i = 3.
Suche in Skala y den letzten Eintrag < y. Er habe den Index j = 1.
Lade den Teil des Grid-Directory in den Hauptspeicher, der G[3, 1] enthält.
Lade Bucket mit Adresse G[3, 1].

Beispiel
für den Zugriff auf das Bucket-Directory:
Vorhanden seien 1.000.000 Datentupel, jeweils 4 passen in einen Block. Die X- und die Y-Achse habe jeweils 500 Unterteilungen. Daraus ergeben sich 250.000 Einträge für das Bucket-Directory G. Bei 4 Bytes pro Zeiger und 1024 Bytes pro Block passen 250 Zeiger auf einen Directory-Block. Also gibt es 1000 Directory-Blöcke. D.h. G[i, j] findet sich auf Block 2 . j als i-te Adresse, falls i < 250 und befindet sich auf Block 2 . j + 1 als (i - 250)-te Adresse, falls i $ \geq$ 250

Bei einer range query, gegeben durch ein Suchrechteck, werden zunächst alle Gitterzellen bestimmt, die in Frage kommen, und dann die zugehörenden Buckets eingelesen.


prev up next