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

• k Skalen zum Einstieg ins Grid-Directory (im Hauptspeicher)
• Grid-Direktory zum Finden der Bucket-Nr. (im Hintergrundspeicher)
• Buckets für Datensätze (im Hintergrundspeicher)

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

• zwei eindimensionale Skalen,
  welche die momentane Unterteilung der X- bzw. Y-Achse enthalten:

  
  var X: array [0..max_x] of attribut_wert_x;
  var Y: array [0..max_y] of attribut_wert_y;
  

• ein 2-dimensionales Grid-Directory,
  welches Verweise auf die Datenblöcke enthält:

  
  var G: array [0..max_x - 1, 0..max_y - 1] of pointer;
  

  D.h. G[i, j] enthält eine Bucketadresse, in der ein rechteckiger Teilbereich der Datenpunkte abgespeichert ist. Zum Beispiel sind alle Punkte mit 30 < x $\leq$ 40, 2050 < y $\leq$ 2500 im Bucket mit Adresse G[1,2] zu finden (in Abbildung 5.8 gestrichelt umrandet). Achtung: mehrere Gitterzellen können im selben Bucket liegen.

• mehrere Buckets,
  welche jeweils eine maximale Zahl von Datenrecords aufnehmen können.

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.