Databases Reference
In-Depth Information
Wenn wir im Beispiel aus Abbildung 20.4 den Wert 42 entfernen, ist das zugehö-
rige Blatt leer. Da beide Nachbarn nur einen Wert enthalten, können dort keine
Werte „geborgt“ werden. Wir verschmelzen also das leere Blatt und das Blatt mit
dem Wert 31 zu einem einzigen und passen die Verkettung der Blätter an. Den
Wert 42 entfernen wir aus dem Vorgängerknoten. Es ergibt sich der Baum aus
Abbildung 20.6.
74
85
80
31
95
12
23
31
74
80
85 90
95
Abbildung 20.6:
Löschen aus einem B
+
-Baum
Wie beim Einfügen kann es auch vorkommen, dass das Löschen bis zur obers-
ten Ebene kaskadiert. Dies ist der Grund dafür, dass Regel 3 eine Ausnahme für
die Wurzel enthält: Als einziger Knoten darf sie auch weniger als halb voll sein.
Bei allen Teiloperationen, die beim Löschen und der möglichen Kaskade durch-
geführt werden, sind in jeder Ebene maximal drei Knoten betroffen, so dass die
Anzahl der Transporte zwischen Festplatte und Arbeitsspeicher proportional zur
Höhe des Baumes ist.
20.8.7
Wie schnell ist das?
Die Algorithmen zum Ändern des Baumes sorgen dafür, dass er niemals ins Un-
gleichgewicht gerät. Sowohl beim Einfügen als auch beim Löschen haben wir
außerdem gesehen, dass in jeder Ebene maximal drei Änderungen durchgeführt
werden. Die Laufzeit der Operationen ist somit von der Höhe des Baumes - al-
so der Anzahl der Ebenen - abhängig. Man kann berechnen, dass die Höhe eines
Baumes logarithmisch von der Anzahl der Werte im Baum abhängt. Somit haben
sämtliche Operationen logarithmische Laufzeiten. Die Praxis zeigt, dass aufgrund
der vielen Werte, die in einer Indexseite Platz haben, es selten zu Bäumen mit einer
Höhe von mehr als 5 Ebenen kommt. Wir haben von der Plausibilität dieser Eigen-
schaft bereits in Abschnitt 20.8.2 überzeugt. Von sehr „breiten“ Indexwerten, wie
sie beispielsweise zu Spalten gehören, die den Typ
varchar(100)
haben, kön-
nen wir also davon ausgehen, dass wir mit einer konstanten Zahl an Operationen
Werte in B
+
-Bäume suchen, löschen und einfügen können.
