EinB-Baum (englischB-tree) ist in derInformatik eineDaten- oderIndexstruktur, die häufig inDatenbanken undDateisystemen eingesetzt wird. Ein B-Baum ist ein immer vollständigbalancierter Baum, der Daten nachSchlüsseln sortiert speichert. Er kann binär sein, ist aber im Allgemeinen keinBinärbaum. Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist inamortisiert logarithmischer Zeit möglich. B-Bäume wachsen und schrumpfen, anders als viele Suchbäume, von den Blättern hin zur Wurzel.

Der B-Baum wurde1972 vonRudolf Bayer undEdward M. McCreight entwickelt. Er erwies sich als ideale Datenstruktur zur Verwaltung von Indizes für dasrelationale Datenbankmodell, das 1970 vonEdgar F. Codd entwickelt worden war. Diese Kombination führte zur Entwicklung des erstenSQL-DatenbanksystemsSystem R beiIBM.

Die Erfinder lieferten keine Erklärung für die Herkunft des NamensB-Baum. Die häufigste Interpretation ist, dassB fürbalanciert steht. Weitere Interpretationen sindB fürBayer,Barbara (nach seiner Frau),Broad,Busch,Bushy,Boeing (da Rudolf Bayer fürBoeing Scientific Research Labs gearbeitet hat),Banyanbaum (ein Baum, bei dem Äste und Wurzeln ein Netz erstellen) oderbinär aufgrund der ausgeführtenbinären Suche innerhalb eines Knotens.

In einemB-Baum kann ein Knoten – im Unterschied zuBinärbäumen – mehr als 2 Kind-Knoten haben. Dies ermöglicht es, mit einer variablen Anzahl Schlüssel (oder Datenwerte) pro Knoten die Anzahl der bei einer Datensuche zu lesenden Knoten zu reduzieren. Die maximale erlaubte Anzahl der Schlüssel ist von einem Parameter${\displaystyle t}$ (in der Literatur manchmal auch als${\displaystyle d}$,${\displaystyle k}$ oder${\displaystyle m}$ definiert), dem Verzweigungsgrad (oder Ordnung) des B-Baumes, abhängig. Die Bedeutung von${\displaystyle t}$ ist je nach Definition unterschiedlich: Entweder bezeichnet${\displaystyle t}$ die maximale Anzahl von Kindknoten – in diesem Fall ist die maximal erlaubte Anzahl von Schlüsseln${\displaystyle t-1}$, oder die minimal erlaubte Anzahl von Kindknoten^[1] – in dem Fall wäre die maximal erlaubte Anzahl an Schlüsseln${\displaystyle 2t-1}$.

Anwendung finden B-Bäume unter anderem bei Datenbanksystemen, die mit sehr großen Datenmengen umgehen müssen, von denen nur ein Bruchteil gleichzeitig in den Hauptspeicher eines Rechners passt. Die Daten sind daherpersistent auf Hintergrundspeicher (z. B.Festplatten) abgelegt und könnenblockweise gelesen werden. Ein Knoten des B-Baumes kann dann als ein Block gelesen bzw. gespeichert werden. Durch den großen Verzweigungsgrad beiB-Bäumen wird die Baumhöhe und damit die Anzahl der (langsamen) Schreib-/Lesezugriffe reduziert. Die variable Schlüsselmenge pro Knoten vermeidet zusätzlich häufigesBalancieren des Baumes. Im Kontext von Datenbanksystemen werden abweichend der o. g. Definition von${\displaystyle t}$, folgendes definiert. Wenn über den Verzweigungsgrad des B-Baumes gesprochen wird, definiert${\displaystyle t}$, welches beim Verzweigungsgrad als${\displaystyle k}$ bezeichnet wird, die minimale Anzahl von Schlüsseln eines Knotens und${\displaystyle 2k}$ die maximale Belegung eines Knotens. Daraus ergibt sich die Anzahl der Kindknoten. Wenn${\displaystyle n}$ die Anzahl vorhandener Schlüsselwerte in einem Knoten ist, dann hat dieser Knoten${\displaystyle n+1}$ Kindknoten. Mit anderen Worten hat ein Knoten mindestens${\displaystyle k+1}$ und maximal${\displaystyle 2k+1}$ Kindknoten^[2]. Die Ordnung eines B-Baumes${\displaystyle m}$ beschreibt im Gegensatz zum Verzweigungsgrad zunächst die Anzahl der Kindknoten. Ein Knoten eines Baumes mit der Ordnung${\displaystyle m}$ besitzt minimal${\displaystyle \lceil m/2\rceil }$ und maximal${\displaystyle m}$ Kindknoten. Wenn nun${\displaystyle n}$ die Anzahl vorhandener Kindknoten ist, dann hat der Vaterknoten${\displaystyle n-1}$ Schlüssel.

