Robert Sedgewick: Algorithmen

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


18. Externes Suchen



Erweiterbares Hashing

Eine Alternative zu B-Bäumen, die digitale Suchalgorithmen in der Weise verallgemeinert, daß sie sich auf externes Suchen anwenden lassen, wurde 1978 von R. Fagin, J. Nievergelt, N. Pippenger und R. Strong entwickelt. Diese Methode, die erweiterbares Hashing (extendible hashing) genannt wird, erfordert bei typischen Anwendungen zwei Plattenzugriffe für jede Suche, während sie gleichzeitig ein effizientes Einfügen ermöglicht. Wie bei B-Bäumen werden unsere Datensätze auf Seiten gespeichert, die in zwei Teile aufgespalten werden, wenn sie sich füllen; wie beim indexsequentiellen Zugriff führen wir einen Index, auf den wir zugreifen, um die Seite zu finden, die die mit unserem Suchschlüssel übereinstimmenden Datensätze enthält. Erweiterbares Hashing kombiniert diese Vorgehensweisen durch die Ausnutzung digitaler Eigenschaften der Suchschlüssel.

Um die Arbeitsweise des erweiterbaren Hashing kennenzulernen, untersuchen wir, wie es sukzessive Einfügungen von Schlüsseln aus E X T E R N A L S E A R C H I N G E X A M P L E vornimmt, wenn Seiten mit einer Kapazität von bis zu vier Datensätzen verwendet werden. Wir beginnen mit einem »Index« mit nur einer Eintragung, einem Zeiger, der auf die Seite zeigt, die die Datensätze aufnehmen soll. Die ersten vier Datensätze lassen sich auf dieser Seite unterbringen, wobei die einfache Struktur entsteht, die in Abbildung 18.7 dargestellt ist.

Abbildung 18.7
Abbildung 18.7 Erweiterbares Hashing: Erste Seite.

Das Inhaltsverzeichnis auf Platte 1 besagt, daß sich alle Datensätze auf Seite 0 von Platte 2 befinden, wo sie, nach der Reihenfolge ihrer Schlüssel sortiert, gespeichert werden. Als zusätzlichen Bezug geben wir auch den binären Wert der Schlüssel an, wobei wir wieder unsere Standard-Kodierung verwenden, in welcher der i-te Buchstabe des Alphabets durch die 5 Bits von i dargestellt wird. Nunmehr ist die Seite voll und muß aufgespalten werden, um den Schlüssel R=10010 hinzufügen zu können. Die Strategie ist einfach: Setze Datensätze mit Schlüsseln, die mit 0 beginnen, auf eine Seite und Datensätze mit Schlüsseln, die mit 1 beginnen, auf eine andere Seite. Dies erfordert die Verdoppelung des Inhaltsverzeichnisses und das Bewegen der Hälfte der Schlüssel von Seite 0 der Platte 2 zu einer neuen Seite, womit sich die in Abbildung 18.8 dargestellte Struktur ergibt.

Abbildung 18.8
Abbildung 18.8 Erweiterbares Hashing: Aufspaltung des Inhaltsverzeichnisses.

Nun können N=01110 und A=00001 hinzugefügt werden, doch damit ist die erste Seite erneut gefüllt, wie in Abbildung 18.9 dargestellt ist. Bevor L=01100 hinzugefügt werden kann, ist ein weiteres Aufspalten erforderlich. Um L=01100 einzufügen, gehen wir in der gleichen Weise vor wie beim ersten Aufspalten, indem wir die erste Seite in zwei Teile aufspalten, einen für die mit 00 beginnenden Schlüssel und einen für die mit 01 beginnenden Schlüssel. Was nicht sofort klar ist, ist die Frage, was mit dem Inhaltsverzeichnis zu geschehen hat. Eine Alternative wäre, einfach eine weitere Eintragung anzufügen, einen Zeiger für jede Seite. Dies ist nicht wünschenswert, da es im wesentlichen auf eine indexsequentielle Suche hinausläuft (wenn auch in einer digitalen Variante): Das Inhaltsverzeichnis muß sequentiell durchsucht werden, um während eines Suchvorgangs die richtige Seite zu finden. Ein anderer Weg ist, einfach das Inhaltsverzeichnis nochmals zu verdoppeln, womit sich die in Abbildung 18.10 dargestellte Struktur ergibt. Eine neue Seite (Seite 2 auf Platte 2) enthält die mit 01 beginnenden Schlüssel (L und N); die aufgespaltene Seite (Seite 0 auf Platte 2) enthält nun die mit 00 beginnenden Schlüssel (A, E und E), und die Seite, die die mit 1 beginnenden Schlüssel (R, T und X) enthält, bleibt unverändert, obwohl es nunmehr zwei auf sie weisende Zeiger gibt: einen, der angibt, daß dort mit 10 beginnende Schlüssel gespeichert werden, und einen weiteren, der angibt, daß dort mit 11 beginnende Schlüssel gespeichert werden. Nun können wir auf jeden beliebigen Datensatz zugreifen, indem wir die ersten beiden Bits seines Schlüssels benutzen, um direkt auf die Eintragung im Inhaltsverzeichnis zuzugreifen, die die Adresse der den Datensatz enthaltenden Seite enthält.

