AI News
中文资讯 掘金 AI Thu, 10 Sep 2026 正文 ok 1332 words

把 AntV S2 列头计算从 O(n²) 降到 O(n)：一次开源组件的性能改造

英文标题：把 AntV S2 列头计算从 O(n²) 降到 O(n)：一次开源组件的性能改造

本文系统拆解了在百万行透视表场景下，针对前端开源表格引擎 AntV S2 布局层的深度性能优化实践。针对列头高度计算中存在的 O(n²) 遍历开销以及 Canvas measureText 重复调用的性能瓶颈，团队通过构建层级 Map 索引及同层列高复用策略，成功将计算复杂度压降至 O(n) 线性级别，彻底解决了渲染卡顿与页面冻结问题。文章还分享了大数据量导出优化及通过 patch 机制维护开源代码的工程实践，为复杂前端数据可视化与表格组件的高性能改造提供了极具参考价值的落地范式。
打开原文相关 2 · 机会 0
media3.2 KB media589 B media8.1 KB

中文

背景：同一篇，百万行透视表。前三篇讲了应用层（砍 30 万 Proxy）、存储层（132MB → 25MB 列式）、线程层（Worker 常驻 + 零拷贝）。这篇讲布局层——直接改 AntV S2 源码，把列头高度计算从 O(n²) 降到 O(n)。

本文会讲清楚：为什么列头计算是性能瓶颈、怎么把计算量从平方级降到线性级、以及改开源代码怎么管理 patch 和保证正确性。

这是这个系列的四篇里的第四篇，讲的是布局层——直接改 S2 源码把列头计算从 O(n²) 降到 O(n)。前三篇分别是应用层、存储层和线程层，这篇是收尾。

一、先定位问题在 S2 的哪个环节

S2（AntV S2）是 canvas 透视表引擎。数据从加载到屏幕的路径：

mermaid graph LR A[原始数据] --> B[DataSet 解析 聚合] --> C[Facet 布局计算] --> D[Canvas 渲染] E[columnar.js packColumnar 列式 groupBy] --> B F[hierarchy.js getNodes O(1)] --> C G[pivot-facet.js fixedColHeight 缓存] --> C H[data-cell-copy.js 导出优化] --> D

前三篇的优化都在 DataSet 和数据传输层。这篇改的是 Facet 层 ——S2 的布局计算引擎。

Facet 干的事：根据数据和字段配置，计算每个单元格的坐标（x, y, width, height），构建行/列层级树，然后交给 Canvas 画出来。

列头高度计算 是 Facet 每次渲染都要做的工作。数据量大时，这里是卡顿的直接来源。

二、getColNodeHeight：S2 最昂贵的函数

先看 getColNodeHeight 干了什么：

javascript getColNodeHeight({ colNode, colsHierarchy, useCache }) { const { colHeight, colWidth } = this.getColNodeSize(...);

const { width } = this.spreadsheet.measureText(colNode.label, colNode);

const lineCount = Math.ceil(width / colWidth); return lineCount * lineHeight; }

2.1 measureText 为什么贵

measureText 是 canvas API，调用浏览器的文本测量逻辑。每次调用都要：

  1. 创建/查找 canvas 上下文
  2. 设置字体样式（字体、字号、加粗等）
  3. 调用 ctx.measureText(text)——浏览器底层的 glyph 索引 + 像素宽度计算
  4. 返回 TextMetrics 对象

第 3 步是核心开销。ctx.measureText(text) 不是简单的"字符数 × 字符宽度"。它要查字体文件中的 glyph 索引，按照字体的 kerning（字距调整）信息逐对计算，累加每个 glyph 的 advance width，返回精确的像素宽度。

这是 S2 里最昂贵的单步操作之一。文本测量的代价和文本长度成正比，透视表的列头往往是长字符串（如维度值拼接），测量开销不可忽视。

2.2 为什么原版要对每个节点都调一次

S2 的 getColNodeHeight 本身有缓存参数，但原版显式传了 useCache: false：

javascript this.getColNodeHeight({ colNode: currentNode, colsHierarchy, useCache: false });

useCache: false 的含义是强制绕过缓存。原因可能是 S2 的缓存以节点为 key，不同节点即使同层也要分别查缓存，而且缓存可能在数据变化时失效不及时。

这意味着原版代码里，每个列节点都要做一次完整的 measureText。

三、原版代码：O(n²) 是怎么形成的

3.1 calculateColNodesHeight 的原始实现

