Static search trees: when a good structure puts binary search at 40× in the shade

An article from 2024, which topped Hacker News today, shows how a better-designed memory layout makes a static structure 40× faster than a binary search. The real lesson isn't the number—it's the reasoning.

Concrete Case: You need to search for a key in a sorted array of 100 million entries. Your first reflex, learned in school, is binary search - log₂(n) ≈ 27 comparisons. Theoretically optimal.

Except that… in 2026, on a modern CPU, binary search is catastrophic. Why? Because each comparison reads a slot whose address depends on the previous result. The processor can neither predict, nor preload, nor pipeline. At each step, it waits for the cache miss (about 100 CPU cycles, or ~30 ns on recent DDR5).

What the Article Does

The article « Static search trees: 40x faster than binary search » (2024, republished at the top of HN today) digs exactly into this problem. The proposed solution is a static B-tree - not a dynamic B-tree from a database manual, but a version optimized for the CPU:

• Eytzinger Layout (named after an Austrian genealogist from the 16th century who invented a tree numbering system) or branchless B-tree: the children of a node are contiguous in memory.
• Nodes calibrated on a cache line (typically 64 bytes, or 16 keys of 4 bytes).
• SIMD comparisons (Single Instruction Multiple Data - an instruction that processes multiple data at once): in a node, compare the 16 keys in a single AVX2/AVX-512 instruction.
• Software prefetch: as soon as you enter a node, you launch the preloading (__builtin_prefetch) of the probable child node.

Result measured in the article: on 100 million entries, the search goes from about 150 ns to 4 ns. That's 40× faster.

What to Remember

The lesson is not « binary search is dead ». It's that classical algorithmic complexity (O log n) ignores the memory cache. On a modern CPU, the structure that minimizes cache misses almost always beats the one that minimizes comparisons.

Other examples we encounter in our projects:

• Robin Hood hash maps (Emmanuel Goossaert, Google Abseil flat_hash_map) vs. classic std::HashMap.
• PDQ sort (Pattern-Defeating Quicksort, Orson Peters - used by Rust slice::sort_unstable) vs. school quicksort.
• Bloom filters before exact lookups to quickly eliminate negatives.
• Column-oriented storage (Parquet, ClickHouse) that exploits cache lines for analytics.

To Read Next

• The paper by Paul-Virak Khuong and Pat Morin (2015): Array Layouts for Comparison-Based Searching - the academic foundation of this entire field.
• « What Every Programmer Should Know About Memory » by Ulrich Drepper (2007) - dated on some details, but the mental foundation remains sound.
• The Rust crate static-search-tree or equivalent for a productive example.

To Remember

When you optimize a hot loop, your first profiler to pull out is not cachegrind - it's perf stat -e cache-misses,cache-references under Linux (or Instruments on macOS). That's where the real performance is at in 2026. Complexity theory tells you what's possible; the memory cache tells you what's achievable.