上一篇中我们从根到叶查找再通过向上传播的分裂完成插入。现在继续回答三个问题删除后节点太空怎么办范围查询怎样跨越多个叶子一个线程正在修改结构另一个线程怎样安全经过这里本文沿用第 04 篇的约定键唯一内部节点最多 M 个孩子叶子最多 L 个条目非根节点采用经典最低占用规则。示例取M 4、L 4所以非根叶子至少有 2 个条目非根内部节点至少有 2 个孩子。分隔键 s 把左、右区间分开满足左最大键 s ≤ 右最小键。相等键走右边。真实系统的占用规则、版本管理和回收机制可能不同不能直接把本文示意当成任何数据库的源码协议。一、删除先删条目再判断结构是否需要调整先查找目标叶子确认条目存在再删除它。若不存在可以返回“未找到”若删除后仍满足结构约束通常无需借用或合并。1. 删除最小键就一定要改父节点吗不一定这取决于分隔键的语义。例如右叶子从[20,25,30]变为[25,30]父节点原来的分隔键 20 仍然可以作为这个子树的下界20 到 25 之间没有条目不会因此把已有键送错子树。如果实现要求父节点的分隔键始终精确等于右子树当前最小键那就必须更新它并考虑更新是否继续向上传播。后面讨论并发“安全节点”时也必须把这个约定算进去。2. 重分配向同一父节点下的相邻兄弟借用假设父节点的分隔键为 20L [10] R [20,25,30]L 低于最低占用R 有多余条目可以把 20 从 R 移到 LL [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 | P340 从父节点下降到左节点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 本身不必存在。基本步骤是从根定位可能包含起点的叶子。在叶子中做lower_bound(25)寻找第一个不小于 25 的条目若结果在页尾就沿后继继续寻找。逐个返回满足上界条件的条目。当前页耗尽时移动到下一叶子若下一个键大于 65 或没有后继则结束。迭代器状态可以包含当前页引用、页内位置和结束标记。是否支持反向遍历是额外设计选择可以维护前驱链接也可以采用其他重新定位方法不能说所有迭代器都必须双向。在并发系统中跨页移动不只是“读一下 next”。线程需要保证当前页和下一页的生命周期有效并按协议处理分裂、合并或删除。四、先分清三种保护Pin、Latch 与事务机制机制主要保护什么不保证什么Pin / 页引用正在使用的页不被淘汰或复用页内容不会同时变化Latch内存中节点结构的短期一致性整个事务始终看到同一逻辑快照事务 Lock、MVCC 等事务间的可见性、冲突与隔离指针和页布局可不经保护随意访问共享读 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会增加对热点上层节点的争用。一种常见改进是在内部节点上通过读保护向下定位。按协议为目标叶子取得写保护并检查路由和页面状态仍然有效。如果叶子上的更新安全直接完成。否则释放相关保护从根按保守写路径重新开始。不能把第 2 步理解为“普通读锁随时无条件升级为写锁”。如果升级需要释放原读 Latch状态可能在间隙中变化必须重新验证如果多个读者都持有读 Latch 等待升级也可能互相阻塞。发现叶子需要分裂时再持有叶子去向上申请祖先可能与另一个“持有父节点、等待孩子”的线程形成循环等待。释放并重走规定顺序是避免临时倒置加锁顺序的一种办法。这是索引操作层面的重试不等同于必然中止整个用户事务。七、横向访问兄弟节点也会带来死锁统一自顶向下取得 Latch有助于避免这类树路径上的顺序环路但它不是所有数据库资源都不会死锁的证明。合并、兄弟借用、正反向扫描和其他元数据访问还可能横向申请节点。图 4横向申请顺序不一致时的等待环。具体持有读还是写模式需要满足互不兼容的条件才会阻塞。例如线程 T1 持有 A 的写 Latch、申请 BT2 持有 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]数据库内核手记 04B 树上——结构、查找与插入[下一篇06]数据库内核手记 06索引不止 B 树——过滤器、跳表与 Trie
上一篇中我们从根到叶查找再通过向上传播的分裂完成插入。现在继续回答三个问题删除后节点太空怎么办范围查询怎样跨越多个叶子一个线程正在修改结构另一个线程怎样安全经过这里本文沿用第 04 篇的约定键唯一内部节点最多 M 个孩子叶子最多 L 个条目非根节点采用经典最低占用规则。示例取M 4、L 4所以非根叶子至少有 2 个条目非根内部节点至少有 2 个孩子。分隔键 s 把左、右区间分开满足左最大键 s ≤ 右最小键。相等键走右边。真实系统的占用规则、版本管理和回收机制可能不同不能直接把本文示意当成任何数据库的源码协议。一、删除先删条目再判断结构是否需要调整先查找目标叶子确认条目存在再删除它。若不存在可以返回“未找到”若删除后仍满足结构约束通常无需借用或合并。1. 删除最小键就一定要改父节点吗不一定这取决于分隔键的语义。例如右叶子从[20,25,30]变为[25,30]父节点原来的分隔键 20 仍然可以作为这个子树的下界20 到 25 之间没有条目不会因此把已有键送错子树。如果实现要求父节点的分隔键始终精确等于右子树当前最小键那就必须更新它并考虑更新是否继续向上传播。后面讨论并发“安全节点”时也必须把这个约定算进去。2. 重分配向同一父节点下的相邻兄弟借用假设父节点的分隔键为 20L [10] R [20,25,30]L 低于最低占用R 有多余条目可以把 20 从 R 移到 LL [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 | P340 从父节点下降到左节点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 本身不必存在。基本步骤是从根定位可能包含起点的叶子。在叶子中做lower_bound(25)寻找第一个不小于 25 的条目若结果在页尾就沿后继继续寻找。逐个返回满足上界条件的条目。当前页耗尽时移动到下一叶子若下一个键大于 65 或没有后继则结束。迭代器状态可以包含当前页引用、页内位置和结束标记。是否支持反向遍历是额外设计选择可以维护前驱链接也可以采用其他重新定位方法不能说所有迭代器都必须双向。在并发系统中跨页移动不只是“读一下 next”。线程需要保证当前页和下一页的生命周期有效并按协议处理分裂、合并或删除。四、先分清三种保护Pin、Latch 与事务机制机制主要保护什么不保证什么Pin / 页引用正在使用的页不被淘汰或复用页内容不会同时变化Latch内存中节点结构的短期一致性整个事务始终看到同一逻辑快照事务 Lock、MVCC 等事务间的可见性、冲突与隔离指针和页布局可不经保护随意访问共享读 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会增加对热点上层节点的争用。一种常见改进是在内部节点上通过读保护向下定位。按协议为目标叶子取得写保护并检查路由和页面状态仍然有效。如果叶子上的更新安全直接完成。否则释放相关保护从根按保守写路径重新开始。不能把第 2 步理解为“普通读锁随时无条件升级为写锁”。如果升级需要释放原读 Latch状态可能在间隙中变化必须重新验证如果多个读者都持有读 Latch 等待升级也可能互相阻塞。发现叶子需要分裂时再持有叶子去向上申请祖先可能与另一个“持有父节点、等待孩子”的线程形成循环等待。释放并重走规定顺序是避免临时倒置加锁顺序的一种办法。这是索引操作层面的重试不等同于必然中止整个用户事务。七、横向访问兄弟节点也会带来死锁统一自顶向下取得 Latch有助于避免这类树路径上的顺序环路但它不是所有数据库资源都不会死锁的证明。合并、兄弟借用、正反向扫描和其他元数据访问还可能横向申请节点。图 4横向申请顺序不一致时的等待环。具体持有读还是写模式需要满足互不兼容的条件才会阻塞。例如线程 T1 持有 A 的写 Latch、申请 BT2 持有 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]数据库内核手记 04B 树上——结构、查找与插入[下一篇06]数据库内核手记 06索引不止 B 树——过滤器、跳表与 Trie
