Es gibt drei Hauptverfahren für das Speichern und Wiedergewinnen von Sätzen in großen Dateien. Das einfachste Verfahren benutzt sequentielles Durchsuchen der n Sätze und benötigt O(n) Schritte, um einen bestimmten Satz wiederzugewinnen. Wenn die n Sätze speziell geordnet oder in einem Baum gespeichert sind, kann ein Satz in O(log n) Schritten wiedergefunden werden (vgl. Kapitel 11). Schließlich kann ein Satz, wenn bestimmte Informationen jedes Satzes zur Erzeugung einer Speicheradresse benutzt werden, im Mittel in O(1) Schritten wiedergewonnen werden! Das letzte Verfahren, das Thema dieses Kapitels ist, wird als Hash-Verfahren¹ bezeichnet. Ein Satz in einer „typischen“ Datei besteht aus einem Schlüssel und einem Datenelement, wie in dem folgenden Beispiel:

3782-A: 670-15 DURALL RADIAL, 87.50, STOCK 24

Hier ist der Schlüssel 3782-A, und das Datenelement besteht aus einer Reifengröße, dem Hersteller, gefolgt vom zugehörigen Stückpreis und dem Lagerbestand. Hinsichtlich der Speicherung, des Suchens und des Wiedergewinnens von Sätzen in bzw. aus einer Datei reicht es aus anzugeben, wie man den Schlüssel manipuliert; gewissermaßen „trottet“ das Datenelement mit, vorausgesetzt, die Programmierung stimmt.