piece table：原始文本从不被改

gap buffer 押注「编辑集中在一处」。piece table 换了个押注方向：既然搬移代价来自「改写既有内容」，那就一个字符也不改写。

1 · 只读缓冲与只增缓冲

打开一个 1 MB 的文件，piece table 的初始状态是：original 一个 1 MB 的字符串，added 空串，piece 列表里一个 piece，覆盖 original 的全部。构造代价 1.6 毫秒，其中大部分是数一遍换行。

关键是这两个缓冲的写入模式：original 从打开到关闭一个字符也不变，added 只在尾部追加。已经写下去的字符永远不动。文档的全部变化都体现在 piece 列表上，而 piece 只是三个整数。

2 · 一次插入产生的三段

在文档偏移 $p$ 处插入一段文本 $t$：先把 $t$ 追加到 added 尾部，记下它的起始偏移；然后在 piece 列表里找到覆盖 $p$ 的那个 piece，按 $p$ 把它拆成两段，中间插入一个指向 added 那一段的新 piece。原来的一个 piece 变成三个。

若 $p$ 恰好落在两个 piece 的边界上，则不需要拆，直接插入一个 piece，一个变两个。

删除偏移 $[p, p+n)$ 的内容：在 $p$ 与 $p+n$ 两处各保证一个 piece 边界（必要时各拆一次），把中间那些 piece 从列表里摘掉。被摘掉的 piece 指向的字符仍然留在缓冲里，只是不再被任何 piece 引用。

这带来一个直接后果：删除的代价与删除长度无关。删掉一个字符和删掉半篇文档，都是「拆两次、摘一段列表」。

3 · 三条不变量

piece table 的正确性靠三条不变量撑着，本系列的测试逐条锁死。

第一条：所有 piece 的长度之和等于文档长度。测试对每一步编辑后的状态都验一次这个等式。

第二条：original 缓冲逐字符不变。测试在编辑前拍一份快照，跑完 800 次随机编辑后与快照整串比对。

第三条：added 缓冲只增不改。测试记下每一步之后的 added 内容，跑完验证每一份都是终态的前缀，且终态长度恰好等于所有插入文本的长度之和。

第三条还顺带说明了一件事：删除操作从不写 added。这正是撤销廉价的来源。要回到某个历史版本，只需要换回当时那份 piece 列表，缓冲原封不动。500 次编辑的全部中间状态共 165183 条 piece 记录，而同样 500 份整串快照是 5193000 个字符，差 31 倍。

4 · 碎片化

代价在别处。每次插入至少新建一个 piece，落在 piece 内部时新建三个；每次删除也可能拆出两个。piece 数只增不减地跟着编辑次数走，这就是 碎片化。

10 KB 文档跑 2000 次随机编辑，实测曲线是一条几乎笔直的线：

终态文档长 11421 个字符，2982 个 piece，平均每个 piece 只剩 3.8 个字符。累计新建过 3665 个 piece，其中 683 个在后续删除中被摘掉。

一个常见的缓解手段是追加合并：若插入位置恰好是上一次插入的紧后方，且那个 piece 正好是 added 的尾巴，就直接把它拉长而不新建。这对连续输入很有效，实测局部编辑模式下 2000 次编辑后从 2540 个 piece 降到 1936 个。

而在随机编辑模式下，追加合并一个 piece 也没省下：开与关都是 2982。这个结果起初让人怀疑开关没生效，查下来是对的——随机位置几乎不可能恰好落在上一次插入的末尾。追加合并优化的是「连续打字」这一种模式，而它恰好是最常见的那一种。

5 · piece 挂上平衡树

碎片化真正伤到的是定位。数组实现要回答「偏移 $p$ 落在第几个 piece」只能从头累加长度，代价与 piece 数成正比。1 MB 文档跑 2000 次随机编辑后，charAt 平均要扫过 1705 个 piece 才找到目标。

把 piece 挂到一棵平衡树上，每个结点记录左子树的字符总数，定位就变成一次下降。同一组测试下，树版平均访问 14.8 个结点，是数组版的百分之一不到。

本系列的树版用 treap，VS Code 用红黑树。两者在本节的用途上没有本质区别：需要的只是「按累计长度定位」与「在任意位置拆开再接上」，任何支持 split 与 merge 的平衡结构都行。选 treap 是因为它的 split 与 merge 各只有十几行，而红黑树的删除要分六种情形。

树上每个结点还额外存了子树的换行总数，行号查询因此也变成一次下降。这一步是下一页的题目，见行号索引：按可加权重定位。

6 · VS Code 换掉行数组的账

VS Code 在 2018 年之前把文档存成一个行数组：按换行切开，每行一个字符串。这个模型对「取第 $k$ 行的内容」是理想的，一次数组下标就到。它输在两处。

一是内存。V8 里每个字符串对象都有固定开销，一个几十万行的文件就是几十万个小对象，加上数组本身的指针表。文件越大、行越短，放大倍数越高。

二是长行。一行如果有几十万个字符（压缩过的 JS、单行 JSON、日志），行数组的每次编辑都要重建那一整行的字符串，退化成了本系列第一页讲的朴素字符串。

换成 piece table 之后，打开文件只需要把内容读成一个字符串再造一个 piece，内存基本等于文件本身。代价是「取第 $k$ 行」不再是一次下标，需要走树。VS Code 的做法是在每个缓冲块上另存一张换行位置表，于是「第 $k$ 行在哪个 piece 的第几个字符」是一次树下降加一次二分。

7 · 参考文献

1. Crowley, C. (1998). Data structures for text sequences, §6 (Piece Tables). University of New Mexico, Technical Report.
2. Microsoft. (2018). Text buffer reimplementation. VS Code Blog, 2018-03-23.
3. Aragon, C. R., & Seidel, R. G. (1989). Randomized search trees. 30th Annual Symposium on Foundations of Computer Science, 540–545.
4. Hunt, J. W., & McIlroy, M. D. (1976). An algorithm for differential file comparison. Bell Laboratories Computing Science Technical Report 41. 差分与 piece 序列是同一类表示。