javascript calculateColNodesHeight(colsHierarchy) { const colNodes = colsHierarchy.getNodes();
colNodes.forEach((currentNode) => { if (currentNode.level === 0) { currentNode.y = 0; } else { const preLevelSample = this.getPreLevelSampleNode(currentNode, colsHierarchy); currentNode.y = preLevelSample?.y + preLevelSample?.height || 0; }

const colNodeHeight = this.getColNodeHeight({
  colNode: currentNode,
  colsHierarchy,
  useCache: false,
});
currentNode.height = currentNode.isGrandTotals && !currentNode.isTotalMeasure && currentNode.isLeaf
  ? colsHierarchy.height
  : colNodeHeight;
layoutCoordinate(this.spreadsheet, null, currentNode);

}); }

问题一目了然：colNodes.forEach 对每个节点都调用一次 getColNodeHeight。如果列层级树有 N 个节点，就是 N 次 measureText。

3.2 getPreLevelSampleNode 的叠加

javascript getPreLevelSampleNode(colNode, colsHierarchy) { return colsHierarchy .getNodes(colNode.level - 1)
.find((node) => !node.isTotals);
}

getNodes(level) 原版是 .filter() 整个节点数组——O(n)。.find() 最坏也是 O(n)。所以每个列节点都要花 O(n) 找上一层的采样节点。

3.3 复杂度汇总

text 原版 calculateColNodesHeight: 对每个节点 i ∈ [0, N): getPreLevelSampleNode(i) // O(n) — getNodes(level-1).find() 扫描该层全部节点 getColNodeHeight(i) // O(T) — T 是文本测量开销

总复杂度: N × (n + T) 最坏情况 n ≈ N → O(N²)

用图来看这个平方级开销是怎么一层层叠起来的：

mermaid graph TD A[遍历 N 个列节点] --> B{每个节点 i} B --> C[getPreLevelSampleNode i O(n) 扫描该层全部节点] B --> D[getColNodeHeight i O(T) measureText] C --> E[累计 N 乘 n] D --> F[累计 N 乘 T] E --> G[总复杂度 O(N平方) N=10000 时 1 亿次比较] F --> G

100 万行数据，透视后列数可能 100010000 个，层级深度 25 层。每次渲染调用 getNodes 约 10000 次，每次 O(10000) = 1 亿次比较。加上 N 次 measureText，渲染一帧就要几百毫秒。

3.4 为什么这是个严重问题

S2 的渲染是每帧都调的。60fps 要求每帧在 16.6ms 内完成。如果 calculateColNodesHeight 就要几百毫秒，意味着用户拖动滚动条时页面完全卡死 ——不是掉帧，是整页冻结。这是百万行透视表"拖拽列头卡顿"的直接原因。

四、修改后：O(n) 怎么做到的

4.1 改动点 A：getNodes 从 O(n) 降到 O(1)

在 hierarchy.js 的 Hierarchy 类里新增 nodesByLevel Map：

javascript class Hierarchy { constructor() { this.allNodesWithoutRoot = []; this.indexNode = [];

this.nodesByLevel = new Map();
this.firstNormalNodeByLevel = new Map();

}

getNodes(level) { if (level !== undefined) { return this.nodesByLevel.get(level) || [];
} return this.allNodesWithoutRoot; }

getFirstNormalNodeOfLevel(level) { return this.firstNormalNodeByLevel.get(level); }

pushNode(node, insetIndex = -1) { if (insetIndex === -1) { this.allNodesWithoutRoot.push(node); } else { this.allNodesWithoutRoot.splice(insetIndex, 0, node); }

const levelNodes = this.nodesByLevel.get(node.level);
if (levelNodes) {
  levelNodes.push(node);
} else {
  this.nodesByLevel.set(node.level, [node]);
}

if (!node.isTotals && !this.firstNormalNodeByLevel.has(node.level)) {
  this.firstNormalNodeByLevel.set(node.level, node);
}

}

clear() { this.allNodesWithoutRoot = []; this.nodesByLevel.clear(); this.firstNormalNodeByLevel.clear(); this.indexNode = []; } }

索引维护的代价：每次 pushNode 做 2 次 Map 操作（get/set），是 O(1)。总节点数 n，维护索引的总代价是 O(n)，与构建层级树本身同阶，不增加复杂度。

4.2 改动点 B：getPreLevelSampleNode 改用 O(1) 缓存

javascript // 修改前 getPreLevelSampleNode(colNode, colsHierarchy) { return colsHierarchy .getNodes(colNode.level - 1) .find((node) => !node.isTotals); }

