Rebuilding search: an S+ tree that beats binary search by 40x

Ragnar Groot Koerkamp takes the static B-tree (S+ tree) design from Algorithmica and pushes it to the limit for one narrow but common problem: given a sorted array of 32-bit integers, find the smallest value at least as large as a query. The target metric is throughput — queries answered per second — rather than the latency of any single lookup. Starting from a standard-library binary search and the cache-friendly Eytzinger layout (already about 4x faster once you prefetch several cache lines ahead), he layers on manual AVX2 SIMD, batching independent queries, software prefetching, hand-tuned pointer arithmetic, and carefully chosen tree node sizes and memory layouts. Reading and trimming the generated assembly instruction by instruction is a recurring part of the work.

The headline gain comes from treating the search as a high-throughput pipeline instead of a sequence of dependent steps. Batching many independent queries lets the CPU’s out-of-order engine hide memory latency, while prefetching and a compact prefix-partitioned tree layout keep the hot data in cache and reduce TLB pressure — helped by allocating the structure on 2MB hugepages. The cumulative effect is roughly a 40x speedup over binary search on large, out-of-cache datasets.

The motivation is bioinformatics: indexing DNA with suffix arrays, where a human genome runs to billions of characters and lookups are classically done by binary search over sorted suffixes. Faster sorted-array search is a first step toward faster suffix-array queries. All benchmarks, plotting code, and the implementation are published on GitHub, and the author sketches future directions including interpolation search, range queries, and tighter data packing.