100 万节点里搜 3 个字：倒排桶、5000 条截断与祖先补全

前情：《MPTT 不是万能编号：一棵百万节点树的增删改与批量事务》 讲了“写”，《WASM 不是银弹》 算的是边界账。这篇讲“读”的另一种形态：搜索。

在 100 万节点的树里搜一个 3 字关键词，最慢的不是“找”，而是“把找到的节点接回树上”。我原本以为搜索的瓶颈是字符串匹配，实测下来：在各自场景里，匹配只占几毫秒到 25ms，祖先补全能到 500ms。这篇文章按顺序拆——匹配、候选桶、截断、补祖先、缓存、变成视口——每一段都给代码、复杂度和本机实测，最后说清楚候选索引什么时候值得开、什么时候不值得。

先给一组数字，避免你看到一半才发现方向不对：

第一行和第三行放在一起看很反直觉：命中越多的词，反而搜得越快。原因不在匹配算法，而在截断——搜索到 5000 个命中就停了，而稀有词要扫完 100 万行才能确认“没有更多”。 第四行是这篇文章真正想讲的部分：匹配只有几毫秒，剩下 500ms 全在补祖先。

如果只记一句话：

候选桶优化的是“扫描范围”，截断优化的是“结果规模”，祖先补全的成本由“命中数 × 平均深度”决定。三者不能互相替代。

文中所有数据都来自这个项目 vue3-giant-tree-wasm：Vue 3 + AssemblyScript/WASM，BSD-2-Clause，npm 包名 vue3-giant-tree-wasm。搜索主体在 assembly/tree-search.ts，视图切换与缓存位于 assembly/giant-tree.ts，高亮在 lib/TreeItem.vue。

搜索全流程一览

在逐段拆解之前，先把整条链路画出来。一次 fuzzySearch 从输入框到 DOM，会依次经过下面几个阶段，每个阶段都有各自的成本来源：

#mermaid-svg-qSSEtMyKPanvNh1H{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-qSSEtMyKPanvNh1H .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-qSSEtMyKPanvNh1H .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-qSSEtMyKPanvNh1H .error-icon{fill:#552222;}#mermaid-svg-qSSEtMyKPanvNh1H .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-qSSEtMyKPanvNh1H .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-qSSEtMyKPanvNh1H .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-qSSEtMyKPanvNh1H .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-qSSEtMyKPanvNh1H .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-qSSEtMyKPanvNh1H .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-qSSEtMyKPanvNh1H .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-qSSEtMyKPanvNh1H .marker{fill:#333333;stroke:#333333;}#mermaid-svg-qSSEtMyKPanvNh1H .marker.cross{stroke:#333333;}#mermaid-svg-qSSEtMyKPanvNh1H svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-qSSEtMyKPanvNh1H p{margin:0;}#mermaid-svg-qSSEtMyKPanvNh1H .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-qSSEtMyKPanvNh1H .cluster-label text{fill:#333;}#mermaid-svg-qSSEtMyKPanvNh1H .cluster-label span{color:#333;}#mermaid-svg-qSSEtMyKPanvNh1H .cluster-label span p{background-color:transparent;}#mermaid-svg-qSSEtMyKPanvNh1H .label text,#mermaid-svg-qSSEtMyKPanvNh1H span{fill:#333;color:#333;}#mermaid-svg-qSSEtMyKPanvNh1H .node rect,#mermaid-svg-qSSEtMyKPanvNh1H .node circle,#mermaid-svg-qSSEtMyKPanvNh1H .node ellipse,#mermaid-svg-qSSEtMyKPanvNh1H .node polygon,#mermaid-svg-qSSEtMyKPanvNh1H .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-qSSEtMyKPanvNh1H .rough-node .label text,#mermaid-svg-qSSEtMyKPanvNh1H .node .label text,#mermaid-svg-qSSEtMyKPanvNh1H .image-shape .label,#mermaid-svg-qSSEtMyKPanvNh1H .icon-shape .label{text-anchor:middle;}#mermaid-svg-qSSEtMyKPanvNh1H .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-qSSEtMyKPanvNh1H .rough-node .label,#mermaid-svg-qSSEtMyKPanvNh1H .node .label,#mermaid-svg-qSSEtMyKPanvNh1H .image-shape .label,#mermaid-svg-qSSEtMyKPanvNh1H .icon-shape .label{text-align:center;}#mermaid-svg-qSSEtMyKPanvNh1H .node.clickable{cursor:pointer;}#mermaid-svg-qSSEtMyKPanvNh1H .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-qSSEtMyKPanvNh1H .arrowheadPath{fill:#333333;}#mermaid-svg-qSSEtMyKPanvNh1H .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-qSSEtMyKPanvNh1H .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-qSSEtMyKPanvNh1H .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-qSSEtMyKPanvNh1H .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-qSSEtMyKPanvNh1H .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-qSSEtMyKPanvNh1H .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-qSSEtMyKPanvNh1H .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-qSSEtMyKPanvNh1H .cluster text{fill:#333;}#mermaid-svg-qSSEtMyKPanvNh1H .cluster span{color:#333;}#mermaid-svg-qSSEtMyKPanvNh1H div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-qSSEtMyKPanvNh1H .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-qSSEtMyKPanvNh1H rect.text{fill:none;stroke-width:0;}#mermaid-svg-qSSEtMyKPanvNh1H .icon-shape,#mermaid-svg-qSSEtMyKPanvNh1H .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-qSSEtMyKPanvNh1H .icon-shape p,#mermaid-svg-qSSEtMyKPanvNh1H .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-qSSEtMyKPanvNh1H .icon-shape .label rect,#mermaid-svg-qSSEtMyKPanvNh1H .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-qSSEtMyKPanvNh1H .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-qSSEtMyKPanvNh1H .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-qSSEtMyKPanvNh1H :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

