B+树/B树并发控制常用方法

以下所有描述基于项目： https://github.com/Spear-Neil/IndexResearch

B+ Tree OLC(乐观锁的方法)

核心机制：

每个节点都有一个 64 位原子字段，包含了三类信息：

• bit0：obsolete（节点是否废弃）
• bit1：locked（是否被写线程持有）
• 高位：版本号（用于检测读期间是否发生修改）

主要方法：

• 读操作开始前不加真正读锁，只读取版本；若节点被锁或已 obsolete，则重试
• 写操作执行前通过CAS 把“读到的版本”升级为写锁；失败则重试
• 写操作执行完时通过对节点的64位原子字段 fetch_add(0b10) 释放写锁并推进版本
• 读操作完成后校验版本是否变化，变化则重试

基本思路是：读路径尽量无锁，写路径短暂独占。读操作一旦检测到冲突，就从根节点重试。

写写冲突依靠互斥锁解决，但不是传统mutex，而是基于CAS实现的锁。

读写冲突依靠读操作主动检查冲突，一旦发生冲突则从根节点重新读。与传统读写锁的区别是读者不会持有读锁/共享锁，而是主动进行版本校验，在发生操作后自行重试。读操作永远不会阻塞并发的写操作，事实上写者察觉不到读者的存在。

B-link Tree（B+Tree 的并发变体）

核心机制：

每个节点（内部节点和叶子节点）都保存指向右兄弟节点的指针，这样即使一个节点刚分裂、来自父节点的指针还不能完全反应新结构，查询/写入操作依然可以沿着节点的右兄弟指针向右侧查询，找到正确的节点。

写写冲突解决方法：写线程在要改的节点上加写锁，多个写线程若命中同一热点节点，会排队。

读写冲突解决方法：对于单个节点内部的数据，依靠节点级的读写锁确保读写互不干扰。对于整体数据结构变化导致的读写冲突，依赖右兄弟指针保证读线程总是能找到目标键，因此在节点分裂期间，读者不会因为父节点的短暂滞后而漏读数据。

既然有读写锁为什么还要右兄弟指针：

• 读写锁只保证“当前锁住节点”的互斥与一致性，不保证“整条路径”在并发分裂下始终是最新拓扑。
• 如果没有右兄弟指针，线程在旧路径上可能需要回到上层重试，甚至频繁失败。
• 右兄弟指针提供了“前向纠偏通道”，让操作在局部继续前进而不是全路径回退。

用一个读写操作典型场景理解B-link Tree：

以 https://github.com/J-XZ/IndexResearch/tree/master/BLinkTree的实现为例：

首先明确：B-link Tree 的每个节点有一个读写锁。实际实现可能不是传统共享锁，而是基于CAS或其他原子内存读写机制的自旋锁，但是语义上和读写锁是相同的。

读操作在检索一个KV时，沿着树进行查找，直到找到叶子节点。它会在读到任何一个节点时对节点加读锁，读取节点内部的数据，以确定下一跳读哪个子节点。然后就会释放当前节点的读锁，去尝试为子节点加读锁。

• 假设读线程在获取子节点读锁前子节点发生分裂，则获取读锁之后，根据节点内kv的范围判断是否需要读取右侧兄弟节点
  • 如果要读取右侧兄弟节点，则进一步对右侧兄弟节点加读锁，然后再释放左侧节点的读锁，确保读路径连续
• 假设读线程在获取子节点读锁前子节点被删除，也不会影响正确性，因为节点只能被逻辑删除，会提供指向正确跳转节点的指针。（被逻辑删除的节点依赖安全内存回收机制释放。
• 如果上述两种情况都没有发生，则沿着子节点继续检索，直到找到叶子节点。

写操作在向B-link Tree写入一个KV时，首先需要沿着树进行查找，直到找到叶子节点。查找的过程和读操作相同。写操作找到目标叶子节点之后，会为叶子节点加写锁，写完叶子节点之后，写线程判断叶子节点是否需要分裂

• 如果不用分裂，释放写锁，写操作完成
• 如果分裂，在持有旧叶子写锁期间完成“旧叶 + 新叶 + 右链”的局部结构更新。由于持有旧叶的写锁，因此在更新期间新旧叶子节点都不会被任何其他节点访问。
  • 进一步，如果下层节点导致了分裂，写线程会在持有下层节点锁的情况下，获取其父节点的写锁。只有成功获得父节点的写锁之后，才会释放子节点的写锁。这样主要是为了防止并发的写者多次分裂子节点导致父节点被改乱的情况。获得父节点的写锁并释放子节点的写锁后，写线程继续修改父节点。如果继续触发父节点分裂，则按照相同的逻辑继续向上传播节点更新。

