Bw-Tree 无锁 B+树深度实战：从 Mapping Table 增量更新到学习索引 RMI / PGM-index / ALEX 的工程全解
在数据库存储引擎的演进史上，B+树是最长寿的数据结构，但它也是最"不适合多核"的数据结构之一。传统 B+树靠闩锁耦合（latch crabbing / lock coupling）保证并发正确性：读路径上必须逐层持有读锁，写路径则要在发现子节点安全后逐层释放写锁。这意味着一棵深度为 4 的树，一次点查要获取 4 次 latch，而根节点 latch 天然成为全局热点。
NVMe 时代这个矛盾被进一步放大。单块 NVMe SSD 可以轻松跑出百万 IOPS，而一棵带 latch 的 B+树在 64 核上的点查吞吐往往卡在十几万 QPS —— 瓶颈根本不在磁盘，而在树结构自身的同步开销。
微软 2013 年在 ICDE 发表的 Bw-Tree（Buzzword-Tree，后用于 SQL Server Hekaton、MongoDB WiredTiger 的原型探索）给出了一套完全不同的答案：把"原地修改节点"彻底废掉，改成纯追加式（append-only）+ 无锁 CAS，从而让读路径完全不需要任何 latch。
一、Bw-Tree 的三块基石
1. Mapping Table：把物理指针换成逻辑 ID
Bw-Tree 引入一层间接映射表（Mapping Table），树中所有"指向子节点的指针"都不再是内存地址，而是一个 PID（Page ID，逻辑标识符）。Mapping Table 是一个数组，负责把 PID 映射到当前生效的物理页面地址。
Mapping Table
┌──────┬───────────────────────────────┐
│ PID │ 物理地址 │
├──────┼───────────────────────────────┤
│ 0 │ 0x7f00... (base page) │
│ 1 │ 0x7f80... (base + deltas) │
│ 2 │ 0x7fc0... (flushed page) │
└──────┴───────────────────────────────┘这层间接性带来三个关键收益：
- CAS 原子更新：修改一个节点 = 把 Mapping Table 里的一项 CAS 成新地址。一次 8 字节原子写就完成了"整节点替换"。
- 逻辑删除：节点被删除后 PID 可复用或标记为无效，无需像传统 B+树那样处理并发悬垂指针。
- 存算分离友好：PID 可以对应到磁盘上的 LSS（Log-Structured Store）偏移，内存不够时只需把 PID 映射改为"磁盘位置"，无需遍历整棵树重写指针——这正是 Bw-Tree 天然支持大于内存的索引的原因。
2. Delta Update：增量链代替原地写
所有修改（插入、删除、更新）都不重写节点本体，而是在 base page 前面挂一个 delta record，形成一个从新到旧的单向链表：
newest oldest
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ InsertDelta │──▶│ DeleteDelta │──▶│ Base Page │
│ (k=42,v=..) │ │ (k=17) │ │ [sorted KVs] │
└──────────────┘ └──────────────┘ └──────────────┘
▲
└── Mapping Table[pid] 指向这里查找时从链头往下走：命中 InsertDelta 直接返回，命中 DeleteDelta 说明键不存在，走到 base page 则做二分查找。
代价很明显：链越长，读越慢（额外的 cache miss + 分支）。因此必须有一个后台线程做 consolidation：把 delta 链折叠回一个新的 base page，再 CAS 替换 Mapping Table 项。WiredTiger 的经验值是链长超过 8~16 触发折叠。
3. 无锁读：真的不需要 latch 吗？
读线程拿到 PID → 查 Mapping Table 得到物理地址 → 顺着 delta 链扫描。整个过程中读线程不加任何锁。这听起来违反直觉：如果读的过程中别人把页面回收了怎么办？
答案是 epoch-based reclamation：每个线程进入临界区时登记到一个全局 epoch，页面被替换后并不立刻 free，而是挂到对应 epoch 的 retirement list 上；只有当所有线程都已离开该 epoch，这批页面才真正释放。这也是 crossbeam-epoch、Hazard Pointer 那一族方案的标准做法。
二、SMO：无锁树结构变更的真正难点
点查的插入删除只是"挂 delta"，很简单。真正的硬骨头是 SMO（Structure Modification Operation）——节点满了要分裂、太空了要合并。一个 SMO 需要同时修改父节点和子节点，这在无锁世界里无法一次 CAS 完成。
Bw-Tree 的解法是把 SMO 拆成两个可独立完成的小步骤，用 delta 记录中间状态：
以分裂为例（子节点 P 分裂出 Q）：
- Child Split Delta：先在 P 上挂一个
SplitDelta，记录分裂键 K 和新的兄弟 Q 的物理地址。此时 P 处于"半分裂"状态：
┌────────────────┐ ┌──────────┐
│ SplitDelta │──▶│ Base P │
│ sep=K, sib=Q │ │ │
└────────────────┘ └──────────┘这一步是单节点的 CAS，已经对外生效：任何查到 P 且键 ≥ K 的请求，会顺着 sib 指针自动跳到 Q。也就是说，即使第 2 步永远不做，树在语义上依然是正确的，只是父节点还不知道 Q 的存在（访问路径变长一点）。
- Parent Update Delta：再往父节点挂一个
IndexDelta(newpid=Q, sep=K)，把 Q 正式纳入父的索引范围。若父节点因此也满了，则递归触发父的分裂。
这种"先让状态在语义上生效、再优化访问路径"的设计，是 Bw-Tree 最精妙的地方：SMO 的中间态是合法态，所以不需要事务、不需要回滚、不需要全局锁。MongoDB 把它称为 *restructure-the-tree-by-delta* 模式。
合并同理，只是多一步：先挂 RemoveNodeDelta 标记兄弟失效，再更新父节点删除该指针，最后由 GC 回收物理页。
三、核心代码：一个最小可运行的 Mapping Table + Delta Chain
下面用 Rust 给出 Bw-Tree 最核心的两块逻辑。省略了 epoch 回收与 LSS，但完整保留了并发语义。
use std::sync::atomic::{AtomicPtr, Ordering};
/// 增量记录类型
enum Delta {
Insert { key: u64, val: u64, next: *const Node },
Delete { key: u64, next: *const Node },
Split { sep: u64, sibling: *const Node, next: *const Node },
}
struct Node {
/// base page: 有序键值对；若是 delta 节点则为空
base: Option<Vec<(u64, u64)>>,
delta: Option<Box<Delta>>,
}
/// Mapping Table: PID -> AtomicPtr<Node>
struct MappingTable {
slots: Vec<AtomicPtr<Node>>,
len: std::sync::atomic::AtomicUsize,
}
impl MappingTable {
/// 无锁更新：把新节点 CAS 到槽位上
fn try_update(&self, pid: usize, old: *mut Node, new: *mut Node) -> bool {
self.slots[pid]
.compare_exchange(old, new, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
}
/// 无锁读：获取最新快照指针（调用方需在 epoch 保护下解引用）
fn get(&self, pid: usize) -> *mut Node {
self.slots[pid].load(Ordering::Acquire)
}
}查找逻辑——注意没有任何锁：
/// 从 delta 链头向下扫描；返回 None 表示键不存在
unsafe fn search(head: *const Node, key: u64) -> Option<u64> {
let mut cur = head;
while !cur.is_null() {
let n = &*cur;
match &n.delta {
Some(Delta::Insert { key: k, val, next }) => {
if *k == key { return Some(*val); }
cur = *next;
}
Some(Delta::Delete { key: k, next }) => {
if *k == key { return None; } // 已删除，短路
cur = *next;
}
Some(Delta::Split { sep, sibling, next }) => {
if key >= *sep { return search(*sibling, key); } // 分裂中，跳兄弟
cur = *next;
}
None => { // 走到 base page
let base = n.base.as_ref().unwrap();
return base.binary_search_by_key(&key, |&(k, _)| k)
.ok()
.map(|i| base[i].1);
}
}
}
None
}插入则是经典的 CAS 重试循环（optimistic concurrency control）：
unsafe fn insert(mt: &MappingTable, pid: usize, key: u64, val: u64) {
loop {
let old = mt.get(pid);
let new = Box::into_raw(Box::new(Node {
base: None,
delta: Some(Box::new(Delta::Insert { key, val, next: old })),
}));
if mt.try_update(pid, old, new) { return; } // 成功
// 失败说明别人抢先修改了，释放后重试
drop(Box::from_raw(new));
std::hint::spin_loop();
}
}这段代码的工程价值在于：写冲突被压缩到单个 8 字节 CAS 上，冲突窗口只有几十纳秒，根本不会像 latch 那样把整个节点锁住几百微秒。这就是 Bw-Tree 在多核上能线性扩展的根因。
四、从 Bw-Tree 到学习索引：索引结构的范式转移
Bw-Tree 解决的是"如何无锁地做树导航"，但它没有回答另一个问题：树本身是不是必需的？
2018 年 Google 的 *The Case for Learned Index Structures* 给出了激进答案：索引本质上是一个从 key 到 position 的单调映射函数 f(k) ≈ pos。既然是函数，就可以用模型去拟合它，而不是用树去分段逼近。
RMI（Recursive Model Index）
RMI 是一个分层模型：顶层用一个小模型把 key 空间粗分成若干桶，每个桶再挂一个专家模型精修。查询就是从根模型一路走到叶模型，得到预测位置，再在预测位置附近 ±ε 做局部二分查找。
/// 两层 RMI 的极简形态：顶层线性分段，底层线性回归
struct RmiIndex {
root: LinearModel, // 粗分桶
experts: Vec<LinearModel>, // 每桶一个精修模型
}
impl RmiIndex {
fn lookup(&self, key: u64, sorted: &[(u64, u64)]) -> Option<u64> {
let bucket = (self.root.predict(key) as usize).min(self.experts.len() - 1);
let pred = self.experts[bucket].predict(key) as usize;
// last-mile search：在预测位置邻域内二分
let lo = pred.saturating_sub(self.experts[bucket].max_err as usize);
let hi = (pred + self.experts[bucket].max_err as usize + 1).min(sorted.len());
sorted[lo..hi]
.binary_search_by_key(&key, |&(k, _)| k)
.ok()
.map(|i| sorted[lo + i].1)
}
}RMI 的精髓在于 max_err：模型训练时记录最大误差界，查询时就能把搜索范围从"整棵树"收敛到"几十个元素的窗口"，而窗口内是连续内存，一次 cache line 就能覆盖——这比跳跃 4 层树节点的 4 次 cache miss 快得多。
PGM-index：可证明最优的分段模型
RMI 的误差界是经验性的，PGM-index 则给出理论上 ε-最优的分段算法：给定误差界 ε，用最少的分段数覆盖全部数据，且可在 O(n) 时间内流式构建。它天然支持合并与流式更新，在时序、日志类 append-heavy 场景比 B+树更省空间（压缩率常达 10~100 倍，因为只需存少量线性段而非全部 key）。
ALEX：把学习索引和树真正结合起来
纯模型索引的最大痛点是写入：数据分布漂移后模型失准，而重训练代价高。ALEX（*Updatable Learned Index*）的做法是保留 Bw-Tree 式的节点 + 增量骨架，但把节点内部的查找从"二分"换成"模型预测"：
- 节点满时不再按中位数分裂，而是按模型预测的线性度选择分裂点（gapped array 留出插入空隙，减少数据搬移）；
- 插入采用类似 delta 的局部间隙填充，摊还 O(1)；
- 节点内部维护一个极小的线性模型，冷启动即训练，代价可忽略。
实测 ALEX 在多数读多写少负载下比 B+树快 2~4 倍，内存占用仅为 1/3 左右。
五、工程观点：什么时候该选什么
| 场景 | 推荐 | 理由 |
|---|---|---|
| 通用 OLTP，需 MVCC + 范围扫描 | Bw-Tree / B+树变体 | 结构稳定，范围扫描友好，MVCC 版本链易挂 |
| 只读分析型，key 分布平滑 | RMI / PGM-index | 内存最省，点查最快 |
| 读多写少，分布会漂移 | ALEX | 模型 + 树的折中，更新摊还 O(1) |
| 键值分离严重的宽表 | Bw-Tree + LSS | PID 间接层天然支持大于内存的索引 |
几点实战经验值得强调：
- Bw-Tree 的 delta 链是双刃剑。写负载高时链会暴涨，consolidation 线程跟不上就会读放大。生产环境务必监控
avg_delta_chain_len，并给 consolidation 配置独立的 CPU 配额。WiredTiger 后来在部分场景回退到传统 B+树，很大程度上就是栽在这上面。 - epoch 回收的"内存滞留"问题。长事务或长查询会拖住 epoch 推进，导致 retired pages 迟迟不能释放。监控系统里一定要有
oldest_active_epoch指标。 - 学习索引不要盲目上。key 分布如果是哈希值（均匀随机），模型拟合不出任何结构，
max_err会退化到接近全表范围，此时学习索引反而比二分更慢。先画 key 的 CDF 曲线，再决定是否上模型——这是唯一的判断标准。 - SMO 的可观测性。Bw-Tree 的"半分裂态"让传统 B+树的树结构校验工具全部失效。调试时建议维护一个后台校验线程，定期从根做全量遍历，统计"通过 sibling 指针跳转次数"来发现未完成的 SMO。
六、小结
Bw-Tree 与学习索引代表的是两条不同但互补的演进路线：前者保持树结构，重写并发协议（原地写 → 增量追加，latch → CAS，物理指针 → 逻辑 PID）；后者质疑树本身（分段逼近 → 函数拟合）。
对工程实践而言，最现实的落地形态是 ALEX 那类混合结构：用模型压缩树高、用增量链承载更新、用 epoch 保证无锁安全。理解这三层，就掌握了现代存储引擎索引设计的主干脉络。
一句话选型建议：需要事务语义和范围扫描，选 Bw-Tree；数据只读且分布可学习，选 PGM-index；介于两者之间，选 ALEX。
发表评论 取消回复