第 6 章：SumTree、Rope 与快照——高性能编辑的地基

Zed 的核心数据结构策略：把长序列存进持久化 B+ tree，在每个子树保存可组合 Summary，再用不同 Dimension 在同一棵树上按 byte、行列、UTF-16 或自定义坐标跳转。

1. 为什么 `String` 和 `Vec` 不够

编辑器热路径反复需要：

在百万字节文件中间插入；
byte offset ↔ row/column ↔ UTF-16 position；
保留旧版本快照给后台 parse/LSP；
把局部修改映射到折叠、换行、inlay 后的坐标；
复制文档视图时避免复制全文。

平坦字符串中间插入是 O(n)，旧快照要么复制，要么加锁。Zed 把问题拆成 SumTree 和 Rope。

2. SumTree：叶子是数据，内部节点是摘要

SumTree<T> 是持久化 B+ tree：

叶节点最多 TREE_BASE * 2 个 Item；
每个 Item 产生 Summary；
内部节点保存子树 Summary；
根和子树由 Arc<Node<T>> 共享；
修改路径使用 copy-on-write，未触及子树继续共享。

源码：crates/sum_tree/src/sum_tree.rs:206-213。

3. Item、Summary、Dimension 三件套

rust

trait Item {
    type Summary: Summary;
    fn summary(&self, cx: ...) -> Self::Summary;
}

trait Summary {
    fn zero(...) -> Self;
    fn add_summary(&mut self, other: &Self, ...);
}

trait Dimension<'a, S: Summary> {
    fn zero(...) -> Self;
    fn add_summary(&mut self, summary: &'a S, ...);
}

源码：crates/sum_tree/src/sum_tree.rs:31-110。

Summary 是可结合的子树统计；Dimension 是从 Summary 中选择一种累计坐标。一个 Summary 可以同时支持多种 Dimension。

示例

假设 Chunk Summary 包含：

text

bytes = 120
utf16 = 118
lines = Point(row: 3, column: 14)
longest_row = 51

Cursor 按 byte 找第 80 个字节，或按 Point 找第 2 行，都能跳过 Summary 小于目标的整棵子树。

4. Bias 解决边界歧义

位置恰好落在两个 Item 之间时，Bias::Left 与 Bias::Right 决定附着哪边。折叠边界、插入点和 selection anchor 都依赖这个概念。

源码带了直观例子：crates/sum_tree/src/sum_tree.rs:167-195。

Bias 不是渲染小细节，而是“边界发生插入后位置跟谁走”的语义。

5. Rope：Chunk 的 SumTree

Rope 本身只有：

rust

pub struct Rope {
    chunks: SumTree<Chunk>,
}

源码：crates/rope/src/rope.rs:25-28。

Chunk 保存一段 UTF-8 文本及字符/tab/newline bitmap 和 TextSummary。Rope 操作通过切分、拼接和替换少量 Chunk 完成，大部分树节点继续共享。

`replace` 的本质

Rope::replace 不是原地移动后半段内存，而是：

cursor slice 出 range 前缀；
跳过旧 range；
push 新文本；
append 原 suffix；
用新根替换旧 Rope。

源码：crates/rope/src/rope.rs:124-132。

6. 为什么必须同时支持 UTF-8 和 UTF-16

Rust 字符串和文件偏移自然使用 UTF-8 byte；LSP position 使用 UTF-16 code unit；UI 又经常使用 row/column。Emoji 等字符会让三者不相等。

Rope/BufferSnapshot 提供：

point_to_offset；
offset_to_point；
point_to_point_utf16；
offset_to_offset_utf16；
反向转换和 unclipped 版本。

这些转换依赖树摘要，避免每次从文档开头扫描。

7. Snapshot 为什么便宜

BufferSnapshot、Rope、SumTree 大量字段可 clone，因为内部树节点和文本片段通过 Arc 共享。创建快照主要复制根句柄和小型索引；后续编辑只复制受影响路径。

于是可以安全地：

text

UI 前台持有当前 Buffer
  ├─ snapshot A → 后台 Tree-sitter parse
  ├─ snapshot A → LSP request position conversion
  └─ 用户继续编辑 → 当前变为 snapshot B

后台结果回来时携带版本/anchor，再判断能否映射到 B，而不是锁住 UI 等 parse。

8. Patch：传播“哪里失效”

text::Patch<T> 是一组 Edit<T>，描述旧坐标 range 对应到新坐标 range。它可以 compose、 invert，并做 old-to-new 映射。

源码：crates/text/src/patch.rs:8-88。

Patch 不一定携带新文本；它更像精确的 invalidation map。DisplayMap 各层接收下层 Patch，把坐标变换为本层 Patch，只重算受影响区域。

9. SumTree 在文本之外的复用

同一种“序列 + 摘要 + 多维定位”还用于：

operation queue 按 Lamport key 排序；
undo map；
MultiBuffer excerpts；
DisplayMap transforms；
Worktree entries；
diagnostics / selections / map-like collections。

这是 Zed 很强的内部设计语言：看到 Item/Summary/Dimension/Cursor，就知道该模块正在把某种长序列变成可增量定位的持久化结构。

10. 复杂度直觉

操作	平坦结构	摘要树直觉
中间插入	移动 O(n)	修改树路径 + 邻近 chunk，约 O(log n + k)
offset → row	扫描 O(n)	摘要 seek，约 O(log n)
clone snapshot	O(n) copy	O(1) 根共享
局部坐标失效	常退化全量	Patch 传播局部范围

实际复杂度还受 chunk split、并发 fragment、wrap 重算等影响，但架构方向清楚：让工作量与变化范围相关，而不是与文档总长度相关。

11. 代价与风险

类型系统复杂：每层有自己的 Point/Offset/Dimension；
Bias、边界和 Unicode 转换容易产生 off-by-one；
持久化节点会暂时保留旧内存；
Summary 必须满足结合语义，错误会让 seek 静默定位错；
调试时看到的是树片段和 snapshot，而不是一个直观 String。

因此这些 crate 有大量 property tests 和 invariant check。性能数据结构必须用随机操作序列证明 “任意编辑后仍等价于朴素模型”，单个示例测试不够。

第 6 章：SumTree、Rope 与快照——高性能编辑的地基 ​

1. 为什么 String 和 Vec 不够 ​

2. SumTree：叶子是数据，内部节点是摘要 ​

3. Item、Summary、Dimension 三件套 ​

示例 ​

4. Bias 解决边界歧义 ​

5. Rope：Chunk 的 SumTree ​

replace 的本质 ​

6. 为什么必须同时支持 UTF-8 和 UTF-16 ​

7. Snapshot 为什么便宜 ​

8. Patch：传播“哪里失效” ​

9. SumTree 在文本之外的复用 ​

10. 复杂度直觉 ​

11. 代价与风险 ​