Robert Sedgewick: Algorithmen

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


18. Externes Suchen



B-Bäume

Ein besserer Weg zur Realisierung der Suche in einer dynamischen Situation ist die Verwendung von ausgeglichenen Bäumen. Um die Anzahl der (relativ teuren) Plattenzugriffe zu verringern, ist es sinnvoll, eine große Anzahl von Schlüsseln pro Knoten zuzulassen, so daß die Knoten einen hohen Verzweigungsgrad besitzen. Solche Bäume wurden von R. Bayer und E. McCreight, die als erste die Benutzung von ausgeglichenen Mehrwege-Bäumen für das externe Suchen betrachteten, B-Bäume genannt. (Von vielen Autoren wird der Begriff »B-Baum« auf die Beschreibung der exakten Datenstruktur beschränkt, die durch den von Bayer und McCreight vorgeschlagenen Algorithmus erzeugt wird; wir wollen ihn in allgemeinerem Sinne verwenden, um »externe ausgeglichene Bäume« zu bezeichnen.)

Der Top-Down-Algorithmus, den wir für 2-3-4-Bäume verwendeten (siehe Kapitel 15), läßt sich leicht auf die Behandlung von mehr Schlüsseln pro Knoten verallgemeinern: Nehmen wir an, daß zwischen 1 und M - 1 Schlüssel pro Knoten vorhanden sind (und somit zwischen 2 und M Verkettungen pro Knoten). Die Suche läuft dann in einer zu 2-3-4-Bäumen analogen Weise ab: Um von einem Knoten zum nächsten zu gelangen, finde zuerst im aktuellen Knoten das richtige Intervall für den Suchschlüssel und verlasse ihn dann über die entsprechende Verkettung, um zum nächsten Knoten zu gelangen. Fahre in dieser Weise fort, bis ein äußerer Knoten erreicht wird, und füge dann den neuen Schlüssel in den letzten erreichten inneren Knoten ein. Wie bei Top-Down 2-3-4-Bäumen ist es erforderlich, auf dem Weg im Baum abwärts Knoten »aufzuspalten«, welche »voll« sind; jedesmal, wenn wir einen k-Knoten vorfinden, der mit einem M-Knoten verbunden ist, ersetzen wir ihn durch einen (k+1)-Knoten, der mit zwei (M/2)-Knoten verbunden ist (damit eine Aufspaltung in gleich große Teile möglich ist, nehmen wir an, daß M gerade ist). Dadurch wird garantiert, daß Platz für das Einfügen des neuen Knotens vorhanden ist, wenn die unterste Ebene erreicht wird.

Abbildung 18.3 zeigt den B-Baum, der für M = 4 und unsere Beispielschlüssel erzeugt wird. Dieser Baum besitzt 13 Knoten, von denen jeder einer Seite einer Platte entspricht. Jeder Knoten muß sowohl Verkettungen als auch Datensätze enthalten. Die Wahl von M = 4, auch wenn sie wieder die uns vertrauten 2-3-4-Bäume liefert, wurde getroffen, um folgende Tatsache zu verdeutlichen: Vorher konnten wir vier Datensätze pro Seite unterbringen; jetzt lassen sich nur drei unterbringen, damit Platz für die Verkettungen bleibt. Der tatsächlich verwendete Speicherplatz hängt von der jeweiligen Größe der Datensätze und Verkettungen ab. Später lernen wir ein Verfahren kennen, bei dem diese Vermischung von Datensätzen und Verkettungen vermieden wird.

Abbildung 18.3
Abbildung 18.3 Ein B-Baum.

Ebenso wie wir den Hauptindex für die indexsequentielle Suche im Speicher ablegten, ist es sinnvoll, den Wurzelknoten des B-Baumes zu speichern. Für den in Abbildung 18.3 dargestellten B-Baum gibt der Wurzelknoten an, daß sich die Wurzel des Unterbaumes, der Datensätze mit Schlüsseln kleiner oder gleich E enthält, auf Seite 0 von Platte 1 befindet, die Wurzel des Unterbaumes mit Schlüsseln kleiner oder gleich N (aber nicht kleiner als E) auf Seite 1 von Platte 1 und die Wurzel des Unterbaumes mit Schlüsseln größer oder gleich N auf Seite 2 von Platte 1. Die anderen Knoten für unser Beispiel könnten in der Weise gespeichert werden, wie es Abbildung 18.4 zeigt.

