Unter der Haube - Grundkurs Datenbanksysteme - page 319

74 85

31 42 80 95

90

12 31 42 74 80 85 90 95

23 87

Abbildung 20.5: Einfügen in einen B + -Baum

20.8.6 Löschen
Daten werden in Blätter eingefügt und wieder aus den Blättern gelöscht. Der Wert,
der gelöscht werden soll, wird wie in Abschnitt 20.8.4 gesucht und aus seinem
Blatt P entfernt.
Möglicherweise war der gelöschte Wert der kleinste im Blatt. In diesem Fall müs-
sen wir den Wert seines Vorgängers im übergeordneten Knoten ersetzen. Unter
Umständen kaskadiert diese Änderung bis zur Wurzel, aber es ist wie beim Ein-
fügen je Ebene nur eine Operation erforderlich.
Es kann aber auch passieren, dass plötzlich zu wenige Werte im Blatt P stehen
und Regel 3 verletzt ist: Möglicherweise haben wir die Mindestanzahl m - die
Ordnung des Baumes - von Werten in einem Knoten unterschritten. Wenn die-
ser Fall eintritt, versuchen wir es erst einmal im Guten und inspizieren die bei-
den Nachbarn, die den gleichen Vorgänger wie P haben. Wir entnehmen dem
linken Nachbarblatt P i 1 , und wenn das nicht reicht, dem rechten Nachbarblatt
P i + 1 einen Eintrag, sofern wir dadurch die Mindestanzahl von Einträgen in diesen
Blättern nicht unterschreiten. Wenn wir uns bei einem Nachbarn bedient haben,
müssen wir unter Umständen seinen Vorgänger in der nächsten Ebene anpassen.
Wenn wir den Mangel im Blatt P i so ausgleichen konnten, ist die Operation -
nachdem wir die Vorgänger nachjustiert haben - abgeschlossen. Wenn das alles
nichts nützt und wir P i nicht halb voll bekommen, befinden sich alle drei Blätter
P i1 , P i und P i+1 am Rande des Existenzminimums. Wir verteilen die Inhalte der
drei Blätter auf zwei Knoten. Wenn vorher alle drei Blätter knapp halb voll wa-
ren, sind die beiden Blätter, die den Bestand aufnehmen, zu etwa 75% gefüllt und
genügen somit Bedingung 3. Durch die Umverteilung wird der Vorgänger von
P i überflüssig und muss gelöscht werden. Der Vorgänger des rechten Nachbarn
wird den neuen Gegebenheiten angepasst.