Statische Suchbäume: 40x schneller als binäre Suche
Static search trees: 40x faster than binary search (2024)
Dieser Artikel zeigt, wie man statische Suchbäume (S+ Bäume) für die Hochdurchsatzsuche in sortierten Daten implementiert und bis an ihre Grenzen optimiert. Ausgehend von der Einführung auf Algorithmica werden Techniken wie Batching, Prefetching, SIMD und optimierte Speicherlayouts kombiniert, um eine 40-fache Beschleunigung gegenüber der binären Suche zu erreichen. Der Autor analysiert Assembly-Code und nutzt Hugepages, um die Leistung auf moderner Hardware maximal auszureizen. Der vollständige Quellcode ist auf GitHub verfügbar.
Durch Batching und gezielte Optimierungen erreichen wir eine 40-fache Beschleunigung gegenüber der binären Suche – ein Ergebnis, das die Grenzen des Machbaren aufzeigt.