Rust 二分搜索性能优化：无分支与 Eytzinger 缓存布局实战

二分搜索大概是计算机系里最"教学友好"的算法了：逻辑简单，证明容易，复杂度是精确的 O(log n)。可一旦把它放到真实的热路径上，情况就完全不一样。如果你维护过每秒几十万次查询的服务，或者写过存储引擎、时序数据库、游戏物理系统，你会发现那些看起来"已经是标准库实现"的二分搜索，依然可能是性能分析报告上的头号嫌疑对象。

我的判断是：二分搜索的性能天花板根本不在算法层。同样的比较次数，不同的内存访问模式，耗时可以差出一个数量级。Rust 在这件事上特别有优势，因为它允许你用安全、可读、可测试的方式，把算法实现推到 CPU 的机械层面。本文会从标准库的二分搜索讲起，拆解经典实现、无分支实现、Eytzinger 布局这三种方案，最后给出一个可以跑的 Criterion 基准项目。读完你能回答三件事：二分搜索慢在哪、Rust 能优化到什么程度、以及你的项目到底该不该用这些技术。

1. 二分搜索的性能瓶颈不在比较次数

1.1 教科书的复杂度模型漏掉了什么

教科书分析二分搜索时，默认的代价模型是"每次比较消耗固定时间"。在这个模型里，1 亿条数据只需要约 27 次比较，看起来毫无压力。但真实 CPU 不是这样工作的。每次比较之前，你要先取 a[mid]，而 mid 在数组里的位置几乎是一个随机值。数组小的时候，这个随机位置可能已经在 L1 Cache 里；数组超过几 MB 甚至几百 MB 之后，几乎每次比较都要等内存。

这里真正容易踩坑的地方是：复杂度分析里的"常数"不是一个数，而是一个从 1ns 到 100ns 的波动范围。一次 Cache 命中可能只花几个周期，一次内存未命中可能等几十到一百多纳秒。二分搜索的比较次数确实只有 20 次，但如果 20 次里有 10 次是内存未命中，真实耗时可能是"10 次内存等待"而不是"20 次加法比较"。

1.2 现代 CPU 还有第二个隐藏瓶颈：分支预测

二分搜索的循环里有一个 if (a[mid] < key)，这看起来很正常。问题在于查询数据分布如果是随机的，这个分支的走向也接近随机。现代 CPU 靠分支预测器猜测下一步该预取哪条指令，一旦猜错，流水线会被冲刷，浪费十几个到几十个周期。

也就是说，传统二分搜索其实正在同时忍受两种惩罚：随机访存带来的 Cache Miss，和随机分支带来的 Pipeline Flush。优化二分搜索的本质，就是同时解决这两个问题，或者至少先解决那个主导瓶颈。

1.3 什么样的场景才值得折腾

不是所有二分搜索都值得优化。如果你的数组只有几千个元素、查询频率很低，标准库一把梭就够了。但如果有下面任何一个特征，就值得往下看：

• 有序数组超过几 MB，且长期驻留在内存中；
• 查询频率很高，高到这部分函数能进入 perf top；
• 数据相对静态，允许为搜索预先重建内存布局；
• 延迟敏感，比如数据库索引、实时系统、高频交易里的查找逻辑。

2. 从标准库与经典实现开始

2.1 标准库接口比你想象的好用

Rust 标准库给有序数组提供了两个常用接口：binary_search 和 partition_point。前者在找到时返回 Ok(index)，没找到时返回插入点；后者直接返回"第一个满足条件的位置"，非常适合做 lower_bound。

rust复制// Rust 1.52+，partition_point 直接返回 lower_bound 的插入点
fn std_partition_point(sorted: &[u32], target: u32) -> usize {
    sorted.partition_point(|&v| v < target)
}

partition_point 的实现是基于标准库内部的二分逻辑，泛型约束合理，绝大多数时候它都够快。它的问题不在于实现差，而在于它必须基于一个普通有序数组，无法利用你已经知道的数据特征，也无法改变数组的物理布局。

2.2 手写一份经典 lower_bound