// 修改后 getPreLevelSampleNode(colNode, colsHierarchy) { return colsHierarchy.getFirstNormalNodeOfLevel(colNode.level - 1); }

4.3 改动点 C：calculateColNodesHeight 缓存列高——核心优化

javascript calculateColNodesHeight(colsHierarchy) { const colNodes = colsHierarchy.getNodes(); let fixedColHeight = null;
colNodes.forEach((currentNode) => { if (currentNode.level === 0) { currentNode.y = 0; } else { const preLevelSample = this.getPreLevelSampleNode(currentNode, colsHierarchy); currentNode.y = preLevelSample?.y + preLevelSample?.height || 0; }

if (fixedColHeight === null) {
  fixedColHeight = this.getColNodeHeight({
    colNode: currentNode,
    colsHierarchy,
    useCache: false,
  });
}

currentNode.height = fixedColHeight;
if (currentNode.isGrandTotals && !currentNode.isTotalMeasure && currentNode.isLeaf) {
  currentNode.height = colsHierarchy.height;
}
layoutCoordinate(this.spreadsheet, null, currentNode);

}); }

关键变化：getColNodeHeight 从 每个节点调一次 降为 每层调一次 （只在 fixedColHeight === null 时调）。

4.4 为什么"同层共用同一高度"是正确的

这个假设的依据：列头高度由该层文本的最大换行数决定。S2 在 calculateColNodesHeight 之前已经通过 updateColsHierarchySampleMaxHeightNodes 确定了每层的采样节点（高度最大的节点）。所以 getColNodeHeight 在该层上的结果对所有非 Totals 节点相同。

总计节点仍走 colsHierarchy.height 分支，不复用 fixedColHeight，所以不会影响总计行的布局。

五、复杂度分析：形式化

5.1 修改前

text 对每个节点 i ∈ [0, N): getPreLevelSampleNode(i) // O(n) — getNodes(level-1).find() 扫描该层全部节点 getColNodeHeight(i) // O(T) — T 是文本测量开销

总复杂度: N × (n + T) 最坏情况 n ≈ N → O(N²)

5.2 修改后

text 对每个节点 i ∈ [0, N): getPreLevelSampleNode(i)
仅 i=0 时 getColNodeHeight(0)
其余节点复用 fixedColHeight

总复杂度: N × 1 + T → O(N)

用图来看这个线性化是怎么做到的：

mermaid graph TD A[遍历 N 个列节点] --> B{每个节点 i} B --> C[getPreLevelSampleNode i O(1) Map 查找] B --> D{i = 0} D -- 是 --> E[getColNodeHeight 0 O(T) measureText 仅一次] D -- 否 --> F[复用 fixedColHeight O(1)] C --> G[总复杂度 O(N) N=10000 时 1 万次操作] E --> G F --> G

从 O(N²) 降到 O(N)，在 N=10000 时是 10000 倍的差距。

5.3 为什么 measureText 从 N 次降到 1 次是正确的

这里有一个关键判断：同层所有列头节点的文本换行行数是否相同？

答案是：在 S2 的当前实现中，列头高度由该层文本的最大换行数决定。S2 在 calculateColNodesHeight 之前已经通过 updateColsHierarchySampleMaxHeightNodes 确定了每层的采样节点（高度最大的节点）。所以 getColNodeHeight 在该层上的结果对所有非 Totals 节点相同。

换句话说：如果该层最宽的列头文本需要 2 行，那该层所有列头都是 2 行高。S2 不会让同一层的列头高度不同——那样布局会错乱。所以缓存"该层第一个节点的测量结果"给整层用，是正确的。

六、为什么不用 S2 内置的缓存机制

S2 的 getColNodeHeight 本身有缓存参数，但原版显式传了 useCache: false：

javascript this.getColNodeHeight({ colNode: currentNode, colsHierarchy, useCache: false });

修改后不在节点级别缓存，而是在层级别 缓存（fixedColHeight），粒度更粗但足够正确，且避免了缓存失效问题。这比 S2 原生的节点级缓存更激进，但也更简单。

这里有一个权衡：节点级缓存的正确性更高（每个节点单独缓存，不会漏掉差异），但缓存失效管理复杂；层级别缓存假设同层高度一致，正确性依赖 S2 的布局约束，但实现简单且没有失效问题。我们选择了层级别，因为 S2 的布局约束保证了同层高度一致。

七、另外两处修改：导出性能

