算法与复杂度

「虚拟滚动原理」讲的是整体流程，这一页讲的是让流程在几十万条数据下依然成立的具体算法。

n 表示数据总量。所有耗时都是在 30 万条不定高数据上实测的量级，仅供参考——真实数字请用首页的实测面板在你自己的设备上跑。

复杂度总览

操作	固定高	不定高	说明
稳态滚动定位	O(1)	O(1)	从上一帧的位置增量推进
跳转到任意项	O(1)	O(√n)	固定高一次除法；不定高走分块索引
查询某项的顶部偏移	O(1)	O(√n)	同上
单项尺寸变化后修正	—	O(1)	只改渲染块那一个 transform
渲染窗口 DOM 节点数	O(视口)	O(视口)	与数据量无关
整体替换数据源	O(1)	O(n)	总尺寸依赖每一项，这一趟省不掉

除最后一行，其余都与数据量无关或近似无关。下面逐个说明是怎么做到的，以及最后一行为什么做不到。

位置查询：分块尺寸索引

不定高列表有一个绕不开的困难：第 i 项的顶部偏移等于前面所有项的尺寸之和。项高只有渲染后才能实测，无法像固定高那样用乘法算出，朴素实现就只能从头累加，即 O(i)。

30 万条列表滚到中段时，这一次累加约 2.3ms。单看不算多，但它出现在热路径上——每次跳转、每次滚动锚点求解都要算一遍，一旦每帧发生几次就吃掉了整个帧预算。

ChunkedSizeIndex 把列表切成定长的块（默认 1024 项一块），只缓存每块的尺寸总和：

块 0            块 1            块 2
[0 .. 1023]     [1024 .. 2047]  [2048 .. 3071]   ...
   sum₀            sum₁            sum₂

于是两个核心查询都变成「跨块查表 + 块内累加」：

prefix(index)  —— [0, index) 的尺寸之和
  1. 累加 index 所在块之前的全部块和        → 最多 n/1024 次
  2. 在块内从块首逐项累加到 index          → 最多 1024 次

locate(offset) —— offset 落在第几项
  1. 逐块累加，跳过整块，直到 offset 落入某块 → 最多 n/1024 次
  2. 在块内逐项推进，找到目标项              → 最多 1024 次

两步之和是 n / 1024 + 1024：n = 30 万时约 1300 次运算，而不是 30 万次。

关于 O(√n) 这个说法

块大小固定为 1024，严格写应是 O(n/C + C)。这个式子在 C = √n 时取到最小，也是分块结构的理论最优，因此习惯上记作 O(√n)。就本项目关心的十万至百万量级而言，1024 已经接近最优取值（30 万条的理论最优约 548，两者成本相差不到 20%），没有必要随数据量动态调整。

为什么只缓存块和，不缓存每项尺寸

把每项尺寸也复制进索引会让块内累加从「查表」变成「读数组」，更快。但那样单项尺寸就有了两个存放处——sizesMap 和索引内部的副本，两者一旦不同步就会算出错误的偏移量，而这种 bug 表现为「偶尔跳一下」，极难排查。

所以索引只持有块和这一层派生数据，单项尺寸的唯一权威来源始终是 sizesMap。块内那几百次查表的代价，换来的是不可能出现状态分歧。

尺寸变化时的增量更新

ResizeObserver 上报某项的实测尺寸后，只需修正它所属那一块的和与总和，与列表长度无关：

applyDelta(index, delta):
  chunkSums[index / 1024] += delta
  total += delta

这要求知道项的索引，而 ResizeObserver 只给得到 key（DOM 上的 data-id）。引擎为此让渲染窗口维护一张 key → 索引 的映射——被观察的项必定在窗口内，所以这张只有几十项的表就够用了。

窗口之外的项若上报了尺寸（例如头部插入的新项还没进入视口就完成测量），块和便不再可信，此时索引整体置为待重建，下次查询时重扫一遍。这种情况很罕见，用一次 O(n) 换取实现上的确定性是划算的。

惰性重建

reset() 只记录新长度并打上标记，真正的扫描推迟到下一次查询。列表替换后如果没有任何查询发生，这一趟就不会执行。

区间定位：增量搜索与索引回退

有了 O(√n) 的 locate()，是否所有定位都交给它？不是——稳态滚动比它更快。

用户正常滚动时，每帧只跨越几项。从上一帧的 inViewBegin 出发逐项推进，通常 1~3 步就能找到新起点，这是 O(1) 级的，比走索引的上千次运算便宜得多。

所以引擎保留增量搜索作为快路径，但给它设了步数上限（内部常量 MAX_INCREMENTAL_STEPS，取 64）：

• 跨越 ≤ 64 项：增量搜索，几步搞定
• 跨越更远：放弃增量，改用 locate() 直接定位

一次性大跳（scrollToBottom()、End 键、拖动滚动条到底、恢复滚动位置）正是后者。没有这个上限时，从头拖到尾要走完 30 万次迭代、约 55ms，掉三四帧；有了上限后是 0.2ms。

两条路径必须给出同一答案

同一个目标偏移量，无论走增量搜索还是索引定位，得出的 inViewBegin、inViewEnd、leadingSize 都必须完全一致，否则滚动过程中会出现「快速滚过去和慢慢滚过去看到的内容不一样」。core 的测试用例专门比对这两条路径的结果。

两条 O(1) 快路径

有两种情形下，所有项的尺寸是均匀的，位置可以直接算出来，完全不必经过索引：