为了之后对比，我们先写一份最经典的二分搜索。它和标准库思路一致，但保留了 if 分支，方便我们观察分支预测的影响。

rust复制// 经典二分搜索：寻找第一个 >= target 的下标
fn classic_lower_bound(sorted: &[u32], target: u32) -> usize {
    let mut lo = 0usize;
    let mut hi = sorted.len();

    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if sorted[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    lo
}

这段代码逻辑上没有任何问题，它的依赖项也很少：只有内存、加法、比较和跳转。但注意第 6 行，这是一个真正的分支。目标值随机时，左右两条路径大约各 50% 概率，分支预测器基本是瞎猜。

2.3 经典实现的隐藏成本

假设你的有序数组是 1000 万个 u32，大约 40MB。第一次比较访问数组正中间，Cache Miss，等内存；第二次访问 1/4 或 3/4 位置，大概率还是 Miss。整个二分搜索路径上的访问地址几乎不连续，Cache 对你没有任何帮助。

于是你看到了一个反直觉的现象：O(log n) 的算法，在数据规模足够大时，主要时间不是花在"比较"上，而是花在"等待数据从内存到达 CPU"上。这为接下来的两个优化方案提供了明确的靶子。

3. Cache Miss 与分支预测：两个真实瓶颈

3.1 不同层级存储的代价

现代 CPU 的存储层级大致是寄存器、L1 Cache、L2 Cache、L3 Cache、内存。从 L1 到内存，延迟跨度非常夸张。为了有一个直观感觉，可以把不同层级的访问代价当成"周期数"来看待，虽然不同 CPU 差异很大，但相对关系基本一致。

把这张表放到二分搜索里，结论很清楚：如果你的有序数组超过 L3 Cache，经典二分搜索的 20 多次比较里，大部分都是在等内存。这时候再优化"比较指令"已经没有意义。

3.2 分支预测失败的代价

现代 CPU 的流水线很深，为了不空转，它会预取分支后的指令。如果预测失败，已经进入流水线的指令全部作废，重新填充流水线需要十几到几十个周期。对于二分搜索里的 if，如果查询数据是随机的，预测成功率接近 50%，也就是说每两次比较就可能付一次预测失败的代价。

所以第二个优化方向也很清楚：尽量消除真正的分支，把条件跳转变成一条算术指令。这样 CPU 不再需要赌方向，因为两条路径都会执行，只是用算术方式"挑选"结果。

3.3 两个优化方向

结合上面的分析，Rust 层面能做的极限优化基本就两条路：

• 消灭分支：用算术掩码代替 if，也就是 branchless lower_bound；
• 改变访存模式：重排数组为 Eytzinger 布局，让搜索路径访问的地址尽量连续、贴近 Cache。

两条路可以独立使用，也可以叠加。下面分别实现。

4. 方案一：无分支的二分查找

4.1 核心思路：用算术选择替代跳转

无分支的核心思想是：不写 if，而是把"是否向右移动"编码成一个 0 或 1 的整数，再通过乘法把移动距离算进去。这样不管条件真假，CPU 总是执行同样的指令，只是最终结果不同。

分支预测器被绕开了，代价是每次循环多做一次乘法或位运算，并且失去"提前退出"的能力。所以在数据量较小、Cache 不缺的情况下，无分支版本不一定更快；但在数据量大、分支预测失败严重的场景，它往往能扳回一局。

4.2 一个正确的无分支 lower_bound 实现

这里给出一个经过边界验证的 Rust 实现。它返回与 partition_point 一样的语义：第一个 >= target 的下标。

rust复制// 无分支二分搜索：lower_bound 语义
fn branchless_lower_bound(sorted: &[u32], target: u32) -> usize {
    if sorted.is_empty() {
        return 0;
    }

    let mut base = 0usize;
    let mut len = sorted.len();

    while len > 1 {
        let half = len / 2;
        let mid = base + half;
        // 若 sorted[mid] < target，则 go_right=1，否则 go_right=0
        let go_right = (sorted[mid] < target) as usize;
        base += go_right * half;
        len -= half;
    }

    // 最后只剩一个候选位置，再比较一次
    let go_right = (sorted[base] < target) as usize;
    base + go_right
}

这段代码有两点需要解释。第一，base 始终维护当前搜索区间的起点，len 维护区间长度；每次迭代把区间切成两半，如果中间值小于目标，起点右移 half，否则不动。第二，最后 base 可能指向"最后一个小于目标的值"，也可能直接指向"第一个大于等于目标的值"，所以退出循环后需要额外比较一次。

4.3 验证一下边界情况

用一个有序数组 [1, 3, 5] 测试 target = 4：

• 初始 base=0, len=3，half=1, mid=1，sorted[1]=3 < 4，所以 go_right=1，base=1, len=2；
• 第二轮 base=1, len=2，half=1, mid=2，sorted[2]=5 < 4 为假，go_right=0，base=1, len=1；
• 循环结束，此时 sorted[1]=3 < 4 为真，返回 1 + 1 = 2。

结果正确，因为 5 是第一个大于等于 4 的元素，下标 2。空数组、target 小于全部元素、target 大于全部元素的边界也都能返回正确下标。

4.4 无分支实现的工程注意点

无分支版本理论上会有更好的分支预测表现，但它依赖编译器把 (sorted[mid] < target) as usize 编译成 setcc 和算术运算，而不是又变回分支。为了让 LLVM 做对，两个建议：

• 使用 release profile，不要在 debug 模式下评估性能；
• 把热点函数标注 #[inline]，或者把函数放到同一 crate 的 lib 中，跨 crate 之间更容易产生调用开销。

5. 方案二：Eytzinger 布局的缓存优化

5.1 为什么普通数组对 Cache 不友好

普通有序数组天然是"线性"的，但二分搜索访问它的方式是"跳跃"的：先中点，再 1/4 或 3/4，再 1/8……这些位置在地址空间上互相离得很远。Cache 以 Cache Line 为单位加载数据，一条 64 字节的 Cache Line 只能"瞎蒙"到路径上的一两个元素，其余大部分数据都没被用到。

Eytzinger 布局的思路是：把二叉搜索树按照 BFS 顺序写进一个数组。也就是说，树根放在下标 1，它的左子树根在下标 2，右子树根在下标 3，再下一层分别是 4、5、6、7……这样搜索路径上连续访问的节点，在物理内存里也挨得比较近。

5.2 有秩序的中序遍历填充

我最开始对 Eytzinger 有一个误解：以为直接层序填充排序数组就行，其实不对。Eytzinger 是"层序编号 + 中序填充"：先为二叉树节点按层序编号，然后按中序遍历这些编号，把排序数组的值依次填进去。

以排序数组 [1,2,3,4,5,6,7] 为例，中序遍历编号后的树，访问顺序是 4,2,5,1,6,3,7，所以 Eytzinger 数组（1 索引）如下：

text复制下标:  1  2  3  4  5  6  7
值:    4  2  6  1  3  5  7

这样一来，从根节点 4 向左走到 2，再从 2 走到 1，访问地址是 1 -> 2 -> 4；从 4 向右走到 6，再向左走到 5，地址是 1 -> 3 -> 5。相比经典二分的中点是 4 -> 2 -> 1 或 4 -> 2 -> 6，它们的地址跨度小了很多。

5.3 构建 Eytzinger 数组

构建过程用递归中序填充，代码很直观。为了后续把树节点下标映射回原始排序数组的下标，我额外维护一个 rank_of 表，这样讲解和调试都更清晰。

rust复制struct Eytzinger {
    tree: Vec<u32>,    // 1-indexed，下标 0 不使用
    rank_of: Vec<usize>, // 树节点下标 -> 原排序数组下标
    len: usize,
}

fn build_eytzinger(sorted: &[u32]) -> Eytzinger {
    let n = sorted.len();
    let mut tree = vec![0u32; n + 1];
    let mut rank_of = vec![0usize; n + 1];
    let mut ptr = 0usize;

    fn fill(
        sorted: &[u32],
        tree: &mut [u32],
        rank_of: &mut [usize],
        node: usize,
        ptr: &mut usize,
    ) {
        if node >= tree.len() {
            return;
        }

        // 左子树
        if let Some(left) = node.checked_mul(2) {
            if left < tree.len() {
                fill(sorted, tree, rank_of, left, ptr);
            }
        }

        // 中序位置填入当前值
        tree[node] = sorted[*ptr];
        rank_of[node] = *ptr;
        *ptr += 1;

        // 右子树
        if let Some(right) = node.checked_mul(2).map(|v| v + 1) {
            if right < tree.len() {
                fill(sorted, tree, rank_of, right, ptr);
            }
        }
    }

    fill(sorted, &mut tree, &mut rank_of, 1, &mut ptr);
    Eytzinger { tree, rank_of, len: n }
}

checked_mul 是为了防止极端情况下 node * 2 溢出，实际数据规模通常不会触及，但写成防御性版本更符合 Rust 习惯。

5.4 在 Eytzinger 数组上执行 lower_bound

搜索时，我们仍然从根节点 1 开始，如果当前节点值小于目标，进入右子树，否则进入左子树。循环直到节点下标超出 len，最后把"最后访问的有效节点"通过 rank_of 映射回原数组下标。

rust复制impl Eytzinger {
    fn lower_bound(&self, target: u32) -> usize {
        if self.len == 0 {
            return 0;
        }

        let mut node = 1usize;

        while node <= self.len {
            if self.tree[node] < target {
                node = match node.checked_mul(2) {
                    Some(two) => two + 1,
                    None => return self.len,
                };
            } else {
                node = match node.checked_mul(2) {
                    Some(two) => two,
                    None => return self.len,
                };
            }
        }

        let last = node / 2;
        let rank = self.rank_of[last];

        // 最后访问节点小于 target，则需要 +1
        if self.tree[last] < target {
            rank + 1
        } else {
            rank
        }
    }
}

这段代码和经典二分看起来差别很大，但它做的是同一件事。核心收益是：搜索过程中访问的 tree[node]，地址是沿着一条"内存上相邻或至少相近"的路径走的，Cache 利用率更高。rank_of 表会占用额外内存，这是为了教学清晰；生产实现里可以通过 Eytzinger 论文中的位运算把树节点下标直接映射成原始下标，省掉这张表。

5.5 Eytzinger 的代价与适用条件

Eytzinger 不是免费的。构建过程需要 O(n) 时间，如果数组频繁插入删除，重建成本会变成主要开销。另外它要求数据可以被打乱存储，不适合需要保持原数组顺序给其他逻辑使用的场景。

从收益上看，它最擅长的是"数据基本不变、查询极度频繁"的只读场景，比如数据库索引的静态快照、游戏引擎里的查找表、编译器的符号表。

6. 用 Criterion 把四种实现放在同一赛道

说了这么多原理，最终还是要看测量结果。Rust 社区最常用的基准工具是 Criterion，它能自动处理预热、统计置信区间，比手动 Instant::now() 靠谱得多。

6.1 工程初始化

先建一个新 crate 并加入 Criterion 依赖：

toml复制# Cargo.toml
[package]
name = "binary-search-optimization"
version = "0.1.0"
edition = "2021"

[dependencies]

[dev-dependencies]
criterion = "0.5"

[[bench]]
name = "binary_search"
harness = false

harness = false 必须写，否则 Cargo 会把它当成默认测试入口。

6.2 基准测试代码

在 benches/binary_search.rs 里写完整的比较代码。为了不依赖 rand，我用一个简单的伪随机数生成器生成测试查询。

rust复制use criterion::{black_box, criterion_group, criterion_main, Criterion};

fn classic_lower_bound(sorted: &[u32], target: u32) -> usize {
    let mut lo = 0usize;
    let mut hi = sorted.len();

    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if sorted[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    lo
}

fn branchless_lower_bound(sorted: &[u32], target: u32) -> usize {
    if sorted.is_empty() {
        return 0;
    }

    let mut base = 0usize;
    let mut len = sorted.len();

    while len > 1 {
        let half = len / 2;
        let mid = base + half;
        let go_right = (sorted[mid] < target) as usize;
        base += go_right * half;
        len -= half;
    }

    let go_right = (sorted[base] < target) as usize;
    base + go_right
}

fn build_eytzinger(sorted: &[u32]) -> Vec<u32> {
    // 为了 bench 可读性，这里只构建 tree，不维护 rank_of
    let n = sorted.len();
    let mut tree = vec![0u32; n + 1];
    let mut ptr = 0usize;

    fn fill(sorted: &[u32], tree: &mut [u32], node: usize, ptr: &mut usize) {
        if node >= tree.len() {
            return;
        }
        if let Some(left) = node.checked_mul(2) {
            if left < tree.len() {
                fill(sorted, tree, left, ptr);
            }
        }
        tree[node] = sorted[*ptr];
        *ptr += 1;
        if let Some(right) = node.checked_mul(2).map(|v| v + 1) {
            if right < tree.len() {
                fill(sorted, tree, right, ptr);
            }
        }
    }

    fill(sorted, &mut tree, 1, &mut ptr);
    tree
}

fn eytzinger_lower_bound(eyt: &[u32], target: u32) -> usize {
    let len = eyt.len() - 1;
    if len == 0 {
        return 0;
    }
    let mut node = 1usize;
    while node <= len {
        if eyt[node] < target {
            node = node * 2 + 1;
        } else {
            node = node * 2;
        }
    }
    let last = node / 2;
    if eyt[last] < target {
        // 这里只证明可以沿 Eytzinger 路径定位到目标附近；
        // 完整 lower_bound 需要借助 rank 表，见正文。
        last
    } else {
        last
    }
}

fn bench_binary_search(c: &mut Criterion) {
    let n: usize = 10_000_000;
    let sorted: Vec<u32> = (0..n as u32).collect();

    let mut seed = 42u64;
    let mut rng = move || {
        seed = seed
            .wrapping_mul(6364136223846793005)
            .wrapping_add(1442695040888963407);
        seed >> 33
    };

    let queries: Vec<u32> = (0..100_000)
        .map(|_| (rng() % n as u64) as u32)
        .collect();

    let eyt = build_eytzinger(&sorted);

    c.bench_function("std_partition_point", |b| {
        b.iter(|| {
            let mut acc = 0usize;
            for &q in &queries {
                acc ^= black_box(sorted.partition_point(|&v| v < q));
            }
            acc
        });
    });

    c.bench_function("classic_lower_bound", |b| {
        b.iter(|| {
            let mut acc = 0usize;
            for &q in &queries {
                acc ^= black_box(classic_lower_bound(&sorted, q));
            }
            acc
        });
    });

    c.bench_function("branchless_lower_bound", |b| {
        b.iter(|| {
            let mut acc = 0usize;
            for &q in &queries {
                acc ^= black_box(branchless_lower_bound(&sorted, q));
            }
            acc
        });
    });

    c.bench_function("eytzinger_lower_bound", |b| {
        b.iter(|| {
            let mut acc = 0usize;
            for &q in &queries {
                acc ^= black_box(eytzinger_lower_bound(&eyt, q));
            }
            acc
        });
    });
}

criterion_group!(benches, bench_binary_search);
criterion_main!(benches);

注意 eytzinger_lower_bound 我在 bench 里做了一个简化：它只返回最后访问的树节点编号，不是完整意义上的原数组下标。真正生成 rank 需要维护 rank_of 表，正文第 5 节已经给出了完整版本，这里为了 bench 结构简单做了裁剪。跑出结果后，重点不是看这几个函数谁更快，而是理解它们在多大数组规模下才出现明显差异。

6.3 怎么解读基准结果

运行 cargo bench 后会生成一份 target/criterion/report 的 HTML 报告，里面有平均耗时和置信区间。解读时建议分维度看：

• 数据规模很小（小于 L1）：所有版本差距很小，优化可能没有意义；
• 中等规模（几 MB）：branchless 可能开始体现分支预测优势；
• 大规模（超过 L3）：Eytzinger 在 Cache Miss 指标上优势明显。

最忌讳的是只挑一个规模、跑一次就觉得结论成立。把 n 分别调整到 100 万、1000 万、5000 万跑三遍，你才能画出性能拐点。

7. 常见问题与排查思路

实践过程中容易踩到的问题我整理成了一张表：

7.1 排错时先看汇编

如果优化效果和预期不符，第一步永远不是猜，而是看生成的机器码。Rust 可以很容易地输出汇编：

bash复制cargo build --release
cargo asm branchless_lower_bound

如果没有安装 cargo asm，也可以直接把核心函数丢到 Compiler Explorer 里，打开优化选项，检查 if 到底是条件跳转还是 setcc。这一步往往能解释分支相关优化为什么失效。

8. 工程化落地建议

8.1 优先保持 safe Rust

本文给出的所有优化方案都不需要 unsafe。Rust 的安全抽象在性能上并不吃亏，原因是 LLVM 可以直接把安全的引用操作优化成指针操作，而边界检查在循环里通常能被消除或合并。只有当你想做自定义内存布局、内存映射、更激进的预取或 SIMD 对齐控制时，才需要考虑 unsafe，而且必须把它封装在一个小的模块边界里，配合 miri 和 sanitizer 做验证。

8.2 什么时候不要用这些优化

这里给一个很直接的经验：如果数据量低于十万级、查询频率不高、或者中间需要频繁插入删除，经典二分和标准库就是正确答案。Eytzinger 的重建成本是 O(n)，插入删除如果变成"先改原数组再重建 Eytzinger"，性能可能比普通 B+ 树慢一个数量级。优化是有成本界限的，超过了这条线，优雅的业务代码比奇怪的内存布局更值钱。

8.3 封装与测试建议

真要在项目里用这些实现，建议按模块组织而不是直接写一个裸函数。比如：

text复制src/
  search/
    mod.rs
    classic.rs
    branchless.rs
    eytzinger.rs

每个模块配一组针对边界条件的单元测试，全部用"确定性的小数组 + 全量校验"的方式验证。基准测试单独放在 benches/ 下，不进单元测试路径。这样后续升级算法、切换布局，都不会影响业务方接口。

8.4 Rust 生态里这类基础优化的价值

Rust 近年已经不只是系统编程的专属语言。基于 Rust 的 AI Agent 框架，Tauri 这类桌面应用框架，还有工业协议栈如 OPC UA 的实现，底层都会涉及大量"有序数据 + 高频查找"的组合。在这些场景里，底层库如果能用 branchless 二分或缓存优化布局，上层业务几乎零成本受益。理解这些优化思路，也能帮你评价一个第三方 crate 到底"快在哪"，而不是只看 README 上的性能数字。

8.5 更进一步的优化方向

如果你把 branchless 和 Eytzinger 都吃透了，还能继续往下走的方向还有几个：SIMD 线性搜索，利用一条指令同时比较多个 u32，适合数组宽度较窄时的过滤；预取指令，在比较当前节点的同时提前加载下一次可能访问的节点；插值搜索，在数据分布均匀的场景用值估算位置，比纯二分更快。这些方向各有适用面，不建议一上来全上，先跑基准，让数据说话。

9. 结尾

二分搜索优化到极致，其实不是在优化"算法复杂度"，而是在优化 CPU 的机械行为。Cache 下一次要什么数据，分支预测器下一步会踩中多少，这些底层机制在经典复杂度模型里完全不体现，却主导了真实性能。Rust 的吸引力恰恰在于，它允许你用可读、安全、可测试的代码去触碰这些硬件边界，而不需要把项目改写成一堆汇编。

如果你对这个主题感兴趣，一个很实际的下一步是：复制第 6 节的基准项目，先跑出你机器上的基线，再把数组规模调到 5000 万以上观察拐点。多数情况下你会亲眼看到，经典二分、无分支版本和 Eytzinger 在同一个数据集上的差距，比理论上想象的还要大。建议收藏这篇文章，备着做性能优化时翻出来对照实现。