Bayer Bäume

1.1 Suchen in Bayer-Bäumen

Das Suchen nach einem Schlüssel x in einem B-Baum der Ordnung k kann als natürliche Verallgemeinerung des von binären Suchbäumen bekannten Verfahrens aufgefaßt werden1. Man beginnt bei der Wurzel und stellt zunächst fest, ob der gesuchte Schlüssel x einer der im gerade betrachteten Knoten p gespeicherten Schlüssel s1,...,s2k (mit den Zeigern p0,...,p2k) ist. Ist das nicht der Fall, so bestimmt man das kleinste i, 1 ? i ? 2 * k, für das x < si ist, falls es ein solches i gibt; sonst ist x > s2k. Im ersten Fall setzt man die Suche bei dem Knoten fort, auf den der Zeiger pi-1 zeigt; im letzten Fall folgt man dem Zeiger p2k. Das wird solange fortgesetzt, bis man den gesuchten Schlüssel gefunden hat oder die Suche erfolglos in einem Blatt endet. Es ist klar, daß man im schlechtesten Fall höchstens alle Knoten auf einem Pfad von der Wurzel zu einem Blatt betrachten muß. Man kann es offen lassen, wie man die Suche nach einem x eines Knotens p mit den Schlüsseln s und den Zeigern p durchführt. Um dasjenige i zu finden, für das gilt, x = si bzw. das kleinste i zu bestimmen für das x < si ist, bzw. festzustellen, daß x > s2k ist kann man beispielsweise sowohl lineares als auch binäres Suchen verwenden. Da diese Suche in jedem Fall im Hauptspeicher stattfindet, beeinflußt sie die Effizienz des gesamten Suchverfahrens weit weniger als die Anzahl der Knoten, die betrachtet werden müssen, die ja unmittelbar mit der Zahl der bei der Suche nach x erforderlichen Hintergrundspeicherzugriffe zusammenhängt.



1.2 Einfügen in Bayer-Bäume

Um einen neuen Schlüssel x in einen B-Baum einzufügen, sucht man zunächst im Baum nach x. Da x im Baum noch nicht vorkommt, endet die Suche erfolglos in einem Blatt, welches die erwartete Position des Schlüssels x repräsentiert.
Für die weitere Bearbeitung befindet sich also der entsprechende Knoten jetzt im Hauptspeicher1.

Einfügen durch Spalten2

Zu Abb. 3 a

Zunächst ist der Baum leer, und die Pointervariable Wurzel hat den Wert NULL, zeigt also auf nichts.

Zu Abb. 3 b

Nach dem das Datum "A" eingefügt worden ist, entsteht die zweite Struktur.
Der Baum besteht nur aus einem Knoten, der zugleich Wurzel und Blatt ist.
Die B-Baum-Eigenschaften sind nicht verletzt.

Zu Abb. 3 c

Analog werden die Element "B", "C" und "D" eingefügt.

Zu Abb. 3 d

Komplizierter wird es, wenn das Datum "E" mit aufgenommen werden soll. Beim vergleichbaren 5-Wege-Suchbaum würde jetzt rechts von "D" ein neuer Knoten erzeugt. Die B-Baum-Eigenschaften schreiben aber vor, daß alle Wege von der Wurzel zu den Blättern gleich lang sein sollen.
Also greift man zu folgendem Trick :

Der Knoten, in dem eingefügt werden soll, wird um ein Element erweitert, und es entsteht ein Knotenüberlauf. Nach diesem Einfügen enthält der Knoten auf jeden Fall eine ungerade Anzahl von Elementen, weil 2 * k + 1 für alle k ungerade ist.

Zu Abb. 3 e

Dieser "große" Knoten kann also in zwei Söhne zerlegt werden, und nur das mittlere Element verbleibt im Vaterknoten. Das Einfügen eines Elementes hat demnach die Erzeugung von zwei neuen Knoten bewirkt, und der neue Baum genügt wieder den B-Baum-Eigenschaften

Zu Abb. 3 f

Neue Elemente werden grundsätzlich in einem Blatt eingefügt. Deswegen landen die Elemente "F" und "G" nicht in der Wurzel, sondern im rechten Blatt.

Zu Abb. 3 g

Als nächstes soll das Element "H" eingefügt werden. Das Element muß in das Blatt eingefügt werden, in dem schon die Elemente "D", "E", "F" und "G" sind. Es entsteht ein Überlauf, das Blatt muß also gesplittet werden. Das mittlere Element ("F") gelangt dabei in den darüber liegenden Knoten.

Anmerkung

Es kann natürlich passieren, daß das mittlere Element in der höheren Ebene wieder einen Split-Vorgang hervorruft, wenn dieser Knoten schon voll ist. Diese Reorganisation kann also recht komplex sein und läßt sich nur mit rekursiven Prozeduren sinnvoll lösen. Insgesamt garantiert dieser Einfügemechanismus die
B-Baum-Eigenschaften, der Baum kann nie zu einer linearen Liste entarten und behält somit seine guten Sucheigenschaften.