固定高（fixedSize: true）：每项都是 estimatedSize + itemGap。定位是一次除法，前缀和是一次乘法，全部 O(1)。

尚无任何实测尺寸：sizesMap 为空时，每项都回落到预估尺寸，等价于固定高。这正是首次装载的情形——此时遍历几十万项去查一张空表纯属做白工。加上这条判断后，30 万条列表的首次挂载从 67.6ms 降到 0.7ms。

这条快路径的收益被低估了

首屏是用户唯一无法回避的等待。而首屏恰好是「一项都还没测量过」的时刻，也就是这条快路径唯一确定生效的时刻。

不定高的视口稳定：滚动锚点

向列表头部滚动时，上方的项刚进入渲染窗口，尺寸还是预估值；ResizeObserver 测出真实尺寸后，如果预估偏小，这些项会「长高」，把下方的内容整体推走——用户看到的画面就会跳动。

一种做法是补偿位移：测得尺寸变化 diff，就令 offset += diff。它的问题是无法区分变化发生在视口上方还是下方——下方项变高本不该移动视口，却也会被补偿。

引擎采用的是求解不变量：以视口顶部的那一项为锚点，记下它的索引与视口相对它的偏移；此后每当尺寸变化，就重新解一次「让这一项回到原位」的偏移量。

锚点 = { 参照项索引, 视口偏移 = offset − 该项顶部偏移 }

尺寸变化后：
  新 offset = 该项当前的顶部偏移 + 视口偏移

这个形式有两个好处：幂等——重复应用没有副作用，也不需要判断是否已经补偿过；自动忽略下方变化——锚点下方的项变高不会改变它自己的顶部偏移，解出来的位移自然为零。

参照项要选已经渲染测量过的项，它自身的尺寸才是稳定的。锚点在向列表头部跨项时立起，向尾部滚动意味着用户已离开原来那段内容，锚点随即作废。

修正之后必须同步内部状态

锚点写入新的偏移量后，引擎内部记录的「区间算到哪了」必须在同一帧内跟着更新。否则本帧的绘制用的是新位置，而渲染区间还按旧位置算——视口就落在没有 DOM 的地方，也就是一帧露白。向列表头部滚动时每次 ResizeObserver 回调都会走到这里，会被放大成连续白屏。

方向也必须一起更新：区间定位的增量搜索是按方向分支的，方向不对时两个分支都不进，区间就原地不动（贴底求解正是这种情形——目标比当前位置更靠上）。

这套机制曾经是三套

偏移量归 JS 掌管之前，这件事由三套并行机制分别做（锚点求解 + 两端轮询 + 索引轮询，共 237 行）：原生滚动下既不知道浏览器会把 scrollTop 夹到哪，也分不清是谁动的它。

两个前提消失后，三套塌缩成上面这一套——不需要收敛判据、不需要重试上限、也不需要「这次是谁写的」标记窗口。

leadingSize 的维护

renderBegin 之前的所有项不渲染 DOM，它们的累计尺寸记作 leadingSize。它是渲染窗口那一整块的位移量（写进 itemsEl 的 transform），不是某个占位元素的高度——没有占位元素。

稳态滚动时它走增量更新：renderBegin 只挪动几项，加减这几项的尺寸即可。但一次性大跳时两端相距成千上万项，「增量」累加本身就成了 O(n)——所以跨越距离超过上限时，改用索引重算前缀和。

这是与区间定位同一套判断，两者必须一起处理：只改定位不改这里，大跳跃仍然会慢一半。

总尺寸为什么仍是 O(n)

滚动条的长度由 itemsTotalSize 决定，而它是所有项尺寸之和——任何一项的高度都会影响它，所以整体替换数据源时必须把新列表扫一遍。30 万条约 31ms。

理论上可以反过来只遍历 sizesMap（通常只有几十项已测量），用「n × 预估尺寸 + 已测量项的偏差之和」算出总和。但那需要判断每个已测量的 key 是否还在新列表中，而这个判断本身就是 O(n)。若乐观地假设 key 都还在，换一批全新数据时总高就会算错，滚动条长度随之出错——这个代价不值得。

能做的是压低常数：已经把重建时的属性读取提到循环外，并让「尚无实测尺寸」的情形走乘法。剩下的是每项一次查表，属于固有成本。

它不在每帧路径上

setList 是数据替换时的一次性开销，不是滚动开销。滚动本身与数据量无关，30 万条和 30 条是同一个量级（实测 0.1~0.2ms）。

实测量级

30 万条不定高数据，桌面 Chrome（2026-08 实测，用的就是首页那个面板的代码）。 「处理一次滚动」走的是滚轮 / 键盘 / 拖动滑块的真实路径（scrollFromUser）：

操作	耗时
处理一次滚动	0.23ms
首次挂载并渲染	0.6ms
跳转到任意项	0.5ms
首尾之间整程跨越	0.36ms
整体替换数据源	95ms

固定高模式下任意项的位置由乘除法直接算出，与数据量无关。差别最大的是 setList—— 不必逐项累加总尺寸，从 95ms 降到 0.06ms：

操作	不定高	固定高
处理一次滚动	0.23ms	0.14ms
跳转到任意项	0.5ms	0.29ms
首尾之间整程跨越	0.36ms	0.18ms
整体替换数据源	95ms	0.06ms

「首次挂载并渲染」没有列进这张对照表：它的耗时主要花在首屏那十几个节点的创建与 测量上，与索引结构关系不大，两次运行之间的机器负载波动就足以盖过模式差异。

这些数字随设备与浏览器变化，首页的实测面板会在你自己的设备上重新跑一遍。