【数据结构】深入理解PieceTable数据结构

引言

当在vscode中键入文字的时候，这些文字会缓存在内存中的数据结构（piecetable）中。此外另有Abiword，atom，bravo，某些版本的microsoft word都使用了piecetable这种数据结构来表示文本文档的内容。

什么是PieceTable

维基百科中有如下定义

A Piece Table is a data structure typically used to represent a series of edits on a text document

一个PieceTable是一种数据结构，通常用来表示文本文档中一系列的编辑操作。

概念

PieceTable中有两个文件内容，一个是原始文件内容（original），还有一个新增文件内容（add）。这两部分的内容由两个string buffer来存在内存中。有顺序的获取 原始文件内容和新增文件内容 中的部分内容（Piece），就是组成了最终的文档的内容。

• Original File (Buffer): 原始文件内容，只能读取
• Add File (Buffer): 新增文本内容，只能增加、读取
• Piece: 通常包含以下属性
  • buffer type: buffer类型，是original还是add
  • start: 在该buffer中所在的开始的index
  • length: 内容的长度。

比如：

Original File: 这是一段文字
Add File: 美好，这是另一段文字

piece: original, 0, 6 表示 ‘这是一段文字’

所有的piece连起来就是：这是一段美好的文字

这样一篇在编辑中的文档内容就这样被一连串顺序的piece所指代。

操作

PieceTable有以下基本的操作

• itemAt(p1, p2) : 获取p1到p2的文本内容
• insert(p, str) : 在某个位置输入一段文本
• delete(p1, length) : 删除p1位置开始一定长度的内容
• (split): 把一个piece分割为两个piece，隐藏在insert和delete之后的操作，不直观，文章后面的例子可以直观感受这个操作。

特点

其特点简单总结就是两点：

1. PieceTable的一大特点是：只增不减。PieceTable在初次加载文本之后会缓存在内存中不动，后续添加更改的文字会缓存在内存中。
2. 每个piece存储的是对于文本的指针，所以对于任何插入、删除操作其实就是一个index的变更而已，任何真实的文本内容是不变的。这样的特性，可以为无限撤销、重放提供了可能性

稍复杂的例子

下面用一个稍微复杂的例子来看PieceTable的各种操作是如何达到编辑的效果的？

编辑后文档内容：这是一段文字

 // 执行操作 
 insert(4, '美好的')

编辑后文档内容：这是一段优美的文字

// 执行操作：位置2，长度1
delete(2, 1)

编辑后文档内容：这是段优美的文字

piecetable实现：Piece的管理

PieceTable的所有的操作的性能，都是依赖于使用何种数据结构来管理产生的Piece。整个pieceTable的实现难度主要集中在这里。下面列举一些数据结构，分别分析：

• 数组：最常用的数据结构之一，优势在于实现简单直接，劣势在于随着piece的增多，插入删除数组中的某个值，性能是比较差的。
• 链表：也是最常用的数据结构之一，插入、删除的性能较好[O(1)]，但是获取的性能就不稳定了[搜索时间 + O(1)]，搜索时间最好是 O(1)，最差是O(n)，非常不稳定。
• 平衡二叉树：各个操作都在 O(logn)，非常的稳定。

从这些常用的数据结构来说，使用平衡二叉树是最好的选择，即使在piece非常膨胀的时候，也能有较好的表现。

平衡二叉树中，使用红黑说或者splayTree是比较常见的。
比如：vscode是使用了红黑树，atom使用的是splaytree这种结构来管理。下面的链接vscode和atom的text buffer源码地址。

vscode-textbuffer: https://github.com/microsoft/vscode-textbuffer

atom-textbuffer: https://github.com/atom/text-buffer

下面是自己写的一个实验性的piecetable实现，用的是红黑树来管理piece。还有添加了一些额外的功能，比如undo/redo，富文本支持等

flowerpiece: https://github.com/Basaltic/flowerpiece

总结

PieceTable本身的概念是非常易于理解的，实现层面的难点在于用什么方式来管理piece，兼顾性能，内存开销，undo\redo，树快照等等功能。