Gridfile

Ein Gridfile (engl. Grid = Gitter) ist eine mindestens zweidimensionale Indexstruktur, die das Suchen nach Daten mit 2 oder mehr Kriterien erheblich beschleunigt. Bei den traditionellen eindimensionalen Datenstrukturen (z. B. Hashtabelle) ist eine Suche nach einem Kriterium meist sehr einfach, die Suche nach einem zweiten Kriterium sehr zeitintensiv. Gridfiles stellen eine besondere Art von Hashing dar, in welcher die klassische Hashfunktion durch ein Grid-Verzeichnis ersetzt wird.

Allgemeine Gridfiles haben die Dimension k, was bedeutet, dass sie k-dimensionale Daten mit den Schlüsseln S1...Sk speichern. Gridfiles zählen zu den symmetrischen Datenstrukturen, da keiner der Schlüsselwerte bevorzugt wird, sondern immer alle Schlüssel gleichberechtigt eingehen.

Im Gridfile kann zum Beispiel bei der Suche nach drei Kriterien wie in einem dreidimensionalen Würfel direkt der betroffene Datensatz gefunden werden. Im Gridfile selbst sind meistens nicht die Daten abgelegt (was bei einem nur mäßig gefüllten Würfel zu viel Platz in Anspruch nehmen würde), sondern nur ein Verweis, in welchem Bucket die gewünschten Daten abgelegt sind. Ein Bucket speichert mehrere im Gridfile nebeneinanderliegende Datensätze ab.

Bei einem Gridfile gilt das so genannte Two-Disk-Access-Prinzip. D.h., dass ein gesuchter Datensatz nach spätestens zwei Anfragen auf einen Sekundärspeicher vorliegt. Um dies zu gewährleisten, werden die Indexstruktur und die eigentlichen Daten in zwei separaten Datenstrukturen abgelegt. Da die Indexstruktur im Vergleich zu den zu adressierenden Daten relativ klein ist, kann diese im Optimalfall auch im Hauptspeicher gehalten werden.

Die Adressierung der Buckets geschieht hierbei durch die Benutzung sogenannter Skalen, welche die Indexstruktur bilden. Für jede Dimension k wird eine Skala erstellt, welche die Grenzen der Buckets in der entsprechenden Dimension sortiert hinterlegen und einen Index für diese Dimension enthalten. Durch die Kombination der Einträge in den einzelnen Skalen kann somit der entsprechende Bucket ermittelt werden, welcher die Daten für die gesuchten Koordinaten enthält.

Ein Gridfile ist unempfindlich gegenüber Datenhäufungen, da es als adaptive Datenstruktur durch Splittung oder Dimensionsverfeinerung (bei Bucketüberlauf), sowie Verschmelzung (bei Bucketunterlauf) auf die Eigenschaften des Inhalts reagiert.