否

是

否

输入关键词

关键词为空?

清空搜索状态回到 fullTree

命中缓存?同一关键词

复用 searchTree

匹配阶段indexOf 子串扫描

开启候选索引?

取最短字符桶缩小扫描范围

全表扫描

收集命中最多 5000 条

达到 MAX_RESULTS?

标记 truncated

继续扫描

祖先补全沿 parent 链上溯

按 leftNode 排序

重建搜索视图应用搜索折叠

只序列化视口serializeShownSlice

主线程渲染 DOM

这张图里最值得记住的是三个分叉点：候选索引开关决定扫描范围，5000 截断决定结果规模，祖先补全决定最坏耗时。后面每一节都在展开其中一个。

0. 为什么树搜索不是“过滤一个数组”

如果数据是平表，搜索就是一行 filter：

rows.filter(row => row.name.includes(keyword))

树不能这么写。假设你搜到了 研发一部-项目 42，但它的父节点 研发一部 本身不包含关键词。如果只把命中行放进结果，这行在树里就没有父节点，层级、缩进、展开箭头全部失效。

所以一个树搜索至少要产出两样东西：

这个项目的做法是：把两者都塞进一个独立的 searchTree 数组，按 MPTT 的 leftNode 排好序，然后交给虚拟滚动。searchTree 不改主树的 shown 标志，也不改主树的折叠状态。

// assembly/giant-tree.ts
fuzzySearch(keyword: string): string {
if (keyword === '') {
this._searchCollapsedIds.clear()
this._searchTruncated = false
this.tree = this.fullTree
resetShownFlags(this.fullTree)
this._rebuildShownNodes()
return serializeShownSlice(
this._shownNodes,
this.scrollTop,
this.scrollHeight,
this.lineHeight
)
}

if (!this._hasSearchCache || this._lastSearchKeyword !== keyword) {
this._searchCollapsedIds.clear()
if (this.useSearchCandidateIndex) this._ensureSearchCandidates()
this.shownCount = fuzzySearchTree(
this.fullTree,
this.searchTree,
keyword,
this._searchIdSet,
this._searchParents,
this.useSearchCandidateIndex ? this._searchCandidates : null,
this.compactStore.parent
)
this._searchTruncated = lastSearchTruncated
this._lastSearchKeyword = keyword
this._hasSearchCache = true
} else {
this.shownCount = this.searchTree.length
}

this.tree = this.searchTree
this._rebuildSearchShownNodes()
this._invalidateCache()
return serializeShownSlice(
this._shownNodes,
this.scrollTop,
this.scrollHeight,
this.lineHeight
)
}

这一段里藏着后面要展开的所有线索：

• useSearchCandidateIndex 是一个默认关闭的开关；
• compactStore.parent 是祖先补全用的索引；
• _hasSearchCache 让同一个关键词只算一次；
• 返回值是 serializeShownSlice，只序列化视口，不是整个结果。

1. 第一步：匹配

核心循环只有十几行：

// assembly/tree-search.ts
const MAX_RESULTS: i32 = 5000
lastSearchTruncated = false
let matchCount: i32 = 0
let candidates: i32[] | null = null

if (candidateIndex !== null && keyword.length > 0) {
for (let i: i32 = 0; i < keyword.length; i++) {
const key = keyword.charAt(i)
if (!candidateIndex.has(key)) {
candidates = []
break
}
const bucket = candidateIndex.get(key)
if (candidates === null || bucket.length < (candidates as i32[]).length) {
candidates = bucket
}
}
}

