Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


18. Externes Suchen



Indexsequentieller Zugriff

Sequentielle Suche auf Platten ist die natürliche Erweiterung der elementaren sequentiellen Suchmethoden, die in Kapitel 14 betrachtet wurden: Die Datensätze werden entsprechend der wachsenden Reihenfolge ihrer Schlüssel gespeichert, und Suchvorgänge werden einfach realisiert, indem die Datensätze der Reihe nach so lange eingelesen werden, bis ein Datensatz gefunden wird, der einen Schlüssel enthält, der größer oder gleich dem Suchschlüssel ist. Wenn zum Beispiel unsere Suchschlüssel von E X T E R N A L S E A R C H I N G E X A M P L E kommen und wir Platten haben, die in der Lage sind, drei Seiten zu je vier Datensätzen aufzubewahren, so liegt die Konfiguration vor, die Abbildung 18.1 zeigt. (Wie im Falle des externen Sortierens müssen wir sehr kleine Beispiele betrachten, um die Algorithmen zu verstehen, und an sehr große Beispiele denken, um ihre Leistungsfähigkeit zu beurteilen.) Offensichtlich ist reines sequentielles Suchen unzweckmäßig, da es zum Beispiel in Abbildung 18.1 bei der Suche nach W erforderlich wäre, alle Seiten zu lesen.

Abbildung 18.1
Abbildung 18.1 Sequentieller Zugriff.

Um die Such-Geschwindigkeit beträchtlich zu erhöhen, können wir für jede Platte einen Index führen, der angibt, welche Schlüssel zu welchen Seiten auf dieser Platte gehören (siehe Abbildung 18.2). Die erste Seite jeder Platte ist ihr Index; die kleinen Buchstaben geben an, daß nur der Schlüsselwert gespeichert wird und nicht der vollständige Datensatz, und die kleinen Zahlen sind Seitenangaben (0 bezeichnet die erste Seite der Platte, 1 die nächste Seite usw.). Im Index erscheint jede Seitennummer unter dem Wert des letzten Schlüssels der vorangehenden Seite. (Das Leerzeichen ist ein Marken-Schlüssel, der kleiner ist als alle anderen; das »+« bedeutet »siehe nächste Platte«.) Demzufolge gibt zum Beispiel der Index für Platte 2 an, daß ihre erste Seite Datensätze mit Schlüsseln zwischen E und I (einschließlich) enthält, und daß ihre zweite Seite Datensätze mit Schlüsseln zwischen I und N (einschließlich) enthält. Es ist normalerweise möglich, viel mehr Schlüssel und Seitenangaben auf einer Indexseite unterzubringen als Datensätze auf einer Seite mit »Daten«; in Wirklichkeit sollte der Index einer Platte nur wenige Seiten benötigen.

Abbildung 18.2
Abbildung 18.2 Indexsequentieller Zugriff.

Um die Suche weiter zu beschleunigen, können diese Indizes mit einem »Hauptindex« gekoppelt werden, der angibt, welche Schlüssel sich auf welcher Platte befinden. Für unser Beispiel würde der Hauptindex aussagen, daß Platte 1 Schlüssel enthält, die kleiner oder gleich E sind, daß Platte 2 Schlüssel enthält, die kleiner oder gleich N sind (aber nicht kleiner als E), und daß Platte 3 Schlüssel enthält, die kleiner oder gleich X sind (aber nicht kleiner als N). Der Hauptindex dürfte hinreichend klein sein, um im Speicher abgelegt werden zu können, so daß die meisten Datensätze gefunden werden können, indem auf nur zwei Seiten zugegriffen wird: ein Zugriff für den Index auf der entsprechenden Platte und ein Zugriff für die Seite, die den entsprechenden Datensatz enthält. Zum Beispiel wäre es bei einer Suche nach W erforderlich, zuerst die Indexseite von Platte 3 zu lesen und danach die zweite Datenseite von Platte 3, welche die einzige ist, die W enthalten könnte. Eine Suche nach Schlüsseln, die im Index erscheinen, erfordert das Lesen von drei Seiten: den Index sowie die beiden Seiten, die den Schlüsselwert im Index flankieren. Falls in der Datei keine mehrfach auftretenden Schlüssel enthalten sind, kann der zusätzliche Seitenzugriff vermieden werden. Andererseits können, falls die Datei viele gleiche Schlüssel enthält, mehrere Seitenzugriffe notwendig sein (Datensätze mit gleichen Schlüsseln können mehrere Seiten füllen).

Diese Organisation wird indexsequentieller Zugriff genannt, da sie eine Kombination einer sequentiellen Organisation der Schlüssel und dem Zugriff über einen Index darstellt. Sie ist die bevorzugte Methode für Anwendungen, bei denen Änderungen der Datenbank nicht oft zu erwarten sind. Der Nachteil bei der Verwendung eines indexsequentiellen Zugriffs ist, daß er sehr unflexibel ist. Zum Beispiel wäre es beim Hinzufügen eines B zu der obigen Konfiguration erforderlich, praktisch die gesamte Datenbank umzubauen, mit neuen Positionen für viele der Schlüssel und neuen Werten für die Indizes.

Eigenschaft 18.1 Eine Suche in einer indexsequentiellen Datei erfordert nur eine konstante Anzahl von Plattenzugriffen, während ein Einfügen das Umordnen der gesamten Datei erforderlich machen kann.

In der Praxis hängt die hierbei auftretende »Konstante« von der Anzahl der Platten und von der jeweiligen Größe der Datensätze, Indizes und Seiten ab. Zum Beispiel könnte eine umfangreiche Datei aus Schlüsseln, die nur aus einem Wort bestehen, sicherlich nicht auf nur einer Platte so gespeichert werden, daß eine Suche mit einer konstanten Anzahl von Zugriffen ermöglicht wird. Oder, um als anderes Extrem ein weiteres absurdes Beispiel zu nennen, eine große Zahl sehr kleiner Platten, von denen jede nur einen Datensatz aufbewahren kann, könnte die Suche ebenfalls sehr schwer machen. w.z.b.w.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]