上一篇中，我们从根到叶查找，再通过向上传播的分裂完成插入。现在继续回答三个问题：

1. 删除后节点太空，怎么办？
2. 范围查询怎样跨越多个叶子？
3. 一个线程正在修改结构，另一个线程怎样安全经过这里？

本文沿用第 04 篇的约定：键唯一，内部节点最多 M 个孩子，叶子最多 L 个条目；非根节点采用经典最低占用规则。示例取M = 4、L = 4，所以非根叶子至少有 2 个条目，非根内部节点至少有 2 个孩子。

分隔键 s 把左、右区间分开，满足左最大键 < s ≤ 右最小键。相等键走右边。真实系统的占用规则、版本管理和回收机制可能不同，不能直接把本文示意当成任何数据库的源码协议。

一、删除：先删条目，再判断结构是否需要调整

先查找目标叶子，确认条目存在，再删除它。若不存在，可以返回“未找到”；若删除后仍满足结构约束，通常无需借用或合并。

1. 删除最小键，就一定要改父节点吗？

不一定，这取决于分隔键的语义。

例如右叶子从[20,25,30]变为[25,30]，父节点原来的分隔键 20 仍然可以作为这个子树的下界；20 到 25 之间没有条目，不会因此把已有键送错子树。

如果实现要求父节点的分隔键始终精确等于右子树当前最小键，那就必须更新它，并考虑更新是否继续向上传播。后面讨论并发“安全节点”时，也必须把这个约定算进去。

2. 重分配：向同一父节点下的相邻兄弟借用

假设父节点的分隔键为 20：

L = [10] R = [20,25,30]

L 低于最低占用，R 有多余条目，可以把 20 从 R 移到 L：

L = [10,20] R = [25,30] 父分隔键：20 → 25

此时必须更新边界。若仍保留 20，查找 20 会被送到 R，而 20 已经搬到了 L。

3. 合并：兄弟没有余量时，把两个节点合成一个

假设：

L = [10] R = [20,25]

R 只有最低数量的条目，不能借出。可以合并成[10,20,25]，仍不超过容量 4；同时让 L 接到 R 原来的后继，父节点移除指向 R 的子指针和相应分隔键。

图 1：上半部从右兄弟借用，下半部合并。所有例子都采用叶容量 4、非根最低占用 2。

在经典重平衡过程中，兄弟应是同一个父节点下相邻的孩子。叶子链表上的相邻节点，未必有相同父节点，不能只凭next就随意进行这类借用或合并。

二、内部节点不能照搬叶子的合并方法

叶子保存数据条目，内部节点保存分隔键和子指针。调整内部节点时，父分隔键也参与移动。

1. 从右内部兄弟借一个孩子

设左节点因删除只剩 P0，父分隔键为 40，右节点有三个孩子：

左：P0 父分隔键：40 右：P1 | 60 | P2 | 80 | P3

把右边最左的孩子 P1 移到左侧，需要同时旋转两个边界：

左：P0 | 40 | P1 父分隔键：60 右：P2 | 80 | P3

40 从父节点下降到左节点，60 从右节点上升到父节点。只搬一个 key、不搬对应子指针，会破坏覆盖区间。

2. 合并内部节点

若左侧是P0，右侧是P1 | 60 | P2，父分隔键为 40，则合并结果是：

P0 | 40 | P1 | 60 | P2

这里需要把父分隔键 40 带下来，才能区分原来的左右子树。这与叶子合并不同：叶子中已有全部数据条目，不应再把父分隔键当成新记录插入一次。

父节点少了一个孩子后，也可能低于最低占用，于是继续向上处理。

3. 根收缩与空树

非叶根若最终只剩一个孩子，就可以让这个孩子成为新根，树高减一。若根本身就是叶子，删除最后一个条目后进入空树状态；采用空叶根还是无效根标识，取决于实现。

根变化时，保存根页标识的位置也必须更新。并发系统还要确保旧根或合并掉的页面不会被正在访问它们的线程继续误用。

“逻辑上不再属于树”不等于“物理内存立刻可以复用”。回收往往需要等待引用、Pin、版本或其他安全条件满足。

