Introduction

The classic binary search on a sorted array is simple and cache-friendly for small datasets, but as data grows beyond cache size, memory latency dominates. The Eytzinger layout improves this by prefetching multiple levels ahead, achieving up to 6x speedup over binary search on 1GB data. But the S+ tree (static B-tree) goes further—up to 40x faster than binary search in throughput benchmarks.

This post, based on CuriousCoding's article, implements and optimizes an S+ tree for high-throughput searching of static sorted 32-bit integers. The source code is available on GitHub.

Problem and Metric

Input: sorted list of n 32-bit unsigned integers. Output: smallest element ≥ query, or u32::MAX. The metric is throughput: number of independent queries per second. Benchmarks measure reciprocal throughput in ns/query on a fixed 2.6GHz i7-10750H CPU with L1 32KB, L2 256KB, L3 12MB. Hugepages (2MB) are used to reduce TLB misses.

S+ Tree Basics

An S+ tree is a B-tree where each node stores B keys and B+1 children. The keys are stored in a contiguous array in a specific memory layout that maximizes cache line utilization. Instead of binary search's log2 n steps, the S+ tree uses log_{B+1} n steps, each loading a full cache line of B keys. For B=15 (16 keys per cache line), a search on 1GB data takes about 5 steps vs 28 for binary search.

Optimizing the Search

Batching

The biggest throughput gain comes from batching: processing multiple queries simultaneously. The CPU can overlap memory latency for one query with computation for another. The article implements a batched search that processes 4 queries at a time using SIMD (AVX2).

// Simplified batching with SIMD
fn query_batch(&self, queries: &[u32; 4]) -> [u32; 4] {
    let mut idx = [1u32; 4];
    loop {
        // Load keys from current node
        let keys = self.load_node(idx[0]); // assumes all idx same for simplicity
        // Compare all 4 queries with keys using SIMD
        let cmp = simd_compare(queries, keys);
        // Update indices based on comparison
        for i in 0..4 {
            idx[i] = 2 * idx[i] + cmp[i] as usize;
        }
        if idx[0] >= self.len() { break; }
    }
    // ... extract result
}

Prefetching

Prefetching is done by issuing a prefetch instruction for the cache line that will be needed several iterations ahead. The Eytzinger layout prefetches 4 levels ahead; the S+ tree prefetches the next node's cache line.

Pointer Arithmetic

To reduce instruction count, the code uses byte-based pointers instead of index arithmetic. This avoids multiplication by 4 (size of u32) and allows direct memory access.

// Byte pointer version
let base = self.vals.as_ptr() as usize;
let mut ptr = base + 4; // start at root
loop {
    let node = *(ptr as *const [u32; 16]);
    let cmp = (q > node[7]) as usize; // example: binary search within node
    ptr = base + (ptr - base) * 2 + cmp * 64; // next node offset
    // ...
}

Manual SIMD

For the linear search within a node (B=15), the article uses AVX2 to compare all keys in one instruction:

// AVX2 comparison
let keys = _mm256_load_si256(ptr as *const __m256i);
let broadcast = _mm256_set1_epi32(q as i32);
let cmp = _mm256_cmpgt_epi32(broadcast, keys); // q > key?
let mask = _mm256_movemask_epi8(cmp);
let idx = _tzcnt_u32(mask) / 4; // trailing zeros count

Memory Layout

The S+ tree uses a left-tree layout: nodes are stored in breadth-first order, but each node's children are contiguous. This improves spatial locality for sequential traversal.

Prefix Partitioning

For even larger datasets, the article introduces prefix partitioning: split the data into chunks based on the first few bits of the keys, then build separate trees for each chunk. This reduces tree depth and improves cache usage.

Results

On 1GB data, binary search takes ~1150 ns/query. The Eytzinger layout achieves ~200 ns/query (6x faster). The optimized S+ tree with batching and SIMD achieves ~30 ns/query—a 40x improvement over binary search. The gains are most pronounced for datasets larger than L3 cache (12MB).

Conclusion

Static search trees, combined with batching, prefetching, SIMD, and careful memory layout, can dramatically outperform binary search on large static datasets. The techniques are directly applicable to suffix array searching in bioinformatics and any high-throughput lookup system.

Next steps: Implement the S+ tree for your use case. Start with the basic layout, then add batching and SIMD. Profile on your target hardware. The full source code is available on GitHub.