const scanCount = candidates !== null ? candidates.length : fullTree.length
for (let c: i32 = 0; c < scanCount; c++) {
const i = candidates !== null ? candidates[c] : c
const node: MpttTree = fullTree[i]
if (node.name.indexOf(keyword) !== –1) {
searchTree.push(node)
idSet.add(node.id)
matchedIndices.push(i)
matchCount++
if (matchCount >= MAX_RESULTS) {
lastSearchTruncated = true
break
}
}
}

没有正则、没有分词、没有编辑距离。indexOf 就是全部语义：区分大小写的子串匹配。这个选择很朴素，但它是后面所有优化的基准——先把最笨的版本跑通，再决定要不要加索引。 1M 宽树的实测：

25ms 看起来不算慢，但搜索是输入框的实时操作。用户每敲一个字符就搜一次，10 个字符就是 250ms 的主线程计算，再加上序列化和渲染，输入框会明显卡顿。项目因此在组件层加了 300ms 防抖（后面会讲），但 WASM 侧仍然值得把单次搜索做快。

2. 第二步：候选桶

2.1 数据结构

候选索引的本质是一个字符级倒排表：

// assembly/giant-tree.ts
_searchCandidates: Map<string, i32[]> = new Map<string, i32[]>()

private _buildSearchCandidates(): void {
this._searchCandidates.clear()
for (let i: i32 = 0; i < this.fullTree.length; i++) {
const name = this.fullTree[i].name
const seen: Set<string> = new Set<string>()
for (let j: i32 = 0; j < name.length; j++) {
const key = name.charAt(j)
if (seen.has(key)) continue
seen.add(key)
if (!this._searchCandidates.has(key))
this._searchCandidates.set(key, [])
const bucket = this._searchCandidates.get(key)
bucket.push(i)
}
}
this._searchCandidateIndexReady = true
}

每个节点对名字里出现过的不同字符各登记一次。seen 是为了避免 Node 111 里的三个 1 把同一个节点登记三次。

搜索时，遍历关键词的每个字符，取最短的那个桶作为候选集：

if (candidates === null || bucket.length < candidates.length) {
candidates = bucket
}

2.2 为什么取最小桶不会漏

这是一个很容易想错的点：取一个字符的桶，难道不会漏掉“包含完整关键词、但不包含这个字符”的节点吗？

不会。因为包含完整关键词的节点，必然包含关键词的每一个字符。所以它一定在每一个字符的桶里。取任意一个桶，都不会漏掉真正的命中；取最短的桶，只是把“一定不会漏”的集合缩到最小。

反过来说，桶里的节点不一定命中完整关键词。999 的桶里可能有 Node 1999，它确实包含 9，但不一定包含连续三个 9。所以候选集只是“候选”，最终仍要跑一次 indexOf：

if (node.name.indexOf(keyword) !== –1) { … }

这两步的分工是：

• 倒排桶：把 N 次 indexOf 变成 |桶| 次；
• indexOf：保证子串语义不变。

用一张图概括“取最小桶”的正确性推理：

