/ Datenstrukturen

B-Baum max. Schlüssel

Maximale Schlüsselanzahl in einem B-Baum der Ordnung m und Tiefe h: MaxKeys = m^(h+1) − 1. Grundlage für Indexdimensionierung in Datenbanken.

01 · Eingabe

B-Baum max. Schlüssel berechnen

Maximale Schlüsselanzahl in einem B-Baum der Ordnung m und Tiefe h: MaxKeys = m^(h+1) − 1. Grundlage für Indexdimensionierung in Datenbanken.

Lösen für

MaxKeys = m^(h + 1) − 1

m Ordnung

h Tiefe

Worum geht es?

Ein B-Baum der Ordnung m kann pro Knoten bis zu m Kinder und m − 1 Schlüssel halten. Bei Tiefe h ergibt sich daraus eine maximale Schlüsselzahl von MaxKeys = m^(h+1) − 1 — die direkte Verallgemeinerung der Binärbaum-Formel.

B-Bäume sind die Standard-Datenstruktur für Datenbankindizes (B+Tree in MySQL, PostgreSQL, SQLite) und Dateisysteme (NTFS, ext4, Btrfs, ZFS). Da die Ordnung typischerweise an die Block-/Seitengröße des Speichers angepasst wird (4 KiB → m ≈ 200), bleiben die Bäume extrem flach: 4–5 Ebenen genügen für Milliarden Einträge.

Die Formel

Formel Max. Schlüssel

MaxKeys = m^(h + 1) − 1

Umstellung:
    h = log_m(MaxKeys + 1) − 1

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
m	Ordnung	—	Maximale Kinder pro Knoten (m ≥ 2).
h	Tiefe	—	Tiefe des Baums (Wurzel = 0).
MaxKeys	Max. Schlüssel	—	Maximale Schlüsselanzahl im Baum.

Minimal-Beispiel

B-Baum der Ordnung 5 bei Tiefe 2:

Rechnung m=5, h=2

MaxKeys = 5^3 − 1
        = 125 − 1
        = 124

Praxis-Beispiele

Beispiel 1 — Postgres-Index

PostgreSQL nutzt 8 KiB-Seiten und passt typisch ≈ 200 Schlüssel pro Knoten. Wie viele Schlüssel fasst ein B-Tree der Tiefe 3?

Rechnung Postgres h=3

MaxKeys = 200^4 − 1
        = 1,6 · 10⁹
        ≈ 1,6 Mrd. Einträge

Mit nur 4 Ebenen erreicht der Index also Milliarden-Datensätze — daher die typischen 3–4 I/O-Operationen pro Suche.

Beispiel 2 — Benötigte Tiefe

Wie tief muss ein B-Tree der Ordnung 100 sein, um 1 Mio. Schlüssel zu fassen?

Rechnung m=100, n=10⁶

h = log₁₀₀(10⁶ + 1) − 1
  ≈ 3 − 1
  = 2

Zwei Ebenen (Wurzel + Blätter, plus eine Zwischenebene = h = 2) genügen.

Beispiel 3 — Vergleich Binärbaum vs. B-Baum

Ein Index über 10⁹ Schlüssel:

Rechnung Tiefen-Vergleich

Binärbaum (m=2):    h ≈ 29
B-Baum (m=200):     h ≈ 3
⇒ I/O-Faktor:       ~10× weniger Plattenzugriffe