Abbildung 18.9
Abbildung 18.9 Erweiterbares Hashing: erste Seite erneut voll.

Abbildung 18.10
Abbildung 18.10 Erweiterbares Hashing: zweite Aufspaltung.

Die Abspeicherung der Datensätze in geordneter Reihenfolge innerhalb der Seiten mag als grobe Vereinfachung erscheinen, doch wir erinnern an unsere grundlegenden Annahmen, daß wir die Plattenein- und -ausgabe in Seiten-Einheiten vornehmen und daß die Verarbeitungszeit im Vergleich zu der Zeit, die für die Eingabe oder Ausgabe einer Seite benötigt wird, vernachlässigbar ist. Somit ist die Abspeicherung der Datensätze in einer Reihenfolge, die der Reihenfolge ihrer Schlüssel entspricht, kein wirklicher Aufwand; um einer Seite einen Datensatz hinzuzufügen, müssen wir die Seite in den Speicher einlesen, sie ändern und sie wieder zurückschreiben. Die für die Beibehaltung der geordneten Reihenfolge benötigte zusätzliche Zeit dürfte in typischen Fällen, wenn die Seiten nicht groß sind, unerheblich sein.

Indem wir weiter fortfahren, können wir S=10011 und E=00101 hinzufügen, bevor ein weiteres Aufspalten notwendig ist, um A=00001 hinzuzufügen. Dieses Aufspalten erfordert ebenfalls die Verdoppelung des Inhaltsverzeichnisses, wodurch die in Abbildung 18.11 dargestellte Struktur erzeugt wird. Der Prozeß der Verdoppelung des Inhaltsverzeichnisses ist einfach: Lies das alte Inhaltsverzeichnis und stelle dann das neue her, indem jede Eintragung des alten zweimal ausgeschrieben wird. Dadurch entsteht Platz für den Zeiger, der auf die soeben durch das Aufspalten erzeugte neue Seite weist.

Abbildung 18.11
Abbildung 18.11 Erweiterbares Hashing: dritte Aufspaltung.

Im allgemeinen besteht die Struktur, die durch erweiterbares Hashing erzeugt wird, aus einem Inhaltsverzeichnis (directory) aus 2d Wörtern (einem für jedes Bitmuster aus d Bits) und einer Menge von Blatt-Seiten (leaf pages), die alle Datensätze mit Schlüsseln enthalten, die mit einem bestimmten Bitmuster beginnen (mit weniger als oder genau d Bits). Ein Suchvorgang erfordert die Benutzung der führenden d Bits des Schlüssels für den Zugriff auf das Inhaltsverzeichnis. Dieses enthält Zeiger, die auf Blatt-Seiten weisen. Danach wird auf die betreffende Blatt-Seite zugegriffen, und sie wird (unter Benutzung einer beliebigen Strategie) nach dem richtigen Datensatz durchsucht. Es ist möglich, daß mehrere Eintragungen im Inhaltsverzeichnis auf die gleiche Blatt-Seite zeigen. Genau gesagt, falls eine Blatt-Seite alle Datensätze mit Schlüsseln enthält, die mit bestimmten k Bits beginnen (den Bits, die in den Abbildungen nicht schattiert sind), so gibt es 2d-k Eintragungen im Inhaltsverzeichnis, die auf diese Seite zeigen. In Abbildung 18.11 ist d = 3, und Seite 1 von Platte 2 enthält alle Datensätze mit Schlüsseln, die mit einem Bit 1 beginnen, so daß es im Inhaltsverzeichnis vier Eintragungen gibt, die auf sie zeigen.

