Este artículo técnico presenta la implementación y optimización de un árbol de búsqueda estático (S+ tree) para localizar datos ordenados con un rendimiento muy superior al de la búsqueda binaria clásica. Partiendo de la idea introducida en Algorithmica, el autor parte de un código base y lo somete a un proceso iterativo de optimización: técnicas SIMD manuales con instrucciones AVX2, vectorización automática, uso de popcount y trailing zeros, layouts de memoria tipo Eytzinger, prefetching y aritmética de punteros para minimizar instrucciones. También rediseña el layout del árbol con particionado por prefijos, subárboles compactos y mapas de prefijos.
La principal novedad es la introducción de batching (procesamiento por lotes), que eleva el rendimiento hasta hacerlo entre 30 y 40 veces más rápido que la búsqueda binaria estándar y unas 4 veces más rápido que el layout Eytzinger. El trabajo se evalúa con enteros aleatorios uniformes de 31 bits y se apoya en hugepages de 2 MB para reducir la presión sobre la TLB.
La motivación del proyecto es acelerar la búsqueda en suffix arrays, una estructura clave en bioinformática para indexar genomas humanos y otras secuencias de ADN. Todo el código fuente, los benchmarks y el código de generación de gráficas están disponibles en el repositorio GitHub 'RagnarGrootKoerkamp/static-search-tree'.