B-Tree

CREATE INDEX ON users(email). Die Datenbank baut im Hintergrund einen B-Tree für die Spalte email. Wenn du SELECT * FROM users WHERE email='...' machst: Die DB springt durch den B+Tree in 3 Schritten zum Ziel. Ohne Index müsste sie die ganze Tabelle scannen ($O(N)$).

1. B vs B+

• B-Tree: Daten stehen auch in den inneren Knoten.
• B+Tree: Daten stehen nur in den Blättern (ganz unten). Innere Knoten sind nur Wegweiser. Vorteil B+: Man kann die Blätter als verkettete Liste verbinden ("Full Table Scan" ist super schnell). Datenbanken nutzen fast immer B+.

2. Fragmentation

Wenn man viel löscht und einfügt, werden B-Tree Pages halbleer. Die DB muss "Page Splits" und "Merges" machen, um den Baum balanciert zu halten. Das verlangsamt Schreiben (Random Writes). Das ist der Grund, warum für Write-Heavy Workloads LSM-Trees (wie RocksDB) besser sind.

1. B-Tree Page Layout & Cache-Lines

Innerhalb eines 8KB-Knotens (der Node des Baums) liegen in PostgreSQL hunderte Pointer und Keys verschachtelt. Um diesen 8KB Block selbst noch zu durchsuchen (z.B. binäre Suche im Block), muss die CPU springen. Die Datenbank-Entwicklung dreht sich heute extrem um Cache Data Locality. Man trennt oft Index-Keys und Pointer in separate Arrays (AOS vs SOA), damit der Prozessor-Prefetcher eine 64-Byte lange CPU Cache-Line auf einmal reinladen und vectorisiert (SIMD Instruktionen) komplett abarbeiten kann, ohne zu stocken.

2. Lock-free Concurrency: Latch Crabbing

Was passiert, wenn 10.000 SQL-Connections gleichzeitig Nodes im B-Tree splitten oder traversieren? Man braucht Latches (kurzlebige Mutexes für Memory Pages). Klassischer Ansatz ist das Latch Crabbing (oder Coupling): Beim Absteigen in den Baum blockiert (Read-Latch) der Thread den Parent. Er blockiert dann das Kind, lässt dann erst den Parent wieder los. Er "krabbelt" den Baum hinab wie eine Krabbe. Für Insert-Splits nutzt man kompliziertere Write-Latches. Engpässe entstehen sofort an der Tree-Root, wenn alle Theads gleichzeitig versuchen, die oberste Ebene zu latchen. Moderne Ansätze (Bw-Trees) lassen Latches ganz weg und nutzen lock-free Delta-Updates mit Compare-and-Swap (CAS).

3. Log-Structured Merge Trees (LSM) als Antagonisten

Die Schwäche des B-Tree ist das Write Amplification am Laufwerk. Eine Random-Write Operation (UPDATE) führt dazu, dass eine komplette 8KB Page auf Disk überschrieben wird, nur weil 4 Bytes verändert wurden. Und wenn der Tree splittet, erzeugt das wildes I/O-Rauschen. Deshalb haben Write-Intensive Stores (Cassandra, RocksDB, InfluxDB) den B-Tree komplett verdrängt und durch den LSM-Tree ersetzt. Dieser hängt alle Writes linear ("append-only") in RAM-Buffer an und spült sie geordnet auf Disk (SSTables), was SSDs extrem schont. Der B-Tree gewinnt hingegen das Read-Duell haushoch.