7.1 base-data-cell-copy.js：禁用 HTML 转换

导出时不需要 HTML 格式，跳过这一步省掉大量字符串拼接和 DOM 解析。

7.2 pivot-data-cell-copy.js：分块处理 + 进度事件

导出 100 万行数据时，单次 requestIdleCallback 处理可能被用户交互打断。改用 requestAnimationFrame 保证每帧都推进，setTimeout(0) 处理长任务切片，避免阻塞 UI。

7.3 为什么 requestIdleCallback 不够好

requestIdleCallback 的问题是：它只在浏览器空闲时回调，但如果用户一直在操作页面（比如滚动），浏览器可能永远不"空闲"，回调一直不触发，导出进度卡在 0%。改用 requestAnimationFrame 后，每帧都会回调，保证导出一定在推进。setTimeout(0) 用于在帧与帧之间让出主线程，避免单帧内处理太多行导致掉帧。

八、patch 管理与正确性保障

8.1 最小化修改原则

每处修改只改"确实有性能问题"的部分，不改业务逻辑：

  • hierarchy.js 只新增索引结构和查询方法，不改 pushNode 的核心逻辑
  • pivot-facet.js 只缓存 getColNodeHeight 结果，不改高度计算公式
  • base-data-cell-copy.js 只禁用一个 transformer
  • pivot-data-cell-copy.js 只改调度方式和加容错

8.2 等价性验证

修改前后跑相同的测试数据集，对比渲染结果（单元格坐标、文本内容）是否一致。fixedColHeight 缓存的正确性已验证——同层所有非 Totals 节点确实共用同一高度，总计节点仍走 colsHierarchy.height 分支。

8.3 patch 文件管理

修改以 patches/@antv__s2.patch 形式保存，与 npm 包版本绑定。升级时重新应用 patch 并跑回归测试。

版本升级时 patch 冲突了怎么办 ：patch 基于 S2 2.7.2 版本。升级时先比对新版本对应文件的差异，如果修改部分未变则 patch 仍适用；如果 S2 在这部分重构了代码，需要重新分析性能瓶颈并生成新 patch。这是开源项目修改的通用维护成本。

用图来看 patch 的生命周期：

mermaid graph TD A[修改 S2 源码 基于 2.7.2] --> B[生成 patch patches/@antv__s2.patch] B --> C[npm install 自动应用 patch] C --> D[运行时使用 O(N) 布局计算] E[S2 升级新版本] --> F{修改部分是否变化?} F -- 未变 --> C F -- 已重构 --> G[重新分析瓶颈 生成新 patch] G --> B

8.4 为什么选择 patch 而不是 fork

patch 方案的好处：改动最小化，升级时只需要重新应用 patch，不需要维护一个完整的 fork。代价：每次升级都要检查 patch 是否适用。对于 S2 这种活跃开发的项目，patch 冲突是常态，需要建立回归测试流程来快速发现。

九、已知边界

自定义列头场景 ：fixedColHeight 缓存在自定义列头（custom fields）下可能不完全正确，因为自定义列头的文本差异大，换行行数可能不同。但 S2 在 calculateColNodesHeight 之后有 adjustCustomColLeafNodesHeight 修正步骤，会针对自定义列头节点重新计算高度。所以 fixedColHeight 是"默认值"，自定义列头会被后续步骤覆盖。这个修正确实生效——但这是已知的待验证边界。

用图来看这个修正流程：

mermaid graph LR A[calculateColNodesHeight fixedColHeight 缓存] --> B[所有节点设为统一默认高度] B --> C{节点是自定义列头?} C -- 否 --> D[保持 fixedColHeight] C -- 是 --> E[adjustCustomColLeafNodesHeight 重新 measureText 覆盖为真实高度]

9.1 为什么这个边界可以接受

自定义列头是少数场景（大部分列头使用默认的维度值显示）。即使 fixedColHeight 在自定义列头场景下不完全正确，后续的 adjustCustomColLeafNodesHeight 会覆盖。所以最坏情况是：自定义列头的高度计算多了一次 measureText 调用——这比原版的 N 次仍然少得多。

十、这一层没有做的事

  • 没有改行头计算 ：行头在透视图里通常只有一层或两层，调用次数远少于列头，ROI 低
  • 没有改 DataSet 的数据解析 ：那属于前几篇的优化范围
  • 没有改 Canvas 渲染 ：S2 的 canvas 渲染本身已经够优化，瓶颈在布局计算

