【WiredTiger 内核】B-Tree 与 update chain：未提交更新只挂链

第 4 篇 说明 dirty eviction 必须 reconcile。Reconcile 消化的对象，是叶页上的 insert list 与 update chain。Architecture Guide B-Trees 与 Cache 把写路径说成：下行到 leaf → 新键进 WT_INSERT → 已有键的修改进 WT_UPDATE 链表；读者按时间戳/事务可见性看到链上某一环。

本文钉住 row-store 内存形态与「未提交只挂链」不变量；磁盘页格式与分裂细节见第 6、12 篇；可见性规则见第 7 篇。

本文是「WiredTiger 内核」系列第 5 篇（共 17 篇）。→ 系列目录

先修：第 3–4 篇。续读：第 6 篇 Reconciliation；第 08 篇。

版本锚定：Architecture Guide Version 12.0.0 / develop B-Trees、Cache；源码 mongodb-8.0 的 src/include/btmem.h、btree.h、src/btree/。MongoDB 默认路径为 row-store（WT_BTREE_ROW）；列存仅作边界。

一、WT_BTREE：表即 B-Tree

Guide B-Trees：

• 表用 B-Tree 表示（WT_BTREE in btree.h）；节点是 page。
• Internal 页只存键与子页引用；leaf 存键值。
• 记录按键有序；达到配置上限则 split，树增高/变宽。
• 页同时有 in-memory 与 on-disk 表示；本章聚焦 btmem.h 中的内存形态。

Data handle 若指向 B-Tree，则内含 WT_BTREE*：内存中的 KV 缓存视图、读写文件的函数、类型、根页 WT_REF，以及维护树形结构的元信息。访问方法以 row-store 最常见；另有变长列存 WT_BTREE_COL_VAR 等。

大树无法整树进内存：每个节点经 WT_REF 表示「已加载 / 未加载」；已加载时 WT_REF 持有有效 WT_PAGE*（与第 3 篇一致）。

二、叶页上的两类修改结构

对 row-store leaf（WT_ROW 数组承载「读盘时已在页上的 KV」）：

Guide B-Trees：新更新链进 update list 后，同一条目可能保留旧值或删除标记；读者能否看见某一环，取决于所用时间戳（及事务快照）。

flowchart TB
  leaf["Row-store leaf WT_PAGE"]
  leaf --> onpage["WT_ROW array<br/>keys from disk image"]
  leaf --> mod["WT_PAGE_MODIFY"]
  mod --> ins["WT_INSERT skiplists"]
  mod --> upd["WT_UPDATE chains"]
  onpage --> upd

Cache 补充：几乎所有在这些结构上的操作设计为 lock-free，以支撑并发。

未提交更新只挂链

与 第 08 篇 一致：

• 更新首先出现在 cache 的 update chain 上。
• 未提交更新不进入用户表的 on-disk 镜像。
• 把「最新已提交值写进用户表页、更旧已提交值写入 History Store」的步骤，发生在 reconciliation（常由 eviction 或 checkpoint 触发）。

这不是口头约定，而是 History Store 章与 dirty eviction 路径的共同前提：reconcile 检查 update chain，选出最新已提交更新作为 on-disk 值。

三、读路径直觉（为第 7–8 篇铺垫）

对某一键的可见值查找顺序（History Store）：

1. 在内存 update chain 上找对当前事务可见的更新；
2. 若无，看 on-disk 页上的值是否可见；
3. 若仍不可见，再查 History Store。

因此「主表页上只有最新已提交值」并不否定 MVCC：旧快照要么还挂在尚未 reconcile 的链上，要么已进 HS。Eviction 清掉用户页之后，旧读者依赖的是第 2–3 步，而不是「页还在 cache」。

四、Truncate（边界）

Guide B-Trees 用较长篇幅讨论 range truncate：用 start/stop cursor（search-near 定位）按页遍历，能整页标记删除则 fast-truncate，否则逐键 tombstone（slow-truncate）。文档对 logged tree 上与并发插入的交互仍保留 hedge；本系列不展开 truncate 正确性全集，只提醒：truncate 在实现上仍走更新/可见性逻辑，且与 logging 回放有已知边界——需要时直接读 Guide 该节与 Truncation 专页。

五、学术锚点与工程间隙

工程间隙： Wiki Reconciliation overview（2015 起稿）描述的内存布局字段名与今日 btmem.h 别名可能不完全一致；以 mongodb-8.0 头文件与 Architecture Guide 为准。本篇无插入微基准实测。

开放问题： 文档模型下一次小字段更新是否在链上保留整份旧 BSON——影响 HS 体积（第 08 篇开放问题 1）；本篇只钉「链上可以有多版本」，不估 BSON 大小分布。

六、收束

1. MongoDB 默认路径上，用户表是 row-store B-Tree；页经 WT_REF 按需进 cache。
2. 新键走 WT_INSERT，已有键走 WT_UPDATE 链；未提交更新只挂链，不进磁盘镜像。
3. 下一篇 Reconciliation：遍历链与 insert list，生成 on-disk image，并在契约上对接 History Store。

参考资料

规范 / 官方文档

• WiredTiger Architecture Guide, B-Trees：https://source.wiredtiger.com/develop/arch-btree.html
• WiredTiger Architecture Guide, Cache
• WiredTiger Architecture Guide, History Store

源码

• mongodb-8.0：src/include/btmem.h、btree.h；src/btree/bt_cursor.c、bt_page.c、bt_read.c 等

站内

• 第 3 篇 · Cache、第 4 篇 · Eviction
• 第 08 篇 · History Store
• 系列索引

上一篇：Eviction
下一篇：Reconciliation