Árboles de búsqueda estáticos: 40 veces más rápidos que la búsqueda binaria

Static search trees: 40x faster than binary search (2024)

Este artículo detalla la implementación y optimización de árboles de búsqueda estáticos (S+ trees) para lograr un rendimiento 40 veces superior al de la búsqueda binaria tradicional. Se exploran técnicas como el layout Eytzinger, el uso de prefetching, SIMD, y el procesamiento por lotes, todo ello respaldado por benchmarks y análisis de ensamblador. El autor comparte el código fuente completo y discute aplicaciones en bioinformática, como la búsqueda en arrays de sufijos.