Robert Sedgewick: Algorithmen

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


18. Externes Suchen



Suchalgorithmen für den
Zugriff auf Elemente sehr umfangreicher Dateien, sind von enormer praktischer Bedeutung. Suchen ist die grundlegende Operation für umfangreiche Dateien und verbraucht sicher einen sehr erheblichen Teil der Ressourcen vieler Computeranlagen.

Wir wollen uns in der Hauptsache mit Suchmethoden in großen Platten-Dateien beschäftigen, da das Suchen auf Platten von größtem praktischen Interesse ist. Bei Medien mit sequentiellem Zugriff wie etwa Bändern entartet die Suche rasch zu einer simplen, langsamen Methode: Um ein Band nach einem Element abzusuchen, bleibt nicht viel anderes übrig, als das Band abzuspielen und zu lesen, bis das Element gefunden wird. Bemerkenswerterweise kann man mit Hilfe der im folgenden untersuchten Methoden ein Element auf einer Platte, die eine Milliarde Wörter umfaßt, mit nur zwei oder drei Plattenzugriffen finden.

Wie beim externen Sortieren ist der »System«-Aspekt bei der Verwendung komplexer Hardware für die Ein- und Ausgabe ein Faktor, der für die Leistungsfähigkeit externer Suchverfahren von vorrangiger Bedeutung ist, wobei wir aber nicht in der Lage sind, ihn eingehend zu untersuchen. Im Gegensatz zum Sortieren, wo sich die externen Methoden von den internen Methoden tatsächlich stark unterscheiden, werden wir jedoch feststellen, daß externe Suchverfahren logische Erweiterungen der bereits untersuchten internen Verfahren sind.

Suchen ist eine grundlegende Operation für Plattengeräte. Dateien werden typischerweise so organisiert, daß sie spezielle Gerätemerkmale ausnutzen, um den Zugriff auf die Information so effizient wie möglich zu gestalten. Wie bereits beim Sortieren, arbeiten wir mit einem sehr einfachen und ungenauen Modell von »Platten«, um die wichtigsten Merkmale der grundlegenden Verfahren zu erläutern. Die Bestimmung der besten externen Suchmethode für eine spezielle Anwendung ist äußerst kompliziert und sehr stark von den Eigenschaften der Hardware (und der System-Software) abhängig, so daß diese Frage über den Rahmen des vorliegenden Buches hinausführt. Wir können jedoch einige allgemeine Ansätze vorschlagen.

Bei vielen Anwendungen besteht häufig der Wunsch, in sehr großen Dateien kleine Informationsmengen zu ändern, hinzuzufügen, zu löschen oder (was am wichtigsten ist) auf sie zuzugreifen. In diesem Kapitel betrachten wir einige Methoden für solche dynamischen Situationen, die gegenüber den einfachen Methoden Vorteile der gleichen Art aufweisen, wie sie binäre Suchbäume und Hashing gegenüber binärer Suche und sequentieller Suche besitzen.

Eine sehr umfangreiche Sammlung von Informationen, die unter Verwendung eines Computers verarbeitet werden soll, wird Datenbank (database) genannt. Es wurden sehr viele Untersuchungen über die Methoden der Erzeugung, Verwaltung und Nutzung von Datenbanken durchgeführt. Allerdings besitzen umfangreiche Datenbanken eine sehr große Trägheit: Wenn eine sehr große Datenbank einmal geschaffen worden ist und dabei an eine spezielle Suchstrategie angepaßt wurde, kann es sehr aufwendig werden, sie an eine andere anzupassen. Aus diesem Grunde sind die älteren, statischen Methoden weit verbreitet und werden es wahrscheinlich auch bleiben, obwohl für neue Datenbanken häufig schon die neueren dynamischen Methoden eingesetzt werden.

Datenbanksysteme unterstützen gewöhnlich weit kompliziertere Operationen als nur eine einfache Suche nach einem Element auf der Basis eines einzigen Schlüssels. Suchvorgänge beruhen oft auf Kriterien, die mehr als einen Schlüssel betreffen, und es wird von ihnen erwartet, daß sie viele Datensätze zurückgeben. In späteren Kapiteln werden wir einige Beispiele von Algorithmen kennenlernen, die für gewisse Suchaufgaben dieser Art geeignet sind. Jedoch sind bereits allgemeine Suchprobleme hinreichend kompliziert, so daß es üblich ist, eine die gesamte Datenbank einbeziehende sequentielle Suche vorzunehmen, wobei jeder Datensatz überprüft wird, um zu sehen, ob er den Kriterien genügt.

Die Verfahren, die wir behandeln wollen, sind bei der Implementation großer Dateisysteme von praktischer Bedeutung, in denen jede Datei eine eindeutige Kennung besitzt und der Zweck des Dateisystems darin besteht, auf der Basis dieser Kennung ein effizientes Zugreifen, Einfügen und Löschen zu unterstützen. In unserem Modell wird angenommen, daß der Plattenspeicher in Seiten eingeteilt ist, das heißt in zusammenhängende Blöcke von Informationen, die einen effizienten Zugriff auf die Platte gestatten. Jede Seite enthält viele Datensätze; unsere Aufgabe besteht darin, die Datensätze innerhalb der Seiten so zu organisieren, daß der Zugriff auf jeden Datensatz möglich ist, indem nur einige wenige Seiten gelesen werden. Wir nehmen an, daß die für das Lesen einer Seite erforderliche Ein-/Ausgabe-Zeit die Verarbeitungszeit, die benötigt wird, um irgendwelche diese Seite betreffenden Berechnungen auszuführen, dominiert. Wie bereits erwähnt wurde, ist dieses Modell in vielerlei Hinsicht übermäßig vereinfacht, doch es enthält noch genügend viele der Merkmale reeller externer Speichergeräte, um uns zu ermöglichen, einige der zur Anwendung kommenden grundlegenden Methoden zu betrachten.


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