7.7 Interne Ebene: Gridfiles

• mehrdimensionale, dynamische Organisationsform
• von Hinrichs und Nievergelt, ETH Zürich, 1981
• wesentliche Zielsetzung: jeder Datensatz in 2 Zugriffen erreichbar ('Zweiplatten-Zugriffsgarantie')
• n-dimensionale Quader bilden Suchregion
• ähnliche Objekte (benachbarte Punkte im Datenraum) sollen auf gleicher Seite gespeichert werden
• symmetrische Behandlung aller Raum-Dimensionen (Mehrdimensionalität)
• dynamische Anpassung beim Löschen und Einfügen

Gridfiles Prinzip der 2 Plattenzugriffe

• Voraussetzung: Datensatz gesucht, alle k Attributwerte vorgegeben (= exact match)
• 1) Abbildung des gesuchten k-Tupels auf die Intervalle der Skalen mittels einer bestimmten Funktion;
  für jeden Attributwert ex. Dimension und damit Skala, die sich aus Intervallen zusammensetzt; Intervalle werden durch Indizes repräsentiert -> Kombination von Indizes entspr. der Intervalle ermitteln; da Skalen im Hauptspeicher: 1 Hauptspeicherzugriff
• 2) Über Indizes Zugriff auf Grid-Directory;
  Grid-Directory speichert Adressen der zugeordneten Datenseiten; ist selbst auf Sekundärspeicher gespeichert; Index verweist auf Eintrag im Grid-Directory ; 1 Plattenzugriff
• 3) Falls gesuchter Datensatz existiert, liegt er auf entspr. Datenseite, -> Zugriff auf diese Datenseite; 1 Plattenzugriff

Gridfiles Beispiel: k=2, Relation mit 2 Attributen A1, A2 vom Typ Integer
Skalen: bzgl. A1: 0/4/8, bzgl. A2: 0/5
Grid-Directory G: (mehrere Gitterzellen können auf gleicher Datenseite liegen, bilden eine Region)

Gridfiles Operationen

• Lookup: Suche nach Datensatz (x,y)
  suche in Skala zu x nach letztem Eintrag der kleiner ist als x (z.B. Index i=3),
  suche in Skala zu y nach letztem Eintrag der kleiner ist als y (z.B. Index j=1),
  lade Teil des Grid-Directories in den HS, der G[i,j] enthält,
  lade Seite mit der Adresse unter G[i,j]
• Einfügen: Start mit Grid-Directory mit 1 Zelle (einer Region) und einer zugeordneten Datenseite,
  ist Seite, auf die Datensatz eingetragen werden soll, voll: Seite teilen,
  gehört nur eine Grid-Zelle zur Datenseite: Unterteilung eines Intervalls auf einer Skala in 2 Intervalle, Aufdatieren des Grid-Directories, Datensätze entspr. der Teilung verteilen, neuen Datensatz auf entspr. Seite speichern
• Löschen: Lookup durchführen,
  Datensatz von Seite löschen, ist Seite leer: Zusammenfügen zweier Regionen
• Modifikation: Datensatz löschen, geänderten Datensatz einfügen

Gridfiles Beispiel: mehrfaches Einfügen von Datensäten, Annahme: max. 2 Datensätze pro Datenseite