补充：上面的代码实现为读者一定会为节点加读锁，但是B-link Tree定义并不一定要求读者加读锁，读线程也可能实现为乐观版本校验甚至其他无锁变体。写线程之间则一定需要某种互斥/同步机制来保证结构修改原子性（可用写锁、CAS 协议、版本化重试等）

FAST

核心机制

类似B+树，是一个为快速查询定制的、CPU缓存友好的静态索引。输入大量数据然后创建索引，并支持后续大量读取，不支持在线插入/删除数据。

数据结构的创建过程：

输入一组有序的key和相同数量的value。把所有数据按固定块大小切分到和cache line对齐。每个块里不是简单的顺序KV，而是块的前一半放key，后一半放value。这些块构成了树的最底层。

继续采用自底向上的方法构建索引。

对于每个底层块，提取一个代表key（实现为块里面最后一个有效键），然后将代表key和这个块的起始位置索引按照与底层块相似的布局，生成次底层的所有块。

重复这个过程，直到整个树建完（顶部只有1个块）。

主要目的是内存布局的优化，所有层尽量按 cache line 对齐，便于 CPU 顺序取数。这个实现也不支持变长key，因此还能用simd指令实现更快速的并行key比较

读操作很直观，不赘述。

FBTree

核心机制

是一个实现得更完善的 B-link Tree

• 更像 B+ 树：内部节点主要存分隔信息（anchor/separator）和子指针，真实 KV 在叶子。

• 还带有 B-link 树特征：叶子和内部节点都有“右兄弟指针 + high key/边界键”，查找时可向右跳，支持并发分裂/合并下的正确路由。

• 路由层（内部节点）：用“前缀压缩 + 特征字节（SIMD 友好）”做快速分流，减少比较开销。
• 数据层（叶子节点）：用槽位+bitmap管理 KV，不强制每次写入都保持全局有序；范围查询时按需整理（lazy sort）。
• 结构调整：
  • 插入满了会分裂，产生新右兄弟，并把边界键向上插入；
  • 删除后可能与右兄弟合并，并向上删除/更新分隔键；
  • 根节点可升高/降低树高。

读写并发怎么处理

• 读路径是“乐观读”：读节点版本 -> 执行查找 -> 结束时校验版本没变；变了就重试。这里的重试是重读本节点。
• 写线程做结构修改时会更新版本，读线程据此检测冲突。
• 当读到一个正在分裂/刚变动的节点时，会根据 high key 与兄弟指针“向右纠偏”，避免读到错误分支。
• 结果是：读通常不阻塞写（除少数需要整理叶子顺序的场景），靠重试保证一致性。

写写并发怎么处理

• 同一节点结构修改（插入触发分裂、删除触发合并）通过节点排它锁串行化。
• 沿路径向上修复时采用类似 lock-coupling（拿到下一个再放当前），并依靠 sibling/right-link 处理并发结构变化。
• 同键更新值时使用原子替换（CAS/exchange）减少锁冲突；结构性写仍需排它保护。
• 本质上：值更新尽量无锁，结构变更有锁且局部化。

用EBR实现安全内存回收。

GoogleBTree

标准的B树实现，不支持读写并发和写写并发。

MassTree

一个高扇出、面向缓存/访存局部性优化的分层 trie

并发控制和B+ Tree OLC是一样的

STX

标准内存型B+树。没有提供并发控制机制。

Wormhole

• 叶子层很像 B+tree：叶子里放有序键值，叶子之间有链表，可顺序扫描。
• 但上层不是“多路比较树节点”，而是一个前缀元数据索引（论文里叫 MetaTrieHT）：按 key 前缀做最长前缀匹 配，再把查询“跳”到目标叶子。
• 所以本质是：“前缀跳转 + 叶内查找”，不是经典 B/B+ 的逐层比较下降。

• 核心机制

• 每个叶子管理一段有序 key 范围，容量满了就 split，太空了就 merge。
• 上层维护“前缀 -> 路由信息”的映射，路由信息记录该前缀对应的叶区间边界。
• 查询流程：
  1. 在前缀索引里做最长前缀匹配（LPM），快速定位候选叶。
  2. 在叶子内做精确匹配/范围定位。
• 范围扫描直接沿叶链表向右走，不必回到上层反复查。

用节点级的读写锁控制读写并发和写写并发。

用 QSBR RCU 做安全内存回收