Static Search Trees: 40x Faster Than Binary Search

Binary search on sorted arrays is a classic, but it's far from optimal on modern hardware. A new post from Curious Coding walks through building a static search tree (S+ tree) that achieves up to 40x higher throughput than the standard binary search. The work builds on the S-tree concept from Algorithmica and pushes it to the limit with aggressive micro-optimizations.

Problem and baseline

The input is a sorted list of 32-bit unsigned integers. The goal is to answer many independent queries, returning the smallest element greater than or equal to the query. The metric is throughput — queries per second — and the baseline is Rust's standard library binary search.

Key optimizations

The post systematically improves the S+ tree through several layers:

• Eytzinger layout: Reorders the binary search tree in memory so that nodes accessed in successive steps are close together, improving cache behavior. Prefetching can then hide memory latency.
• Batching: Instead of processing one query at a time, the implementation processes many queries in parallel, amortizing overhead and enabling better SIMD utilization.
• SIMD vectorization: Uses AVX2 instructions to compare multiple keys at once, reducing the number of branches and memory accesses per query.
• Node size tuning: Experiments with node sizes (B=15, B=16, etc.) to align with cache lines and SIMD register widths.
• Prefetching strategies: Prefetches cache lines several steps ahead, hiding DRAM latency.
• Pointer arithmetic: Eliminates unnecessary indirection by using byte-based pointers and up-front splatting of query values.

Results

The final implementation achieves roughly 40x higher throughput than standard binary search on random data. The author also explores prefix partitioning for non-uniform query distributions and multi-threaded scaling.

Why this matters

This isn't just a toy benchmark. The motivation comes from bioinformatics — specifically suffix array searching for DNA indexing. A human genome has 3 billion base pairs, and searching it efficiently is critical. The techniques here directly apply to any high-throughput search on static sorted data, from database indexes to genome analysis pipelines.

The post is refreshingly concrete: every optimization is backed by assembly analysis and benchmark numbers. It's a masterclass in how to think about memory hierarchies, SIMD, and branch prediction.