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.

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. Die B-Baum-Indizierung eignet sich besonders für Bereichsabfragen und Gleichheitssuchen und ist daher eine beliebte Wahl zur Optimierung der Datenbankleistung.

Wie funktioniert das?

Der B-Baum-Index organisiert Daten in hierarchischer 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 nutzt 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 zum Auffinden passender Datensätze und 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 der Wurzelknoten beispielsweise drei verschiedene Werte, besitzt er 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 abgeschlossen, nachdem drei Baumblöcke durchlaufen wurden, 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, indem die Blattknoten nacheinander durchlaufen werden.

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 von Kindern pro Knoten ist typischerweise auf 16 festgelegt.

Index-Implementierung

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 der Standardindex in SQL ist, kann auch die folgende Anweisung verwendet werden, um ihn zu erstellen:

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