#mermaid-svg-OUS7TDJRqOtgHYSt{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-OUS7TDJRqOtgHYSt .error-icon{fill:#552222;}#mermaid-svg-OUS7TDJRqOtgHYSt .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-OUS7TDJRqOtgHYSt .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-OUS7TDJRqOtgHYSt .marker{fill:#333333;stroke:#333333;}#mermaid-svg-OUS7TDJRqOtgHYSt .marker.cross{stroke:#333333;}#mermaid-svg-OUS7TDJRqOtgHYSt svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-OUS7TDJRqOtgHYSt p{margin:0;}#mermaid-svg-OUS7TDJRqOtgHYSt .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-OUS7TDJRqOtgHYSt .cluster-label text{fill:#333;}#mermaid-svg-OUS7TDJRqOtgHYSt .cluster-label span{color:#333;}#mermaid-svg-OUS7TDJRqOtgHYSt .cluster-label span p{background-color:transparent;}#mermaid-svg-OUS7TDJRqOtgHYSt .label text,#mermaid-svg-OUS7TDJRqOtgHYSt span{fill:#333;color:#333;}#mermaid-svg-OUS7TDJRqOtgHYSt .node rect,#mermaid-svg-OUS7TDJRqOtgHYSt .node circle,#mermaid-svg-OUS7TDJRqOtgHYSt .node ellipse,#mermaid-svg-OUS7TDJRqOtgHYSt .node polygon,#mermaid-svg-OUS7TDJRqOtgHYSt .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-OUS7TDJRqOtgHYSt .rough-node .label text,#mermaid-svg-OUS7TDJRqOtgHYSt .node .label text,#mermaid-svg-OUS7TDJRqOtgHYSt .image-shape .label,#mermaid-svg-OUS7TDJRqOtgHYSt .icon-shape .label{text-anchor:middle;}#mermaid-svg-OUS7TDJRqOtgHYSt .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-OUS7TDJRqOtgHYSt .rough-node .label,#mermaid-svg-OUS7TDJRqOtgHYSt .node .label,#mermaid-svg-OUS7TDJRqOtgHYSt .image-shape .label,#mermaid-svg-OUS7TDJRqOtgHYSt .icon-shape .label{text-align:center;}#mermaid-svg-OUS7TDJRqOtgHYSt .node.clickable{cursor:pointer;}#mermaid-svg-OUS7TDJRqOtgHYSt .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-OUS7TDJRqOtgHYSt .arrowheadPath{fill:#333333;}#mermaid-svg-OUS7TDJRqOtgHYSt .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-OUS7TDJRqOtgHYSt .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-OUS7TDJRqOtgHYSt .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-OUS7TDJRqOtgHYSt .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-OUS7TDJRqOtgHYSt .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-OUS7TDJRqOtgHYSt .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-OUS7TDJRqOtgHYSt .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-OUS7TDJRqOtgHYSt .cluster text{fill:#333;}#mermaid-svg-OUS7TDJRqOtgHYSt .cluster span{color:#333;}#mermaid-svg-OUS7TDJRqOtgHYSt div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-OUS7TDJRqOtgHYSt .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-OUS7TDJRqOtgHYSt rect.text{fill:none;stroke-width:0;}#mermaid-svg-OUS7TDJRqOtgHYSt .icon-shape,#mermaid-svg-OUS7TDJRqOtgHYSt .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-OUS7TDJRqOtgHYSt .icon-shape p,#mermaid-svg-OUS7TDJRqOtgHYSt .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-OUS7TDJRqOtgHYSt .icon-shape .label rect,#mermaid-svg-OUS7TDJRqOtgHYSt .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-OUS7TDJRqOtgHYSt .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-OUS7TDJRqOtgHYSt .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-OUS7TDJRqOtgHYSt :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

关键词: 999

字符 9 的桶

字符 9 的桶

字符 9 的桶

候选集 = 最短桶

逐个 indexOf 校验

真正的命中

被排除的伪命中如 Node 1999

进入 searchTree

丢弃

关键点在于：包含完整关键词的节点必然出现在每一个字符的桶里，所以取任意一个桶都不会漏；取最短的那个，只是把候选集缩到最小，后续 indexOf 负责把伪命中剔除。

2.3 建桶不是免费的

_buildSearchCandidates 的复杂度是 O(N × 名字平均长度)，而且在 AssemblyScript 里，每个节点都要新建一个 Set<string>，每个字符都要 charAt 出一个单字符字符串。这个分配成本正是它默认关闭的原因：

// Candidate buckets can halve median search time, but their per-character
// allocation is too expensive to enable for every tree by default.
useSearchCandidateIndex: bool = false

实测建桶成本：

100 万节点建一次桶要 1.3 秒，比建树本身还久。这意味着：如果用户只搜一两次，建桶永远不划算。

2.4 收益取决于桶有多小

同一棵 100 万英文宽树，开/关候选索引的对比：

中文树的数字更极端一点：

这张表比“候选索引能提速”本身更有用。它说明收益完全由最短桶的规模决定：

• 稀有字符（H、重）的桶很小，收益接近两个数量级；
• 常见字符（数字 9、项）的桶很大，收益迅速衰减；
• 全命中时最短桶就是全表，收益为零；
• 无命中时桶为空，直接返回，收益最大。

所以候选索引不是“开了就快”，而是“关键词里至少有一个稀有字符时才快”。

2.5 一个容易忽略的边界

charAt(j) 取的是 UTF-16 code unit。对 BMP 字符（ASCII、常用汉字）没问题；对 emoji 这类代理对，一个字符会被拆成两个 code unit，桶会更碎。但 indexOf 本身也是按 code unit 匹配的，所以“候选集不会漏”这个正确性不受影响，只是索引的粒度变了。

真正需要注意的是大小写。搜索和索引都区分大小写：Node 能命中 Node 42，node 一个都命中不了。中文没有这个问题，英文场景要在文档里写清楚，否则用户会以为是搜索出了故障。

3. 第三步：5000 条截断

3.1 截断发生在匹配阶段

MAX_RESULTS 的判断在匹配循环里：

if (matchCount >= MAX_RESULTS) {
lastSearchTruncated = true
break
}

它不是一个“结果列表渲染到 5000 条就停”的 UI 限制，而是收集阶段就停。这意味着：

