第 5 章 · 01 缓冲区模型:不止是字符串

第 5 章 · 01 缓冲区模型:不止是字符串

本节摘要:造文本编辑器,第一个要回答的问题是:「文本在内存里怎么存?」最直觉的答案「用一个大字符串」在小文件上够用,但一插入/删除就要搬移大量字符,大文件上极慢。本节导读三种专业缓冲区结构:行数组(每行一个字符串,简单)、gap buffer(在光标处留空隙,Vim 早期用它)、piece table(原文+增量片段表,VS Code 用它)。理解它们的取舍,你就懂得编辑器内核的基础。

内容来源:基于「Build your own X」Text Editor 域整理的导读。

学习目标

阅读完本节,你应当能够:

1. 说清「一个大字符串」方案的缺陷:插入/删除要 O(n) 搬移。
2. 描述三种专业缓冲区结构:行数组、gap buffer、piece table。
3. 解释各自的取舍:简单 vs 性能 vs 内存。
4. 理解 Vim、Emacs、VS Code 各自的选择。

一、学习价值:数据结构决定编辑器上限

编辑器的核心操作是「频繁插入/删除字符」。这些操作的性能,完全由「文本在内存里怎么存」决定。选对数据结构,大文件也流畅;选错,小文件都卡。

本节不是抽象理论——它直接解释「为什么 Vim 能流畅编辑几百 MB 文件,而某些编辑器卡顿」:缓冲区结构不同。理解这点,你造编辑器时才能做出合适选择。

二、子系统拆解:三种结构

方案 0:一个大字符串(朴素,反例)

整篇文本 = "Hello, world!\nThis is..."
插入一个字符在中间: 后半部分全部右移一格, O(n)
​

小文件够用,大文件灾难。这是反面教材。

方案 1:行数组(gap buffer 之前)

lines = ["Hello, world!", "This is...", ...]
每行一个字符串, 插入在某行内仍是 O(该行长), 但跨行操作简单
​

简单直观,适合大多数情况。很多教学编辑器(如 kilo)用它。缺点:单行很长时仍慢。

方案 2:Gap Buffer(间隙缓冲)

[abcde][    gap    ][fghij]
       ↑光标在这里
​

在光标位置留一段空隙(gap)。插入:写进 gap,光标后移;删除:gap 扩大。光标移动时,gap 跟着移动(搬移少量字符)。优势:光标附近的插入/删除是 O(1)(只要 gap 没满)。Emacs 早期用它。

方案 3:Piece Table(片段表)

original: "原文, 只读"
add:      "增量缓冲, 只追加"
pieces:   [{from original, len 5}, {from add, len 3}, {from original, len 10}, ...]
​

原文只读、增量只追加,编辑器维护一个「片段表」记录「文档由哪些片段、按什么顺序拼成」。插入/删除只改片段表(记录「从哪到哪」的元数据),不动原文。VS Code、Word 用它。优势:编辑操作 O(1),内存高效(原文只存一份)。缺点:实现复杂。

三者取舍

三、上手第一步:从行数组开始

造第一个编辑器,推荐行数组:简单、够用、能让你专注学其他子系统(渲染、输入)。实现:

lines: List<String>   # 每行一个字符串
插入字符: 找到对应行, 在该行字符串里 splice
删除字符: 同上
光标: (行号, 列号) 二元组
​

行数组足够支撑你造一个能用的编辑器。等你理解了其他子系统,再考虑换 gap buffer 或 piece table 优化。

本节要点回顾

1. 缓冲区结构决定编辑器性能上限——「大字符串」方案插入删除 O(n),大文件卡。
2. 行数组:每行一字符串,简单,教学编辑器常用。
3. Gap buffer:光标处留空隙,光标附近插入删除 O(1),Emacs 早期用。
4. Piece table:原文只读+增量只追加+片段表,编辑 O(1),VS Code 用。
5. 第一个编辑器推荐行数组,简单够用,先学其他子系统再优化。

推荐上手顺序

1. 用行数组实现最小缓冲区(打开文件→分行→编辑→保存)。
2. 实现光标移动(上下左右)与基本插入删除。
3. 体会「长行插入慢」后,考虑改 gap buffer(光标附近留空隙)。
4. 进阶:实现 piece table(原文+增量+片段表),理解 VS Code 的选择。

下一节讲光标移动与模式——致敬 Vim 的 normal/insert 双模式。