Abbildung 18.4
Abbildung 18.4 Zugriff mit Hilfe eines B-Baumes.

Knoten werden in diesem Beispiel den Plattenseiten zugewiesen, indem einfach im Baum abwärts vorgegangen wird, wobei auf jeder Ebene von rechts nach links vorgegangen wird. Die Knoten werden zunächst der Platte 1 zugewiesen, dann der Platte 2 usw. Wir vermeiden das Speichern von leeren Verkettungen, indem wir aufpassen, wann die unterste Ebene erreicht ist: In diesem Falle haben alle Knoten auf den Platten 2, 3 und 4 nur leere Verkettungen (die nicht gespeichert zu werden brauchen). In einer praktischen Anwendung spielen noch weitere Überlegungen eine Rolle. Zum Beispiel könnte es besser sein zu vermeiden, daß alle Suchvorgänge die Platte 1 durchlaufen, indem zuerst Seite 0 alle Platten belegt wird usw. Tatsächlich werden auf Grund der Dynamik der Erzeugung des Baums kompliziertere Strategien benötigt (man betrachte die Schwierigkeit der Implementation einer split-Routine (Aufspalten), die eine der obigen Strategien berücksichtigt).

Eigenschaft 18.2 Ein Suchen oder ein Einfügen in einen B-Baum der Ordnung M mit N Datensätzen erfordert garantiert weniger als logM/2N Plattenzugriffe, was für praktische Zwecke eine konstante Zahl ist (solange M nicht klein ist).

Diese Eigenschaft folgt aus der Beobachtung, daß alle Knoten im »Inneren« des B-Baumes (Knoten, die nicht die Wurzel und nicht Blätter sind) zwischen M/2 und M Schlüssel haben, da sie durch das Spalten eines vollen Knotens mit M Schlüsseln gebildet werden, und daß ihre Größe nur zunehmen kann (wenn ein weiter unten befindlicher Knoten gespalten wird). Im ungünstigsten Fall bilden diese Knoten einen vollständigen Baum vom Grad M/2, woraus sich unmittelbar die in der Behauptung angegebene Schranke ergibt. w.z.b.w.

Eigenschaft 18.3 Ein B-Baum der Ordnung M, der aus N zufälligen Datensätzen erzeugt wurde, hat im Durchschnitt ungefähr 1,44N/M Knoten.

Der Beweis dieser Tatsache würde über den Rahmen dieses Buches hinausgehen; es ist jedoch anzumerken, daß im ungünstigsten Fall, wenn alle Knoten ungefähr halb voll sind, der Umfang des vergeudeten Platzes etwa N erreicht. w.z.b.w.

Im obigen Beispiel waren wir gezwungen, M = 4 zu wählen, da es notwendig war, Platz für Verkettungen in den Knoten zu reservieren. Doch am Ende ergab es sich, daß wir in den meisten Knoten keine Verkettungen verwendeten, da die meisten Knoten in einem B-Baum äußere Knoten sind und die meisten Verkettungen leer sind. Außerdem kann auf den höheren Ebenen des Baumes ein viel größerer Wert von M verwendet werden, wenn wir in den inneren Knoten wie beim indexsequentiellen Zugriff nur Schlüssel (keine vollständigen Datensätze) speichern. Um zu sehen, wie in unserem Beispiel aus diesen Beobachtungen Nutzen gezogen werden kann, nehmen wir an, daß wir bis zu sieben Schlüssel und acht Verkettungen auf einer Seite unterbringen können, so daß wir M = 8 für die inneren Knoten und M = 5 für die Knoten der untersten Ebene benutzen können (nicht M = 4, da auf der untersten Ebene kein Platz für Verkettungen reserviert werden muß). Ein Knoten der untersten Ebene wird aufgespalten, wenn ihm ein fünfter Datensatz hinzugefügt wird (in einen Knoten mit zwei Datensätzen und einen mit drei Datensätzen); das Aufspalten endet mit dem »Einfügen« des Schlüssels des mittleren (spaltenden) Datensatzes in den darüberliegenden Knoten, wo Platz vorhanden ist, da der darüberliegende Baum als ein normaler B-Baum für M = 8 behandelt worden ist (mit den gespeicherten Schlüsseln und nicht Datensätzen). Dies führt zu dem Baum, den Abbildung 18.5 zeigt.