• 命中 5000 个之后，后面的节点根本不会被检查；
• 最终 searchTree 的长度由“5000 个命中 + 它们的祖先”决定；
• 截断标志 lastSearchTruncated 会一直保留到下一次搜索。

3.2 为什么全命中反而快

再看一遍 100 万宽树的数据：

扫描成本由“最后一个命中出现的位置”决定，而不是命中数量。全命中时第 5000 个节点就攒够了，后面的 99.5 万行根本不看；稀有词和无命中必须扫到表尾才能确认“没有更多”。

这也是为什么候选索引对全命中没有收益：最短桶就是全表，扫描上限仍然是 5000 个命中，和关闭时完全一样。

3.3 截断后行数可能超过 5000

祖先补全发生在截断之后，所以最终结果行数是“5000 个命中 + 去重后的祖先”。深树实测：

所以“最多 5000 条”这个说法只对命中数成立，对 UI 看到的总行数不成立。文档里如果写“最多返回 5000 行”，会误导使用者。

3.4 把“不全”暴露出去

早期版本是静默截断：用户搜一个常见词，看到 5000 条，以为这就是全部。后来加了显式 API：

// assembly/index.ts
export function isSearchTruncated(target: GiantTree): bool {
return target.wasSearchTruncated()
}

组件层的用法很直接：

const truncated = treeRef.value?.isSearchTruncated()
if (truncated) {
// 提示：只显示了前 5000 个匹配，请补充关键词
}

一个布尔值就能避免“搜索结果看起来完整、实际上缺了一大半”的误解。这个改动的成本几乎为零，但不做的话，用户迟早会在几百万行的数据上踩到。

4. 第四步：祖先补全

4.1 代码

命中节点收集完之后，逐个向上走父链：

// assembly/tree-search.ts
if (parentIndices !== null) {
for (let i: i32 = 0; i < matchedIndices.length; i++) {
let parentIndex = parentIndices[matchedIndices[i]]
while (parentIndex >= 0) {
const parent = fullTree[parentIndex]
if (!idSet.has(parent.id)) {
idSet.add(parent.id)
parentNodes.push(parent)
}
parentIndex = parentIndices[parentIndex]
}
}
}

parentIndices 是 compactStore.parent，一个 Int32Array，根节点为 -1。它是在建树时顺带算出来的，搜索阶段不需要再遍历树。

idSet 里一开始装的是命中节点的 id，所以祖先补全会跳过已经命中过的节点；parentNodes 收集完后，直接追加到 searchTree 末尾，最后统一排序：

sortByLeftNode(searchTree)

4.2 复杂度

这段代码的复杂度不是 O(N)，而是：

O(命中数 × 平均祖先链长)

while 循环每次向上走一层，即使父节点已经在 idSet 里，也不会停——它只是不重复 push，但仍然继续走到根。这个细节是深树慢的根本原因。

4.3 三种深度的实测

构造一棵 10 万节点的深树：一条 9090 层的链，每层挂 10 个叶子。

三个场景的命中数都是 5000，耗时却差了 25 倍。差别只在平均链长：

• leaf：命中集中在前 500 层，5000 × 250 ≈ 125 万次上溯；
• chain：命中是链节点本身，深度从 0 到 5000，5000 × 2500 ≈ 1250 万次；
• deep：命中集中在 4090–4590 层，5000 × 4300 ≈ 2150 万次。

按循环次数折算，每次上溯大约 16–28ns，量级吻合。这不是 WASM 慢，而是工作量本来就大。

4.4 去重不等于剪枝

chain 这个场景特别值得看：命中的是链节点本身，所以每个命中的祖先全部已经在 idSet 里。直觉上应该很快，实测却是 350ms。

原因就是 while 没有提前退出：

while (parentIndex >= 0) {
const parent = fullTree[parentIndex]
if (!idSet.has(parent.id)) { // 已经在集合里
idSet.add(parent.id) // 不执行
parentNodes.push(parent) // 不执行
}
parentIndex = parentIndices[parentIndex] // 但仍然继续走
}

去重只避免了重复 push，没有避免重复遍历。要真正剪枝，需要区分“命中集合”和“已完成祖先补全的集合”，或者把命中项按深度从深到浅处理：一旦遇到一个已经完成补全的祖先，就可以停，因为更上层必然也完成过。

这是一个“知道但还没做”的优化。它不影响正确性，只影响最坏情况的耗时；在当前 5000 上限下，最坏 500ms 还能接受，所以没有优先做。

4.5 搜索视图的折叠

祖先补全只解决了“结果是一棵完整的树”，还没解决“这棵树怎么显示”。搜索结果有自己的一套折叠状态，不复用主树的：

