静态搜索树：当优秀的数据结构让二分搜索相形见绌40倍

2024年的一篇文章在今天登上了Hacker News头条，展示了如何通过更好的内存布局设计使静态结构比二分搜索快40倍。真正的教训不是数字本身，而是背后的思考逻辑。

Cas concret : 你需要在一个包含1亿条目且已排序的数组中搜索一个键。你的第一反应（在学校学到的）是二分搜索（binary search）——log₂(n) ≈ 27次比较。理论上最优。

但……在2026年，在现代CPU上，二分搜索简直是灾难。为什么？因为每次比较都会读取一个地址依赖于上一次结果的内存单元。处理器无法预测、预加载或流水线化。每一步都要等待缓存未命中（约100个CPU周期，即DDR5上约30纳秒）。

文章内容

文章《Static search trees: 40x faster than binary search》（2024年，今日在HN头条重新发布）深入探讨了这一问题。提出的解决方案是一个静态B树——不是数据库手册中的动态B树，而是为CPU优化的版本：

• Eytzinger布局（一位16世纪奥地利系谱学家的名字，他发明了一种树编号系统）或无分支B树：一个节点的子节点在内存中是连续的。
• 节点校准到缓存行大小（通常64字节，即16个4字节键）。
• SIMD比较（单指令多数据———次指令处理多个数据）：在一个节点中，用一次AVX2/AVX-512指令比较16个键。
• 软件预取：一旦进入一个节点，就启动对可能子节点的预加载（__builtin_prefetch）。

文章中测得的结果：在1亿条目中，搜索时间从约150纳秒降至4纳秒。即快40倍。

关键要点

教训不是“二分搜索已死”。而是经典算法复杂度（O log n）忽略了缓存。在现代CPU上，最小化缓存未命中的结构几乎总能击败最小化比较次数的结构。

我们在项目中遇到的其他例子：

• “罗宾汉”哈希表（Emmanuel Goossaert，Google Abseil flat_hash_map）vs. 经典std::HashMap。
• PDQ排序（Pattern-Defeating Quicksort，Orson Peters——Rust slice::sort_unstable使用）vs. 教科书快排。
• 在精确查找前使用布隆过滤器快速排除负例。
• 面向列的存储（Parquet、ClickHouse）利用缓存行进行分析。

进一步阅读

• Paul-Virak Khuong与Pat Morin（2015）的论文：《Array Layouts for Comparison-Based Searching》——该领域的学术基础。
• Ulrich Drepper（2007）的《What Every Programmer Should Know About Memory》——某些细节已过时，但核心思维仍然健全。
• Rust crate static-search-tree或同类产品，用于生产实践示例。

记住

当你优化热点循环时，你要调用的第一个分析器不是cachegrind——而是Linux下的perf stat -e cache-misses,cache-references（或macOS下的Instruments）。这才是2026年真正的性能关键。复杂度理论告诉你什么是可能的；缓存则告诉你什么是可达的。