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.