四篇系列到此结束。总结：应用层砍 30 万 Proxy，存储层 132MB→25MB 列式，线程层 structuredClone 559ms→0ms，布局层 O(n²)→O(n)。每一项都对应一个具体的、可量化的底层开销——优化的本质是"把 JS 引擎和浏览器原本要做、但这里并不需要的工作，明确地不做"。

English / 原文

背景：同一篇，百万行透视表。前三篇讲了应用层（砍 30 万 Proxy）、存储层（132MB → 25MB 列式）、线程层（Worker 常驻 + 零拷贝）。这篇讲布局层——直接改 AntV S2 源码，把列头高度计算从 O(n²) 降到 O(n)。

本文会讲清楚：为什么列头计算是性能瓶颈、怎么把计算量从平方级降到线性级、以及改开源代码怎么管理 patch 和保证正确性。

这是这个系列的四篇里的第四篇，讲的是布局层——直接改 S2 源码把列头计算从 O(n²) 降到 O(n)。前三篇分别是应用层、存储层和线程层，这篇是收尾。

一、先定位问题在 S2 的哪个环节

S2（AntV S2）是 canvas 透视表引擎。数据从加载到屏幕的路径：

graph LR
    A[原始数据] --> B[DataSet 解析 聚合] --> C[Facet 布局计算] --> D[Canvas 渲染]
    E[columnar.js packColumnar 列式 groupBy] --> B
    F[hierarchy.js getNodes O(1)] --> C
    G[pivot-facet.js fixedColHeight 缓存] --> C
    H[data-cell-copy.js 导出优化] --> D

前三篇的优化都在 DataSet 和数据传输层。这篇改的是 Facet 层 ——S2 的布局计算引擎。

Facet 干的事：根据数据和字段配置，计算每个单元格的坐标（x, y, width, height），构建行/列层级树，然后交给 Canvas 画出来。

列头高度计算 是 Facet 每次渲染都要做的工作。数据量大时，这里是卡顿的直接来源。

二、getColNodeHeight：S2 最昂贵的函数

先看 getColNodeHeight 干了什么：

getColNodeHeight({ colNode, colsHierarchy, useCache }) {
  const { colHeight, colWidth } = this.getColNodeSize(...);
  
  const { width } = this.spreadsheet.measureText(colNode.label, colNode);
  
  const lineCount = Math.ceil(width / colWidth);
  return lineCount * lineHeight;
}

2.1 measureText 为什么贵

measureText 是 canvas API，调用浏览器的文本测量逻辑。每次调用都要：

  1. 创建/查找 canvas 上下文
  2. 设置字体样式（字体、字号、加粗等）
  3. 调用 ctx.measureText(text)——浏览器底层的 glyph 索引 + 像素宽度计算
  4. 返回 TextMetrics 对象

第 3 步是核心开销。ctx.measureText(text) 不是简单的"字符数 × 字符宽度"。它要查字体文件中的 glyph 索引，按照字体的 kerning（字距调整）信息逐对计算，累加每个 glyph 的 advance width，返回精确的像素宽度。

这是 S2 里最昂贵的单步操作之一 。文本测量的代价和文本长度成正比，透视表的列头往往是长字符串（如维度值拼接），测量开销不可忽视。

2.2 为什么原版要对每个节点都调一次

S2 的 getColNodeHeight 本身有缓存参数，但原版显式传了 useCache: false：

this.getColNodeHeight({ colNode: currentNode, colsHierarchy, useCache: false });

useCache: false 的含义是强制绕过缓存 。原因可能是 S2 的缓存以节点为 key，不同节点即使同层也要分别查缓存，而且缓存可能在数据变化时失效不及时。

这意味着原版代码里，每个列节点都要做一次完整的 measureText 。

三、原版代码：O(n²) 是怎么形成的

3.1 calculateColNodesHeight 的原始实现

calculateColNodesHeight(colsHierarchy) {
  const colNodes = colsHierarchy.getNodes();  
  colNodes.forEach((currentNode) => {
    if (currentNode.level === 0) {
      currentNode.y = 0;
    } else {
      const preLevelSample = this.getPreLevelSampleNode(currentNode, colsHierarchy);
      currentNode.y = preLevelSample?.y + preLevelSample?.height || 0;
    }
    
    const colNodeHeight = this.getColNodeHeight({
      colNode: currentNode,
      colsHierarchy,
      useCache: false,
    });
    currentNode.height = currentNode.isGrandTotals && !currentNode.isTotalMeasure && currentNode.isLeaf
      ? colsHierarchy.height
      : colNodeHeight;
    layoutCoordinate(this.spreadsheet, null, currentNode);
  });
}

