持久化数据结构在数据库中的应用

数据库要解决的最核心矛盾之一：读和写要同时发生。一个事务在写表 A 的同时，另一个事务在读表 A。怎么保证读到的是一致的快照，而不是写了一半的中间状态？

大多数数据库的答案是 MVCC (Multi-Version Concurrency Control)。但 MVCC 不是一种算法——它是一种策略。具体实现千差万别：PostgreSQL 用 heap tuple versioning + vacuum，MySQL InnoDB 用 undo log + read view，SQLite 用 WAL。

但有另一条路：让数据结构本身就是持久化的。所谓”持久化数据结构”(persistent data structure)，不是指”存到磁盘”，而是指”修改不破坏旧版本”。你每次写入不是在原地改，而是创建一个新版本，旧版本完好无损地保留着。

这意味着读操作永远不需要锁。因为它读的版本不会被任何人修改——它是不可变的。

一、三种路径

持久化的核心操作是 Copy-on-Write (COW)。但 COW 的粒度和方式有很多选择：

数据库	COW 粒度	写放大	空间回收	读性能
CouchDB	整个 B-tree 路径	高	compaction	极好
LMDB	B+ tree page	中	旧页面复用	极好
DuckDB	column chunk	低	版本链回收	极好

路径一：CouchDB — Append-Only B-tree

CouchDB 的存储引擎是最纯粹的持久化 B-tree。所有写入都是追加到文件末尾。

当你修改一个叶子节点时： 1. 写一个新的叶子节点到文件末尾 2. 写一个新的父节点（指向新叶子），也追加到末尾 3. 一直到根节点，写一个新的根 4. 更新 header 指向新根

旧的根、旧的路径上的所有节点全部保留。一个读事务只要记住它开始时的根节点，就能看到一个完整的快照。

