2018年之前，Visual Studio Code用户经常报告一个奇怪的问题：打开某些文件会导致内存溢出崩溃。罪魁祸首是一个35 MB的文件——听起来不大，但它有1370万行。VSCode为每一行创建一个对象，每个对象占用40-60字节，结果光是行数组就消耗了约600 MB内存，是原文件大小的近20倍。

这不是个例。每一位开发者都经历过：打开一个日志文件，编辑器开始卡顿、风扇狂转，最后要么崩溃，要么不得不强制关闭。问题的根源不在文件大小，而在于编辑器如何存储和处理文本。

为什么不能直接用字符串

最直观的想法是将文件内容读入一个字符串。这确实是最紧凑的表示方式，代码也简单。但字符串有一个致命特性：它是连续的内存块。

假设有一个20000行的文件，你想在中间插入一个单词。为了给新单词腾出空间，必须把插入点之后的所有字符向后移动。在最坏情况下，这可能意味着移动整个文件。删除操作同理——不能在字符串中间"戳一个洞"，必须把后面的内容向前移动来填补空隙。

更隐蔽的问题是内存重新分配。当字符串需要扩容时，运行时通常会分配一个更大的缓冲区，把原有内容复制过去，然后释放旧缓冲区。对于小文件，这几乎不可察觉。但当文件达到几百MB，一次插入操作可能触发一次完整的内存拷贝，把本该O(n)的操作变成O(n²)。

还有一个问题：如何实现撤销/重做？最简单的方法是存储每次操作前后的差异，但这意味着大量的额外内存分配——删除大量文本时，需要把被删除的内容完整保存。

这些问题催生了几种专门为文本编辑设计的数据结构。

Gap Buffer：Emacs的选择

Gap Buffer（间隙缓冲区）是最简单的解决方案之一，也是Emacs使用的数据结构。

它的核心思想是：编辑操作通常是局部的。你很少在文件的开头输入一个字符，然后跳到结尾输入另一个。大多数时候，你在一个相对集中的区域内工作。

Gap Buffer在内存中维护一个带"间隙"的缓冲区。间隙是预留的空白空间，位于光标位置。当你在光标处插入字符时，只需把字符写入间隙的前端，然后将间隙起点向后移动一位——这是O(1)操作。删除字符时，间隙向前扩展，同样是O(1)。

问题在于移动光标。如果你从文件开头跳到结尾，间隙必须跟着移动，这意味着要把间隙和目标位置之间的所有字符搬移。这是O(n)操作，但前提是你真的会频繁跳来跳去。

2017年，Chris Wellons发表了一篇名为《Gap Buffers Are Not Optimized for Multiple Cursors》的文章，指出了Gap Buffer在现代编辑场景下的致命缺陷：多光标编辑。当你在文件的多个位置同时编辑时，Gap Buffer只有一个间隙，每次编辑前都必须移动间隙，这可能导致严重的性能下降。

尽管如此，Gap Buffer因其实现简单、对单光标编辑高效，至今仍被Emacs等编辑器使用。

Piece Table：历史的选择

Piece Table（片段表）的历史可以追溯到早期的文字处理软件，Microsoft Word曾使用它来实现高效的撤销/重做。

Piece Table的核心设计非常优雅。它维护两个缓冲区：

  • 原始缓冲区：文件加载时的原始内容，只读
  • 添加缓冲区：所有新增的内容，只追加

然后通过一个"片段描述符"数组来描述文档的当前状态。每个描述符记录：这段文本来自哪个缓冲区、从哪里开始、有多长。

当你在文档中间插入文本时，不需要移动任何现有内容。只需把新文本追加到添加缓冲区，然后更新片段描述符数组——把原来的片段拆成三段：前半部分、新插入部分、后半部分。

删除操作同样优雅：只需调整描述符的起始位置和长度，不需要真正删除任何内容。这意味着撤销操作几乎是免费的——只需恢复之前的描述符状态。

Piece Table的内存效率很高。原始缓冲区直接映射到文件内容，添加缓冲区按需增长。描述符数组的大小与编辑次数成正比，而不是文件大小。

但它也有弱点。如果用户进行了数千次小编辑，片段描述符数组会变得很长，遍历它的效率会下降。传统实现用数组存储描述符，查找第N行的内容需要从头遍历所有描述符，累计计算长度。