// assembly/giant-tree.ts
private _rebuildSearchShownNodes(): void {
this._shownNodes.splice(0)
this.shownCount = 0
const boundaries: i32[] = []
for (let i: i32 = 0; i < this.searchTree.length; i++) {
const node = this.searchTree[i]
while (
boundaries.length > 0 &&
node.leftNode >= boundaries[boundaries.length – 1]
)
boundaries.pop()
if (boundaries.length === 0) {
this._shownNodes.push(node)
this.shownCount++
if (
this._searchCollapsedIds.has(node.id) &&
node.rightNode – node.leftNode > 1
)
boundaries.push(node.rightNode)
}
}
}

searchTree 已经按 leftNode 排好序，所以这里又是一次单遍遍历：用 boundaries 栈记录“当前折叠节点的右边界”，后续节点只要 leftNode 落在边界内就跳过。

这段代码的复杂度是 O(searchTree.length)，在 5000–10000 行的规模下可以忽略；它保证的是语义：在搜索结果里展开/收起，不会改到主树的折叠状态。

把截断和祖先补全的成本关系画在一起，就能看清为什么“命中越多反而越快”和“深树最慢”可以同时成立：

#mermaid-svg-jkhUwJ0CMADqzqM9{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-jkhUwJ0CMADqzqM9 .error-icon{fill:#552222;}#mermaid-svg-jkhUwJ0CMADqzqM9 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-jkhUwJ0CMADqzqM9 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .marker.cross{stroke:#333333;}#mermaid-svg-jkhUwJ0CMADqzqM9 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-jkhUwJ0CMADqzqM9 p{margin:0;}#mermaid-svg-jkhUwJ0CMADqzqM9 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .cluster-label text{fill:#333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .cluster-label span{color:#333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .cluster-label span p{background-color:transparent;}#mermaid-svg-jkhUwJ0CMADqzqM9 .label text,#mermaid-svg-jkhUwJ0CMADqzqM9 span{fill:#333;color:#333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .node rect,#mermaid-svg-jkhUwJ0CMADqzqM9 .node circle,#mermaid-svg-jkhUwJ0CMADqzqM9 .node ellipse,#mermaid-svg-jkhUwJ0CMADqzqM9 .node polygon,#mermaid-svg-jkhUwJ0CMADqzqM9 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-jkhUwJ0CMADqzqM9 .rough-node .label text,#mermaid-svg-jkhUwJ0CMADqzqM9 .node .label text,#mermaid-svg-jkhUwJ0CMADqzqM9 .image-shape .label,#mermaid-svg-jkhUwJ0CMADqzqM9 .icon-shape .label{text-anchor:middle;}#mermaid-svg-jkhUwJ0CMADqzqM9 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-jkhUwJ0CMADqzqM9 .rough-node .label,#mermaid-svg-jkhUwJ0CMADqzqM9 .node .label,#mermaid-svg-jkhUwJ0CMADqzqM9 .image-shape .label,#mermaid-svg-jkhUwJ0CMADqzqM9 .icon-shape .label{text-align:center;}#mermaid-svg-jkhUwJ0CMADqzqM9 .node.clickable{cursor:pointer;}#mermaid-svg-jkhUwJ0CMADqzqM9 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .arrowheadPath{fill:#333333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-jkhUwJ0CMADqzqM9 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-jkhUwJ0CMADqzqM9 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-jkhUwJ0CMADqzqM9 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-jkhUwJ0CMADqzqM9 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-jkhUwJ0CMADqzqM9 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-jkhUwJ0CMADqzqM9 .cluster text{fill:#333;}#mermaid-svg-jkhUwJ0CMADqzqM9 .cluster span{color:#333;}#mermaid-svg-jkhUwJ0CMADqzqM9 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-jkhUwJ0CMADqzqM9 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-jkhUwJ0CMADqzqM9 rect.text{fill:none;stroke-width:0;}#mermaid-svg-jkhUwJ0CMADqzqM9 .icon-shape,#mermaid-svg-jkhUwJ0CMADqzqM9 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-jkhUwJ0CMADqzqM9 .icon-shape p,#mermaid-svg-jkhUwJ0CMADqzqM9 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-jkhUwJ0CMADqzqM9 .icon-shape .label rect,#mermaid-svg-jkhUwJ0CMADqzqM9 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-jkhUwJ0CMADqzqM9 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-jkhUwJ0CMADqzqM9 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-jkhUwJ0CMADqzqM9 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

扫描 fullTree

命中数达到 5000?

停止扫描扫描成本 = 第 5000 个命中的位置

扫到表尾扫描成本 = 全表

5000 个命中

实际命中数

祖先补全成本 = 命中数 × 平均链长

最终 searchTree 行数= 命中 + 去重祖先

视口序列化只传当前可见行

