Piece Table(片段表)

定义

Piece Table(片段表)是一种文本编辑器缓冲区结构:维护两块只追加的文本存储——原始文件内容(original)和新输入内容(add buffer)——文档本身表示为一张片段(piece)列表,每个片段用(缓冲区、起点、长度)三元组引用其中一段。

原理

插入文本时把新内容追加到 add buffer,并在片段表中把所在片段一分为二、中间插入指向新内容的片段;删除只需调整或拆分片段,原文永不改动。因此任何历史版本都可由片段表快照重现,撤销重做实现自然。片段表可用数组、链表或平衡树组织,树形组织可把定位从 O(片段数) 降为对数级别。

应用

Piece Table 源自早期编辑器(如 Bravo)的设计传统,微软 Word 的文件格式历史上使用过 piece table 思想;VS Code 于 2018 年重写文本缓冲区,采用红黑树组织的 piece tree,大幅降低了大文件的内存占用与加载时间。

优缺点

优点是原文只读利于内存映射、撤销与多版本廉价、插入删除不搬移正文;缺点是长时间编辑后片段碎片化,顺序读取与搜索变慢,需要定期整理。