Alle Blattknoten sind auf gleicher Höhe. Ein B-Baum wird durch den Mindestgrad${\displaystyle t}$ definiert. Der Wert von${\displaystyle t}$ hängt von der Größe derSpeicherblöcke ab. Jeder Knoten außer dem Wurzelknoten muss mindestens${\displaystyle t-1}$ Schlüssel enthalten. Der Wurzelknoten darf mindestens 1 Schlüssel enthalten. Alle Knoten einschließlich dem Wurzelknoten dürfen höchstens${\displaystyle 2t-1}$ Schlüssel enthalten. Die Anzahl der Kindknoten eines Knotens ist gleich der Anzahl der darin enthaltenen Schlüssel plus 1. Alle Schlüssel eines Knotens sind in aufsteigender Reihenfolge sortiert. Der Kindknoten zwischen zwei Schlüsseln${\displaystyle k_1}$ und${\displaystyle k_2}$ enthält alle Schlüssel im Bereich von${\displaystyle k_1}$ und${\displaystyle k_2}$. Der B-Baum wächst und schrumpft vom Wurzelknoten, was im Gegensatz zubinären Suchbäumen steht. Wie bei anderen balancierten binären Suchbäumen ist dieZeitkomplexität zum Suchen, Einfügen und Löschen gleich${\displaystyle O(\log (n))}$. Das Einfügen eines Knotens in den B-Baum erfolgt nur am Blattknoten.^[3]

Ein vollständig besetzter B-Baum, in dem${\displaystyle t}$ als die maximal erlaubte Anzahl von Kindknoten und h als die Höhe des Baums definiert ist, speichert gerade${\displaystyle t^{h+1}-1}$ Schlüssel. So können etwa bei einem entsprechend groß gewählten${\displaystyle t}$ (z. B.${\displaystyle t=1024}$) bei einer Höhe von${\displaystyle h=3}$ bereits${\displaystyle {1024}^4-1=(2^{10}{)}^4-1=2^{40}-1=1099511627775}$ Schlüssel gespeichert werden. Da eine Suchoperation höchstens${\displaystyle h+1}$ Knotenzugriffe benötigt, müssen für jede Suchanfrage in einem solchen Baum höchstens fünf Baumknoten inspiziert werden.

Für die Höhe${\displaystyle h}$ eines B-Baumes mit${\displaystyle n}$ gespeicherten Datenelementen gilt:

${\displaystyle {\log }_{2t-1}\left(n+1\right)\le h\le {\log }_t\left(\frac{n+1}{2}\right)+1}$

Damit sind im schlimmsten Fall immer noch Zugriffe auf${\displaystyle O(\log (n))}$ Baumknoten zum Auffinden eines Datenelements notwendig. Die Konstante dieser Abschätzung ist aber deutlich geringer als bei (balancierten)binären Suchbäumen mit Höhe${\displaystyle {\log }_2(n)}$:

${\displaystyle \frac{{\log }_2(n)}{{\log }_t(\frac{n+1}{2})}\approx {\log }_2(t)}$

Bei einem minimalen Verzweigungsgrad von${\displaystyle t=1024}$ benötigt ein B-Baum damit Zugriffe auf zehnmal weniger Knoten zum Auffinden eines Datenelements. Wenn der Zugriff auf einen Knoten die Dauer der gesamten Operation dominiert (wie das beim Zugriff auf Hintergrundspeicher der Fall ist), ergibt sich dadurch eine zehnfach erhöhte Ausführungsgeschwindigkeit.^[4][5][6]

1. Ein Knoten eines B-Baumes speichert
   • eine variable Anzahl${\displaystyle s}$ von Schlüsseln${\displaystyle k_1,\dots ,k_s}$ (und optional ein pro Schlüssel zugeordnetes Datenelement),
   • eine MarkierungisLeaf, die angibt, ob es sich bei dem Knoten um ein Blatt oder einen inneren Knoten handelt.
   • Falls es sich um einen inneren Knoten handelt, zusätzlich${\displaystyle s+1}$ Verweise auf Kindknoten.
2. Für die Schlüssel in einem B-Baum gilt eine gegenüber binären Suchbäumen verallgemeinerte Sortierungsbedingung:
   • Alle Schlüssel eines Knotens sind aufsteigend sortiert.
   • Bei einem inneren Knoten${\displaystyle x}$ teilen seine Schlüssel${\displaystyle x.k_i}$ die Schlüsselbereiche seiner Unterbäume${\displaystyle x.c_j}$ in${\displaystyle s+1}$ Teilbereiche ein. Jeder Schlüssel${\displaystyle x.k_i}$ stellt demnach eine Grenze dar, dessen linksseitiger Verweis auf kleinere Werte und dessen rechtsseitig angeordneter Verweis auf größere Werte verweist. In einem Unterbaum${\displaystyle x.c_j}$ kommen folglich nur Schlüssel${\displaystyle k}$ vor, für die gilt:
     • , falls${\displaystyle j=1}$
     • , falls${\displaystyle j\in \{2,\dots ,s\}}$
     • , falls${\displaystyle j=s+1}$
