静态搜索树：比二分查找快40倍

Static search trees: 40x faster than binary search (2024)

本文深入探讨了如何通过优化静态搜索树（S+ tree）来实现超高吞吐量的数据检索。作者从经典的二分查找和Eytzinger布局出发，逐步引入Auto-vectorization、Manual SIMD、Batching以及Prefetching等高级优化技巧。通过精细调整内存布局、利用Hugepages减少TLB压力，并针对CPU指令集进行汇编级优化，最终实现了比传统二分查找快40倍的查询性能。这一成果不仅展示了底层系统编程的魅力，也为Bioinformatics领域的后缀数组搜索等应用提供了重要的加速方案。

"我们将从Algorithmica上介绍的静态搜索树（S+ tree）实现入手，将其优化至极限，并通过批量处理（batching）这一重大改进来最大化吞吐量。"