Ausführliche Infos rund um den B-Baum, 2. Teil
Ein wichtiges Konzept für Datenbanken und Dateisysteme ist der B-Baum. Er sorgt für eine effiziente Struktur, die es ermöglicht, große Datenmengen zu speichern, ohne dabei an Geschwindigkeit einzubüßen. In einer kleinen Beitragsreihe schauen wir uns den B-Baum genauer an. Dabei haben wir im 1. Teil erklärt, was genau ein B-Baum in der Informatik ist und wie er erstellt wird.
Hier ist der 2. Teil!:
Inhalt
Schlüssel in den B-Baum einfügen
Einen neuen Schlüssel in den B-Baum einzufügen, ist vergleichsweise anspruchsvoll. Wie auch das Löschen von Schlüsseln setzt das Einfügen ein gutes Verständnis der Regeln und Eigenschaften eines B-Baums voraus. Außerdem muss der dazugehörige Algorithmus korrekt implementiert sein, damit die Eigenschaften des B-Baums erhalten bleiben.
Der Einfüge-Algorithmus umfasst mehrere Schritte:
-
Zunächst muss die richtige Position des neuen Schlüssels in einem Blattknoten gesucht werden.
-
Nun den Schlüssel in den Blattknoten einfügen.
-
Stellt sich heraus, dass der Knoten nach dem Einfügen zu voll ist, also mehr Schlüssel enthält als zulässig, den Knoten splitten.
-
Dann den mittleren Schlüssel des aufgeteilten Knotens in seinen Elternknoten einfügen.
-
Das Aufteilen und Einfügen in den Elternknoten so oft wiederholen, bis kein Knoten mehr zu voll ist oder bis ein neuer Schlüssel in die Wurzel eingefügt wird.
Vor allem das Splitting, also das Aufteilen, ist beim Einfügen eines neuen Schlüssels in den B-Baum sehr wichtig. Wird ein Schlüssel in einen vollen Knoten eingefügt, muss dieser Knoten gesplittet werden. Der mittlere Knoten wird dann nach oben in den Elternknoten bewegt und die Schlüssel auf jeder Seite anschließend in neue Knoten unterhalb des verschobenen Schlüssels positioniert.
Um sicherzugehen, dass der Algorithmus richtig und sinnvoll implementiert ist, sollten diese Punkte beachtet werden:
-
Es muss gewährleistet sein, dass der B-Baum seine grundlegenden Eigenschaften auch nach dem Einfügen beibehält. Das schließt die Balance des Baums, die Anzahl der Schlüssel in jedem Knoten und die richtige Position jedes Schlüssels ein.
-
Wenn der Einfüge-Algorithmus in den Code implementiert wird, muss der Speicher effizient verwaltet werden. Dazu sollte vor allem bei jedem Aufteilen ein neuer Knoten erzeugt werden, damit die neue Teilmenge von Schlüsseln gespeichert wird.
-
Nach jedem Einfügen muss der B-Baum auf Konsistenz überprüft werden. Möglich ist das, indem zum Beispiel der gesamte B-Baum durchlaufen und in diesem Zuge seine Eigenschaften überprüft werden.
Schlüssel aus dem B-Baum löschen
Das Löschen von Schlüsseln aus dem B-Baum kann sich ähnlich komplex gestalten wie das Einfügen.
Dabei sind grundsätzlich drei Szenarien denkbar:
-
Der Schlüssel, der gelöscht werden soll, befindet sich in einem Blattknoten. In diesem Fall kann der Schlüssel einfach aus dem Knoten entfernt werden.
-
Der zu löschende Schlüssel befindet sich in einem internen Knoten oder hat Kinder. Dann muss der Knoten entweder durch seinen direkten Vorgänger oder seinen direkten Nachfolger ersetzt werden. Der Vorgänger ist der maximale Schlüssel im linken Unterbaum des zu löschenden Schlüssel, der Nachfolger der maximale Schlüssel im rechten Unterbaum.
-
Der Schlüssel, der gelöscht werden soll, befindet sich in einem Knoten mit zu wenigen Schlüsseln. Um auf die notwendige Mindestanzahl zu kommen, kann der Knoten mit einem Geschwisterknoten verschmolzen, ein Knoten aus dem Geschwisterknoten verschoben oder mit einem Schlüssel aus dem Elternknoten ausgetauscht werden.
Nach dem Löschen bleiben die wesentlichen Eigenschaften des B-Baums erhalten. Zu diesen Eigenschaften gehört, dass alle Blätter das gleiche Level haben und jeder Knoten, mit Ausnahme der Wurzel, mindestens die Hälfe der Höchstanzahl an Schlüsseln enthält.
Das passiert beim Löschen
Wird ein Schlüssel aus einem B-Baum entfernt, können verschiedene Aktionen eintreten.
Was genau passiert, hängt davon ab, welche Position der Schlüssel hat und wie der B-Baum strukturiert ist:
-
Ein Schlüssel in einem Blattknoten kann einfach aus dem Knoten entfernt werden. Hat der Knoten danach zu wenige Schlüssel, müssen geeignete Maßnahmen ergriffen werden, um auf die notwendige Mindestanzahl an Schlüsseln zu kommen.
-
Befindet sich ein Schlüssel in einem internen Knoten und hat er Kinder, kann er nicht ohne Weiteres gelöscht werden. Stattdessen muss er durch seinen direkten Vorgänger oder Nachfolger ersetzt werden. Anschließend wird der Ersatzschlüssel aus dem vorherigen Knoten entfernt.
-
Hat das Löschen eines Schlüssels zur Folge, dass ein Knoten zu wenige Schlüssel hat, muss entweder ein Schlüssel von einem Geschwisterknoten verschoben oder der Knoten mit einem Geschwisterknoten verschmolzen werden. Teilweise ist alternativ möglich, den fehlenden Schlüssel durch einen Schlüssel aus dem Elternknoten zu ersetzen.
Wurde der Löschalgorithmus korrekt umsetzt, bleibt der B-Baum nach jedem Löschvorgang ein gültiger B-Baum. Alle Eigenschaften des B-Baums bleiben also erhalten. Das schließt die Höhe des Baums, die Anzahl der Schlüssel in jedem Knoten und die Position jedes Schlüssels ein.
Eine spezielle Anwendung des B-Baums ist die Verwaltung von räumlichen Daten. Warum der B-Baum dafür besonders gut geeignet ist und wie das Ganze funktioniert, erklären wir im 3. Teil.
Mehr Ratgeber, Tipps und Anleitungen:
- Ausführliche Infos rund um den B-Baum, 1. Teil
- Wen betrifft das Barrierefreiheitsstärkungsgesetz?
- Was ist Datenmapping?
- Was ist die O-Notation? 2. Teil
- Was ist die O-Notation? 1. Teil
- Infos zu Listen als Datenstruktur
- Die wichtigsten Infos rund um Suchalgorithmen, 2. Teil
- Die wichtigsten Infos rund um Suchalgorithmen, 1. Teil
Thema: Ausführliche Infos rund um den B-Baum, 2. Teil
Übersicht:
Fachartikel
Verzeichnis
Über uns
- Die 5 größten Gefahren für externe Festplatten - 6. April 2024
- Eine E-Mail an mehrere Empfänger verschicken – so geht’s richtig - 15. März 2024
- Grundlegendes Wissen zu verteilten Datenstrukturen, 2. Teil - 7. März 2024