3. Alle Blattknoten des B-Baumes befinden sich in gleicher Tiefe. Die Tiefe der Blattknoten ist gleich der Höhe${\displaystyle h}$ des Baumes.
4. Es gilt folgende Beschränkung für die erlaubte Anzahl von Kindverweisen bzw. Schlüsseln pro Knoten. Dazu wird eine Konstante${\displaystyle t}$ festgelegt, die den minimalen Verzweigungsgrad von Baumknoten angibt.
   • Alle Knoten außer der Wurzel haben
     • mindestens${\displaystyle t-1}$ und höchstens${\displaystyle 2t-1}$ Schlüssel und
     • mindestens${\displaystyle t}$ und höchstens${\displaystyle 2t}$ Kindverweise, wenn es sich um innere Knoten handelt.
   • Die Wurzel hat
     • mindestens${\displaystyle 1}$ und höchstens${\displaystyle 2t-1}$ Schlüssel, wenn die Wurzel der einzige Knoten im B-Baum ist, und
     • mindestens${\displaystyle 2}$ und höchstens${\displaystyle 2t}$ Kindverweise, wenn die Höhe des Baumes größer 0 ist.

Für den Spezialfall${\displaystyle t=2}$ spricht man von2-3-4-Bäumen, da Knoten in einem solchen Baum 2, 3 oder 4 Kinder haben können. Verbreitete Varianten des B-Baumes sindB⁺-Bäume, in denen die Daten nur in den Blättern gespeichert werden, undB*-Bäume, die durch eine modifizierte Überlaufbehandlung immer zu${\displaystyle 2/3}$ gefüllt sind. Alle diese Varianten werden wie auch der reguläre B-Baum in der Praxis oft eingesetzt.

Auch einR-Baum kann als balancierter Baum als Erweiterung des B-Baumes bezeichnet werden.

Die Suche nach einem Schlüssel${\displaystyle k}$ liefert denjenigen Knoten${\displaystyle x}$, der diesen Schlüssel speichert, und die Position${\displaystyle j}$ innerhalb dieses Knotens, für die gilt, dass${\displaystyle k=x.k_j}$. Enthält der Baum den Schlüssel${\displaystyle k}$ nicht, liefert die Suche das Ergebnisnicht enthalten.

Die Suche läuft in folgenden Schritten ab:

1. Die Suche beginnt mit dem Wurzelknoten${\displaystyle r}$ als aktuellem Knoten${\displaystyle x}$.
2. Ist${\displaystyle x}$ ein innerer Knoten,
   • wird die Position${\displaystyle j}$ des kleinsten Schlüssels bestimmt, der größer oder gleich${\displaystyle k}$ ist.
   • Existiert eine solche Position${\displaystyle j}$,
     • aber ist${\displaystyle k\ne x.k_j}$, kann der gesuchte Schlüssel nur in dem Unterbaum mit Wurzel${\displaystyle x.c_j}$ enthalten sein. Die Suche wird daher mit Schritt 2 und dem Knoten${\displaystyle x.c_j}$ als aktuellem Knoten fortgesetzt.
     • ansonsten wurde der Schlüssel gefunden und${\displaystyle (x,j)}$ wird als Ergebnis zurückgeliefert.
   • Existiert keine solche Position, ist der Schlüssel größer als alle im aktuellen Knoten gespeicherten Schlüssel. In diesem Fall kann der gesuchte Schlüssel nur noch in dem Unterbaum enthalten sein, auf den der letzte Kindverweis${\displaystyle x.c_{x.s+1}}$ zeigt. In diesem Fall wird die Suche mit Schritt 2 und dem Knoten${\displaystyle x.c_{x.s+1}}$ als aktuellem Knoten fortgesetzt.
3. Ist${\displaystyle x}$ ein Blattknoten,
   • Wird${\displaystyle k}$ in den Schlüsseln von${\displaystyle x}$ gesucht.
   • Wenn der Schlüssel an Position${\displaystyle j}$ gefunden wird, ist das Ergebnis${\displaystyle (x,j)}$, ansonstennicht enthalten.

In Abbildung 2 ist die Situation während der Suche nach dem Schlüssel${\displaystyle k=9}$ dargestellt. Im Schritt 2 aus obigem Algorithmus wird im aktuellen Knoten${\displaystyle x}$ die kleinste Position${\displaystyle j}$ gesucht, für die${\displaystyle 9\le x.k_j}$ gilt. Im konkreten Beispiel wird die Position${\displaystyle 2}$ gefunden, da${\displaystyle 5\le 9\le 13}$ gilt. Die Suche wird daher im rot markierten Unterbaum${\displaystyle x.c_2}$ fortgesetzt, weil sich aufgrund der B-Baum-Eigenschaft (2) der gesuchte Schlüssel${\displaystyle 9}$ nur in diesem Unterbaum befinden kann.

Das Einfügen eines Schlüssels${\displaystyle k}$ in einen B-Baum geschieht immer in einem Blattknoten.