问题一目了然：colNodes.forEach 对每个节点都调用一次 getColNodeHeight。如果列层级树有 N 个节点，就是 N 次 measureText。

3.2 getPreLevelSampleNode 的叠加

getPreLevelSampleNode(colNode, colsHierarchy) {
  return colsHierarchy
    .getNodes(colNode.level - 1)        
    .find((node) => !node.isTotals);    
}

getNodes(level) 原版是 .filter() 整个节点数组——O(n)。.find() 最坏也是 O(n)。所以每个列节点都要花 O(n) 找上一层的采样节点。

3.3 复杂度汇总

原版 calculateColNodesHeight:
  对每个节点 i ∈ [0, N):
    getPreLevelSampleNode(i)        // O(n) — getNodes(level-1).find() 扫描该层全部节点
    getColNodeHeight(i)             // O(T) — T 是文本测量开销

  总复杂度: N × (n + T)
  最坏情况 n ≈ N → O(N²)

用图来看这个平方级开销是怎么一层层叠起来的：

graph TD
    A[遍历 N 个列节点] --> B{每个节点 i}
    B --> C[getPreLevelSampleNode i O(n) 扫描该层全部节点]
    B --> D[getColNodeHeight i O(T) measureText]
    C --> E[累计 N 乘 n]
    D --> F[累计 N 乘 T]
    E --> G[总复杂度 O(N平方) N=10000 时 1 亿次比较]
    F --> G

100 万行数据，透视后列数可能 100010000 个，层级深度 2 5 层。每次渲染调用 getNodes 约 10000 次，每次 O(10000) = 1 亿次比较 。加上 N 次 measureText，渲染一帧就要几百毫秒。

3.4 为什么这是个严重问题

S2 的渲染是每帧都调的。60fps 要求每帧在 16.6ms 内完成。如果 calculateColNodesHeight 就要几百毫秒，意味着用户拖动滚动条时页面完全卡死 ——不是掉帧，是整页冻结。这是百万行透视表"拖拽列头卡顿"的直接原因。

四、修改后：O(n) 怎么做到的

4.1 改动点 A：getNodes 从 O(n) 降到 O(1)

在 hierarchy.js 的 Hierarchy 类里新增 nodesByLevel Map：

class Hierarchy {
  constructor() {
    
    this.allNodesWithoutRoot = [];
    this.indexNode = [];

    
    this.nodesByLevel = new Map();
    
    this.firstNormalNodeByLevel = new Map();
  }

  
  getNodes(level) {
    if (level !== undefined) {
      return this.nodesByLevel.get(level) || [];   
    }
    return this.allNodesWithoutRoot;
  }

  
  getFirstNormalNodeOfLevel(level) {
    return this.firstNormalNodeByLevel.get(level);
  }

  
  pushNode(node, insetIndex = -1) {
    if (insetIndex === -1) {
      this.allNodesWithoutRoot.push(node);
    } else {
      this.allNodesWithoutRoot.splice(insetIndex, 0, node);
    }

    
    const levelNodes = this.nodesByLevel.get(node.level);
    if (levelNodes) {
      levelNodes.push(node);
    } else {
      this.nodesByLevel.set(node.level, [node]);
    }

    
    if (!node.isTotals && !this.firstNormalNodeByLevel.has(node.level)) {
      this.firstNormalNodeByLevel.set(node.level, node);
    }
  }

  
  clear() {
    this.allNodesWithoutRoot = [];
    this.nodesByLevel.clear();
    this.firstNormalNodeByLevel.clear();
    this.indexNode = [];
  }
}

索引维护的代价：每次 pushNode 做 2 次 Map 操作（get/set），是 O(1)。总节点数 n，维护索引的总代价是 O(n)，与构建层级树本身同阶，不增加复杂度 。

4.2 改动点 B：getPreLevelSampleNode 改用 O(1) 缓存

getPreLevelSampleNode(colNode, colsHierarchy) {
  return colsHierarchy
    .getNodes(colNode.level - 1)
    .find((node) => !node.isTotals);
}


getPreLevelSampleNode(colNode, colsHierarchy) {
  return colsHierarchy.getFirstNormalNodeOfLevel(colNode.level - 1);
}

4.3 改动点 C：calculateColNodesHeight 缓存列高——核心优化

