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


Abbildung 5.8: 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 (statisch, maximale Platznutzung):
Vorhanden seien 32.000 Datentupel, jeweils 5 passen in einen Block. Die $X$- und die $Y$-Achse habe jeweils 80 Unterteilungen. Daraus ergeben sich 6.400 Einträge für das Bucket-Directory $G$. Bei 4 Bytes pro Zeiger und 1024 Bytes pro Block passen 256 Zeiger auf einen Directory-Block. Also gibt es 25 Directory-Blöcke. D.h. $G[i,j]$ befindet sich auf Block $b = 5 * \lfloor j/16 \rfloor
+ \lfloor i/16 \rfloor$ an der Adresse $a = 16 * (j~ mod~ 16) + (i~ mod~ 16)$.

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