1. In einem vorbereitenden Schritt wird der Blattknoten${\displaystyle x_{\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{t}}}$ gesucht, in den eingefügt werden muss. Dabei werden Vorkehrungen getroffen, damit die Einfügeoperation nicht die B-Baum-Bedingungen verletzt und einen Knoten erzeugt, der mehr als${\displaystyle 2t-1}$ Schlüssel enthält.
2. In einem abschließenden Schritt wird${\displaystyle k}$ unter Berücksichtigung der Sortierreihenfolge lokal in${\displaystyle x}$ eingefügt.

Die Suche von${\displaystyle x_{\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{t}}}$ läuft mit zwei Unterschieden so ab, wie unterSuchen beschrieben. Diese Unterschiede sind:

• Das Einfügen eines neuen Schlüssels${\displaystyle k}$ geschieht immer in einem Blattknoten. Dem Einfügen muss daher immer ein vollständiger Suchlauf vorhergehen, der ergibt, dass der Schlüssel${\displaystyle k}$ noch nicht existiert, und der ermittelt, in welchen Knoten er einzutragen ist. Dies kann nur ein Blattknoten sein, denn diese Aussage ist erst nach dem Durchsuchen über die gesamte Höhe des Baumes zulässig. Die Suche bricht jedoch in einem inneren Knoten ab, wenn dort der Schlüssel${\displaystyle k}$ bereits gefunden wird und ein Einfügen deshalb nicht notwendig ist.
• Bevor die Suche zu einem Kindknoten${\displaystyle x.c_j}$ absteigt, wird überprüft, ob${\displaystyle x.c_j}$ voll ist, d. h. bereits${\displaystyle 2t-1}$ Schlüssel enthält. In diesem Fall wird${\displaystyle x.c_j}$ vorsorglich geteilt. Dies garantiert, dass die Einfügeoperation mit einem einzigen Baumabstieg durchgeführt werden kann und keine anschließenden Reparaturmaßnahmen zur Wiederherstellung der B-Baum-Bedingungen durchgeführt werden müssen.

Das Teilen eines vollen Baumknotens geschieht, wie in Abbildung 3 gezeigt. Die Suche ist an Knoten${\displaystyle x}$ angekommen und würde zum Kindknoten${\displaystyle x.c_2}$ absteigen (roter Pfeil). Das heißt, die Suchposition ist${\displaystyle j=2}$. Da dieser Kindknoten voll ist, muss er vor dem Abstieg geteilt werden, um zu garantieren, dass ein Einfügen möglich ist. Ein voller Knoten hat mit${\displaystyle 2t-1}$ immer eine ungerade Anzahl von Schlüsseln. Der mittlere davon (in der Abbildung ist das Schlüssel${\displaystyle x.c_2.k_3}$) wird im aktuellen Knoten an der Suchposition${\displaystyle j}$ eingefügt. Der Knoten${\displaystyle x.c_2}$ wird in zwei gleich große Knoten mit jeweils${\displaystyle t-1}$ Schlüsseln geteilt und diese über die beiden neuen Zeigerpositionen verlinkt (zwei rote Pfeile im Ergebnis). Die Suche steigt anschließend entweder in den Unterbaum${\displaystyle x.c_2}$ oder${\displaystyle x.c_3}$ ab, je nachdem, ob der einzufügende Schlüssel kleiner oder gleich dem mittleren Schlüssel des geteilten Knotens ist oder nicht.

Das Löschen eines Schlüssels${\displaystyle k_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}}}$ ist eine komplexere Operation als das Einfügen, da hier auch der Fall betrachtet werden muss, dass ein Schlüssel aus einem inneren Knoten gelöscht wird. Der Ablauf ist dabei wie die Suche nach einem geeigneten Platz zum Einfügen eines Schlüssels, allerdings mit dem Unterschied, dass vor dem Abstieg in einen Unterbaum überprüft wird, ob dieser genügend Schlüssel (${\displaystyle \ge t}$) enthält, um eine eventuelle Löschoperation ohne Verletzung der B-Baum-Bedingungen durchführen zu können. Dieses Vorgehen ist analog zum Einfügen und vermeidet anschließende Reparaturmaßnahmen.

Enthält der Unterbaum, den die Suche für den Abstieg ausgewählt hat, die minimale Anzahl von Schlüsseln${\displaystyle t-1}$, wird entweder eineVerschiebung oder eineVerschmelzung durchgeführt. Wird der gesuchte Schlüssel in einem Blattknoten gefunden, kann er dort direkt gelöscht werden. Wird er dagegen in einem inneren Knoten gefunden, passiert die Löschung wie inLöschen aus inneren Knoten beschrieben.