calculateColNodesHeight(colsHierarchy) {
  const colNodes = colsHierarchy.getNodes();
  let fixedColHeight = null;   
  colNodes.forEach((currentNode) => {
    if (currentNode.level === 0) {
      currentNode.y = 0;
    } else {
      const preLevelSample = this.getPreLevelSampleNode(currentNode, colsHierarchy);
      currentNode.y = preLevelSample?.y + preLevelSample?.height || 0;
    }
    
    if (fixedColHeight === null) {
      fixedColHeight = this.getColNodeHeight({
        colNode: currentNode,
        colsHierarchy,
        useCache: false,
      });
    }
    
    currentNode.height = fixedColHeight;
    if (currentNode.isGrandTotals && !currentNode.isTotalMeasure && currentNode.isLeaf) {
      currentNode.height = colsHierarchy.height;
    }
    layoutCoordinate(this.spreadsheet, null, currentNode);
  });
}

关键变化：getColNodeHeight 从 每个节点调一次 降为 每层调一次 （只在 fixedColHeight === null 时调）。

4.4 为什么"同层共用同一高度"是正确的

这个假设的依据：列头高度由该层文本的最大换行数决定。S2 在 calculateColNodesHeight 之前已经通过 updateColsHierarchySampleMaxHeightNodes 确定了每层的采样节点（高度最大的节点）。所以 getColNodeHeight 在该层上的结果对所有非 Totals 节点相同。

总计节点仍走colsHierarchy.height 分支，不复用 fixedColHeight，所以不会影响总计行的布局。

五、复杂度分析：形式化

5.1 修改前

对每个节点 i ∈ [0, N):
  getPreLevelSampleNode(i)        // O(n) — getNodes(level-1).find() 扫描该层全部节点
  getColNodeHeight(i)             // O(T) — T 是文本测量开销

总复杂度: N × (n + T)
最坏情况 n ≈ N → O(N²)

5.2 修改后

对每个节点 i ∈ [0, N):
  getPreLevelSampleNode(i)        
  仅 i=0 时 getColNodeHeight(0)   
  其余节点复用 fixedColHeight    

总复杂度: N × 1 + T → O(N)

用图来看这个线性化是怎么做到的：

graph TD
    A[遍历 N 个列节点] --> B{每个节点 i}
    B --> C[getPreLevelSampleNode i O(1) Map 查找]
    B --> D{i = 0}
    D -- 是 --> E[getColNodeHeight 0 O(T) measureText 仅一次]
    D -- 否 --> F[复用 fixedColHeight O(1)]
    C --> G[总复杂度 O(N) N=10000 时 1 万次操作]
    E --> G
    F --> G

从 O(N²) 降到 O(N)，在 N=10000 时是 10000 倍的差距。

5.3 为什么 measureText 从 N 次降到 1 次是正确的

这里有一个关键判断：同层所有列头节点的文本换行行数是否相同？

答案是：在 S2 的当前实现中，列头高度由该层文本的最大换行数决定。S2 在 calculateColNodesHeight 之前已经通过 updateColsHierarchySampleMaxHeightNodes 确定了每层的采样节点（高度最大的节点）。所以 getColNodeHeight 在该层上的结果对所有非 Totals 节点相同。

换句话说：如果该层最宽的列头文本需要 2 行，那该层所有列头都是 2 行高。S2 不会让同一层的列头高度不同——那样布局会错乱。所以缓存"该层第一个节点的测量结果"给整层用，是正确的。

六、为什么不用 S2 内置的缓存机制

S2 的 getColNodeHeight 本身有缓存参数，但原版显式传了 useCache: false：

this.getColNodeHeight({ colNode: currentNode, colsHierarchy, useCache: false });

修改后不在节点级别缓存，而是在层级别 缓存（fixedColHeight），粒度更粗但足够正确，且避免了缓存失效问题。这比 S2 原生的节点级缓存更激进，但也更简单。

这里有一个权衡：节点级缓存的正确性更高（每个节点单独缓存，不会漏掉差异），但缓存失效管理复杂；层级别缓存假设同层高度一致，正确性依赖 S2 的布局约束，但实现简单且没有失效问题。我们选择了层级别，因为 S2 的布局约束保证了同层高度一致。

七、另外两处修改：导出性能

7.1 base-data-cell-copy.js：禁用 HTML 转换

导出时不需要 HTML 格式，跳过这一步省掉大量字符串拼接和 DOM 解析。

7.2 pivot-data-cell-copy.js：分块处理 + 进度事件

