ISAM

ISAM: Ausgangslage

ISAM: nach Einfügen von Elasmosaurus

ISAM: nach Umbenennen von Brontosaurus

Offenes und auch erweiterbares Hashing sind nicht in der Lage, Datensätze in sortierter Reihenfolge auszugeben oder Bereichsabfragen zu bearbeiten. Für Anwendungen, bei denen dies erforderlich ist, kommen Index-Strukturen zum Einsatz (englisch: index sequential access method = ISAM) Wir setzen daher voraus, daß sich die Schlüssel der zu verwaltenden Records als Zeichenketten interpretieren lassen und damit eine lexikographische Ordnung auf der Menge der Schlüssel impliziert wird. Sind mehrere Felder am Schlüssel beteiligt, so wird zum Vergleich deren Konkatenation herangezogen.

Neben der Haupt-Datei (englisch: main file), die alle Datensätze in lexikographischer Reihenfolge enthält, gibt es nun eine Index-Datei (english: index file) mit Verweisen in die Hauptdatei. Die Einträge der Index-Datei sind Tupel, bestehend aus Schlüsseln und Blockadressen, sortiert nach Schlüsseln. Liegt < v, a > in der Index-Datei, so sind alle Record-Schlüssel im Block, auf den a zeigt, größer oder gleich v. Zur Anschauung: Fassen wir ein Telefonbuch als Hauptdatei auf (eine Seite ein Block), so bilden alle die Namen, die jeweils links oben auf den Seiten vermerkt sind, einen Index. Da im Index nur ein Teil der Schlüssel aus der Hauptdatei zu finden sind, spricht man von einer dünn besetzten Index-Datei (englisch: sparse index).

Wir nehmen an, die Records seien verschiebbar und pro Block sei im Header vermerkt, welche Subblocks belegt sind. Dann ergeben sich die folgenden Operationen:

• LOOKUP:
  Gesucht wird ein Record mit Schlüssel v₁. Suche (mit binary search) in der Index-Datei den letzten Block mit erstem Eintrag v₂ $\leq$ v₁. Suche in diesem Block das letzte Paar (v₃, a) mit v₃ $\leq$ v₁. Lies Block mit Adresse a und durchsuche ihn nach Schlüssel v₁.

• MODIFY:
  Führe zunächst LOOKUP durch. Ist der Schlüssel an der Änderung beteiligt, so wird MODIFY wie ein DELETE mit anschließendem INSERT behandelt. Andernfalls kann das Record überschrieben und dann der Block zurückgeschrieben werden.

• INSERT:
  Eingefügt wird ein Record mit Schlüssel v. Suche zunächst mit LOOKUP den Block B_i, auf dem v zu finden sein müßte (falls v kleinster Schlüssel, setze i =1). Falls B_i nicht vollständig gefüllt ist: Füge Record in B_i an passender Stelle ein, und verschiebe ggf. Records um eine Position nach rechts (Full/Empty-Bits korrigieren). Wenn v kleiner als alle bisherigen Schlüssel ist, so korrigiere Index-Datei. Wenn B_i gefüllt ist: Überprüfe, ob B_{i + 1} Platz hat. Wenn ja: Schiebe überlaufendes Record nach B_{i + 1} und korrigiere Index. Wenn nein: Fordere neuen Block B'_i an, speichere das Record dort, und füge im Index einen Verweis ein.

• DELETE: analog zu INSERT

Bemerkung: Ist die Verteilung der Schlüssel bekannt, so sinkt für n Index-Blöcke die Suchzeit durch Interpolation Search auf log log n Schritte!

Abbildung 4.8 zeigt die Ausgangslage für eine Hauptdatei mit Blöcken, die jeweils 2 Records speichern können. Die Blöcke der Index-Datei enthalten jeweils vier Schlüssel/Adreß-Paare. Weiterhin gibt es im Hauptspeicher eine Tabelle mit Verweisen zu den Index-Datei-Blöcken.

Abbildung 4.9 zeigt die Situation nach dem Einfügen von Elasmosaurus. Hierzu findet man zunächst als Einstieg Diplodocus. Der zugehörige Dateiblock ist voll, so daß nach Einfügen von Elasmosaurus für das überschüssige Record Plateosaurus ein neuer Block angelegt und sein erster Schlüssel in die Index-Datei eingetragen wird.

Nun wird Brontosaurus umbenannt in Apatosaurus. Hierzu wird zunächst Brontosaurus gelöscht, sein Dateinachfolger Compsognathus um einen Platz vorgezogen und der Schlüssel in der Index-Datei, der zu diesem Blockzeiger gehört, modifiziert. Das Einfügen von Apatosaurus bewirkt einen Überlauf von Brachiosaurus in den Nachfolgeblock, in dem Compsognathus nun wieder an seinen alten Platz rutscht. Im zugehörigen Index-Block verschwindet daher sein Schlüssel wieder und wird überschrieben mit Brachiosaurus.