Enthält der für den Abstieg ausgewählte Unterbaum nur die minimale Schlüsselanzahl${\displaystyle t-1}$, aber ein vorausgehender oder nachfolgender Geschwisterknoten hat mindestens${\displaystyle t}$ Schlüssel, wird ein Schlüssel in den ausgewählten Knoten verschoben, wie in Abbildung 4 gezeigt. Die Suche hat hier${\displaystyle x.c_2}$ für den Abstieg ausgewählt (da), dieser Knoten enthält aber nur${\displaystyle t-1}$ Schlüssel (roter Pfeil). Da der nachfolgende Geschwisterknoten${\displaystyle x.c_3}$ ausreichend viele Schlüssel enthält, kann von dort der kleinste Schlüssel${\displaystyle x.c_3.k_1}$ in den Vaterknoten verschoben werden, um im Gegenzug den Schlüssel${\displaystyle x.k_2}$ als zusätzlichen Schlüssel in den für den Abstieg ausgewählten Knoten zu verschieben. Dazu wird der linke Unterbaum von${\displaystyle x.c_3.k_1}$ zum neuen rechten Unterbaum des verschobenen Schlüssels${\displaystyle x.k_2}$. Man kann sich leicht davon überzeugen, dass dieseRotation die Sortierungsbedingungen erhält, da für alle Schlüssel${\displaystyle k}$ im verschobenen Unterbaum vor und nach der Verschiebung die Forderung${\displaystyle x.k_2\le k\le x.c_3.k_1}$ gilt. Eine symmetrische Operation kann zur Verschiebung eines Schlüssels aus einem vorausgehenden Geschwisterknoten durchgeführt werden.

Enthalten sowohl der für den Abstieg ausgewählte Unterbaum${\displaystyle x.c_2}$ als auch sein unmittelbar vorausgehender und nachfolgender Geschwisterknoten genau die minimale Schlüsselanzahl, ist eineVerschiebung nicht möglich. In diesem Fall wird eine Verschmelzung des ausgewählten Unterbaumes mit dem vorausgehenden oder nachfolgenden Geschwisterknoten gemäß Abbildung 5 durchgeführt. Dazu wird der Schlüssel aus dem Vaterknoten${\displaystyle x}$, welcher die Wertebereiche der Schlüssel in den beiden zu verschmelzenden Knoten trennt, als mittlerer Schlüssel in den verschmolzenen Knoten verschoben. Die beiden Verweise auf die jetzt verschmolzenen Kindknoten werden durch einen Verweis auf den neuen Knoten ersetzt.

Da der Algorithmus vor dem Abstieg in einen Knoten sicherstellt, dass dieser mindestens${\displaystyle t}$ anstelle der von den B-Baum-Bedingungen geforderten${\displaystyle t-1}$ Schlüssel enthält, ist gewährleistet, dass der Vaterknoten${\displaystyle x}$ eine ausreichende Schlüsselanzahl enthält, um einen Schlüssel für die Verschmelzung zur Verfügung zu stellen. Nur im Fall, dass zwei Kinder des Wurzelknotens verschmolzen werden, kann diese Bedingung verletzt sein, da die Suche bei diesem Knoten beginnt. Die B-Baum-Bedingungen fordern für den Wurzelknoten mindestens einen Schlüssel, wenn der Baum nicht leer ist. Bei Verschmelzung der letzten zwei Kinder des Wurzelknotens, wird aber sein letzter Schlüssel in das neu entstehende einzige Kind verschoben, was zu einem leeren Wurzelknoten in einem nicht leeren Baum führt. In diesem Fall wird der leere Wurzelknoten gelöscht und durch sein einziges Kind ersetzt.

Wird der zu löschende Schlüssel${\displaystyle k_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}}}$ bereits in einem inneren Knoten gefunden (${\displaystyle k_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}}=x.k_2}$ in Abbildung 6), kann dieser nicht direkt gelöscht werden, weil er für die Trennung der Wertebereiche seiner beiden Unterbäume${\displaystyle x.c_2}$ und${\displaystyle x.c_3}$ benötigt wird. In diesem Fall wird sein symmetrischer Vorgänger (oder sein symmetrischer Nachfolger) gelöscht und an seine Stelle kopiert. Der symmetrische Vorgänger ist der größte Blattknoten im linken Unterbaum${\displaystyle x.c_2}$, befindet sich also dort ganz rechts außen. Der symmetrische Nachfolger ist entsprechend der kleinste Blattknoten im rechten Unterbaum${\displaystyle x.c_3}$ und befindet sich dort ganz links außen. Die Entscheidung, in welchen Unterbaum der Abstieg für die Löschung stattfindet, wird davon abhängig gemacht, welcher genügend Schlüssel enthält. Haben beide nur die minimale Schlüsselanzahl, werden die Unterbäume verschmolzen. Damit wird keine Trennung der Wertebereiche mehr benötigt und der Schlüssel kann direkt gelöscht werden.

Abbildung 7 zeigt die Entwicklung eines B-Baumes mit minimalem Verzweigungsgrad${\displaystyle t=2}$. Knoten in einem solchen Baum können minimal einen und maximal drei Schlüssel speichern und haben zwischen zwei und vier Verweise auf Kindknoten. Man spricht daher auch von einem2-3-4-Baum. In einer praktischen Anwendung würde man dagegen einen B-Baum mit wesentlich größerem Verzweigungsgrad verwenden.

Folgende Operationen wurden auf einem 2-4 Baum (siehe Abbildung 7) durchgeführt:

• a–c) Einfügen von 5, 13 und 27 in einen anfangs leeren Baum.
• d–e) Einfügen von 9 führt zum Teilen des Wurzelknotens.
• f) Einfügen von 7 in einen Blattknoten.
• g–h) Einfügen von 3 führt zum Teilen eines Knotens.
• i–j) Um 9 löschen zu können, wird ein Schlüssel aus einem Geschwisterknoten verschoben.
• k–l) Das Löschen von 7 führt zum Verschmelzen von zwei Knoten.
• m) Löschen von 5 aus einem Blatt.
• n–q) Löschen von 3 führt zur Verschmelzung der letzten zwei Kinder des Wurzelknotens. Der entstehende leere Wurzelknoten wird durch sein einziges Kind ersetzt.

Das folgende Beispiel in derProgrammierspracheC++ zeigt die Implementierung eines B-Baums mit denFunktionensearch (suchen),insert (einfügen) undtraverse (durchlaufen). Der B-Baum wird alsKlasseBTree und seine Knoten als KlasseBTreeNode deklariert. Bei der Ausführung des Programms wird die Funktionmain verwendet.^[7]

#include<iostream>usingnamespacestd;// Deklariert die Klasse für die Knoten des B-BaumsclassBTreeNode{int*keys;// Zeiger auf das Array mit den SchlüsselnBTreeNode**childNodes;// Array von Zeigern auf das Array mit den KindknotenBTreeNode*root;// Zeiger auf den Wurzelknoten des B-Baumsintt;// Mindestgrad des Knotens (Mindestanzahl der Kindknoten, Mindestanzahl der Schlüssel plus 1)intn;// Aktuelle Zahl der SchlüsselboolisLeafNode;// Gibt an, ob der Schlüssel ein Blattknoten istpublic:// Deklariert die Klasse BTree als friend class von BTreeNode, damit BTreeNode auf private Attribute von BTree zugreifen kannfriendclassBTree;// KonstruktorBTreeNode(int_t,bool_isLeafNode){t=_t;keys=newint[2*t-1];// Deklariert ein Array für die maximale Anzahl der SchlüsselchildNodes=newBTreeNode*[2*t];// Deklariert ein Array für die maximale Anzahl der Kindknoten// Initialisiert die Attributeroot=NULL;n=0;isLeafNode=_isLeafNode;}// Diese rekursive Funktion durchläuft alle Knoten des Teilbaums mit dem aktuellen Knoten als Wurzelknoten und gibt sie auf der Konsole ausvoidtraverse(){inti;// Index für den aktuellen Kindknoten und aktuellen Schlüssel// Diese for-Schleife durchläuft alle Kindknoten und Schlüssel des aktuellen Knotensfor(i=0;i<n;i++){// Wenn der aktuelle Knoten kein Blattknoten istif(!isLeafNode){childNodes[i]->traverse();// Rekursiver Aufruf für den aktuellen Kindknoten}cout<<" "<<keys[i];// Ausgabe auf der Konsole}// Wenn der aktuelle Knoten kein Blattknoten istif(!isLeafNode){childNodes[i]->traverse();// Rekursiver Aufruf für den Kindknoten}}// Diese rekursive Funktion durchläuft die Knoten des Teilbaums mit dem aktuellen Knoten als Wurzelknoten und sucht einen Schlüssel mit dem gegebenen Wert// Diese Funktion gibt einen Zeiger auf den Knoten mit dem angegebenen Wert zurück, wenn vorhanden, sonst einen NullzeigerBTreeNode*search(intvalue){inti=0;// Initialisiert den Index für den aktuellen Schlüssel// Diese while-Schleife durchläuft das Array mit den Schlüsseln, bis ein Schlüssel größer oder gleich dem gegebenen Wert gefunden oder das Ende des Arrays erreicht istwhile(i<n&&keys[i]<value){i++;}// Wenn der gefundene Schlüssel gleich dem gegebenen Wert ist, wird ein Zeiger auf den Knoten zurückgegebenif(keys[i]==value){returnthis;}// Wenn kein Schlüssel gefunden wurde und der aktuelle Knoten ein Blattknoten ist, wird ein Nullzeiger zurückgegebenif(isLeafNode){returnNULL;}returnchildNodes[i]->search(value);// Rekursiver Aufruf der Funktion für den Kindknoten vor dem Schlüssel, der größer oder gleich dem gegebenen Wert ist}// Diese Funktion fügt den gegebenen Schlüssel in den Teilbaums mit dem aktuellen Knoten als Wurzelknoten einvoidinsert(intkey){// Wenn der Baum leer ist, wird ein Wurzelknoten mit dem gegebenen Schlüssel eingefügtif(root==NULL){root=newBTreeNode(t,true);// Erzeugt den Wurzelknotenroot->keys[0]=key;// Initialisiert den Schlüsselroot->n=1;// Aktualisiert das Attribut für die Anzahl der Schlüssel}else// Wenn der Baum nicht leer ist{// Wenn der Wurzelknoten voll istif(root->n==2*t-1){BTreeNode*newRoot=newBTreeNode(t,false);// Erzeugt einen neuen WurzelknotennewRoot->childNodes[0]=root;// Macht den alten Wurzelknoten zum Kindknoten des neuen WurzelknotensnewRoot->splitChild(0,root);// Aufruf der Funktion, teilt den alten Wurzelknotensinti=0;// Index für den Kindknotenif(newRoot->keys[0]<key)// Wenn der Schlüssel kleiner als der gegebene Schlüssel ist, Index um 1 erhöhen{i++;}newRoot->childNodes[i]->insertNonFull(key);// Fügt den Schlüssel in den Teilbaum mit dem Kindknoten als Wurzelknoten einroot=newRoot;// Setzt den neuen Wurzelknoten}else// Wenn der Wurzelknoten nicht voll ist{root->insertNonFull(key);// Aufruf der Funktion insertNonFull für den Wurzelknoten}}}// Diese rekursive Funktion fügt den gegebenen Schlüssel in einen Knoten ein, der nicht voll sein darfvoidinsertNonFull(intkey){inti=n-1;// Initialisiert den Index des Schlüssels mit dem Maximumif(isLeafNode)// Wenn der Knoten ein Blattknoten ist{// Diese while-Schleife bestimmt den Index, wo der Schlüssel eingefügt wird und schiebt alle größeren Schlüssel um einen Index weiterwhile(i>=0&&keys[i]>key){keys[i+1]=keys[i];i--;}keys[i+1]=key;// Fügt den gegebenen Schlüssel für diesen Index einn++;// Aktualisiert das Attribut für die Anzahl der Schlüssel}else// Wenn der Knoten kein Blattknoten ist{// Diese while-Schleife bestimmt den Index des Kindknotens, in den der Schlüssel eingefügt wirdwhile(i>=0&&keys[i]>key){i--;}if(childNodes[i+1]->n==2*t-1)// Wenn der Kindknoten voll ist{splitChild(i+1,childNodes[i+1]);// Teilt den Kindknoten// Bestimmt, ob der gegebene Schlüssel, links oder rechts vom mittleren Schlüssel eingefügt wirdif(keys[i+1]<key)// Wenn der Schlüssel kleiner als der gegebene Schlüssel ist, wird der Schlüssel rechts vom mittleren Schlüssel eingefügt, sonst links{i++;}}childNodes[i+1]->insertNonFull(key);// Rekursiver Aufruf für den Kindknoten, fügt den Schlüssel in den zugehörigen Teilbaum ein}}// Diese Funktion teilt den gegebenen Kindknoten des aktuellen Knotens, der voll sein mussvoidsplitChild(intindex,BTreeNode*_node){BTreeNode*node=newBTreeNode(_node->t,_node->isLeafNode);// Erzeugt einen neuen Knotennode->n=t-1;// Initialisiert das Attribut für die Anzahl der Schlüssel des neuen Knotens// Diese for-Schleife kopiert die letzten t - 1 Schlüssel vom gegebenen Kindknoten in den neuen Knotenfor(inti=0;i<t-1;i++){node->keys[i]=_node->keys[i+t];}// Wenn der Knoten kein Kindknoten istif(!node->isLeafNode){// Diese for-Schleife kopiert die letzten t Kindknoten in den neuen Knotenfor(inti=0;i<t;i++){node->childNodes[i]=_node->childNodes[i+t];}}node->n=t-1;// Aktualisiert das Attribut für die Anzahl der Schlüssel des neuen Knotens// Diese for-Schleife bestimmt den Index des Kindknotens, in den der Schlüssel eingefügt wird// Der Kindknoten rechts vom gegebenen Kindknoten um einen Index weiter geschobenfor(inti=n;i>=index+1;i--){childNodes[i+1]=childNodes[i];}childNodes[index+1]=node;// Setzt den neuen Knoten als Kindknoten mit diesem Index// Die Schlüssel rechts vom gegebenen Kindknoten werden um einen Index weiter geschobenfor(inti=n-1;i>=index;i--){keys[i+1]=keys[i];}keys[index]=_node->keys[t-1];// Kopiert den mittleren Schlüssel in den Knotenn++;// Aktualisiert das Attribut für die Anzahl der Schlüssel des aktuellen Knotens}};// Deklariert die Klasse für den B-BaumclassBTree{BTreeNode*root;// Zeiger auf den Wurzelknotenintt;// Mindestgrad der Knoten (Mindestanzahl der Kindknoten, Mindestanzahl der Schlüssel plus 1)public:// KonstruktorBTree(int_t){root=NULL;t=_t;}// Diese Funktion durchläuft alle Knoten des Baums und gibt sie auf der Konsole aufvoidtraverse(){if(root!=NULL){root->traverse();// Aufruf der Funktion für den Wurzelknoten}}// Diese sucht einen Schlüssel mit dem gegebenen Wert// Diese Funktion gibt einen Zeiger auf den Knoten mit dem angegebenen Wert zurück, wenn vorhanden, sonst einen NullzeigerBTreeNode*search(intk){returnroot==NULL?NULL:root->search(k);// Aufruf der Funktion für den Wurzelknoten}// Diese Funktion fügt den gegebenen Schlüssel einvoidinsert(intkey){if(root==NULL){root=newBTreeNode(t,true);root->keys[0]=key;root->n=1;}else{if(root->n==2*t-1){BTreeNode*newRoot=newBTreeNode(t,false);newRoot->childNodes[0]=root;newRoot->splitChild(0,root);inti=0;if(newRoot->keys[0]<key){i++;}newRoot->childNodes[i]->insertNonFull(key);root=newRoot;}else{root->insertNonFull(key);}}}};// Hauptfunktion die das Programm ausführtintmain(){// Erzeugt einen B-Baum mit Mindestgrad 3 und fügt 8 Knoten einBTreebTree(3);bTree.insert(10);bTree.insert(20);bTree.insert(5);bTree.insert(6);bTree.insert(12);bTree.insert(30);bTree.insert(7);bTree.insert(17);cout<<"Durchlauf des erzeugten B-Baums:"<<endl;// Ausgabe auf der KonsolebTree.traverse();// Aufruf der Funktion, die die Knoten durchläuft und die Schlüssel auf der Konsole ausgibtcout<<endl;// Ruft die Funktion auf, die einen Knoten mit dem Schlüssel 6 sucht und gibt das Ergebnis auf der Konsole ausintk=6;bTree.search(k)!=NULL?cout<<"Es ist ein Knoten mit dem Schlüssel "<<k<<" vorhanden"<<endl:cout<<"Es ist kein Knoten mit dem Schlüssel "<<k<<" vorhanden"<<endl;// Ruft die Funktion auf, die einen Knoten mit dem Schlüssel 15 sucht und gibt das Ergebnis auf der Konsole ausk=15;bTree.search(k)!=NULL?cout<<"Es ist ein Knoten mit dem Schlüssel "<<k<<" vorhanden"<<endl:cout<<"Es ist kein Knoten mit dem Schlüssel "<<k<<" vorhanden"<<endl;}

