Ein B-Baum-Index ist eine balancierte Baumdatenstruktur, die in Datenbanken häufig verwendet wird, um große Datenmengen effizient zu organisieren und zu durchsuchen.
B-Bäume ähneln sehr den binären Suchbäumen (BST), jedoch können die Knoten in einem B-Baum mehr als zwei Kinder haben. Weitere Informationen zu BSTs finden Sie im Kurs: Algorithmen und Datenstrukturen Übersicht.

Ein B-Baum speichert Schlüssel in sortierter Reihenfolge innerhalb der Knoten, was eine schnelle Datenabfrage durch hierarchisches Durchlaufen vom Wurzel- bis zum Blattknoten ermöglicht. B-Baum-Indizierung eignet sich besonders für Bereichsabfragen und Gleichheitsabfragen und ist daher eine beliebte Wahl zur Optimierung der Datenbankleistung.

Wie funktioniert es?

Der B-Baum-Index organisiert Daten in einer hierarchischen Struktur, wobei jeder Knoten eine feste Anzahl von Schlüsseln und Zeigern auf Kindknoten enthält.
B-Bäume bleiben balanciert, indem sie sicherstellen, dass alle Blattknoten auf derselben Ebene liegen, was Suchoperationen optimiert.
Bei der Suche nach einem bestimmten Schlüssel durchläuft der B-Baum-Algorithmus den Baum vom Wurzelknoten bis zu den Blattknoten und verwendet dabei die binäre Suche, um den gewünschten Schlüssel effizient zu finden.

Indexsuche umfasst das Durchlaufen des Baums bis zu den Blattknoten, das Folgen der Blattknoten-Kette zur Suche nach passenden Datensätzen sowie das Abrufen der tatsächlichen Daten von der Festplatte.

In der Abbildung ist die Suche nach dem Schlüssel 302 dargestellt:

1. Eine Suchbaumstruktur ist eine Baumart, bei der jeder Knoten zwei Zeiger besitzt: Der linke Zeiger verweist auf Kindknoten mit kleineren Werten als der Elternknoten, der rechte Zeiger auf Kindknoten mit größeren Werten als der Elternknoten;

2. In einem B-Baum kann der Wurzelknoten mehrere Indexwerte enthalten. Enthält die Wurzel beispielsweise drei verschiedene Werte, besitzt sie drei Zeiger, die jeweils auf den Wertebereich zwischen diesen Schlüsseln zeigen;

3. Um nach einem Schlüssel wie 302 zu suchen, beginnt die Suche am Wurzelknoten und folgt den entsprechenden Zeigern bis zu den Blattknoten. Die Suche ist nach dem Durchlaufen von drei Baumblöcken abgeschlossen, wie im Diagramm rot hervorgehoben;

4. Um nach einem Wertebereich ab 302 zu suchen, können die horizontalen Zeiger zwischen den Blattknoten verwendet werden. Beispielsweise erfolgt das Abrufen der Werte von 302 bis 502 durch sequentielles Folgen der Blattknoten.

Hinweis

Der für die Suche in einem B-Baum-Index verwendete Schlüssel stammt aus den Werten der indizierten Spalte(n) der Datenbanktabelle. Wenn der Index beispielsweise auf einer Spalte wie "client_id" liegt, ist der Suchschlüssel der tatsächliche "client_id"-Wert. Jeder eindeutige numerische Wert in der indizierten Spalte dient als Schlüssel im B-Baum-Index und erleichtert das Auffinden und Abrufen der entsprechenden Zeilen in der Datenbanktabelle.

Vor- und Nachteile

Im Gegensatz zur Standarddatenstruktur des binären Suchbaums können B-Baum-Knoten mehr als 2 Kinder aufnehmen. Die standardmäßige maximale Anzahl an Kindern pro Knoten ist typischerweise auf 16 gesetzt.

Indeximplementierung

Um einen B-Baum-Index auf einer Spalte in PostgreSQL zu erstellen, kann folgender SQL-Befehl verwendet werden:

CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);

Da der B-Baum-Index ein Standardindex in SQL ist, kann auch folgende Anweisung zur Erstellung verwendet werden:

CREATE INDEX index_name ON table_name(column_name1, column_name2,..);

Hinweis

In SQL wird beim Erstellen einer Tabelle mit einer Primary Key Constraint in den meisten Datenbankmanagementsystemen automatisch ein Index auf die in der Primary Key Constraint angegebenen Spalte(n) erstellt. Dieser Index unterstützt die Durchsetzung der Eindeutigkeitsbedingung des Primärschlüssels und verbessert zudem die Performance von Abfragen, die auf der Suche oder dem Join anhand der Primärschlüsselspalte(n) basieren.