Unter der Haube - Grundkurs Datenbanksysteme - page 318

Im Folgenden wird noch beschrieben, wie wir Werte in einen B + -Baum einfügen
und löschen können. Beide Verfahren beinhalten auch den soeben beschriebenen
Suchalgorithmus.

20.8.5 Einfügen

Wenn wir den Wert, den wir einfügen wollen, mit dem im vorherigen Abschnitt
beschriebenen Verfahren suchen, finden wir selbst bei der erfolglosen Suche dasje-
nige Blatt, in das er eingefügt werden muss.
Wenn wir im Beispiel aus Abbildung 20.4 den Wert 36 einfügen wollen, dann führt
uns die Suche zu dem Blatt, das 31 als einzigen Wert enthält.
Wenn in diesem Blatt noch Platz für den Eintrag ist, fügt das RDBMS den Eintrag
dort an die richtige Stelle ein. Wir beachten, dass es innerhalb des Blattes in der
Regel zu einer Verschiebung kommt. Da diese Reorganisation aber vollständig im
Arbeitsspeicher ausgeführt wird, können wir den Aufwand vernachlässigen.
Der spannende Fall tritt ein, wenn im passenden Blatt P i kein Platz mehr ist: Wenn
m die Ordnung des Baumes bezeichnet, haben wir 2m Plätze für 2m+1 Werte. In
diesem Fall erzeugen wir ein neues Blatt P und verändern die Referenzen, mit
deren Hilfe die Blätter geordnet wurden so, dass P in dieser verketteten Blattliste
zwischen P i und P i+1 liegt. Dieser Anordnung entsprechend, werden die m größ-
ten Einträge des Blattes P i

nach P verschoben. Beide Blätter, P i und P, enthalten

jetzt m + 1 und m Einträge und erfüllen somit Regel 3.
Der neue Knoten P hat jetzt auf der untersten Ebene der inneren Knoten keinen
Vorgänger. Wir nehmen den Vorgänger von P i und versuchen dort den kleinsten
Wert von P zusammen mit einer Referenz auf P einzufügen. Das klappt bestens,
wenn in diesem inneren Knoten genügend Platz ist. Anderenfalls geht das Spiel-
chen wieder von vorne los: Es wird ein neuer Knoten erzeugt, der die Hälfte der
Werte aus dem vollen inneren Knoten aufnimmt.
Natürlich muss auch bei der Zerlegung eines inneren Knotens die Buchführung
der nächsthöheren Ebene wieder in Ordnung gebracht werden. Wenn es ganz
dumm läuft, wird die Reorganisation bis zur Wurzel kaskadiert. In diesem Fall
wird die Wurzel geteilt, und es entsteht eine neue Ebene. Der Baum ist gewach-
sen.
Der Wert 87 kann beispielsweise nicht in das volle Blatt mit den Werten 85 und 90
eingefügt werden. Der Knoten wird zerlegt. Es ergibt sich, wie in Abbildung 20.5
dargestellt, ein Blatt mit den Werten 85 und 87 sowie eines mit dem Wert 90. Diese
Änderung wirkt sich nur auf den unmittelbaren Vorgängerknoten aus, der eben-
falls angepasst wird.
Wir beachten, dass der Baum zwar geändert wird, wenn wir einen Wert einfü-
gen, die Änderungen aber selbst im schlimmsten Fall jede Ebene genau einmal
betreffen.