Problemstellung
Die B-Bäume, die wir bisher behandelt haben, waren eigentlich keine "richtigen" B-Bäume, sondern didaktisch stark vereinfachte Bäume, die so ähnlich aussehen wie B-Bäume. Wie B-Bäume tatsächlich aufgebaut sind, soll auf dieser Seite dargestellt werden. Für meine eigenen Q1- und Q2-Schüler habe ich eine Präsentation erstellt, die den Aufbau eines richtigen B-Baums zeigt. Auf die Bilder dieser Präsentation werde ich auf dieser Seite ständig zurückgreifen. Die Präsentation können Sie sich gerne hier herunterladen.
Aufbau eines richtigen B-Baums
Der B-Baum nach Einfügen der ersten vier Zahlen
Nach dem Einfügen der ersten vier Zahlen sieht der richtige B-Baum genau so aus wie der einfache B-Baum, den wir auf den vorherigen Seiten besprochen haben. Der Knoten enthält vier int-Zahlen, die aufsteigend sortiert worden sind. Die Nachfolger-Zeiger haben alle noch den Wert null. Der Übersichtlichkeit wegen wurden diese Null-Zeiger nicht in das Bild eingezeichnet.
Der B-Baum nach Einfügen der Zahl 80
Nun wird eine fünfte Zahl in den B-Baum eingefügt, die 80. Bei dem einfachen B-Baum wird jetzt ein neuer Knoten mit vier leeren Elementen erzeugt und die 80 als erstes Element in diesen Knoten geschrieben. Dann wird einer der Zeiger des Vorgängerknotens auf diesen neuen Knoten gesetzt.
Bei einem richtigen B-Baum wird das fünfte Element zunächst "provisorisch" in den alten Knoten eingefügt. Obwohl eigentlich nur vier Elemente in den Knoten passen, wird vorübergehend ein fünftes Element angelegt. In der Abbildung ist dieses fünfte Element grün markiert. Die neue Zahl steht übrigens nicht in diesem provisorischen Element, sondern rechts daneben. Das liegt daran, dass die fünf Zahlen aufsteigend sortiert werden, und das provisorische Element nimmt jetzt die mittlere Zahl auf, also die 70.
Aufteilung des Knotens in drei neue Knoten
Jetzt passiert etwas Interessantes. Der alte Knoten "platzt aus allen Nähten" und spaltet sich auf (man könnte jetzt an so eine Art Zellteilung denken...). Das mittlere Element des alten Knotens wird zum neuen Mutterknoten (Vorgängerknoten), und die Teilknoten links und rechts dieses mittleren Elementes werden zu neuen Tochterknoten (Nachfolgerknoten).
Leere Stellen oder Plätze sieht man auf dieser Abbildung nicht. Wenn man die Datenstruktur B-Baum so modellieren will, wie es auf den Abbildungen zu sehen ist, kann man natürlich keinen einfachen Array verwenden, sondern muss zu dynamischen Datenstrukturen greifen. Stacks oder Queues sind dafür allerdings nicht geeignet, da ein Direktzugriff auf die Daten möglich sein muss (zum Beispiel wegen der aufsteigenden Sortierung).
Nach dem Einfügen weiterer Zahlen sind die Tochterknoten "voll"
Wenn wir noch ein paar Zahlen in den B-Baum einfügen, sind die beiden Tochterknoten vollbesetzt. Was passiert nun, wenn noch eine Zahl eingefügt wird?
Nach dem Einfügen der 45 enthält der linke Tochterknoten fünf Elemente
Fügen wir doch mal die Zahl 45 in den B-Baum ein. Zunächst wird die neue Zahl mit der 70 in der Wurzel verglichen. Da 45 kleiner ist als 70, wird im linken Tochterbaum gesucht. Hier wird die 45 zwischen die 40 und die 50 geschoben. Der linke Tochterbaum enthält jetzt fünf Elemente, also eines zu viel. Daher wird dieser Tochterknoten aufgespalten:
Aufspalten des linken Tochterknotens
Das sieht jetzt aber komisch aus, und irgendwie auch nach Platzverschwendung. Drei Ebenen für diese wenigen Zahlen? Da muss aber aufgeräumt werden:
Nach dem Aufräumen
Die neu entstandene "Wurzel" 45 wird nun einfach in den Mutterknoten mit der 70 aufgenommen. Schließlich können vier Zahlen in jedem Knoten untergebracht werden (und vorübergehend ja sogar fünf Zahlen). Dieser B-Baum sieht schon besser aus, er hat nur zwei Ebenen und enthält immer noch keine leeren Stellen.
Dass der Baum keine leeren Stellen hat, liegt natürlich an der Art der Darstellung. Würde man diesen Baum mit statischen Arrays implementieren, müsste man jeden Knoten mit fünf Datenelementen zeichnen. Der Mutterknoten enthielte dann zwei besetzte Elemente (45, 70) und drei leere Elemente (0, 0, 0). Wir gehen aber davon aus, dass die Knoten dynamische Datenstrukturen sind, die mit der Zahl der gespeicherten Elemente wachsen.
Für Experten
In richtigen B-Bäumen, wie sie in Datenbanken eingesetzt werden, sind natürlich keine int-Zahlen als Element enthalten, sondern Zeiger auf komplexe Datensätze. Zwischen diesen Daten-Zeigern (ZD) befinden sich die Zeiger auf die Nachfolger-Knoten (ZN). Im Grunde besteht ein solcher Knoten also nur aus Zeigern:
ZN - ZD - ZN - ZD - ZN - ZD - ZN - ZD - ..... - ZN
Das heißt, man kann eine einfache dynamische Liste mit Zeigern benutzen, um einen solchen B-Baum zu verwalten. Allerdings handelt es sich um eine Art heterogene Liste, weil die Zeiger ja auf unterschiedliche Daten zeigen.
Wir wollen jetzt die Zahl 120 in den B-Baum einfügen.
Nach dem Einfügen der Zahl 120
Der Knoten ganz links im Bild enthält wieder ein zusätzliches Element. Das mittlere Element, hier also die 90, wird dann wieder nach oben gezogen, da in dem Mutterknoten noch Platz für zwei weitere Elemente ist. Der Knoten mit den fünf Zahlen wird dann wieder in zwei Knoten aufgeteilt:
Nach Aufteilung des Knotens rechts unten
Wir wollen nun so viele weitere Zahlen in den Baum einfügen, bis alle Knoten mehr oder weniger voll besetzt sind:
Nach Einfügen weiterer Zahlen
Die Wurzel des Baumes ist nun voll besetzt. Was passiert, wenn wir die Zahl 83 in den Baum einfügen?
Die 83 wird zunächst als fünftes Element in den zweiten Knoten von rechts aufgenommen. Anschließend spaltet sich dieser Knoten auf, und das mittlere Element wandert nach oben in die Wurzel. Nun enthält aber die Wurzel ein Element zu viel:
Die Wurzel enthält ein Element zu viel
Was geschieht nun? Die bisherige Wurzel splittet sich auf, das mittlere Element 70 wird zur neuen Wurzel, diese hat dann zwei Nachfolger, die ihrerseites Nachfolger haben:
Der neue B-Baum mit drei Ebenen
So sieht der B-Baum jetzt aus. Wegen der dynamischen Datenstruktur sind immer noch keine leeren Plätze zu sehen.
Ein B-Baum wächst "von unten nach oben". Neue Elemente werden zunächst in die Blätter eingebaut. Sind diese voll, werden die Blätter geteilt, und die mittleren Elemente wandern eine Ebene nach oben, wo sie in den Mutterknoten integriert werden. Ist auch dieser voll, wiederholt sich der ganze Vorgang, bis schließlich die Wurzel des Baums erreicht ist. Wenn auch die Wurzel voll ist, so wird diese nach dem gleichen Prinzip geteilt, und es entsteht eine neue Wurzel, die dann nur ein Element enthält.