• R-Baum ist ein verwandtes Indexverfahren für mehrdimensionale Daten.
• B⁺-Baum undB*-Baum sind B-Baum-Varianten.
• 2-3-4-Baum ist ein Spezialfall eines B-Baumes mit minimalem Verzweigungsgrad${\displaystyle t=2}$.
• AVL-Baum
• Rot-Schwarz-Baum

Deutsch

• Niklaus Wirth:Algorithmen und Datenstrukturen mit Modula-2. Stuttgart 1986,ISBN 3-519-02260-5.
• T. Ottmann, P. Widmayer:Algorithmen und Datenstrukturen-3. Spektrum, Heidelberg/Berlin/Oxford 1996,ISBN 3-8274-0110-0, S. 317–327.
• Alfons Kemper, André Eickler: Datenbanksysteme. Oldenbourg Verlag, München 2009,ISBN 978-3-486-59018-0, S. 218

Englisch

• R. Bayer, E. McCreight:Organization and Maintenance of Large Ordered Indexes. In:Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control. 1970, S. 107–141.^[8]
• R. Bayer, E. McCreight:Organization and Maintenance of Large Ordered Indexes. In:Acta Informatica, Band 1, 1972, S. 173–189.
• R. Bayer, E. McCreight:Symmetric binary B-Trees: data structure and maintenance algorithms. In:Acta Informatica, Band 1, 1972, S. 290–306.

