Ein B-Baum (englisch B-tree) ist in der Informatik eine Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B-Baum ist ein immer vollständig balancierter Baum, der Daten nach Schlüsseln sortiert speichert. Er kann binär sein, ist aber im Allgemeinen kein Binärbaum. Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist in amortisiert logarithmischer Zeit möglich. B-Bäume wachsen und schrumpfen, anders als viele Suchbäume, von den Blättern hin zur Wurzel.

Geschichte und Namensgebung

Der B-Baum wurde 1972 von Rudolf Bayer und Edward M. McCreight entwickelt. Er erwies sich als ideale Datenstruktur zur Verwaltung von Indizes für das relationale Datenbankmodell, das 1970 von Edgar F. Codd entwickelt worden war. Diese Kombination führte zur Entwicklung des ersten SQL-Datenbanksystems System R bei IBM.

Die Erfinder lieferten keine Erklärung für die Herkunft des Namens B-Baum. Die häufigste Interpretation ist, dass B für balanciert steht. Weitere Interpretationen sind B für Bayer, Barbara (nach seiner Frau), Broad, Busch, Bushy, Boeing (da Rudolf Bayer für Boeing Scientific Research Labs gearbeitet hat), Banyanbaum (ein Baum, bei dem Äste und Wurzeln ein Netz erstellen) oder binär aufgrund der ausgeführten binären Suche innerhalb eines Knotens.

Eigenschaften

In einem B-Baum kann ein Knoten – im Unterschied zu Binä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 – 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 daher persistent auf Hintergrundspeicher (z. B. Festplatten) abgelegt und können blockweise gelesen werden. Ein Knoten des B-Baumes kann dann als ein Block gelesen bzw. gespeichert werden. Durch den großen Verzweigungsgrad bei B-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äufiges Balancieren 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. 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 der Speicherblö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-Tree wächst und schrumpft vom Wurzelknoten, was im Gegensatz zu binären Suchbäumen steht. Wie bei anderen balancierten binären Suchbäumen ist die Zeitkomplexitä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.

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={1\,099\,511\,627\,775}}$ 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.

Definitionen

1. Ein Knoten eines B-Baumes speichert
   • eine variable Anzahl ${\displaystyle s}$ von Schlüsseln ${\displaystyle k_{1},\ldots ,k_{s}}$ (und optional ein pro Schlüssel zugeordnetes Datenelement),
   • eine Markierung isLeaf, 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:
     • ${\displaystyle k<x.k_{j}}$, falls ${\displaystyle j=1}$
     • ${\displaystyle x.k_{j-1}<k<x.k_{j}}$, falls ${\displaystyle j\in \{2,\ldots ,s\}}$
     • ${\displaystyle x.k_{j-1}<k}$, 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 k}$ und höchstens ${\displaystyle 2k}$ Schlüssel und
     • mindestens ${\displaystyle k+1}$ und höchstens ${\displaystyle 2k+1}$ Kindverweise, wenn es sich um innere Knoten handelt.
   • Die Wurzel hat
     • mindestens ${\displaystyle 1}$ und höchstens ${\displaystyle 2k}$ Schlüssel, wenn die Wurzel der einzige Knoten im B-Baum ist, und
     • mindestens ${\displaystyle 2}$ und höchstens ${\displaystyle 2k+1}$ Kindverweise, wenn die Höhe des Baumes größer 0 ist.

Spezialfälle und Varianten

Für den Spezialfall ${\displaystyle t=2}$ spricht man von 2-3-4-Bäumen, da Knoten in einem solchen Baum 2, 3 oder 4 Kinder haben können. Verbreitete Varianten des B-Baumes sind B⁺-Bäume, in denen die Daten nur in den Blättern gespeichert werden, und B*-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 ein R-Baum kann als balancierter Baum als Erweiterung des B-Baumes bezeichnet werden.

Operationen

Beispiel

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 einem 2-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.

Programmierung

Das folgende Beispiel in der Programmiersprache C++ zeigt die Implementierung eines B-Baums mit den Funktionen search (suchen), insert (einfügen) und traverse (durchlaufen). Der B-Baum wird als Klasse BTree und seine Knoten als Klasse BTreeNode deklariert. Bei der Ausführung des Programms wird die Funktion main verwendet.

#include <iostream>
using namespace std;

// Deklariert die Klasse für die Knoten des B-Baums
class BTreeNode
{
    int* keys; // Zeiger auf das Array mit den Schlüsseln
    BTreeNode** childNodes; // Array von Zeigern auf das Array mit den Kindknoten
    BTreeNode* root; // Zeiger auf den Wurzelknoten des B-Baums
    int t; // Mindestgrad des Knotens (Mindestanzahl der Kindknoten, Mindestanzahl der Schlüssel plus 1)
    int n; // Aktuelle Zahl der Schlüssel
    bool isLeafNode; // Gibt an, ob der Schlüssel ein Blattknoten ist
public:
    // Deklariert die Klasse BTree als friend class von BTreeNode, damit BTreeNode auf private Attribute von BTree zugreifen kann
    friend class BTree;