• 宽而浅的树：扫描很快被截断，祖先链短，整体毫秒级；
• 宽而深的树：扫描同样被截断，但 命中数 × 平均链长 迅速放大，deep 场景到 518ms；
• 稀有词：扫描必须走完全表，但命中少、祖先少，成本集中在扫描阶段。

5. 缓存与防抖

5.1 同一关键词只算一次

if (!this._hasSearchCache || this._lastSearchKeyword !== keyword) {
// 重新搜索
} else {
this.shownCount = this.searchTree.length
}

实测同一关键词的第二次搜索：

缓存命中后仍然会走 _rebuildSearchShownNodes 和视口序列化，所以不是 0，但已经从“几百毫秒”降到“几百微秒”。

5.2 为什么还要防抖

缓存只对“同一个关键词”有效。用户在输入框里每敲一个字符，关键词就变了，缓存必然失效。组件层因此提供两个入口：

// 带 300ms 防抖，适合 input 实时输入
fuzzySearch(keyword)
// 立即执行，适合回车/按钮
fuzzySearchRaw(keyword)

300ms 的选择是一个体验权衡：太短，连续输入仍然会触发多次全表搜索；太长，用户会觉得“按了没反应”。对一个 1M 树、单次搜索 25ms 的场景，300ms 足够把 10 次按键合并成 1 次。

5.3 高亮不能跟着输入框走

高亮用的关键词必须是“实际执行过搜索的那个关键词”，而不是输入框的实时值。否则防抖还没触发，DOM 已经开始按新关键词高亮旧结果了：

// 搜索真正执行时才更新
const rawFuzzySearch = (keyword: string) => {
activeSearchKeyword.value = keyword
…
}

这个细节在文档里只有一句话，但它是“搜索看起来不闪”的关键。

6. 从结果到 DOM

6.1 只序列化视口

fuzzySearch 的返回值不是整个 searchTree，而是 serializeShownSlice：

return serializeShownSlice(
this._shownNodes,
this.scrollTop,
this.scrollHeight,
this.lineHeight
)

即使搜索结果有 5000 行，跨边界传给主线程的也只有当前视口那几十行。这是为什么“1M 全命中 5000 行”只需要 1.1ms：匹配在 5000 个节点就停了，序列化只做视口，两个成本都被截断和视口切片压住了。

这也解释了一个常见误解：搜索结果的大小不等于跨边界的数据量。真正决定每次搜索开销的，是“扫描范围 + 祖先补全循环 + 视口序列化”，不是结果总行数。

6.2 高亮

高亮默认关闭，打开后只标记输入的关键词本身：

// lib/TreeItem.vue
const highlightParts = computed<SearchHighlightPart[] | null>(() => {
const keyword = props.highlightKeyword
if (!keyword) return null
const name = props.item.name
let from = 0
let at = name.indexOf(keyword)
if (at < 0) return null
const parts: SearchHighlightPart[] = []
while (at >= 0) {
if (at > from) parts.push({ text: name.slice(from, at), hit: false })
parts.push({ text: keyword, hit: true })
from = at + keyword.length
at = name.indexOf(keyword, from)
}
if (from < name.length) parts.push({ text: name.slice(from), hit: false })
return parts
})

三个语义和 WASM 搜索严格对齐：

渲染时用 <mark class="giant-tree__search-hit">，颜色可以用 CSS 变量覆盖：

–giant-tree-search-hit-bg
–giant-tree-search-hit-color

如果用了 #node 插槽，组件默认的 <mark> 不会生效，但会把切好的 highlights 传给你：

<template #node="{ node, highlights }">
<span v-if="!highlights">{{ node.name }}</span>
<span v-else>
<template v-for="(part, i) in highlights" :key="i">
<mark v-if="part.hit" class="giant-tree__search-hit">{{
part.text
}}</mark>
<template v-else>{{ part.text }}</template>
</template>
</span>
</template>

7. 语义边界：搜索是视图，不是数据子集

这是最容易踩坑的一块。搜索结果只是 _shownNodes 的一个过滤视图，底层的 fullTree 没有被复制，也没有被裁剪。

所以下面这些行为都是“正确但反直觉”的：

7.1 搜索中勾选父节点，会影响未显示的子节点

// 搜索结果里勾选“研发一部”
checkNode(tree, 'dept-1', CheckType.CHECKED)

checkNode 操作的是 fullTree 里的节点，会级联到它的整棵子树，包括那些因为不匹配关键词而没有显示的行。清空搜索后，你会看到子节点也都被勾选了。

