Index-Größe B-Baum
Tiefe eines B-Baum-Index bei n indexierten Datensätzen und Ordnung m: Tiefe = ⌈log_m(n)⌉. Bestimmt direkt die Anzahl Random-I/Os pro Indexsuche.
Index-Größe B-Baum berechnen
Tiefe eines B-Baum-Index bei n indexierten Datensätzen und Ordnung m: Tiefe = ⌈log_m(n)⌉. Bestimmt direkt die Anzahl Random-I/Os pro Indexsuche.
Worum geht es?
Ein B-Baum-Index organisiert seine Schlüssel in einer flachen, balancierten Baumstruktur. Die Tiefe des Baums hängt von zwei Größen ab: der Anzahl indexierter Datensätze n und der Ordnung m (Fan-out, also Schlüssel pro Knoten).
Die Tiefe wächst nur logarithmisch — das ist genau der Grund, warum sich B-Bäume in Datenbanken durchgesetzt haben. Selbst Milliarden Zeilen liegen bei realistischen Fan-outs (m ≈ 100–500) typischerweise innerhalb von 3–5 Ebenen, was 3–5 Random-I/Os pro Indexsuche bedeutet.
Die Formel
Tiefe = ⌈log_m(n)⌉Die Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| n | Datensätze | — | Anzahl indexierter Datensätze (n ≥ 1). |
| m | Ordnung | — | Fan-out des B-Baums, Schlüssel pro Knoten (m > 1). |
| Tiefe | Indextiefe | — | Tiefe des Baums, ⌈log_m(n)⌉. |
Minimal-Beispiel
1 Million Datensätze, Fan-out 100:
Tiefe = ⌈log₁₀₀(1 000 000)⌉
= ⌈3⌉
= 3Praxis-Beispiele
Beispiel 1 — Tabelle mit 100 Millionen Zeilen
PostgreSQL-Indexseiten (8 KiB) fassen typischerweise rund 400 Schlüssel:
n = 100 000 000, m = 400
Tiefe = ⌈log₄₀₀(10⁸)⌉
= ⌈3,07⌉
= 4Vier Indexseiten pro Punkt-Suche — das obere Niveau ist üblicherweise im Cache.
Beispiel 2 — Schmaler Schlüssel, breiter Knoten
Integer-Index mit Fan-out 500 über 1 Milliarde Zeilen:
Tiefe = ⌈log₅₀₀(10⁹)⌉
= ⌈3,33⌉
= 4Beispiel 3 — Kleiner Fan-out
Lange String-Schlüssel reduzieren Fan-out drastisch (z. B. m = 20) bei 1 Mio Zeilen:
Tiefe = ⌈log₂₀(1 000 000)⌉
= ⌈4,61⌉
= 5Spürbar tiefere Bäume sind oft das Argument für Prefix- oder Hash-basierte Indexvarianten.