$B^+$-Baum & Indexing Playground

Erleben Sie interaktiv, wie relationale Datenbanksysteme (PostgreSQL, MySQL InnoDB, Oracle) Daten in balancierten $B^+$-Bäumen organisieren. Fügen Sie Schlüssel ein, beobachten Sie Knoten-Splits und vergleichen Sie Index Seek ($O(\log N)$), Index Range Scan und Full Table Scan ($O(N)$).

[+] Schlüssel einfügen:

[?] Index Suche (Point / Range):

bis

Ordnung ($m$):

Presets:

Baumhöhe ($h$)

Höhe 2

Gesamtanzahl Schlüssel

0 Schlüssel

Seiten-I/Os (Point Seek)

2 Page Reads

Full Table Scan Kosten

N Page Reads

Visuelle $B^+$-Baum Struktur

Innere Knoten Blatt-Knoten (Kette →)

$ Aktivitäts-Protokoll:

Bereit für Eingaben. Fügen Sie Schlüssel hinzu oder wählen Sie ein Preset.

Index Seek vs. Full Table Scan

Ein Index Seek navigiert von der Wurzel über genau $h = \lceil \log_m N \rceil$ Seiten zur passenden Blattseite. Bei 1 Million Einträgen und Seitenordnung $m=100$ sind das nur 3 Disketten-/SSD-Zugriffe, während ein Full Table Scan alle $10.000$ Seiten sequentiell durchlesen müsste.

Punkt-Abfrage (`WHERE ID = 42`): $O(\log N)$ I/O

Bereichsabfrage (`WHERE ID BETWEEN 10 AND 50`): $O(\log N + k)$ I/O

Ohne Index (`WHERE Name = 'Sokrates'`): $O(N)$ I/O Full Scan

Clustered vs. Non-Clustered Index

Im Clustered Index (Primärschlüssel-Index) enthalten die Blattseiten direkt die gesamten Tabellenzeilen in physisch sortierter Reihenfolge. Ein Secondary Index speichert in den Blättern lediglich den Schlüsselwert zusammen mit dem Zeiger (RowID / Primärschlüssel) auf den Hauptdatensatz.

• $B^+$-Bäume verketten alle Blätter doppelt: Schnelle sequentielle Range-Scans ohne Rücksprung zur Wurzel!