写入前:  写入后:
  [Root v1]  [Root v1]  [Root v2]
  /  \  /  \  /  \
  [A]  [B]  [A]  [B]  [A]  [B']
  |
  (B 的新版本追加在文件末尾)

优势： - 读写完全不冲突。写入是追加，读取在旧根上，物理上不交叉。 - 崩溃恢复极简单。如果写到一半断电，旧根还在，数据一致。

劣势： - 写放大。改一个叶子节点，整条路径都要重写。B-tree 深度是 log(N)，一次写入涉及 log(N) 个 page。 - 空间膨胀。旧版本永远不删除（直到 compaction），文件会持续增长。CouchDB 的 compaction 是复制整个数据库文件——这在大数据量时很痛苦。

路径二：LMDB — COW B+ tree 原地分支

Howard Chu 设计的 LMDB 走了一条更精巧的路。它也是 COW B+ tree，但不是 append-only。

LMDB 用两个根指针交替指向最新的 B+ tree。写事务创建新版本时，修改的 page 写到新位置（COW），旧 page 进入 free list。下一次写事务可以复用 free list 里的 page。

Meta Page 0 -> Root A (版本 N)
Meta Page 1 -> Root B (版本 N+1)

写事务 N+2:
  COW 修改的 page -> 写到 free list 里的旧 page 位置
  更新 Meta Page 0 -> Root C (版本 N+2)
  版本 N 的旧 page 进入 free list

两个 meta page 交替更新保证原子性。如果写到一半崩溃，回退到另一个 meta page 指向的版本。

LMDB 的关键约束：单写者。任何时刻只有一个写事务。这大幅简化了 COW 的实现——不需要处理两个写事务同时 COW 同一个 page 的情况。

但读事务可以并发。每个读事务 pin 住它开始时的根，沿旧版本的 page 读取。写事务不会修改旧 page（它们是 COW 的），所以读写完全不冲突。

这就是 LMDB “读不加锁”的秘密：不是用了什么复杂的无锁算法，而是数据结构本身就是不可变的。

优势： - 读性能极好（mmap 直接读 page，零拷贝，零分配） - 数据文件不会无限增长（free list 复用空间） - 崩溃恢复零开销（不需要 WAL、不需要 replay）

劣势： - 单写者。写吞吐量受限。 - 写放大仍然存在（COW 整条路径），虽然比 CouchDB 好（旧 page 可以复用）

路径三：DuckDB — 列存 + 版本链

DuckDB 用的不是 B-tree，而是列存结构。但持久化的思路类似。

DuckDB 的存储单元是 row group（约 122K 行）。每个 row group 包含多个 column segment，每个 segment 是连续的列数据。

修改时不重写整个 segment，而是在行级别维护版本链：

Column Segment (不可变):
  row 0: value_a
  row 1: value_b  -> [undo buffer: old_value_b, txn_id=100]
  row 2: value_c

事务 100 修改了 row 1。新值写在 segment 里，
旧值保存在 undo buffer。
事务 100 提交前的读者看 undo buffer 里的旧值。
事务 100 提交后的读者看 segment 里的新值。

这比 B-tree COW 的写放大低得多。改一行只涉及那一行的 undo buffer，不需要重写整个 page 或整条路径。

优势： - 写放大最低（行级 COW） - 列存的分析查询性能好 - 并发读写都支持

劣势： - 版本链长了之后，旧版本的回收（garbage collection）是复杂问题 - 不像 LMDB 那样崩溃自恢复——需要 WAL

二、核心权衡：写放大 vs 空间回收 vs 实现复杂度

权衡	CouchDB	LMDB	DuckDB
写放大	O(log N) pages	O(log N) pages	O(1) row
空间回收	compaction (重写整个文件)	free list (增量)	GC (增量)
并发写	单写者	单写者	多写者 (行锁)
崩溃恢复	不需要	不需要	需要 WAL
实现复杂度	低	中	高

选哪种取决于你的场景： - 读远多于写，数据量不大 -> LMDB。zero-copy 读取，崩溃自恢复，单写者够用。 - 分析型查询为主 -> DuckDB 风格的列存版本链。 - 需要完整历史版本 -> CouchDB 风格的 append-only。Git 本质上也是这个模型。

三、和传统 MVCC 的对比

PostgreSQL 的 MVCC 不是持久化数据结构。它是在 heap tuple 上标记 xmin/xmax（创建和删除的事务 ID），通过 visibility check 判断每行对当前事务是否可见。

维度	持久化数据结构	PostgreSQL MVCC
旧版本存储	数据结构自带	heap + undo/标记
读加锁	不需要	不需要 (snapshot isolation)
写加锁	不需要 (单写者) 或行锁	行锁
空间回收	compaction/free list/GC	VACUUM
死元组问题	没有 (COW 不产生死元组)	有 (VACUUM 不及时会膨胀)
索引膨胀	没有 (COW 重建路径)	有 (HOT 缓解但不完全解决)

PostgreSQL 的 VACUUM 问题是众所周知的运维痛点。LMDB 和 CouchDB 没有这个问题，因为它们的旧版本是数据结构的一部分，不是”需要清理的垃圾”。

当然，这个优势的代价是写放大。PostgreSQL 的 heap update 只改一个 tuple（8KB page 的一部分），LMDB 的 COW 改整条 B+ tree 路径。

结语

持久化数据结构是一个优雅的思路：与其在可变数据上加锁、加版本号、加 undo log，不如让数据天然不可变，修改只创建新版本。

这个思路在数据库以外的地方也出现过：Git 的对象模型是持久化 DAG，React 的虚拟 DOM diff 是持久化树的思想，Clojure 的基础数据结构全部是持久化的（通过 structural sharing 降低拷贝开销）。

持久化不是银弹。它用写放大和空间开销换取了读的自由度和崩溃恢复的简单性。在读多写少、数据一致性要求高的场景下，它是一个被严重低估的设计选择。

延伸阅读：

SQLite 是怎么做到”十亿行每秒”的 – WAL 模式：另一种解决读写冲突的方式
LSM-Tree: WAL + MemTable – LSM-Tree 的 append-only 写入和 compaction

参考资料：

Anderson, J.C. et al. (2010). CouchDB: The Definitive Guide. O’Reilly. – CouchDB 的 append-only B-tree
LMDB 技术文档 – Howard Chu 的设计说明
Raasveldt, M. & Muhleisen, H. (2019). DuckDB: An Embeddable Analytical Database. SIGMOD. – DuckDB 的存储架构
Driscoll, J.R. et al. (1989). Making Data Structures Persistent. JCSS. – 持久化数据结构的原始论文

目录