Bw-Tree

定义

Bw-Tree(Buzz Word Tree)是微软研究院 2013 年提出的无闩锁(latch-free)B 树变体,为多核 CPU 与新型存储设计,应用于 SQL Server 的内存 OLTP 引擎 Hekaton 与 Azure 的存储组件。

原理

Bw-Tree 有两项核心设计。其一是增量更新(delta record):修改不原地改页,而是在页前面挂一条增量记录,通过一次 CAS(比较并交换)原子地把"指向页的指针"替换为"指向增量链的指针",完全避免加锁;增量链过长时再整体合并(consolidate)为新页。其二是映射表(mapping table):所有节点通过逻辑页号间接寻址,父节点存的是页号而非物理指针,因此替换页只需改映射表一个槽位,不必级联更新祖先。

评价

Bw-Tree 在高并发读多写少场景表现优异;但后续研究(如 CMU 的 OpenBw-Tree 复现)指出其实现复杂度高,增量链遍历也带来开销,性能未必稳定胜过精心优化的有锁 B+ 树。它仍是无锁索引设计的里程碑工作。