Abbildung 18.5
Abbildung 18.5 Ein B-Baum, der nur an den äußeren Knoten Datensätze besitzt.

Der Effekt dürfte für eine typische Anwendung wesentlich stärker in Erscheinung treten, da der Verzweigungsgrad des Baumes etwa um das Verhältnis von Datensatzgröße zu Schlüsselgröße erhöht wird, welches gewöhnlich groß ist. Auch kann bei dieser Organisationsform der »Index« (der Schlüssel und Verkettungen enthält) wie bei der indexsequentiellen Suche von den eigentlichen Datensätzen getrennt werden. Abbildung 18.6 zeigt, wie der Baum aus Abbildung 18.5 gespeichert werden könnte: Der Wurzelknoten befindet sich auf Seite 0 von Platte 1 (dort ist genügend Platz für ihn vorhanden, da der Baum in Abbildung 18.5 einen Knoten weniger hat als der Baum in Abbildung 18.3), obwohl er, wie bereits erwähnt, in den meisten Anwendungsfällen wahrscheinlich im Speicher abgelegt würde. Die anderen Bemerkungen betreffs der Anordnung der Knoten auf den Platten treffen hier ebenfalls zu.

Abbildung 18.6
Abbildung 18.6 Zugriff mit Hilfe eines B-Baumes, der nur an den äußeren Knoten Datensätze besitzt.

Es liegen nun zwei Werte von M vor, einer für die inneren Knoten, der den Verzweigungsgrad des Baumes (MI) bestimmt, und einer für die Knoten der untersten Ebene, der die Zuordnung der Datensätze zu den Seiten bestimmt (MB). Um einerseits die Anzahl der Plattenzugriffe zu minimieren, wollern wir sowohl MI als auch MB so groß wie möglich wählen, selbst wenn dann einige zusätzliche Berechnungen erforderlich sind. Andererseits möchten wir MI nicht übermäßig groß wählen, da dann die meisten Knoten im Baum weitgehend leer wären und Platz vergeudet würde, und wir möchten MB nicht übermäßig groß wählen, da dies auf eine sequentielle Suche in den Knoten der untersten Ebene hinauslaufen würde. Gewöhnlich ist es am besten, sowohl MI als auch MB mit der Seitengröße zu verknüpfen. Die naheliegende Wahl für MB ist die Anzahl von Datensätzen, die sich auf einer Seite unterbringen lassen (plus eins): das Ziel der Suche ist es, die Seite zu finden, die den gesuchten Datensatz enthält. Falls für MI die Anzahl der Schlüssel gewählt wird, die sich auf zwei bis vier Seiten unterbringen lassen, so besitzt der B-Baum selbst für sehr große Dateien (ein drei Ebenen umfassender Baum mit MI = 2048 kann bis zu 10243, oder mehr als eine Milliarde, Eintragungen aufnehmen) gewöhnlich nur drei Ebenen. Es sei jedoch daran erinnert, daß der Wurzelknoten des Baumes, auf den für jede Operation zugegriffen wird, im Speicher abgelegt wird, so daß nur zwei Plattenzugriffe erforderlich sind, um ein beliebiges Element in der Datei zu finden.

Wie am Ende von Kapitel 15 kurz erwähnt wurde, wird für B-Bäume gewöhnlich eine kompliziertere Einfüge-Methode angewandt (obwohl die Unterscheidung zwischen Top-Down- und Bottom-Up-Verfahren für Bäume mit drei Ebenen an Bedeutung verliert). In technischer Hinsicht sollten die hier beschriebenen Bäume als »Top-Down B-Bäume« bezeichnet werden, um sie von denen zu unterscheiden, die für gewöhnlich in der Literatur betrachtet werden. Viele weitere Varianten wurden beschrieben, von denen einige für die externe Suche recht wichtig sind. Zum Beispiel kann, wenn ein Knoten voll wird, das Aufspalten (und die resultierenden halbleeren Knoten) vermieden werden, indem ein Teil des Knoteninhalts in dessen »Geschwister«-Knoten (falls dieser nicht zu voll ist) »umgeladen« wird. Dies führt zu einer besseren Ausnutzung des Platzes innerhalb der Knoten, was bei einer umfangreichen Plattensuchanwendung gewöhnlich eine der Hauptaufgaben ist.


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