Statische Suchbäume: 40-mal schneller als die binäre Suche
2025-01-01
Dieser Blogbeitrag beschreibt die Implementierung und Optimierung eines statischen Suchbaums (S+-Baum) für das Hochdurchsatz-Suchen in sortierten Daten, wodurch eine 40-fache Beschleunigung gegenüber der binären Suche erreicht wird. Ausgehend vom Code von Algorithmica optimiert der Autor den Suchalgorithmus sorgfältig mithilfe von Vektorisierung, SIMD-Instruktionen und Batchverarbeitung. Tiefgehende Analysen des Assemblercodes zeigen Möglichkeiten für weitere Leistungsverbesserungen auf. Verschiedene Baumlayouts und Speicherstrategien werden untersucht, was letztendlich zu einer hocheffizienten Lösung führt, die die Abfragezeit von 1150 ns auf 24 ns bei einem Datensatz von 1 GB reduziert.