Statische Suchbäume: Wenn eine gute Struktur die binäre Suche um das 40-fache in den Schatten stellt

Ein Artikel aus dem Jahr 2024, der heute wieder an die Spitze von Hacker News gekommen ist, zeigt, wie ein besser durchdachtes Speicherlayout eine statische Struktur 40-mal schneller macht als eine binäre Suche. Die eigentliche Lehre ist nicht die Zahl - es ist das Denken dahinter.

Konkreter Fall: Sie müssen einen Schlüssel in einem sortierten Array mit 100 Millionen Einträgen suchen. Ihr erster Reflex, den Sie in der Schule gelernt haben, ist die Binärsuche - log₂(n) ≈ 27 Vergleiche. Theoretisch optimal.

Aber... im Jahr 2026, auf einem modernen CPU, ist die Binärsuche katastrophal. Warum? Weil jeder Vergleich ein Feld liest, dessen Adresse vom vorherigen Ergebnis abhängt. Der Prozessor kann weder vorhersagen, noch vorladen, noch pipelinen. Bei jedem Schritt wartet er auf den Cache-Miss (etwa 100 CPU-Zyklen, also ~30 ns bei neuem DDR5).

Was der Artikel macht

Der Artikel « Static search trees: 40x faster than binary search » (2024, heute auf HN neu veröffentlicht) geht genau auf dieses Problem ein. Die vorgeschlagene Lösung ist ein statischer B-Baum - kein dynamischer B-Baum aus dem Datenbankhandbuch, sondern eine für die CPU optimierte Version:

• Layout Eytzinger (benannt nach einem österreichischen Genealogen des 16. Jahrhunderts, der ein Baumnummerierungssystem erfand) oder branchless B-Baum: Die Kinder eines Knotens sind in Speicher zusammenhängend.
• Knoten kalibriert auf eine Cache-Zeile (typischerweise 64 Bytes, also 16 Schlüssel von 4 Bytes).
• SIMD-Vergleiche (Single Instruction Multiple Data - eine Anweisung, die mehrere Daten gleichzeitig verarbeitet): In einem Knoten werden die 16 Schlüssel mit einer einzigen AVX2/AVX-512-Anweisung verglichen.
• Software-Prefetch: Sobald man in einen Knoten eintritt, startet man das Vorladen (__builtin_prefetch) des wahrscheinlichsten Kindknotens.

Gemessenes Ergebnis im Artikel: Bei 100 Millionen Einträgen sinkt die Suche von etwa 150 ns auf 4 ns. Das ist 40-mal schneller.

Was man sich merken sollte

Die Lehre ist nicht « die Binärsuche ist tot ». Es ist, dass die klassische algorithmische Komplexität (O log n) den Cache-Speicher ignoriert. Auf einem modernen CPU gewinnt die Struktur, die die Cache-Misses minimiert, fast immer gegen diejenige, die die Vergleiche minimiert.

Weitere Beispiele, die wir in unseren Projekten sehen:

• Hash-Maps « robin hood » (Emmanuel Goossaert, Google Abseil flat_hash_map) vs. klassische std::HashMap.
• PDQ-Sort (Pattern-Defeating Quicksort, Orson Peters - verwendet von Rust slice::sort_unstable) vs. Quicksort aus der Schule.
• Bloom-Filter vor genauen Lookups, um Negative schnell zu eliminieren.
• Spaltenorientierte Speicherung (Parquet, ClickHouse), die Cache-Lines für die Analytik nutzt.

Als nächstes lesen

• Das Papier von Paul-Virak Khuong und Pat Morin (2015): Array Layouts for Comparison-Based Searching - die akademische Grundlage für dieses gesamte Feld.
• « What Every Programmer Should Know About Memory » von Ulrich Drepper (2007) - auf einigen Details veraltet, aber die geistige Grundlage bleibt gesund.
• Das Rust-Crate static-search-tree oder ein Äquivalent für ein produktives Beispiel.

Zu beachten

Wenn Sie eine Hot-Loop optimieren, ist Ihr erster Profiler nicht cachegrind - es ist perf stat -e cache-misses,cache-references unter Linux (oder Instruments auf macOS). Dort wird die echte Leistung in 2026 gemacht. Die Komplexitätstheorie sagt Ihnen, was möglich ist; der Cache-Speicher sagt Ihnen, was erreichbar ist.