导出 100 万行数据时，单次 requestIdleCallback 处理可能被用户交互打断。改用 requestAnimationFrame 保证每帧都推进，setTimeout(0) 处理长任务切片，避免阻塞 UI。

7.3 为什么 requestIdleCallback 不够好

requestIdleCallback 的问题是：它只在浏览器空闲时回调，但如果用户一直在操作页面（比如滚动），浏览器可能永远不"空闲"，回调一直不触发，导出进度卡在 0%。改用 requestAnimationFrame 后，每帧都会回调，保证导出一定在推进。setTimeout(0) 用于在帧与帧之间让出主线程，避免单帧内处理太多行导致掉帧。

八、patch 管理与正确性保障

8.1 最小化修改原则

每处修改只改"确实有性能问题"的部分，不改业务逻辑：

  • hierarchy.js 只新增索引结构和查询方法，不改 pushNode 的核心逻辑
  • pivot-facet.js 只缓存 getColNodeHeight 结果，不改高度计算公式
  • base-data-cell-copy.js 只禁用一个 transformer
  • pivot-data-cell-copy.js 只改调度方式和加容错

8.2 等价性验证

修改前后跑相同的测试数据集，对比渲染结果（单元格坐标、文本内容）是否一致。fixedColHeight 缓存的正确性已验证——同层所有非 Totals 节点确实共用同一高度，总计节点仍走 colsHierarchy.height 分支。

8.3 patch 文件管理

修改以 patches/@antv__s2.patch 形式保存，与 npm 包版本绑定。升级时重新应用 patch 并跑回归测试。

版本升级时 patch 冲突了怎么办 ：patch 基于 S2 2.7.2 版本。升级时先比对新版本对应文件的差异，如果修改部分未变则 patch 仍适用；如果 S2 在这部分重构了代码，需要重新分析性能瓶颈并生成新 patch。这是开源项目修改的通用维护成本。

用图来看 patch 的生命周期：

graph TD
    A[修改 S2 源码 基于 2.7.2] --> B[生成 patch patches/@antv__s2.patch]
    B --> C[npm install 自动应用 patch]
    C --> D[运行时使用 O(N) 布局计算]
    E[S2 升级新版本] --> F{修改部分是否变化?}
    F -- 未变 --> C
    F -- 已重构 --> G[重新分析瓶颈 生成新 patch]
    G --> B

8.4 为什么选择 patch 而不是 fork

patch 方案的好处：改动最小化，升级时只需要重新应用 patch，不需要维护一个完整的 fork。代价：每次升级都要检查 patch 是否适用。对于 S2 这种活跃开发的项目，patch 冲突是常态，需要建立回归测试流程来快速发现。

九、已知边界

自定义列头场景 ：fixedColHeight 缓存在自定义列头（custom fields）下可能不完全正确，因为自定义列头的文本差异大，换行行数可能不同。但 S2 在 calculateColNodesHeight 之后有 adjustCustomColLeafNodesHeight 修正步骤，会针对自定义列头节点重新计算高度。所以 fixedColHeight 是"默认值"，自定义列头会被后续步骤覆盖。这个修正确实生效——但这是已知的待验证边界。

用图来看这个修正流程：

graph LR
    A[calculateColNodesHeight fixedColHeight 缓存] --> B[所有节点设为统一默认高度]
    B --> C{节点是自定义列头?}
    C -- 否 --> D[保持 fixedColHeight]
    C -- 是 --> E[adjustCustomColLeafNodesHeight 重新 measureText 覆盖为真实高度]

9.1 为什么这个边界可以接受

自定义列头是少数场景（大部分列头使用默认的维度值显示）。即使 fixedColHeight 在自定义列头场景下不完全正确，后续的 adjustCustomColLeafNodesHeight 会覆盖。所以最坏情况是：自定义列头的高度计算多了一次 measureText 调用——这比原版的 N 次仍然少得多。

十、这一层没有做的事

  • 没有改行头计算 ：行头在透视图里通常只有一层或两层，调用次数远少于列头，ROI 低
  • 没有改 DataSet 的数据解析 ：那属于前几篇的优化范围
  • 没有改 Canvas 渲染 ：S2 的 canvas 渲染本身已经够优化，瓶颈在布局计算

四篇系列到此结束。总结：应用层砍 30 万 Proxy，存储层 132MB→25MB 列式，线程层 structuredClone 559ms→0ms，布局层 O(n²)→O(n)。每一项都对应一个具体的、可量化的底层开销——优化的本质是"把 JS 引擎和浏览器原本要做、但这里并不需要的工作，明确地不做"。