In unserem Beispiel erforderte bis jetzt jede Aufspaltung einer Seite eine Aufspaltung des Inhaltsverzeichnisses; unter normalen Umständen kann jedoch davon ausgegangen werden, daß das Inhaltsverzeichnis nur selten aufgespalten werden muß. Das ist das wesentliche an diesem Algorithmus: Die zusätzlichen Zeiger im Inhaltsverzeichnis gestatten eine elegante Anpassung der Struktur an dynamisches Wachstum. Wenn zum Beispiel in die Struktur in Abbildung 18.11 R eingefügt wird, muß die Seite 1 auf Platte 2 aufgespalten werden, um die fünf mit 1 beginnenden Schlüssel unterzubringen; das Inhaltsverzeichnis braucht jedoch nicht zu wachsen, wie Abbildung 18.12 zeigt. Die einzige Veränderung im Inhaltsverzeichnis besteht darin, daß die letzten beiden Zeiger dahingehend geändert werden, daß sie auf die Seite 1 auf Platte 3 zeigen, die neue Seite, die beim Aufspalten erzeugt wurde, um alle mit 11 beginnenden Schlüssel (die X) in der Datenstruktur unterzubringen.

Abbildung 18.12
Abbildung 18.12 Erweiterbares Hashing: vierte Aufspaltung.

Das Inhaltsverzeichnis enthält nur Zeiger, die auf Seiten weisen. Diese Zeiger sind gewöhnlich kleiner als Schlüssel oder Datensätze, so daß sich je Seite mehr Inhaltsverzeichniseinträge unterbringen lassen. Für unser Beispiel wollen wir annehmen, daß wir doppelt so viele Eintragungen des Inhaltsverzeichnisses wie Datensätze auf einer Seite unterbringen, obwohl dieses Verhältnis in der Praxis gewöhnlich wesentlich größer ist. Wenn das Inhaltsverzeichnis mehr als eine Seite umfaßt, behalten wir einen »Wurzelknoten« im Speicher, der angibt, wo sich die Seiten des Inhaltsverzeichnisses befinden, wobei das gleiche Zugriffsschema verwendet wird. Wenn das Inhaltsverzeichnis zum Beispiel zwei Seiten umfaßt, könnte der Wurzelknoten angeben, daß sich das Inhaltsverzeichnis für alle Datensätze mit Schlüsseln, die mit 0 beginnen, auf Seite 0 von Platte 1 befindet, und daß sich das Inhaltsverzeichnis für alle mit 1 beginnenden Schlüssel auf Seite 1 von Platte 1 befindet. Für unser Beispiel erfolgt diese Aufspaltung, nachdem wir C, H, I, N, G und E einfügen. Indem wir fortfahren, erhalten wir nach dem Einfügen von X, A, M, P und L die in Abbildung 18.13 dargestellte Struktur des Plattenspeichers. (Der Klarheit halber haben wir die Platte 1 für das Inhaltsverzeichnis reserviert, obwohl es in der Praxis mit den anderen Seiten vermischt, die Seite 0 einer jeden Platte dafür reserviert oder eine andere Strategie angewandt werden könnte.)

Somit kann das Einfügen in eine erweiterbare Hashing-Struktur eine von drei Operationen erfordern, nachdem auf die Blatt-Seite zugegriffen wurde, die den Suchschlüssel enthalten könnte. Falls in der Blatt-Seite Platz vorhanden ist, wird der neue Datensatz einfach dort eingefügt; andernfalls wird die Blatt-Seite in zwei Teile gespalten (die Hälfte der Datensätze wird auf eine neue Seite verschoben). Falls das Inhaltsverzeichnis mehr als eine auf diese Blatt-Seite zeigende Eintragung aufweist, können die Eintragungen im Inhaltsverzeichnis ebenso wie die Seite aufgespalten werden. Falls das nicht der Fall ist, muß das Inhaltsverzeichnis verdoppelt werden.

