比二分查找快 40 倍，靠的不是新复杂度：CPU 其实一直在等内存
林岚｜OC 开发者生态编辑
林岚｜OC 开发者生态编辑
开发者 Peter de Haan 在文章 Static search trees: 40x faster than binary search 中展示了一套针对静态有序整数集合的搜索实现：在其 4GB 数据和批量查询测试中，普通二分查找约需 1150 纳秒一次，优化后的 S-tree 降至约 27 纳秒，超过 40 倍；六线程下可进一步接近 7 纳秒一次。
一句话结论： 这不是有人把 O(log n) 变成了 O(1)，而是把同样数量级的比较重新排布，让缓存行、SIMD、预取和多个并行查询都能工作；它对数据库、索引和系统开发很有启发，但不适合直接替换所有二分查找。
二分查找在教科书里几乎完美：每比较一次就砍掉一半范围，查找次数是对数级。问题是现代 CPU 的一次比较很便宜，从内存取下一块数据却可能慢上几个数量级。
传统二分查找每一步都依赖上一步结果。CPU 不知道下一次会跳到数组左半还是右半，难以提前取数；目标数组大到放不进缓存后，处理器大量时间都在等待 DRAM。算法只做了几十次比较，墙上时间却被几十次随机内存访问支配。
第一层优化是改变数据摆放方式
Eytzinger 布局把二叉搜索树按层存进连续数组。根节点放在前面，子节点的位置可以直接计算。这样常用的上层节点更容易留在缓存里，CPU 也可以根据当前位置预取可能访问的后续节点。
S-tree 再向前一步：每个节点不只放一个比较值，而是把一组键塞进一条缓存线，通过 SIMD 一次与多个值比较。树的分支因子提高，高度随之降低，同一次缓存访问完成更多工作。
大 O 复杂度并没有发生神奇变化，搜索依旧随着数据规模增长。变化的是每一层需要多少次昂贵内存访问，以及取来一整条缓存线后有多少字节真正参与计算。
真正拉开差距的是批量查询
单个查询仍有依赖链：还没比较当前节点，就不知道下一层去哪里。作者于是一次处理一批查询。某个查询在等待内存时，CPU 可以计算另一个查询；程序还能提前预取下一层节点，把内存等待藏在其他工作后面。
后续的层级交错更加激进。S-tree 的上层偏计算密集，下层偏内存等待，程序让处于不同树层的查询同时前进，用一批查询的计算填补另一批查询的等待。作者称，这项 interleaving 是提升吞吐量的关键之一。
最终的 40 倍来自一串叠加改动，而不是一行神秘代码：缓存线大小的节点、SIMD 比较、指针和偏移计算简化、软件预取、批处理，以及不同层级查询交错。部分分区和前缀映射实验反而没有继续提升结果，这也让文章比只展示成功数字的性能宣传更可信。
40 倍数字有哪些前提
第一，数据基本静态。为 S-tree 重排数组需要预处理；如果每次插入、删除都要重建布局，收益很快被更新成本吃掉。
第二，查询可以批量提交。在线服务里一次只查一个键、并且必须立刻返回时，很难获得相同的交错和预取优势。文章也承认，最复杂的 interleaving 依赖看到完整查询输入，代码比普通批处理长得多。
第三，测试对象是紧凑整数键。真实数据库还要处理变长字符串、记录指针、并发更新、NUMA、磁盘和持久化。一次整数下界查询的 27 纳秒不能直接换算成数据库请求快 40 倍。
第四，比较基线是对大数组做普通二分查找。成熟标准库、数据库 B-tree 和专门索引本来就会利用缓存布局，因此实际替换收益取决于原系统有多朴素。
对普通开发者有什么用
这篇文章最重要的不是让大家复制一个 S-tree，而是提醒我们：性能问题经常不在“执行了多少条指令”，而在数据以什么顺序到达 CPU。
当 profiler 显示缓存未命中和内存停顿占据主要时间时，微调分支或减少一次加法可能没有意义。重新组织数据结构、把请求凑成批次、让访问模式可预测，往往比换一条更聪明的比较语句有效。
OC 判断
“比二分查找快 40 倍”在作者给定的吞吐场景中有完整实验支撑，但它不是通用 API 性能承诺。标题里的数字成立，使用范围必须与数字一起交代。
这项工作真正穿透教科书的地方是：算法复杂度只描述随规模增长的趋势，不描述现代硬件上一条依赖链要等多久。系统性能是算法、数据布局、编译器和微架构共同产生的结果。
关键事实
- 作者测试中，4GB 输入上的普通二分查找约为 1150ns/query，优化 S-tree 约为 27ns/query。
- 六线程结果约为 7ns/query，此时进一步受总内存带宽限制。
- 加速主要来自缓存友好布局、SIMD、批处理、预取与层级交错。
- 算法复杂度并未变成常数时间，测试衡量的是特定硬件上的吞吐量。
- 数据频繁更新、单次低延迟查询或复杂键类型未必适合该方法。
为什么重要
- 对开发者： 优化前应先看缓存未命中和内存停顿，别只数比较次数。
- 对企业： 批处理可以大幅提高吞吐量，但也可能增加单请求等待时间，需要在吞吐与延迟间取舍。
- 对普通用户： “快 40 倍”不是所有软件都会自动变快，而是特定数据结构在特定负载下的工程结果。
评论
围绕这篇文章补充信息、提出问题或分享观察。