“B link树将这里的并发结构边界具体化：在每层增加排他上界与右链，先初始化新右页，再整体发布旧页的左半与链接，允许父页暂时落后。读者拿着旧父指针仍能向右修正，但一致页图像、页生命周期和持久…”
形式陈述
父指针可以暂时落后，定位不能凭空断掉
B+树把记录放在叶页、分隔键放在内部页。顺序执行时，页分裂和父页修复可以视为一个完整操作；并发读者却可能先从父页拿到旧子指针，等读取子页时，目标记录已经搬到新页。本页只解决这种分裂期间的单键查找，不重写普通B+树插删。
对每一层的页增加右邻指针
页内键与指针构成一个一致图像。模型假定读取返回整个旧图像或整个新图像，不会把旧键数组、新上界和缺失右链拼在一起；页ID在读者可能引用期间不回收复用。只允许插入和向右分裂，不允许删除、合并、向左搬记录或进程崩溃。本教学任务固定树高，并假定根页有足够容量容纳本次父页修复；不包含根分裂、增高或根指针切换。主轨迹为一个写者和任意交错的读者；原论文的多写者锁协议比这个受限任务更广。[1, §§2、6.3]
查找在每层都先检查上界
从根页出发，对读到的每个页图像执行：
- 若
- 否则，若是内部页，按本图像的分隔区间取子指针，下降一层
- 否则，在叶图像内比较完整键，返回对应记录或缺失
右移不能只发生在叶层；内部页也可能刚刚分裂。父页过时所造成的位置偏差必须是“正确位置在当前位置或其右边”，右链才有能力修正。随便拿一个位于目标右边的页当起点，并没有向左补救规则。[1, §§3.3、4]
分裂的三次发布各做什么
设旧页A负责
- 初始化不可达的B：B保存右组，
- 发布A的新完整图像：A保存左组，
- 修复父页：增加边界S和指向B的子指针；若父页也需分裂，使用相同的右链原则继续处理
第一步尚未改变可达索引；第二步同时缩小A的范围并提供通往新范围的路；第三步减少以后多走的右链。不能先缩小A再单独补right，也不能让A指向尚未准备好的B。本文把第二步作为这次插入变得可见的发布点；此前的读者允许看到插入前状态。[1, §5.2、§6.2引理2]
直觉
旧地址只需成为安全的左侧入口
想找40时，父页可能还说“去A”。如果A已经把30以上的键交给B，它同时告诉读者“从30起请向右走”。读者不需要立刻回根重试，也不必等父页修好。
这不是允许任意陈旧指针。它能工作，是因为分裂只把原区间拆成左、右两段，旧页仍留在左边，新段可沿明确链接找到。若记录被搬回左边、旧页被复用于别的对象，原证明条件就消失了。
例子与边界
读者拿到旧父指针以后发生分裂
初态父页分隔50，左叶A有[10,20,30,40]且上界50，右叶C有[50,60]且上界无穷。每叶容量4。写者插入35后选择边界30，得到A=[10,20]，B=[30,35,40]，C不变。
| 事件 | 父页路由 | A的图像 | B的状态 | 查40的读者 |
|---|---|---|---|---|
| 读父页 | 50分隔A/C | [10,20,30,40]，H50，right C | 未分配 | 记住A |
| 先准备B | 仍旧 | 仍旧 | [30,35,40]，H50，right C；不可达 | 尚未读A |
| 发布A | 仍旧 | [10,20]，H30，right B | 完整且可达 | 读A，40≥30，向右 |
| 读B | 仍旧 | 新图像 | 完整 | 40<50，在B找到40 |
| 补父页 | 30、50分隔A/B/C | 新图像 | 完整 | 本次查找已可结束 |
根、A、B共读3个页图像；父页修复后新查40读根、B共2个。内部页上的30只是导航边界，叶B才保存实际记录30。
若查询正好是30，也必须向右；排他上界使30不属于A。若查29，在A内未找到便可返回缺失，不应因为“B存在”就无条件遍历右侧所有叶。若读者在分裂前已经复制了A的完整旧图像，它仍能从自己的图像找到40；对尚未插入的35返回缺失，则对应插入发布前的一次合法观察。
两种错误发布会漏掉原有键
错误一：先把A数组截成[10,20]，上界仍50、right仍C。拿着旧父指针的查40进入A，认为40应在本页，却找不到，于是错误返回缺失。这里40在操作开始之前就存在，不能用“并发插入尚未完成”解释。
错误二：一次性把A改成H30、right B，却让B尚未初始化。查40会走向空页或未发布内容。增加右链本身不够，右链目标就绪必须先于其可达发布。
页读取保护与持久化不是同一件事
真实缓冲池可用短期页保护取得一致图像，并用pin或等价生命周期机制避免正在访问的帧被替换。这里把原子页读取作为接口前提，不宣称任意CPU逐字段读取都是原子的，也不把原论文存储模型中的无读锁搜索直接等同现代内存模型里的无同步读取。
本页发布顺序描述运行中可达性。它不证明掉电后B的内容已持久、A的页写不撕裂或父页可重做；这还要由WAL等恢复协议承担。即使B先在内存里初始化，磁盘也可能先看到别的写入。
推论与应用
为什么陈旧父页不会把既有键丢在身后
在只有向右分裂的模型中，旧页中的某个既有键要么仍留在该页，要么进入新右页。发布新的左页时，新右页已经完整就绪；以后若右页再分裂，同样会留下下一条右链。因此从旧父指针进入时，既有键始终在当前页或沿同层右链可达的某页中。
只在
安全修正还要计入实际工作
设主路径下降
若相关分裂总数有限、各页读取最终完成，有限右链会让查找结束。若写者持续在目标方向分裂，则还需额外进展论证，不能仅凭右链无环保证固定时间内完成。单键查找正确也不自动提供范围扫描的事务快照；范围查询仍须规定并发插入可见性与版本规则。
参考资料
[1] Philip L. Lehman、S. Bing Yao，Efficient Locking for Concurrent Operations on B-Trees，ACM TODS 6(4)，1981，pp.650–670。§2在p.651给存储接口；§3.3在p.657定义各层right link；§4在p.659给查找；§5.2在p.662先写B后改A；§6.2引理2在p.664解释可达发布，§6.3在p.665明示get/put不可分割。本文用排他上界和单写者轨迹重述，未搬用其全部多写者算法。