VSCode的Piece Tree：当Piece Table遇见红黑树

2018年3月，VSCode团队发布了一篇博客，宣布他们重写了文本缓冲区实现。这次重写的核心是将传统的Piece Table与平衡二叉树结合，创造了"Piece Tree"。

问题的起点是一个用户报告：无法打开一个35 MB的文件。原因是这个文件有1370万行，VSCode的旧行数组实现为每一行创建一个对象，每个对象约40-60字节，总共消耗约600 MB内存。

VSCode团队最初考虑用C++重写文本缓冲区，但发现JavaScript与C++之间的字符串转换开销抵消了大部分性能收益。最终他们选择在JavaScript层面优化数据结构。

Piece Tree的核心改进是将片段描述符存储在红黑树中，而不是数组。每个节点存储：

  • 该片段来自哪个缓冲区
  • 在缓冲区中的起始位置和长度
  • 左子树的文本总长度和行数（用于快速定位）

有了这些元数据，查找任意位置的内容变成O(log n)操作。要找到第1000行的内容，不需要遍历前999个片段，只需从树根向下查找，根据每个节点的左子树行数决定走左还是走右。

Piece Tree还解决了另一个问题：大文件加载。VSCode使用Node.js的fs.readFile读取文件，它返回64 KB的块。对于64 MB的文件，会有1000个块。传统Piece Table需要将这些块拼接成一个大字符串，但V8对字符串长度有限制（当时是256 MB）。

Piece Tree的解决方案是：不拼接。每个64 KB块直接作为一个独立缓冲区，片段描述符指向这些缓冲区。这避免了字符串拼接的内存开销和长度限制。

性能数据令人印象深刻。对于184 MB的文件（310万行），新实现的内存占用从数GB降到了接近原文件大小。文件打开时间从数秒降到了几百毫秒。随机插入1000次的时间从无法完成降到了几十毫秒。

Rope：Xi和Zed的选择

Rope（绳索）是另一种经典的数据结构。它的名字很形象：把长字符串"搓"成一根由短字符串组成的"绳索"。

Rope是一棵二叉树，每个叶子节点存储一个短字符串，每个内部节点存储左子树的字符串总长度（权重）。查找第i个字符时，从根节点开始：如果i小于当前节点的权重，走左子树；否则减去权重，走右子树。

插入和删除操作通过树的拆分和合并实现。要删除位置a到b之间的字符，先将树在a处拆分，再将树在b处拆分，然后合并第一部分和第三部分，丢弃中间部分。这些操作都是O(log n)。

Rope的优势在于它的"持久化"特性——可以高效地保留历史版本。这对于实现撤销/重做、协作编辑、异步保存都非常有用。当一个Rope被修改时，未修改的部分可以与新版本共享，只有修改的路径需要复制。

Google的Xi编辑器曾使用Rope作为核心数据结构。其作者Raph Levien在回顾文章中写道：Rope最吸引人的特性是它优秀的最坏情况性能——基本上没有它会表现糟糕的场景。

但Rope也有代价。它的实现复杂度高于Gap Buffer和简单的Piece Table。在C语言中，Gap Buffer可能更合适，因为可以直接暴露指向缓冲区的指针，调用者无需关心间隙的存在。但在Rust中，Rope的复杂性可以被良好地封装：所有访问都通过明确定义的接口进行，内部细节对外不可见。

Zed的SumTree：Rope的进化

2024年，Zed编辑器的团队发表了一篇博客，详细介绍了他们的Rope实现——但它不是传统意义上的Rope，而是一个叫SumTree的数据结构。

SumTree本质上是B+树的一个变体。每个叶子节点包含多个"块"（Chunk），每个块最多存储128个字符（在发布构建中）。每个节点——无论是内部节点还是叶子节点——都有一个"摘要"（Summary）。

这个摘要才是SumTree的精髓所在。Zed的文本摘要包含：

  • UTF-8长度
  • UTF-16代码单元长度（LSP协议需要）
  • 行数和最后一行的长度
  • 最长行的位置和长度

内部节点的摘要是其所有子节点摘要的总和。这意味着从根节点就能知道整篇文档的基本信息：有多少字符、多少行、最长行在哪里。

更强大的能力是多维度遍历。你可以在一个维度上查找，同时累加另一个维度的信息。例如，查找第26个字符所在的位置，同时计算到那里经过了多少行：