这不是 bug，而是“搜索是视图过滤”的直接结果。要注意 setCheckedNodes 也不是“只设置这些节点”：它会先重置全部选中，再对每个传入的 ID 级联设置其整棵子树。所以如果业务要“只选搜索结果”，需要把结果里的叶子节点 ID 交给它，或者由业务层自己维护选中集合；把结果里的父节点直接传进去，仍然会勾中未显示的子节点。

项目里有专门的回归测试守住这个语义：

it('搜索中选中父节点后清空搜索，子节点状态仍保留', () => {
fuzzyTree(tree, 'Searchable')
checkNode(tree, 'parent', CheckType.CHECKED)
fuzzyTree(tree, '')
// parent / child / grandchild 都应该是 CHECKED
})

7.2 清空搜索会恢复主树折叠，而不是保留搜索视图

fuzzySearch('') 走的是另一条分支：

this._searchCollapsedIds.clear()
this._searchTruncated = false
this.tree = this.fullTree
resetShownFlags(this.fullTree)
this._rebuildShownNodes()

清空关键词意味着“回到主树”，所以搜索视图里的折叠状态被丢弃，主树按自己的 collapsed 标志重建。搜索视图的展开/收起是临时的，不应该污染主树。

7.3 搜索与 Worker

workerMode 下，搜索命令走的是同一个 WASM 实例：

else if (m.type === 'search') wasm.fuzzyTree(tree, m.keyword)

主线程只负责把 activeSearchKeyword 同步给高亮，结果行由 Worker 的 snapshot 回传。快照带 revision，旧搜索结果不会覆盖新状态；结构变更命令会在搜索之前 flushStructure()，保证“先增删、再搜索”的顺序。

这部分和 Worker 协议的其他命令共用一套机制，展开会太长，这里只记一句：搜索不是一条独立通道，它和勾选、折叠、结构变更共享同一条有序命令队列。

8. 决策表

8.1 候选索引开不开

一个粗略的盈亏平衡：

建桶成本 ≈ 40–50 × 单次全表搜索成本（1M 树）

也就是说，同一棵树至少要被搜几十次，而且关键词要足够稀有，候选索引才回本。底层 GiantTree 的默认值 false 不是保守，而是对大多数“打开页面搜一次”的场景更优。组件目前没有把这个开关做成 prop；如果要在业务里打开，需要直接调用 WASM 的 setUseSearchCandidateIndex()，或者把建桶放到 Worker/空闲时段，避免首屏付这 1.3 秒。

8.2 搜索结果怎么用

8.3 什么时候不该在客户端搜

深树 5000 命中、平均链长 4300 时，单次搜索 518ms，已经超过一帧的预算。这种场景下，候选索引救不了你，截断也只能把 5000 降到更小的数。如果业务要求“输入即出结果”，而树的形状又很深，应该把搜索放到后端，或者预先算好一份“节点 → 祖先链”的扁平索引。

客户端的优势是“数据已经在内存里”，劣势是“每次搜索都要重新走一遍祖先链”。这两件事不矛盾，关键看你的树形状和查询频率。

9. 基准口径

文章里的数字都来自同一套脚本，口径如下，方便你复现或质疑：

• 环境：Node v26.7.0，release WASM，macOS arm64，单进程，–expose-gc；
• 调用：端到端 fuzzyTree()，包含视口序列化（boundary = 800px，约 30 行）；
• 重复：每项 3 次，取 P50/P95；
• 建树：pushNeighborNodes 分批 5 万，popNeighbor 后 setBoundary(0, 800)；
• 宽树：root 下 N 个叶子，英文名 Node ${i}，中文名 ${部门}-项目${i}；
• 深树：一条 9090 层的链，每层 10 个叶子；
• 结果行数：getShownHeight() / 26，包含祖先补全行，不是命中数；
• 候选索引：建桶成本单列，不计入“开启”的 warm 搜索耗时。

有两个数字容易被误读，单独说明：

10. 写在最后

把这次搜索拆完，最有用的不是“候选索引快了 95 倍”这个结论，而是三件事的分工：

• 倒排桶：决定“要扫多少行”，收益取决于最短桶的大小；
• 5000 截断：决定“最多收集多少命中”，它让全命中反而变快，也让结果行数可能超过 5000；
• 祖先补全：决定“最坏情况有多慢”，成本是 命中数 × 平均深度，任何匹配阶段的优化都救不了它。

如果只记一句话：

先搞清楚你的搜索慢在哪一段，再决定加不加索引。 对一棵宽而浅的树，候选桶可能值 95 倍；对一棵深而窄的树，它可能连 1% 都省不下来。

项目地址：github.com/jktantan/vue3-giant-tree-wasm。搜索的文档在 guide/fuzzy-search，里面有在线 playground，可以直接把关键词换成你自己的数据试一试。

附：文中涉及的文件