Tools zum Ausprobieren von B-Bäumen:

• cs.usfca.edu – Animierte JavaScript-Version von David Galles
• slady.net – B-Baum Java-Applet
• ats.oka.nu – Flash-Applet

1. ↑Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest, Clifford Stein:Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001,ISBN 0-262-03293-7,S. 439 (englisch). 
2. ↑Alfons Kemper, André Eickler:Datenbanksysteme eine Einführung. 8. aktualisierte und erw. Auflage. Oldenbourg Verlag, München 2011,ISBN 978-3-486-59834-6,S. 217. 
3. ↑GeeksforGeeks:Introduction of B-Tree
4. ↑Ludwig-Maximilians-Universität München, Institut für Informatik:B-Bäume I
5. ↑T. Härder, Universität Kaiserslautern:Mehrwegbäume, B-Bäume, Höhe des B-Baumes
6. ↑Prof. Dr. E. Rahm, Universität Leipzig, Institut für Informatik:Algorithmen und Datenstrukturen 2
7. ↑GeeksforGeeks:Insert Operation in B-Tree
8. ↑R. Bayer, E. McCreight:Organization and Maintenance of Large Ordered Indices. In:Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control (= SIGFIDET ’70). ACM, New York NY 1970,S. 107–141,doi:10.1145/1734663.1734671 (acm.org [abgerufen am 20. Februar 2019]). 

• Wikipedia:Lesenswert
• Suchbaum
• Datenbankindex