let point = rope.offset_to_point(26);
// 返回 (row: 1, column: 16)

内部实现是：创建一个游标，沿着长度维度查找到第26个字符的位置，同时累加沿途的行数信息。由于每个内部节点都存储了子树的摘要，查找过程可以跳过大片区域，时间复杂度O(log n)。

这种设计让Zed能够高效处理许多操作：将UTF-8偏移转换为UTF-16偏移、计算滚动条的滚动块大小、查找最长行等——所有这些都是O(log n)。

语法高亮的隐形战争

文本存储只是战斗的一半。当打开一个大文件时，另一场战斗在后台悄悄展开：语法高亮。

传统的语法高亮使用正则表达式。它在每行上运行一系列正则模式，匹配到的内容被赋予相应的样式。这种方法实现简单，有大量现成的语法定义可用。

但正则表达式的问题在于性能。Xi编辑器的作者做了一个对比：解析Markdown时，最快的开源正则引擎syntect比专门的Markdown解析器pulldown-cmark慢约2500倍。而且正则引擎甚至无法正确处理某些语法——比如setext风格的标题需要看到下一行才能确定当前行是否是标题，但正则引擎逐行处理，无法"向前看"。

2017年，Max Brunsfeld创建了Tree-sitter，一个增量解析库。它的核心思想是：不每次重新解析整个文件，而是只重新解析受影响的部分。

当用户编辑文本时，Tree-sitter会：

  1. 找到受编辑影响的最小语法树节点
  2. 重新解析该节点及其子树
  3. 将新子树嫁接到原有语法树上

这使得语法高亮的成本从O(n)降到O(log n)甚至O(1)——大多数编辑只影响局部语法树。

Tree-sitter现在是Neovim、Emacs、Zed等编辑器的默认语法高亮引擎。VSCode也在逐步迁移到Tree-sitter。

但即使是增量解析，对于超大文件仍有挑战。Tree-sitter需要构建完整的语法树，对于数百万行的文件，这可能需要几秒钟。一些编辑器选择对大文件禁用语法高亮，或只对可见区域进行高亮。

虚拟滚动：只渲染你看到的

假设你打开了一个有1000万行的日志文件。如果编辑器尝试为每一行创建DOM节点，浏览器会崩溃。解决方案是虚拟滚动：只渲染可见区域的内容，用空的占位元素维持滚动条的正确比例。

虚拟滚动的实现需要解决几个问题：

  1. 行高计算：如果所有行高度相同，计算滚动位置很简单。但实际代码可能有折叠、内嵌编辑器等，行高不统一。Zed通过在摘要中存储额外信息来解决这个问题。

  2. 快速定位：滚动到第500万行时，如何快速找到该位置？这正是Piece Tree和SumTree擅长的——O(log n)的行号到偏移转换。

  3. 平滑滚动：快速滚动时，需要预加载即将进入视口的内容，否则会出现闪烁。这需要在后台线程提前计算。

撤销/重做：不只是Ctrl+Z

实现撤销/重做最直观的方法是命令模式：为每种操作定义一个命令对象，执行时记录"反向操作"。撤销时执行反向操作。

enum Command {
    Insert { position: usize, text: String },
    Delete { position: usize, text: String },
}

但这种方法在大量编辑后会产生大量命令对象，内存消耗可观。

Piece Table和Rope提供了更优雅的方案。由于这些数据结构支持高效的历史版本保留，撤销几乎不需要额外操作——只需切换回之前的树根。

VSCode的Piece Tree实现采用了一种混合方案：文本缓冲区本身不支持撤销，但编辑操作会返回"反向编辑"，由上层负责存储。这避免了复制整个树的开销，同时保持了合理的内存使用。

大文件处理策略

尽管数据结构在进步，但依然没有万全之策。面对真正的大文件——几十GB的日志、数据库导出、视频文件——编辑器仍需采取策略：

懒加载：不一次性读取整个文件，而是按需加载可见部分。这需要文件系统的支持，以及能够处理非连续访问的数据结构。

禁用特性：VSCode的editor.largeFileOptimizations设置会对大文件自动禁用语法高亮、代码折叠、符号解析等功能。这是权衡的结果：牺牲功能换取可用性。

特殊模式：某些编辑器提供"大文件模式"或"十六进制模式"，将文件视为原始字节而非文本，跳过所有文本处理逻辑。