    // Konstruktor
    BTreeNode(int _t, bool _isLeafNode)
    {
        t = _t;
        keys = new int[2 * t - 1]; // Deklariert ein Array für die maximale Anzahl der Schlüssel
        childNodes = new BTreeNode * [2 * t]; // Deklariert ein Array für die maximale Anzahl der Kindknoten
        // Initialisiert die Attribute
        root = 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 aus
    void traverse()
    {
        int i; // Index für den aktuellen Kindknoten und aktuellen Schlüssel
        // Diese for-Schleife durchläuft alle Kindknoten und Schlüssel des aktuellen Knotens
        for (i = 0; i < n; i++)
        {
            // Wenn der aktuelle Knoten kein Blattknoten ist
            if (!isLeafNode)
            {
                childNodes[i]->traverse();// Rekursiver Aufruf für den aktuellen Kindknoten
            }
            cout << " " << keys[i]; // Ausgabe auf der Konsole
        }
        // Wenn der aktuelle Knoten kein Blattknoten ist
        if (!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 Nullzeiger
    BTreeNode* search(int value)
    {
        int i = 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 ist
        while (i < n && keys[i] < value)
        {
            i++;
        }
        // Wenn der gefundene Schlüssel gleich dem gegebenen Wert ist, wird ein Zeiger auf den Knoten zurückgegeben
        if (keys[i] == value)
        {
            return this;
        }
        // Wenn kein Schlüssel gefunden wurde und der aktuelle Knoten ein Blattknoten ist, wird ein Nullzeiger zurückgegeben
        if (isLeafNode)
        {
            return NULL;
        }
        return childNodes[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 ein
    void insert(int key)
    {
        // Wenn der Baum leer ist, wird ein Wurzelknoten mit dem gegebenen Schlüssel eingefügt
        if (root == NULL)
        {
            root = new BTreeNode(t, true); // Erzeugt den Wurzelknoten
            root->keys[0] = key; // Initialisiert den Schlüssel
            root->n = 1; // Aktualisiert das Attribut für die Anzahl der Schlüssel
        }
        else // Wenn der Baum nicht leer ist
        {
            // Wenn der Wurzelknoten voll ist
            if (root->n == 2 * t - 1)
            {
                BTreeNode* newRoot = new BTreeNode(t, false); // Erzeugt einen neuen Wurzelknoten
                newRoot->childNodes[0] = root; // Macht den alten Wurzelknoten zum Kindknoten des neuen Wurzelknotens
                newRoot->splitChild(0, root); // Aufruf der Funktion, teilt den alten Wurzelknotens
                int i = 0; // Index für den Kindknoten
                if (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 ein
                root = 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 darf
    void insertNonFull(int key)
    {
        int i = n - 1; // Initialisiert den Index des Schlüssels mit dem Maximum
        if (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 weiter
            while (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 ein
            n++; // 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 wird
            while (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 wird
                if (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 muss
    void splitChild(int index, BTreeNode* _node)
    {
        BTreeNode* node = new BTreeNode(_node->t, _node->isLeafNode); // Erzeugt einen neuen Knoten
        node->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 Knoten
        for (int i = 0; i < t - 1; i++)
        {
            node->keys[i] = _node->keys[i + t];
        }
        // Wenn der Knoten kein Kindknoten ist
        if (!node->isLeafNode)
        {
            // Diese for-Schleife kopiert die letzten t Kindknoten in den neuen Knoten
            for (int i = 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 geschoben
        for (int i = 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 geschoben
        for (int i = n - 1; i >= index; i--)
        {
            keys[i + 1] = keys[i];
        }
        keys[index] = _node->keys[t - 1]; // Kopiert den mittleren Schlüssel in den Knoten
        n++; // Aktualisiert das Attribut für die Anzahl der Schlüssel des aktuellen Knotens
    }
};

// Deklariert die Klasse für den B-Baum
class BTree
{
    BTreeNode* root; // Zeiger auf den Wurzelknoten
    int t; // Mindestgrad der Knoten (Mindestanzahl der Kindknoten, Mindestanzahl der Schlüssel plus 1)
public:
    // Konstruktor
    BTree(int _t)
    {
        root = NULL;
        t = _t;
    }

    // Diese Funktion durchläuft alle Knoten des Baums und gibt sie auf der Konsole auf
    void traverse()
    {
        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 Nullzeiger
    BTreeNode* search(int k)
    {
        return root == NULL ? NULL : root->search(k); // Aufruf der Funktion für den Wurzelknoten
    }

    // Diese Funktion fügt den gegebenen Schlüssel ein
    void insert(int key)
    {
        if (root == NULL)
        {
            root = new BTreeNode(t, true);
            root->keys[0] = key;
            root->n = 1;
        }
        else
        {
            if (root->n == 2 * t - 1)
            {
                BTreeNode* newRoot = new BTreeNode(t, false);
                newRoot->childNodes[0] = root;
                newRoot->splitChild(0, root);
                int i = 0;
                if (newRoot->keys[0] < key)
                {
                    i++;
                }
                newRoot->childNodes[i]->insertNonFull(key);
                root = newRoot;
            }
            else
            {
                root->insertNonFull(key);
            }
        }
    }
};

// Hauptfunktion die das Programm ausführt
int main()
{
    // Erzeugt einen B-Baum mit Mindestgrad 3 und fügt 8 Knoten ein
    BTree bTree(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 Konsole
    bTree.traverse(); // Aufruf der Funktion, die die Knoten durchläuft und die Schlüssel auf der Konsole ausgibt
    cout << endl;
    // Ruft die Funktion auf, die einen Knoten mit dem Schlüssel 6 sucht und gibt das Ergebnis auf der Konsole aus
    int k = 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 aus
    k = 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;
}

Ähnliche Baumstrukturen

• R-Baum ist ein verwandtes Indexverfahren für mehrdimensionale Daten.
• B⁺-Baum und B*-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

Literatur

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.
• 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.

Weblinks

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

Einzelnachweise

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. 
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]).