In der bisher beschriebenen Gestalt ist dieser Algorithmus sehr empfindlich gegenüber einer ungünstigen Verteilung der Eingabe-Schlüssel: Der Wert von d ist die größte Anzahl von Bits, die benötigt werden, um die Schlüssel in Mengen einzuteilen, die genügend klein sind, um auf Blatt-Seiten untergebracht werden zu können; wenn daher eine große Zahl von Schlüsseln in einer großen Zahl führender Bits übereinstimmt, könnte das Inhaltsverzeichnis unvertretbar groß werden. Für reale, umfangreiche Anwendungen kann dieses Problem vermieden werden, indem ein Hashing (Zerhacken) der Schlüssel vorgenommen wird, so daß die führenden Bits (pseudo-) zufällig werden. Um einen Datensatz zu suchen, führen wir ein Hashing seines Schlüssels durch, um eine Folge von Bits zu erhalten, die wir benutzen, um auf das Inhaltsverzeichnis zuzugreifen; das Inhaltsverzeichnis sagt uns, welche Seite nach einem Datensatz mit dem gleichen Schlüssel zu durchsuchen ist. Vom Standpunkt des Hashing aus können wir uns den Algorithmus in der Weise vorstellen, daß Knoten aufgespalten werden, um Kollisionen von Hash-Werten zu berücksichtigen; hieraus entstand die Bezeichnung »erweiterbares Hashing«. Diese Methode stellt eine sehr verlockende Alternative zu B-Bäumen und indexsequentiellem Zugriff dar, da sie für jeden Suchvorgang stets genau zwei Plattenzugriffe verwendet (wie der indexsequentielle Zugriff), wobei immer noch die Fähigkeit zu einem effizienten Einfügen erhalten bleibt (wie bei B-Bäumen), ohne daß sehr viel Platz vergeudet wird.

Eigenschaft 18.4 Bei Seiten, die M Datensätze aufnehmen können, ist zu erwarten, daß erweiterbares Hashing für eine Datei mit N Datensätzen ungefähr 1,44 (N/M) Seiten benötigt. Beim Inhaltsverzeichnis ist zu erwarten, daß es ungefähr N1+1/M/M Eintragungen aufweist.

Diese Analyse ist eine komplizierte Erweiterung der Analyse von Tries, die im vorangegangenen Kapitel erwähnt wurde. Wenn M groß ist, wird etwa genausoviel Speicherplatz vergeudet wie für B-Bäume; für kleine M kann das Inhaltsverzeichnis jedoch zu groß werden. w.z.b.w.

Selbst mit Hashing müssen außergewöhnliche Maßnahmen ergriffen werden, falls große Mengen gleicher Schlüssel vorhanden sind. Diese können das Inhaltsverzeichnis künstlich vergrößern. Der Algorithmus versagt vollständig, wenn mehr gleiche Schlüssel vorhanden sind, als auf einer Blatt-Seite untergebracht werden können. (Dieser Fall tritt in unserem Beispiel tatsächlich ein, da wir fünf E haben.) Falls viele gleiche Schlüssel vorliegen, könnten wir (beispielsweise) unterschiedliche Schlüssel in der Datenstruktur voraussetzen und Zeiger verwenden, die auf verkettete Listen von Datensätzen zeigen, die gleiche Schlüssel in den Blatt-Seiten enthalten. Um die sich ergebenden Komplikationen zu sehen, untersuche man, was geschehen würde, wenn das letzte E in die Struktur in Abbildung 18.13 eingefügt werden sollte.

Abbildung 18.13
Abbildung 18.13 Zugriff mit Hilfe von erweiterbarem Hashing.

Eine weniger verhängnisvolle Situation, die berücksichtigt werden muß, entsteht dadurch, daß das Einfügen eines neuen Schlüssels dazu führen kann, daß das Inhaltsverzeichnis mehrmals aufgespalten werden muß. Dieser Fall tritt ein, wenn ein weiteres Bit nicht ausreicht, um die Schlüssel einer überfüllten Seite zu unterscheiden. Wenn zum Beispiel zwei Schlüssel mit dem Wert D=00100 in die erweiterbare Hashing-Struktur der Abbildung 18.12 eingefügt werden sollten, so wären zwei Aufspaltungen des Inhaltsverzeichnisses notwendig, da fünf Bits erforderlich sind, um D von E zu unterscheiden (das vierte Bit nützt nichts). Dies läßt sich im Rahmen einer Implementation leicht berücksichtigen, darf jedoch nicht übersehen werden.


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