三、范围迭代：先定位起点，再沿叶子往后走

查询25 ≤ key ≤ 65时，不需要对每个可能的键都从根重新查一遍。

图 2：返回 30、40、50、60；遇到 70 后即可停止。查找值 25 本身不必存在。

基本步骤是：

1. 从根定位可能包含起点的叶子。
2. 在叶子中做lower_bound(25)，寻找第一个不小于 25 的条目；若结果在页尾，就沿后继继续寻找。
3. 逐个返回满足上界条件的条目。
4. 当前页耗尽时，移动到下一叶子；若下一个键大于 65 或没有后继，则结束。

迭代器状态可以包含当前页引用、页内位置和结束标记。是否支持反向遍历，是额外设计选择：可以维护前驱链接，也可以采用其他重新定位方法，不能说所有迭代器都必须双向。

在并发系统中，跨页移动不只是“读一下 next”。线程需要保证当前页和下一页的生命周期有效，并按协议处理分裂、合并或删除。

四、先分清三种保护：Pin、Latch 与事务机制

共享读 Latch 允许兼容的读者并发访问；排他写 Latch 阻止同一保护对象上的其他不兼容访问。具体还可以有乐观读、版本校验等设计，不限于互斥锁一种实现。

Latch 不负责撤销事务修改，Lock 本身也不会自动完成回滚。回滚、可见性和恢复还依赖事务协议、版本或日志。

索引结构线程安全，不等于事务隔离正确。例如，叶子链表没有坏，事务仍可能因隔离级别不同而看到新增记录或不同版本。

Latch 自己又怎样实现？

常见的选择包括互斥锁、自旋锁和读写锁。自旋等待可以避免一次线程休眠与唤醒，但会消耗 CPU，适合临界区很短且持有者能及时运行的情况。等待时间较长或竞争严重时，单纯一直自旋可能更差，实际实现也可能先自旋再休眠。

读写 Latch 允许多个读者共享，写者需要排他；它要额外管理读者计数、等待队列和公平性，并非读多时就一定更快。

CAS 等原子指令可以作为实现这些机制的基础，也能用于无锁数据结构。但一次指针 CAS 成功，只能证明那个原子步骤完成，不能自动保证整棵树的多步修改、内存可见性与页面回收全部正确。

五、Latch Crabbing：确认修改不再向上传播，才能放开祖先

Latch crabbing / coupling 的基本思想，是沿访问路径逐步取得下一节点的保护，而不是先释放所有保护再盲目继续。

1. 查找路径

在一个基本的读 Latch coupling 实现中：

取得父节点读 Latch 在父节点仍受保护时确定孩子 取得孩子的引用和读 Latch 释放父节点保护 继续向下

这让路由决定和孩子的安全访问连接起来。不同系统也可能用版本校验或 B-link 结构减少这种耦合，不能把这一种做法当成唯一合法算法。

2. 插入和删除路径

保守策略从根沿途取得写 Latch。拿到孩子后，如果能证明这次操作不再需要修改其父节点及更高祖先，就可以释放相应祖先的 Latch；否则继续保留。

图 3：孩子 C 不安全时保留 R；到达安全孩子 L 后，示例释放 R、C，继续保护 L。安全性由具体操作及结构约定决定。

在固定条目大小、没有额外祖先更新需求的经典模型里，可以用下面的直觉：

对应到简单计数模型，叶子插入前size < L，删除前size > min_size，通常提供这样的余量。但必须注意：

• 变长键需要检查可用字节，不能只数条目。
• 根有单独规则，根页标识也要保护。
• 如果父分隔键必须精确等于子树最小键，删除最小键可能仍需向上更新。
• 如果要更改父指针、边界或其他共享元数据，“不会下溢”还不足以证明祖先不受影响。

因此，安全的本质是“不需要再修改已释放的祖先”，而不只是某个固定的半满判断。

六、乐观下降：先走轻路径，必要时重来

很多更新只修改一个叶子，不会改变树形。每次都从根持有写 Latch，会增加对热点上层节点的争用。

