1. 背景与核心问题
MVCC（Multi-Version Concurrency Control，多版本并发控制）的核心目标是：
让不同事务在并发访问同一条逻辑记录时，能够看到对自己正确且一致的版本。
从存储引擎实现角度看，MVCC 最关键的是回答四个问题：
- 当前版本存放在哪里；
- 旧版本存放在哪里；
- 查询时如何找到对当前事务可见的版本；
- 旧版本如何被清理与回收。
不同的数据结构与存储引擎，本质上就是对这四个问题给出了不同答案。
2. B+Tree 与 MVCC
2.1 总体思路
在传统基于 B+Tree 的事务型存储引擎中，最典型的设计是：
B+Tree 负责定位记录，MVCC 负责决定当前事务应该看到哪个版本。
其核心特点是：
- B+Tree 中主要维护当前版本
- 旧版本不直接存放在 B+Tree 中
- 旧版本通过 undo/version chain 保存
- 查询时先找到最新版本，不可见时再向历史版本回退
这是一种典型的“当前态主存 + 历史版本外置”方案。
2.2 数据组织方式
这种方案通常可以抽象为如下结构：
B+Tree 叶子节点
-> 当前记录
-> 版本元数据（如事务 ID、删除标记等）
-> 指向旧版本的指针
-> undo record 1
-> undo record 2
-> undo record 3
在这种结构下：
- B+Tree 叶子页中存放的是当前记录；
- 当前记录上带有一些隐藏的版本信息；
- 当前记录通过一个指针与旧版本链连接；
- 历史版本通常位于独立的 undo / version store 区域中。
2.3 查询流程
B+Tree 与 MVCC 的查询配合过程大致如下：
第一步：通过 B+Tree 找到当前版本
对于主键点查、范围扫描、二级索引检索等，B+Tree 先定位出当前记录。
第二步：检查当前版本是否可见
系统根据当前记录携带的版本信息，与事务的快照规则进行比较，判断该版本是否对当前事务可见。
第三步：必要时沿版本链向后回退
如果当前版本不可见，则根据记录中的指针找到 undo 中的上一个版本，在内存中恢复旧版本，再继续做可见性判断。
这个过程会持续进行，直到：
- 找到第一个可见版本；
- 或者版本链结束。
2.4 这种设计的优点
1. 当前版本访问快
由于 B+Tree 中主要只维护当前版本，因此：
- 索引结构更紧凑；
- 页利用率更高；
- 缓存命中率更好；
- 范围扫描性能更稳定。
2. 多版本成本按需支付
并不是所有查询都要访问历史版本。只有在快照读或旧事务读取时，才需要沿版本链回退。
3. 很适合传统 OLTP
大多数 OLTP 系统读的都是最新已提交值，因此把主索引优化为“面向当前态”非常合理。
2.5 这种设计的代价
1. 历史版本读取可能较慢
如果某条记录被频繁更新，而又存在较老的事务快照，那么读取旧版本时可能需要回退很多步。
2. 需要额外的 purge / GC
历史版本不能永久存在，需要在确认不再被任何活跃事务访问后才能清理。
3. 长事务会阻碍版本清理
只要旧快照仍然存活，对应的旧版本就不能回收，容易导致 undo 膨胀。
2.6 适用场景
B+Tree + undo/version chain 的方案更适合：
- 传统关系型 OLTP；
- 大量点查和范围查询；
- 二级索引访问频繁；
- 读请求多数面向当前值；
- 希望主索引保持紧凑的系统。
2.7 小结
B+Tree 与 MVCC 的典型结合方式是：主索引维护当前版本，历史版本外置到 undo/version chain，查询时先查当前版本，不可见再回退。
3. LSM-Tree 与 MVCC
3.1 总体思路
对于基于 LSM-Tree 的存储系统，MVCC 的常见实现方式与 B+Tree 明显不同。
这类系统通常不是：
- 主存只保存最新版本；
- 历史版本放在单独的 undo 链中；
而更常见的是：
把多个版本直接存入底层 LSM/KV 存储中，版本本身就是存储结构的一部分。
也就是说，LSM 路线更接近：
- 同一个逻辑 key 对应多个物理版本；
- 不同版本通过时间戳或版本号区分；
- 查询时直接从多个版本中选择一个可见版本。
3.2 为什么 LSM 天然适合多版本
LSM-Tree 的基本特点是：
- 写入偏追加；
- 不强调原地更新；
- 倾向于顺序写与后台合并；
- 通过 compaction 整理数据。
而 MVCC 恰好需要“保留旧版本、写入新版本”。 因此对于 LSM 来说，一个非常自然的做法就是：
- 不覆盖旧值；
- 直接写入一个新版本；
- 旧版本先保留；
- 后续由 GC / compaction 清理。
所以在 LSM 中，“多版本直接进入主存储层”是非常顺手的设计。
3.3 数据组织方式
可以将 LSM 中的多版本结构抽象为：
k@12 -> value_v12
k@9 -> value_v9
k@5 -> value_v5
其中：
k表示逻辑 key；@12、@9、@5表示不同版本时间戳。
这样，同一个 key 的多个版本会在排序上彼此相邻或便于遍历。
3.4 查询流程
LSM 中的 MVCC 查询流程通常可以概括为：
第一步：定位到该 key 的版本集合
通过 LSM 的查找与迭代机制，找到同一个 user key 的多个版本。
第二步：根据读时间戳选择可见版本
从这些版本中选出满足：
- 版本时间戳不大于当前读时间；
- 且满足事务快照规则；
的那个版本。
第三步：返回该版本
因此，LSM 中读取历史版本通常不是“回退构造”，而是“从已有多个版本中选一个”。
3.5 这种设计的优点
1. 版本管理天然适配分布式事务
如果系统本身就是基于时间戳推进事务，那么多版本直接做进 KV 存储层非常自然。
2. 历史读与时间旅行查询更方便
由于历史版本本来就存在主存储中，因此：
- stale read；
- 历史快照读；
- CDC；
- time-travel query；
都会更自然。
3. 更新路径简单
更新不需要像页式引擎那样维护外部 undo 回退链，而是直接写新版本即可。
3.6 这种设计的代价
1. 多版本扫描会带来读放大
如果某个 key 版本很多，读取时可能需要检查多个历史版本。
2. 更依赖 GC 与 compaction
旧版本长期积累会带来明显的空间与查询代价，因此垃圾回收与压缩合并非常关键。
3. 热点 key 更容易产生 MVCC amplification
高频更新的单行或单 key 会积累大量历史版本，影响读取效率。
3.7 适用场景
LSM + 多版本的方案更适合：
- 分布式 KV / NewSQL；
- 基于时间戳的事务系统；
- stale read / snapshot read 使用频繁；
- 追加写多、更新频繁；
- 系统能接受依赖 compaction 与版本 GC 的架构。
3.8 小结
LSM-Tree 与 MVCC 的典型结合方式是：多个版本直接存入 LSM/KV，查询时按时间戳选择可见版本，而不是依赖外部 undo 链回退。
4. Bw-Tree 与 MVCC
4.1 一个容易混淆的前提
Bw-Tree 中有一个非常重要的概念：delta chain。
但必须明确：
Bw-Tree 的 delta chain 通常不是 MVCC 版本链。
Bw-Tree 中的 delta chain 主要用于描述索引节点本身的增量更新，例如：
- insert；
- delete；
- split；
- merge；
- 节点状态变更。
它体现的是：
- 索引节点结构的演化过程
而不是：
- 记录内容版本的演化过程
因此，Bw-Tree 中“节点 delta 链”和“事务版本链”是两个不同层面的概念。
4.2 Bw-Tree 与 MVCC 的自然分工
Bw-Tree 更适合作为一种：
- 高并发；
- latch-free；
- 节点不原地更新；
- 基于 mapping table 与 CAS 的索引结构。
而 MVCC 更关注的是：
- 记录级别的多版本；
- 事务时间戳可见性；
- 旧版本回收。
所以 Bw-Tree 与 MVCC 最自然的组合方式通常是：
Bw-Tree 负责索引，记录层负责多版本。
换句话说：
- Bw-Tree 叶子节点中通常存放的是记录指针；
- 记录本身是多版本对象；
- 查询时先通过 Bw-Tree 找到记录，再根据版本时间戳选择可见版本。
4.3 数据组织方式
可以抽象为如下结构：
Bw-Tree
-> leaf item
-> pointer to versioned record
-> version 1 [begin, end)
-> version 2 [begin, end)
-> version 3 [begin, end)
其中：
begin和end表示该版本的有效时间区间；- 一个读事务只需检查其读时间戳是否落入该区间。
判断规则通常可以抽象为：
begin <= read_ts < end
4.4 查询流程
Bw-Tree 与 MVCC 结合后的查询过程通常为：
第一步：通过 Bw-Tree 定位到候选记录
Bw-Tree 提供有序索引能力与高并发更新能力。
第二步：根据记录版本元数据判断可见性
记录层维护多个版本，每个版本带有 begin/end timestamp 或等价的版本信息。
第三步：返回对当前事务可见的版本
查询不一定需要像 undo 链那样逐层“回退恢复”，而是直接在记录层的多版本中判断可见性。
4.5 这种设计的优点
1. 索引层与事务层职责清晰
- Bw-Tree 负责高并发索引管理；
- 记录层负责版本管理与可见性控制。
2. 适合内存优化设计
Bw-Tree 非常强调 latch-free / lock-free 风格，与内存优化引擎结合自然。
3. 避免将 MVCC 强行塞入索引节点更新链
索引的节点增量更新与记录版本历史分层管理，结构更加清晰。
4.6 这种设计的代价
1. 系统实现复杂度较高
需要同时管理：
- 索引层的 delta chain；
- 记录层的版本对象；
- 版本 GC；
- 节点 consolidation。
2. 更适合特定体系结构
Bw-Tree 并不是传统磁盘页式 OLTP 的主流选择，它更多出现在特定的高并发内存优化场景中。
4.7 工业界代表
Bw-Tree 与 MVCC 结合的典型工业实现是：
- Microsoft SQL Server In-Memory OLTP（Hekaton）
其设计特点可以总结为：
- Bw-Tree 用作范围索引；
- 记录层维护多版本；
- 更新创建新版本；
- 可见性通过 begin/end timestamp 判断；
- 旧版本由后台 GC 清理。
因此，Hekaton 更接近：
Bw-Tree + row-version MVCC
而不是：
Bw-Tree + undo 链
4.8 小结
Bw-Tree 与 MVCC 的典型结合方式是：Bw-Tree 只做高并发索引，记录层负责多版本，查询时先通过索引找到记录，再根据版本时间戳判断可见性。
5. 三种路线的本质对比
5.1 从“旧版本存放位置”看
B+Tree
- 当前版本在主索引 / 主记录中；
- 旧版本在 undo / version chain 中。
LSM-Tree
- 当前版本与旧版本都直接存在 LSM/KV 主存储中；
- 版本通过时间戳区分。
Bw-Tree
- Bw-Tree 主要负责索引；
- 旧版本保存在记录层的多版本对象中。
5.2 从“读取旧版本方式”看
B+Tree
- 先定位当前版本；
- 当前版本不可见时，沿 undo 链回退。
LSM-Tree
- 直接在多个已存储版本中，按时间戳选一个可见版本。
Bw-Tree
- 先通过索引找到记录；
- 再在记录层依据 begin/end timestamp 选择版本。
5.3 从“设计哲学”看
B+Tree
更像是：
当前态主存 + 历史外置
LSM-Tree
更像是：
历史版本本来就是存储层的一部分
Bw-Tree
更像是：
索引层和版本层分离，索引负责定位，版本层负责 MVCC
6. 应用场景对比
6.1 B+Tree + undo/version chain
更适合：
- 传统关系型 OLTP；
- 高效点查、范围扫；
- 二级索引密集使用；
- 大量查询读取当前值。
6.2 LSM + 多版本 key
更适合：
- 分布式 KV / NewSQL；
- 时间戳驱动的事务模型；
- 历史读、stale read、CDC 需求较多；
- 高写入吞吐与追加写友好场景。
6.3 Bw-Tree + row-version
更适合：
- 内存优化存储引擎；
- 高并发索引更新；
- latch-free / lock-free 风格实现；
- 索引与事务版本管理分层的体系。
7. 最终总结
从本质上看，B+Tree、LSM-Tree、Bw-Tree 与 MVCC 的结合方式可以概括为：
B+Tree
主索引维护当前版本，旧版本外置，查询时先查当前版本，不可见再回退。
LSM-Tree
多个版本直接进入存储层，查询时按时间戳选择一个可见版本。
Bw-Tree
Bw-Tree 负责高并发索引，记录层维护多版本，查询时通过索引定位后再做版本可见性判断。
如果只记一个总判断，可以记为：
B+Tree 强调“当前态索引 + 历史外置”，LSM 强调“多版本就是主存储的一部分”，Bw-Tree 强调“索引层与版本层分离”。
8. 延伸思考
理解各类索引结构与 MVCC 的结合方式，不仅仅是为了回答"旧版本存在哪里"这一个问题，而是帮助我们建立对存储引擎整体设计的直觉：
- 写入路径决定了版本的存放形式——原地更新的 B+Tree 需要外置 undo，追加写的 LSM 可以直接将多版本落入主存储；
- 读取路径决定了可见性判断的代价——undo 链的逐步回退 vs. 多版本的一次定位选择；
- GC 策略决定了旧版本何时能被安全清理——长事务与 GC 之间的张力在三种方案中都必须面对。
不同的工程取舍背后，其实都是对同一组核心问题的不同回答。在设计或评估一个存储引擎时，从这四个维度出发往往能很快抓住其 MVCC 实现的本质。