B-Baum und B+-Baum

Kurz: B-Bäume sind ausgeglichene Suchbäume mit vielen Schlüsseln pro Knoten. Sie bilden die Grundlage der meisten Datenbankindizes, weil sie mit wenigen Plattenzugriffen auskommen.

Genauer: Jeder Knoten entspricht einer Speicherseite (z. B. 8 KB) und enthält hunderte Schlüssel. Dadurch ist der Baum sehr flach: Mit 3–4 Ebenen findet man ein Element unter Millionen. Beim B+-Baum liegen alle Daten in den Blättern, die untereinander verkettet sind, was Bereichsabfragen beschleunigt.

Im Detail

• Suche: Von der Wurzel abwärts, in jedem Knoten binär suchen. Laufzeit O(log n) mit großer Basis.
• Einfügen: In das Blatt; ist es voll, wird es geteilt (Split) und der mittlere Schlüssel wandert nach oben.
• Löschen: Bei zu wenig Einträgen werden Knoten verschmolzen oder umverteilt.
• B+-Baum: Innere Knoten nur als Wegweiser, Blätter verkettet.
• Auswirkungen: Zufällige Schlüssel (UUIDv4) erzeugen viele Splits, fortlaufende Schlüssel sind günstiger.
• Alternativen: LSM-Trees (schreiboptimiert), Hash-Indizes.

Siehe auch: LSM-Tree und Sorted String Tables, SQL-Index