一种常见改进是：

1. 在内部节点上通过读保护向下定位。
2. 按协议为目标叶子取得写保护，并检查路由和页面状态仍然有效。
3. 如果叶子上的更新安全，直接完成。
4. 否则释放相关保护，从根按保守写路径重新开始。

不能把第 2 步理解为“普通读锁随时无条件升级为写锁”。如果升级需要释放原读 Latch，状态可能在间隙中变化，必须重新验证；如果多个读者都持有读 Latch 等待升级，也可能互相阻塞。

发现叶子需要分裂时，再持有叶子去向上申请祖先，可能与另一个“持有父节点、等待孩子”的线程形成循环等待。释放并重走规定顺序，是避免临时倒置加锁顺序的一种办法。

这是索引操作层面的重试，不等同于必然中止整个用户事务。

七、横向访问：兄弟节点也会带来死锁

统一自顶向下取得 Latch，有助于避免这类树路径上的顺序环路，但它不是所有数据库资源都不会死锁的证明。合并、兄弟借用、正反向扫描和其他元数据访问，还可能横向申请节点。

图 4：横向申请顺序不一致时的等待环。具体持有读还是写模式，需要满足互不兼容的条件才会阻塞。

例如线程 T1 持有 A 的写 Latch、申请 B；T2 持有 B 的写 Latch、申请 A，就形成循环等待。

常见解决思路包括：

• 对兄弟节点规定一致的申请顺序。
• 采用 try-lock / no-wait：拿不到就释放并按协议重试。
• 使用更适合并发分裂与遍历的结构，例如 B-link 思路。

“Latch 天生不支持死锁处理”说得太绝对。准确说法是：很多系统不希望为极短的 Latch 等待维护事务锁那样的复杂死锁检测，而是通过协议避免形成等待环。

重试扫描时，还要考虑已经返回的结果

如果扫描已经输出了部分条目，不能无记录地从头再输出一遍，否则可能重复。

实现可以保存稳定的续扫键，并重新定位；重复用户键可能还需要 RID 等次级顺序标识。但“记住最后一个 key”也不自动解决所有问题：并发删除、记录移动和事务快照仍需配套处理。

no-wait 能避免等待环，却可能造成反复失败或饥饿。退避、重试限制或回退策略需要系统设计支持，不能只说“让调度器介入”就算完成了协议。

八、为什么还会出现 B-link 树等变体？

基本 Latch crabbing 通过保护父子节点来协调并发访问。B-link 树是一类面向并发访问的 B+ 树变体，它允许父节点的路由信息暂时落后，再由查找过程修正位置。

它通常为各层节点增加两项信息：

• 右侧链接（right-link）：指向同一层的右邻节点。
• 上界信息（high key）：描述当前节点负责的键范围，帮助判断是否需要向右移动。

例如，一个节点分裂成左右两页，但父节点尚未加入新的分隔键。查找 35 时，线程可能仍按旧路由进入左页；发现目标超过左页上界后，就沿右链进入右页继续查找。如果连续发生分裂，则重复检查并向右移动。

这样，节点分裂与父节点更新可以分步完成，中间状态仍然支持正确查找，为减少并发协调提供了空间。右链也不只是用于叶子扫描，而是参与各层的路由修正。

不过，B-link 并不意味着完全无锁。页面内容、边界和链接仍需一致地更新，页面回收与崩溃恢复也需要配套协议。PostgreSQL 的 B-tree 借鉴了这一思路，同时保留页级保护和恢复机制，具体可参考其 B-tree 实现说明。

下一篇预告

第 06 篇继续扩展索引工具箱：Bloom filter 怎样快速排除不存在的键，跳表怎样利用多层链接查找，Trie 怎样利用字符串前缀？第 07 篇再从精确匹配走向全文与向量检索。补齐这些访问路径之后，第 08 篇开始进入排序、聚合与连接，把找到的数据加工成查询结果。

[上一篇：04]数据库内核手记 04：B+ 树（上）——结构、查找与插入
[下一篇：06]数据库内核手记 06：索引不止 B+ 树——过滤器、跳表与 Trie