流式处理：对于只需要搜索或过滤的场景，使用流式处理而不是加载整个文件。ripgrep等工具正是这样做的——它们使用内存映射而不是读取整个文件到内存。

性能基准的真实故事

2016年底，一篇博客文章对比了Sublime Text、VSCode和Atom的性能。结果令人震惊：Sublime Text在几乎所有测试中都遥遥领先。

操作 Sublime Text VSCode Atom
启动时间 0.5秒 2.5秒 4秒
打开10MB文件 即时 1秒 3秒
滚动流畅度 60fps 30-60fps 15-30fps

差异的根源在于技术栈。Sublime Text用C++编写，使用高度优化的原生UI。VSCode和Atom基于Electron，运行在V8 JavaScript引擎之上，使用HTML/CSS渲染UI。

但这个故事有一个转折。2018年VSCode重写文本缓冲区后，差距显著缩小。更重要的是，VSCode的扩展生态系统和功能丰富度弥补了性能上的不足。2022年，Atom被GitHub宣布停止维护，VSCode成为主导者。

Sublime Text依然是最快的编辑器之一，但它的市场份额远不如VSCode。这揭示了一个更深层的真相：性能只是编辑器选择的一个因素，而往往不是决定性因素。

数据结构的选择逻辑

回顾这段历史，可以看到文本编辑器数据结构的选择遵循一条清晰的逻辑链：

  • 字符串：最简单，但无法处理大文件。仅适用于确定文件大小有限的场景。
  • 行数组：VSCode最初的选择，直观且易于实现，但遇到长行文件时内存爆炸。
  • Gap Buffer：对局部编辑高效，实现简单，但不适合多光标编辑。适合以单光标编辑为主的用户群体。
  • Piece Table：内存效率高，撤销/重做优雅，但传统实现的查找效率随编辑次数下降。
  • Piece Tree：Piece Table与平衡树的结合，查找效率O(log n)，但实现复杂。
  • Rope：最坏情况性能优秀，支持持久化，但实现复杂，在某些语言中可能不如Gap Buffer直观。
  • SumTree：Rope的B+树变体，支持多维度摘要和高效遍历，但实现最复杂。

没有最优解，只有最适合的权衡。Emacs选择Gap Buffer因为它简单、对Emacs的用户习惯高效。VSCode选择Piece Tree因为它需要处理大文件、支持复杂编辑模式、且必须在JavaScript环境中运行。Zed选择SumTree因为它追求极致性能、需要多线程访问文本、且使用Rust实现可以很好地封装复杂性。

Xi编辑器的故事提供了一个警示。它押注于异步多进程架构和CRDT协作机制，技术上雄心勃勃。但最终，这种复杂性超过了收益。作者Raph Levien在回顾中写道：如果我知道建造它需要多少工作量，我可能会选择不同的道路。

好的数据结构设计不是追求最新、最复杂的技术，而是找到满足需求的最简单方案。对于大多数编辑器，Piece Tree或Rope已经足够优秀。对于追求极致性能的场景，Zed的SumTree展示了还有多少优化空间。但对于日常使用，也许最重要的不是微秒级的性能差异，而是整体的用户体验——这正是Sublime Text输给VSCode的原因。

打开一个500MB的文件需要多久？取决于你的编辑器。但更重要的是理解：这不仅仅是一个数字，而是几十年数据结构设计和工程权衡的结果。

参考文献

  1. Peng Lyu. “Text Buffer Reimplementation.” Visual Studio Code Blog, 2018.
  2. Nathan Sobo, Max Brunsfeld, Antonio Scandurra. “Rope & SumTree.” Zed Blog, 2024.
  3. Raph Levien. “xi-editor retrospective.” Raph Levien’s Blog, 2020.
  4. Chris Wellons. “Gap Buffers Are Not Optimized for Multiple Cursors.” null program, 2017.
  5. Darren Burns. “The Piece Table - the Unsung Hero of Your Text Editor.” dev.to, 2019.
  6. “Piece table.” Wikipedia.
  7. “Text Editor Data Structures.” invoke::thought(), 2023.
  8. Will Bond. “Building a High Performance Text Editor.” wbond.net, 2021.
  9. Max Brunsfeld. “Tree-sitter: an incremental parsing system for programming tools.” GitHub, 2017.
  10. “Rope science - Introduction.” Xi Editor Documentation.