做过的最复杂的组件

面试题：你做过的最复杂的组件是什么？

使用简单口语来回答，因为简单口语容易记忆，同时要显示出这个组件最复杂、我解决这个最复杂的组件是很不容易的。

“What is the most complex component you’ve built?”

English (natural spoken answer)

The most complex component I’ve worked on is a large-scale Virtualized Tree component, something like a file explorer used in a dashboard system.

At first glance, it looks simple, but it actually combines several hard problems together.

The main challenges were two things:

First, it’s a tree structure, not a flat list. So we need to handle nested nodes, expand and collapse states, and maintain hierarchy.

Second, we also need virtual scrolling, because the tree can contain tens of thousands of nodes. So rendering everything would completely break performance.

The hardest part was how to combine these two things efficiently.

What I did was redesign the data model. Instead of rendering the tree directly, I flattened it into a visible linear（/ˈlɪniər/） list, where each node carries its depth information.

Then I treated it like a normal virtual list, and only rendered the visible window based on scroll position.

On top of that, I optimized expand and collapse operations so they only update a small part of the visible list instead of recomputing the entire tree.

This reduced unnecessary re-rendering significantly and made the interaction very smooth even with large datasets.

Honestly, it wasn’t a trivial（/ˈtrɪviəl/ 琐碎的，容易解决的） component. It forced me to think deeply about data structure design, performance trade-offs, and rendering strategy, not just React implementation.

中文

是的，我做过最复杂的组件，是一个大规模虚拟化 Tree 组件，类似文件管理器的左侧目录结构。

一开始看起来不复杂，但实际上它同时包含几个难点：

第一，它是一个树结构，不是普通 list，需要处理层级关系、展开/收起状态。

第二，它还要支持虚拟滚动，因为节点数量可能非常大，如果全部渲染会直接卡死。

最难的地方在于：如何把 Tree 和 Virtual List 合在一起。

我当时的做法是重新设计数据结构，不直接渲染 Tree，而是把它转换成一个带层级信息的线性数组（visible list）。

然后用普通虚拟列表的方式，只渲染当前可见区域。

同时在 expand / collapse 时，我没有重新遍历整棵树，而是只对受影响的子树做局部更新，从而避免了 O(N) 的全量计算。

这个优化让大数据量下的交互非常流畅。

说实话，这个组件不只是 UI 问题，而是一个涉及数据结构设计 + 性能优化 + 渲染模型设计的综合问题。

large list 的 virtualize我会做，但如果是large tree的 virtualize呢？可以做吗？我个人感觉就是不好确定是哪一些 nodes 显示出来，是这样吗？

你的直觉是对的，但真正的难点不是 Virtualization 本身，而是：

Tree 不是连续的数据，而 Virtual List 要求是连续的数据。

所以 Tree Virtualization = Tree Flattening + List Virtualization。

先看看为什么 List 很简单

假设一个 list


xxxxxxxxxx
0
1
2
3
4
5
6
7
8
...
99999

Virtual List 很容易。因为


xxxxxxxxxx
scrollTop = 800px
startIndex = Math.floor(scrollTop / itemHeight)
endIndex = startIndex + visibleCount

例如


xxxxxxxxxx
显示
40
41
42
43
44
45

index 是天然存在的。

Tree 为什么难？

Tree 是这种结构：


xxxxxxxxxx
A
 ├── A1
 │    ├── A11
 │    └── A12
 ├── A2
 │    ├── A21
 │    └── A22
 └── A3
B
 ├── B1
 └── B2

问题来了：假设


xxxxxxxxxx
A 是展开
A1 是展开
A2 是收起
B 是收起

真正应该显示的是


xxxxxxxxxx
A
A1
A11
A12
A2
A3
B

而不是


xxxxxxxxxx
A21
A22
B1
B2

因为它们不可见。所以：Virtual Scroll 根本不知道第 50 个 node 是谁。

真正的第一步：Flatten

几乎所有 Tree Virtualization 都会先做


xxxxxxxxxx
Tree
↓
Flatten
↓
Visible List

例如：Tree


xxxxxxxxxx
A
 ├── A1
 │    ├── A11
 │    └── A12
 ├── A2
 └── A3
B

变成


xxxxxxxxxx
[
 A,
 A1,
 A11,
 A12,
 A2,
 A3,
 B
]

注意：这里只放 visible node。

Flatten 怎么写？

DFS （depth-First Search 深度优先搜索）即可。例如


xxxxxxxxxx
function flattenTree(
  nodes: TreeNode[],
  expandedSet: Set<string>
): VisibleNode[] {
  const result: VisibleNode[] = [];
  function dfs(node: TreeNode, depth: number) {
    result.push({
      ...node,
      depth,
    });
    if (
      node.children &&
      expandedSet.has(node.id)
    ) {
      node.children.forEach((child) =>
        dfs(child, depth + 1)
      );
    }
  }
  nodes.forEach((node) => dfs(node, 0));
  return result;
}

最后得到


xxxxxxxxxx
[
 {id:'A', depth:0},
 {id:'A1', depth:1},
 {id:'A11', depth:2},
 {id:'A12', depth:2},
 {id:'A2', depth:1},
 {id:'A3', depth:1},
 {id:'B', depth:0},
]

这个数组就是 Virtual List 的数据源。

这里的expandedSet是什么？
就是当前展开节点的 id。

为什么需要它？
expandedSet 用来记录 Tree 当前的展开状态，因为原始 Tree 数据只描述“结构”，不描述“用户当前看到了什么”。如果一个节点有children，但是它并没有展开，那么它的children节点就不需要计算进入 visibleNodes 里面去。

刚开始它是什么样的？
刚开始它可能只包含root节点，这样第一层的子节点可以看到；或者是特定的节点。反正 expandedSet 不用担心初始值，可以自定义。

整个流程如下：
xxxxxxxxxx
    Tree Data
        |
        |
  用户点击节点
        |
        ↓
 update expandedSet
        |
        ↓
flattenTree(tree, expandedSet)
        |
        ↓
  visibleNodes
        |
        ↓
 Virtual List

xxxxxxxxxx
result.push({
 ...node,
 depth,
});
result里面直接加入了node节点，如果树结构的node节点很大、很深，那么result也会相应的很大，对性能会有影响吗？
实际上不会。因为 JavaScript 的展开运算符（Spread）是浅拷贝（Shallow Copy）。只是复制了一个引用。
但是生产环境还是只将必要的属性复制过来即可，不复制整个node。

然后就和普通 Virtual List 一模一样

假设


xxxxxxxxxx
flatten.length = 20000

Virtual List 根本不知道这是 Tree。它只知道


xxxxxxxxxx
0
1
2
3
4
5

例如


xxxxxxxxxx
start = 150
end = 170

直接


xxxxxxxxxx
visible = flatten.slice(start, end)

就结束了。

Expand / Collapse 怎么办？

这是第二个难点。假设


xxxxxxxxxx
A
 ├── A1
 ├── A2
 └── A3

点击展开 A

以前


xxxxxxxxxx
flatten
A
B

展开后


xxxxxxxxxx
flatten
A
A1
A2
A3
B

其实就是：重新 flatten。

很多人以为要：


xxxxxxxxxx
insert
remove
shift index

实际上没必要。现代框架：


xxxxxxxxxx
用户点击节点
↓
更新 expandedSet
↓
重新 DFS
↓
得到新的 flatten
↓
React diff

已经足够快。

真正的大数据怎么办？

假设


xxxxxxxxxx
100 万 node

每次 DFS？那就炸了。所以真正的大型 Tree（例如 IDE、文件管理器）不会每次重新 DFS 全树。

通常会维护：


xxxxxxxxxx
Tree
+
Visible List

例如


xxxxxxxxxx
visible
A
A1
A2
B

点击


xxxxxxxxxx
Expand A2

直接


xxxxxxxxxx
splice()
插进去
A21
A22
A23

而不是重新 DFS。

例如


xxxxxxxxxx
visible.splice(
  index + 1,
  0,
  ...children
)

Collapse

就是


xxxxxxxxxx
splice(
  index + 1,
  descendantCount
)

这样复杂度从


xxxxxxxxxx
O(N)

变成


xxxxxxxxxx
O(k)

其中


xxxxxxxxxx
k = 被展开的子树大小

最大的坑：Variable Height（这个不用管，因为我做的大概率 item height是一致的）

真正困难的其实不是 Tree。而是：


xxxxxxxxxx
Tree
+
Virtual
+
Variable Height

例如


xxxxxxxxxx
Folder
  File
  File
  File
↓
Folder 展开以后高度变化

Virtual List 需要知道：


xxxxxxxxxx
第 1500 个 item 的 top 是多少？

如果高度不同：


xxxxxxxxxx
20
20
20
38
41
52
19

就不能再简单计算：


xxxxxxxxxx
index * itemHeight

需要维护：


xxxxxxxxxx
height cache
↓
prefix sum
↓
binary search

很多虚拟列表库（例如基于动态尺寸的实现）都会维护每个节点的测量高度和累计偏移，滚动定位时通过二分查找找到当前可见项。

面试官真正想听什么？

如果面试官问：

Tree 能不能做 Virtualization？

比较完整的回答可以是：

可以。核心思路不是直接虚拟化 Tree，而是先根据当前展开状态把 Tree 扁平化（Flatten）成一个只包含可见节点的线性数组，每个节点记录自己的 depth 用于缩进显示。然后 Virtual List 就可以像处理普通数组一样，根据滚动位置只渲染可见区间的节点。
如果数据规模不大，每次展开或收起时重新 DFS 生成扁平数组即可；如果节点数量非常大，为了避免每次都遍历整棵树，通常会维护一个可见节点列表，在展开时插入对应子树、收起时删除对应后代，将更新范围限制在受影响的子树，从而把更新成本降低到与子树大小相关，而不是与整棵树大小相关。

能使用双语简单口语，来说明一下怎么做吗？

English (Interview Answer)

The main challenge is that a tree is not a flat structure like a list.
For a normal virtualized list, every item already has an index, so it's easy to calculate which items should be rendered based on the scroll position.
A tree is different because some nodes are expanded while others are collapsed. That means not every node is actually visible.
So the first step is to flatten the tree into a visible list. I usually perform a DFS traversal（/trəˈvərs(ə)l/ 遍历） and only include the nodes whose parents are expanded. During this process, I also record each node's depth so the UI knows how much indentation（缩进） to apply.
After that, virtualization becomes exactly the same as a normal list. The virtual list only works with the flattened array and renders the visible range.
If the dataset isn't huge, I simply regenerate the flattened list whenever the user expands or collapses a node.
For very large trees, rebuilding the whole list every time can be expensive. In that case, I'd maintain the visible list incrementally, inserting or removing only the affected subtree when a node is expanded or collapsed.

中文（对应理解）

可以，完全可以。
最大的区别是，Tree 不是一个连续的 List。
普通 List 本来就有 index，所以很容易根据 scroll position 算出应该渲染哪些 item。
但是 Tree 有展开和收起的状态，所以很多节点其实并不会显示出来。
因此第一步通常会先把 Tree Flatten 成一个 Visible List。我一般会用 DFS，只把当前可见的节点放进数组，同时记录每个节点的 depth，用来控制缩进。
得到这个数组以后，Virtualization 就和普通 List 完全一样了，只需要根据 scroll position 渲染当前可见范围即可。
如果数据量不是特别大，每次展开或收起时重新生成这个数组就可以。
如果 Tree 非常大，我会维护一个可见节点列表，只更新受影响的那部分子树，而不是重新遍历整棵树。

一句话总结（非常适合收尾）

Tree virtualization is basically "Tree Flattening + List Virtualization". Once the tree is flattened into a visible list, the virtualization logic is almost identical to a normal virtualized list.

中文：

Tree Virtualization 本质上就是：先把 Tree 扁平化成 Visible List，再使用普通的 List Virtualization。 这是很多成熟组件库（例如 IDE 文件树或大型文件管理器）采用的核心思路。

实现思路

核心思路

把 Tree 变成一个“带层级信息的线性数组”，然后当普通 List 做 Virtualization。

中文：

先“压平 Tree”，再用普通虚拟列表渲染。

Step 0：为什么 Tree 不能直接 virtualize？

Tree 是：


xxxxxxxxxx
src
 ├── components
 │    ├── Button
 │    └── Modal
 ├── pages
 │    ├── Home
 │    └── About
 └── package.json

但是 Virtual List 需要索引：


xxxxxxxxxx
index = 0..N

那么因为 Tree：

有层级
有展开状态
顺序不是固定“平铺结构”

所以：

❌ 不能直接 virtualize Tree

Step 1：关键转折（v3 的核心思想）

我们不再直接用 Tree。我们先问一个问题：

“当前页面真正显示了哪些节点？”

例如：


xxxxxxxxxx
src (展开)
    components (展开)
        Button.tsx
        Modal.tsx
    pages (收起)
package.json

👉 UI 实际是：


xxxxxxxxxx
[src,
 components,
 Button,
 Modal,
 pages,
 package.json]

Step 2：核心突破 —— Flatten Tree

我们把 Tree 转换成：


xxxxxxxxxx
VisibleNode[] = Linear Array

每个节点带一个关键字段：


xxxxxxxxxx
depth: number

示例结果：


xxxxxxxxxx
src              depth 0
components       depth 1
Button           depth 2
Modal            depth 2
pages            depth 1
package.json     depth 0

Step 3：Flatten 怎么做？

核心就是 DFS，但有一个关键规则：

只遍历“展开的节点”


xxxxxxxxxx
if node is expanded → traverse children
else skip children

逻辑：


xxxxxxxxxx
visit node 点击节点
  ↓
update expandedSet
  ↓
if expanded → dfs(children)

Step 4：Flatten 的结果是什么？

它不是 Tree：


xxxxxxxxxx
❌ Tree structure

而是：


xxxxxxxxxx
✅ Linear visible array

Step 5：Virtualization 变得极其简单

现在：


xxxxxxxxxx
visibleNodes = flat array

我们直接：


xxxxxxxxxx
startIndex = scrollTop / rowHeight
endIndex = startIndex + visibleCount

然后：


xxxxxxxxxx
slice(startIndex, endIndex)

Step 6：v3 的整体结构


xxxxxxxxxx
Tree
  ↓
flattenTree(expandedSet)
  ↓
visibleNodes[]
  ↓
Virtual List
  ↓
render

Step 7：Expand / Collapse 怎么处理？

Expand：


xxxxxxxxxx
update expandedSet
re-run flattenTree

Collapse：


xxxxxxxxxx
update expandedSet
re-run flattenTree

注意：

❗ 每次变更都会重新 flatten

优缺点（面试重点）

👍 优点：

实现最简单
思路清晰
非常适合面试基础回答
性能对小/中型 Tree 足够

👎 缺点：

每次 expand/collapse 都 O(N)
大 Tree 会重复遍历
没有增量更新

代码实现

目录结构：


xxxxxxxxxx
src/
│
├── App.tsx
├── VirtualTree.tsx
├── flatten.ts
├── types.ts
└── data.ts

Step1：types.ts


xxxxxxxxxx
export interface TreeNode {
  id: string;
  name: string;
  children?: TreeNode[];
}
export interface VisibleNode extends TreeNode {
  depth: number;
}

Step2：data.ts


xxxxxxxxxx
import { TreeNode } from "./types";
export const treeData: TreeNode[] = [
  {
    id: "src",
    name: "src",
    children: [
      {
        id: "components",
        name: "components",
        children: [
          {
            id: "button",
            name: "Button.tsx",
          },
          {
            id: "modal",
            name: "Modal.tsx",
          },
        ],
      },
      {
        id: "pages",
        name: "pages",
        children: [
          {
            id: "home",
            name: "Home.tsx",
          },
          {
            id: "about",
            name: "About.tsx",
          },
        ],
      },
      {
        id: "package",
        name: "package.json",
      },
    ],
  },
];

Step3：flatten.ts

这是整个 Tree Virtualization 最重要的一步。


xxxxxxxxxx
import { TreeNode, VisibleNode } from "./types";
export function flattenTree(
  nodes: TreeNode[],
  expanded: Set<string>
): VisibleNode[] {
  const result: VisibleNode[] = [];
  function dfs(node: TreeNode, depth: number) {
    result.push({
      ...node,
      depth,
    });
    if (
      node.children &&
      expanded.has(node.id)
    ) {
      node.children.forEach((child) =>
        dfs(child, depth + 1)
      );
    }
  }
  nodes.forEach((node) => dfs(node, 0));
  return result;
}

Step4：VirtualTree.tsx

这个组件里面包含：


xxxxxxxxxx
flatten
↓
virtual
↓
render


xxxxxxxxxx
import { useMemo, useState } from "react";
import { TreeNode } from "./types";
import { flattenTree } from "./flatten";
const ROW_HEIGHT = 32;
const HEIGHT = 220;
interface Props {
  tree: TreeNode[];
}
export default function VirtualTree({
  tree,
}: Props) {
  const [expanded, setExpanded] = useState(
    new Set(["src"])
  );
  const [scrollTop, setScrollTop] =
    useState(0);
  const visibleNodes = useMemo(
    () => flattenTree(tree, expanded),
    [tree, expanded]
  );
  const totalHeight =
    visibleNodes.length * ROW_HEIGHT;
  const startIndex = Math.floor(
    scrollTop / ROW_HEIGHT
  );
  const visibleCount =
    Math.ceil(HEIGHT / ROW_HEIGHT);
  const endIndex =
    startIndex + visibleCount + 1;
  const items = visibleNodes.slice(
    startIndex,
    endIndex
  );
  function toggle(id: string) {
    const next = new Set(expanded);
    if (next.has(id)) {
      next.delete(id);
    } else {
      next.add(id);
    }
    setExpanded(next);
  }
  return (
    <div
      style={{
        height: HEIGHT,
        overflow: "auto",
        border: "1px solid #ddd",
      }}
      onScroll={(e) =>
        setScrollTop(
          e.currentTarget.scrollTop
        )
      }
    >
      <div
        style={{
          height: totalHeight,
          position: "relative",
        }}
      >
        {items.map((node, index) => {
          const realIndex =
            startIndex + index;
          return (
            <div
              key={node.id}
              onClick={() =>
                if(!node.children) return;
                toggle(node.id)
              }
              style={{
                position: "absolute",
                top:
                  realIndex *
                  ROW_HEIGHT,
                height: ROW_HEIGHT,
                lineHeight:
                  `${ROW_HEIGHT}px`,
                left:
                  node.depth * 20,
                cursor: "pointer",
              }}
            >
              {node.children
                ? expanded.has(node.id)
                  ? "📂"
                  : "📁"
                : "📄"}{" "}
              {node.name}
            </div>
          );
        })}
      </div>
    </div>
  );
}

Step5：App.tsx


xxxxxxxxxx
import VirtualTree from "./VirtualTree";
import { treeData } from "./data";
export default function App() {
  return (
    <div
      style={{
        width: 400,
        margin: "40px auto",
      }}
    >
      <VirtualTree
        tree={treeData}
      />
    </div>
  );
}

运行效果

第一次：


xxxxxxxxxx
📂 src
    📁 components
    📁 pages
    📄 package.json

点击 components


xxxxxxxxxx
📂 src
    📂 components
        📄 Button.tsx
        📄 Modal.tsx
    📁 pages
    📄 package.json

点击 pages


xxxxxxxxxx
📂 src
    📂 components
        📄 Button.tsx
        📄 Modal.tsx
    📂 pages
        📄 Home.tsx
        📄 About.tsx
    📄 package.json

整个过程中，真正渲染的只有：


xxxxxxxxxx
const items = visibleNodes.slice(startIndex, endIndex);

这就是 Virtualization。

这只是第一版（Fixed Height）

真正生产环境的 Virtual Tree（例如 VS Code Explorer、Chrome DevTools、IDE 文件树）还会继续优化，例如：

Overscan（上下多渲染几行，避免滚动闪烁）
Variable Row Height（不同节点高度不同）-----暂时不用管，连tanstack virtual都花了最大的力气来解决，我就不用管了
增量更新 Visible List（展开/收起时不重新 DFS 整棵树）
滚动位置保持（展开后避免视图突然跳动）
键盘导航（↑ ↓ ← →、Home、End）
ARIA 无障碍支持

这些才是真正接近 react-arborist、VS Code Explorer 等专业 Tree Virtualization 实现的核心技术。如果你准备高级前端或 Staff 级面试，我也可以带你把这个 Demo 一步步演进成接近生产级的实现。

继续优化

如果让我设计一套面试学习路线，我会按下面的版本逐步演进，每一步都对应一个真实工程问题。


xxxxxxxxxx
v1  Tree + Flatten + Fixed Virtual List        ⭐⭐（我们已经完成）
            ↓
v2  Overscan                                  ⭐⭐⭐
            ↓
v3  Variable Height                           ⭐⭐⭐⭐
            ↓
v4  Incremental Visible List                  ⭐⭐⭐⭐⭐
            ↓
v5  Async Load Children                       ⭐⭐⭐⭐⭐
            ↓
v6  Production Virtual Tree                   ⭐⭐⭐⭐⭐⭐

v2 Overscan（真实项目第一步）

现在我们的代码有一个问题。

假设：


xxxxxxxxxx
viewport
--------------------
Item 100
Item 101
Item 102
Item 103
--------------------

滚动 1px

以前：


xxxxxxxxxx
卸载100
挂载104

再滚


xxxxxxxxxx
卸载101
挂载105

React 一直在：


xxxxxxxxxx
mount
unmount
mount
unmount

所以滚动会有一点点抖。

真正 Virtual List 都会这样：


xxxxxxxxxx
viewport
--------------------
98
99
100
101
102
103
104
105
--------------------

也就是说：


xxxxxxxxxx
多渲染上下几行

这就是 Overscan。

代码改动非常小。

以前：


xxxxxxxxxx
const startIndex = Math.floor(scrollTop / ROW_HEIGHT)
const endIndex =
  startIndex + visibleCount + 1

改成：


xxxxxxxxxx
const overscan = 5
const startIndex = Math.max(
    0,
    Math.floor(scrollTop / ROW_HEIGHT) - overscan
)
const endIndex = Math.min(
    visibleNodes.length,
    startIndex + visibleCount + overscan * 2
)

是不是一下就流畅很多。

startIndex有点难理解。
仔细看，startIndex其实变小了，startIndex 变小，并不是为了"向上缓存"，而是为了"用户已经滚过去但马上可能又滚回来"。
最小也就是0。
xxxxxxxxxx
     ↑ 已经滚过去
--------------------
0
1
2
...
8
9
--------------------
10   ← viewport开始
11
12
13
14
--------------------
15
16
17
...
如果startIndex不变小一点，那么用户向上滚动的时候，可能就会出现空白。

v3 真正的大坑：Variable Height

不用管。

v4 真正的大型 Tree

这是 Google、VS Code 最喜欢问的。我们现在：

点击：


xxxxxxxxxx
展开 src

会：


xxxxxxxxxx
DFS
整个 Tree

哪怕：


xxxxxxxxxx
100 万节点

也重新 DFS。

复杂度：


xxxxxxxxxx
O(N)

这就是 Demo。

真正生产不会这样。

生产环境会维护：


xxxxxxxxxx
visibleNodes

例如：


xxxxxxxxxx
src
components
pages
package.json

点击：


xxxxxxxxxx
components

不会重新 DFS。

而是：


xxxxxxxxxx
找到 components

然后：


xxxxxxxxxx
splice()

变成：


xxxxxxxxxx
src
components
Button
Modal
pages
package.json

是不是只改了一小段。

复杂度：


xxxxxxxxxx
O(k)

其中：


xxxxxxxxxx
k = 子树大小

不是：


xxxxxxxxxx
整个 Tree

v5 懒加载（Async Tree）

例如 GitHub：


xxxxxxxxxx
▶ node_modules

根本不知道：


xxxxxxxxxx
children

点击：


xxxxxxxxxx
展开

才：


xxxxxxxxxx
fetch()
↓
API
↓
children

所以 Tree 会变成：


xxxxxxxxxx
children
undefined

不是：


xxxxxxxxxx
[]

展开：


xxxxxxxxxx
Loading...

回来：


xxxxxxxxxx
children
有数据

重新插进去。

v6 真正生产版本

这时候你的组件其实已经接近：

VS Code Explorer
Chrome DevTools
Figma Layer Panel
Notion 左侧目录

架构会变成：


xxxxxxxxxx
Tree
↓
TreeStore
        │
        ├── expandedSet
        ├── visibleNodes
        ├── heightCache
        ├── nodeMap
        ├── parentMap
        └── childrenMap
↓
Virtual Engine
↓
Render

这里你会发现，Virtual List 已经不是重点了。

真正复杂的是：


xxxxxxxxxx
TreeStore

所有状态都在里面。

React Component：

几乎只是：


xxxxxxxxxx
TreeStore
↓
visibleNodes
↓
render()

如果我是面试官，我最希望你能写出来的是哪一版？

我不会让候选人写 TanStack Virtual 那种几千行源码。

我会希望看到下面这个演进过程：


xxxxxxxxxx
✅ v1 Flatten Tree
        ↓
✅ v2 Fixed Virtual List
        ↓
✅ v3 Overscan
        ↓
✅ v4 Incremental Update（⭐⭐⭐⭐⭐）

v4 是最有价值的。

因为它体现的是数据结构和算法能力，而不是会不会用虚拟列表库。

我建议我们下一步实现 v4

不要继续优化滚动，而是重构数据结构。

我们会把现在每次都执行：


xxxxxxxxxx
flattenTree(tree, expanded)

改造成维护一个长期存在的 visibleNodes 数组：


xxxxxxxxxx
visibleNodes
├── src
├── components
├── Button
├── Modal
├── pages
└── package.json

展开 components 时，我们只在数组中插入对应的子节点；收起时，只删除它的后代，而不再重新 DFS 整棵树。

这一版是真正生产级 Tree Virtualization 的核心，也是很多高级前端面试最希望听到的实现思路。

v4 思路

太好了，我们开始做 v4：Incremental Visible List。

这一版开始，我们的思路会发生一个很大的变化。

不再每次都 flattenTree()，而是把 visibleNodes 当作真正的数据源来维护。

这也是 VS Code、Chrome DevTools、很多 Tree 组件的核心思想。

先看看 v1 的问题

我们之前的代码：


xxxxxxxxxx
const visibleNodes = useMemo(
  () => flattenTree(tree, expanded),
  [tree, expanded]
)

假设 Tree 是这样的：


xxxxxxxxxx
src
├── components
│   ├── Button
│   └── Modal
├── pages
│   ├── Home
│   └── About
└── package.json

第一次：


xxxxxxxxxx
visibleNodes
src
components
pages
package.json

点击：


xxxxxxxxxx
components

React：


xxxxxxxxxx
重新 DFS
↓
重新生成
visibleNodes

得到


xxxxxxxxxx
src
components
Button
Modal
pages
package.json

如果 Tree 有：


xxxxxxxxxx
100 万 node

每点一次：


xxxxxxxxxx
DFS()
100 万

是不是很浪费？

真正生产环境

生产环境不会这样。

它会一直维护：


xxxxxxxxxx
const [visibleNodes, setVisibleNodes] = useState(...)

以后：只修改这个数组。

所以：


xxxxxxxxxx
Tree

变成：


xxxxxxxxxx
Tree
+
VisibleNodes

两个同时存在。

第一步：VisibleNode 要记录更多信息

以前：


xxxxxxxxxx
interface VisibleNode {
    id
    name
    depth
}

现在不够。因为：点击


xxxxxxxxxx
components

我要知道：


xxxxxxxxxx
children 是谁？

所以：


xxxxxxxxxx
export interface VisibleNode {
  id: string
  name: string
  depth: number
  children?: TreeNode[]
}

其实最简单就是：


xxxxxxxxxx
VisibleNode extends TreeNode

这个我们之前已经这么做了。

第二步：第一次还是 DFS

注意：第一次还是要 Flatten。

例如：


xxxxxxxxxx
src

展开。得到：


xxxxxxxxxx
src
components
pages
package.json

以后：再也不用 DFS 整棵 Tree。

第三步：Expand

这是最重要的。

假设现在：


xxxxxxxxxx
0 src
1 components
2 pages
3 package.json

点击：


xxxxxxxxxx
components

应该变成：


xxxxxxxxxx
0 src
1 components
2 Button
3 Modal
4 pages
5 package.json

注意：

Button

Modal

是插进去的。

不是重新生成。

所以找到：


xxxxxxxxxx
components

index：


xxxxxxxxxx
const index =
    visibleNodes.findIndex(...)

例如：


xxxxxxxxxx
index = 1

然后DFS：

但是：只 DFS components。

得到：


xxxxxxxxxx
Button
Modal

注意：不是 DFS 整棵 Tree。

只是：


xxxxxxxxxx
components.children

然后：


xxxxxxxxxx
visibleNodes.splice(
    index + 1,
    0,
    ...children
)

是不是完成了？

Collapse 怎么办？

现在：


xxxxxxxxxx
src
components
Button
Modal
pages
package.json

点击：


xxxxxxxxxx
components

应该删掉：


xxxxxxxxxx
Button
Modal

怎么删？

很多人第一反应：DFS。

其实不用。

因为数组已经是：


xxxxxxxxxx
components
Button
Modal
pages

注意：Button Modal 都有


xxxxxxxxxx
depth=2

而pages是：


xxxxxxxxxx
depth=1

所以一直删到：


xxxxxxxxxx
depth <= 当前 depth

停止。

例如：

当前：


xxxxxxxxxx
components
depth=1

后面：


xxxxxxxxxx
Button
depth=2

删。

继续：


xxxxxxxxxx
Modal
depth=2

删。

继续：


xxxxxxxxxx
pages
depth=1

停止。

是不是根本不用 DFS？

所以 Collapse 非常漂亮。

下面代码的目的，就是得到应该删除的个数 removeCount。


xxxxxxxxxx
const index = visibleNodes.findIndex(node => node.id === id);
const current = visibleNodes[index]
let end = index + 1;
// 只要是index之后，并且 depth > 当前节点的 depth 的节点，都要让 end++ ，这个其实很好理解。
while (
    end < visibleNodes.length &&
    visibleNodes[end].depth > current.depth
) {
    end++;
}
let removeCount = end - index - 1;
visibleNodes.splice(
    index + 1,
    removeCount
);

复杂度：


xxxxxxxxxx
O(k)

k：

就是：


xxxxxxxxxx
Button
Modal

两项。

不是：


xxxxxxxxxx
100 万

整个 Toggle 流程

以后 Expand：


xxxxxxxxxx
点击
↓
找到 index
↓
DFS 当前 children
↓
splice 插进去
↓
setVisibleNodes()

Collapse：


xxxxxxxxxx
点击
↓
找到 index
↓
找到所有 descendant
↓
splice 删除
↓
setVisibleNodes()

下一步（真正开始写代码）

这一节我们主要理解了算法。

下一节我建议直接重构我们的 VirtualTree.tsx，把：


xxxxxxxxxx
useMemo(() => flattenTree(...))

彻底删掉。

改成维护：


xxxxxxxxxx
const [visibleNodes, setVisibleNodes] = useState(...)

然后实现两个真正的生产级函数：


xxxxxxxxxx
expandNode(nodeId)
collapseNode(nodeId)

你会看到整个组件从“Demo 思路”升级为“生产级架构”，这也是很多成熟 Tree 组件内部采用的核心实现方式。

v4 代码实现

直接把 VirtualTree.tsx 改造成生产环境更接近的架构。

第一步：以前的数据流

我们以前是：


xxxxxxxxxx
Tree
      ↓
flattenTree()
      ↓
visibleNodes
      ↓
render

也就是说，每次点击都会重新：


xxxxxxxxxx
flattenTree(tree, expanded)

现在的数据流

改成：


xxxxxxxxxx
Tree（永远不变）
        │
        │（初始化一次）
        ▼
visibleNodes（State）
        │
        ├── expand()
        ├── collapse()
        ▼
render

以后：render 永远使用 visibleNodes。Tree 只是数据仓库（Source of Truth）。

第二步：State 改掉

以前：


xxxxxxxxxx
const [expanded, setExpanded] = useState(new Set(["src"]))
const visibleNodes = useMemo(
  () => flattenTree(tree, expanded),
  [tree, expanded]
)

现在改成：


xxxxxxxxxx
const [expanded, setExpanded] = useState(
  new Set(["src"])
)
const [visibleNodes, setVisibleNodes] =
  useState(() =>
    flattenTree(tree, new Set(["src"]))
  )

以后：render 全部来自


xxxxxxxxxx
visibleNodes

而不是


xxxxxxxxxx
flattenTree(...)

第三步：Expand

我们写一个函数：


xxxxxxxxxx
function expandNode(id: string) {
}

第一件事：找到点击的是谁。


xxxxxxxxxx
const index = visibleNodes.findIndex(
  node => node.id === id
)
if (index === -1) return

例如：


xxxxxxxxxx
0 src
1 components
2 pages
3 package.json

点击：


xxxxxxxxxx
components

得到：


xxxxxxxxxx
index = 1

第四步：找到 children


xxxxxxxxxx
const current = visibleNodes[index]
if (!current.children?.length) {
    return
}

例如：


xxxxxxxxxx
components
↓
children

就是：


xxxxxxxxxx
Button
Modal

第五步：只 Flatten 当前子树

注意！

不是：


xxxxxxxxxx
flattenTree(tree)

而是：


xxxxxxxxxx
flattenTree(
    current.children,
    expanded
)

这里还有一个小细节。

因为 Button 应该：


xxxxxxxxxx
depth=2

所以以前：


xxxxxxxxxx
flattenTree()

固定：


xxxxxxxxxx
depth=0

现在需要改一下。

我们修改 flattenTree() 函数，增加 baseDepth：


xxxxxxxxxx
flattenTree(
    children,
    expanded,
    current.depth + 1
)

DFS 从 depth=2 开始。

所以 flatten.ts 变成：


xxxxxxxxxx
export function flattenTree(
  nodes,
  expanded,
  depth = 0
)

DFS：


xxxxxxxxxx
dfs(node, depth)

第六步：插进去

得到：


xxxxxxxxxx
Button
Modal

直接：


xxxxxxxxxx
const next = [...visibleNodes]
next.splice(
    index + 1,
    0,
    ...children
)
setVisibleNodes(next)

是不是结束了？

整个过程：


xxxxxxxxxx
components
↓
Button
Modal
↓
splice()
↓
render

没有重新 DFS 整棵树。

Collapse

Collapse 更漂亮。

现在：


xxxxxxxxxx
0 src
1 components
2 Button
3 Modal
4 pages
5 package.json

点击：


xxxxxxxxxx
components

当前：


xxxxxxxxxx
depth=1

开始：


xxxxxxxxxx
let end = index + 1

循环：


xxxxxxxxxx
Button
depth=2

继续。


xxxxxxxxxx
Modal
depth=2

继续。


xxxxxxxxxx
pages
depth=1

停。

所以：


xxxxxxxxxx
const removeCount =
    end - index - 1

这里：


xxxxxxxxxx
removeCount=2

然后：


xxxxxxxxxx
next.splice(
    index + 1,
    removeCount
)

完成。

Toggle

最后：


xxxxxxxxxx
function toggle(node) {
    if(expanded.has(node.id)) {
        collapseNode(node.id)
    } else {
        expandNode(node.id)
    }
}

现在复杂度是多少？

假设：

整个 Tree：


xxxxxxxxxx
1000000 nodes

点击：


xxxxxxxxxx
components

里面：


xxxxxxxxxx
Button
Modal

以前：


xxxxxxxxxx
DFS()
1000000

现在：


xxxxxxxxxx
DFS()
2

因为只处理：


xxxxxxxxxx
children

是不是一下：


xxxxxxxxxx
O(N)
↓
O(k)

这里还有一个隐藏 Bug（也是很多面试官喜欢追问的）

来看下面这个 Tree：


xxxxxxxxxx
src
└── components
      ├── Button
      │      ├── index.ts
      │      └── styles.css
      └── Modal

假设 Button 已经展开。

也就是说：


xxxxxxxxxx
expanded
=
src
components
Button

收起components文件夹之后，再次展开：

应该出现：


xxxxxxxxxx
components
    Button
        index.ts
        styles.css
    Modal

而不是：


xxxxxxxxxx
components
    Button
    Modal

现有的代码是做不到的。

为什么？因为 Button 本来就在 expanded 集合里。

也就是说：

我们插入 components.children 时，不能只插入第一层，而要递归展开那些已经处于 expanded 状态的子节点。

这也是为什么我前面坚持保留 flattenTree(children, expanded, baseDepth) 的原因。

它不仅能生成第一层，还能自动把那些“已经展开”的子树一起展开。

注意：这里假设的是 Button 文件夹曾经展开过，如果Button文件夹本来就没有展开过，那么展开 components 文件夹，默认是不展开里面的子文件夹的。
当然，具体效果还是要看产品的需求。

下一节（真正生产级）

到这里，我们已经实现了：

✅ 增量更新 visibleNodes
✅ 不重新遍历整棵树
✅ 支持恢复已展开的子树

下一步我建议继续升级，实现 NodeMap + ParentMap。

下一步（了解即可）

好，下面这一步开始，就真的进入生产级 Tree 组件了。

其实我们刚刚的版本还有一个问题。

为什么还不够？

现在我们的代码里，每次点击都会：


xxxxxxxxxx
const index = visibleNodes.findIndex(
    node => node.id === id
)

复杂度：


xxxxxxxxxx
O(N)

如果：


xxxxxxxxxx
visibleNodes
100000

每点击一次：


xxxxxxxxxx
findIndex()
100000

其实还是有点浪费。

真正生产环境

真正的 Tree 一般都会维护一个 Store。

例如：


xxxxxxxxxx
TreeStore
├── nodeMap
├── parentMap
├── childrenMap
├── visibleNodes
├── expandedSet
└── selectedSet

React Component 只是：


xxxxxxxxxx
TreeStore
↓
visibleNodes
↓
render

你会发现：React 根本不关心 Tree。Tree 全部在 Store 里面。

treeStore里面的nodeMap、parentMap、childrenMap会在初始化时一次性构建完成，虽然刚开始会花一点时间，但是后续操作会很快，还是很值得的。

如果 Tree 只有几千到几万个节点，是没有问题的。但是，如果 Tree 的规模达到几十万甚至上百万个节点，比如 IDE 的文件系统、Git 仓库或者日志目录，那么就不会一次性初始化全部数据了。

像 VS Code 就采用了 Lazy Loading（懒加载） 的方式。刚进入页面时，只加载根节点；当用户展开某个文件夹时，再向后端请求它的子节点，同时把这些新节点加入 nodeMap、parentMap 等数据结构，而不是一次性建立整个 Tree 的索引。

第一张 Map：nodeMap

为什么需要？

Tree：


xxxxxxxxxx
src
    components
        Button
        Modal

以前想找到：


xxxxxxxxxx
Button

需要 DFS 整棵 Tree。

生产不会。

初始化一次：


xxxxxxxxxx
const nodeMap = new Map()
nodeMap.set("src", src)
nodeMap.set("components", components)
nodeMap.set("button", button)
nodeMap.set("modal", modal)

以后：


xxxxxxxxxx
nodeMap.get("button")

直接：


xxxxxxxxxx
O(1)

是不是比 DFS 快很多。

第二张 Map：parentMap

为什么？

例如：


xxxxxxxxxx
Button

我要知道：


xxxxxxxxxx
父是谁？

以前 DFS。

现在：


xxxxxxxxxx
parentMap
button
↓
components

直接：


xxxxxxxxxx
parentMap.get("button")

得到：


xxxxxxxxxx
components

很多功能都会用。

例如：


xxxxxxxxxx
Breadcrumb
src
↓
components
↓
Button

初始化一次

整个 Tree 只 DFS 一次。


xxxxxxxxxx
function buildMaps(tree){
}

DFS：


xxxxxxxxxx
function dfs(node,parent){
    nodeMap.set(node.id,node)
    parentMap.set(
        node.id,
        parent?.id
    )
    node.children?.forEach(...)
}

以后 Tree 再也不用 DFS。

Expand

以前：


xxxxxxxxxx
const node =
visibleNodes[index]

现在直接：


xxxxxxxxxx
const node =
nodeMap.get(id)

是不是：


xxxxxxxxxx
O(1)

Collapse

Collapse 还是扫描：


xxxxxxxxxx
visibleNodes

为什么？

因为 Visible List 就是：


xxxxxxxxxx
DFS 顺序

例如：


xxxxxxxxxx
src
components
Button
Modal
pages

Button 后面一定还是 Modal 。不会跑到 src 前面。

所以扫描：


xxxxxxxxxx
depth

就是最快。

面试加分点（很多人答不到）

如果面试官问：

为什么还要保留原始 Tree？为什么不只有 visibleNodes？

这是一个非常好的问题。

你的回答可以是：

English

The original tree is the source of truth. The visible list is only a projection of the tree based on the current expansion state. If I only keep the visible list, collapsing and re-expanding a node becomes difficult because I'd lose the hidden subtree structure. So in production, I keep both: the original tree stores the complete hierarchy, while the visible list is optimized for rendering.

中文

原始 Tree 是数据源（Source of Truth），而 visibleNodes 只是根据当前展开状态计算出来的一个视图。如果只保留 visibleNodes，收起节点后就丢失了被隐藏子树的层级关系，之后再展开会很麻烦。因此生产环境通常会同时保留完整 Tree 和 visibleNodes：前者负责保存完整结构，后者负责高效渲染。

v4 版本最终代码

好，这里给你一份真正完整的 v4（生产思路版）Virtual Tree。

这一版的核心是：

❗ 不再 DFS whole tree ❗ 不再 flatten whole tree ❗ 只维护 visibleNodes + maps ❗ expand / collapse 是局部更新（O(k)）

目录结构


xxxxxxxxxx
src/
├── App.tsx
├── types.ts
├── data.ts
├── treeStore.ts
├── VirtualTree.tsx

1️⃣ types.ts


xxxxxxxxxx
export interface TreeNode {
  id: string;
  name: string;
  children?: TreeNode[];
}
export interface VisibleNode {
  id: string;
  name: string;
  depth: number;
  children?: TreeNode[];
}

2️⃣ data.ts


xxxxxxxxxx
import { TreeNode } from "./types";
export const treeData: TreeNode[] = [
  {
    id: "src",
    name: "src",
    children: [
      {
        id: "components",
        name: "components",
        children: [
          { id: "button", name: "Button.tsx" },
          { id: "modal", name: "Modal.tsx" },
        ],
      },
      {
        id: "pages",
        name: "pages",
        children: [
          { id: "home", name: "Home.tsx" },
          { id: "about", name: "About.tsx" },
        ],
      },
      { id: "pkg", name: "package.json" },
    ],
  },
];

3️⃣ treeStore.ts（⭐核心）

这一层就是“VS Code 思路”。


xxxxxxxxxx
import { TreeNode, VisibleNode } from "./types";
export class TreeStore {
  private nodeMap = new Map<string, TreeNode>();
  private childrenMap = new Map<string, TreeNode[]>();
  private visibleNodes: VisibleNode[] = [];
  private expanded = new Set<string>();
  constructor(tree: TreeNode[]) {
    this.build(tree);
    // 初始展开 root
    const root = tree[0];
    this.expanded.add(root.id);
    this.visibleNodes = this.buildVisible(tree, 0);
  }
  // -------- init --------
  private build(tree: TreeNode[]) {
    const dfs = (node: TreeNode) => {
      this.nodeMap.set(node.id, node);
      this.childrenMap.set(node.id, node.children ?? []);
      node.children?.forEach(dfs);
    };
    tree.forEach(dfs);
  }
  // -------- build visible (only first time) --------
  private buildVisible(
    nodes: TreeNode[],
    depth: number
  ): VisibleNode[] {
    const res: VisibleNode[] = [];
    const dfs = (node: TreeNode, d: number) => {
      res.push({
        ...node,
        depth: d,
      });
        
      // 这里是关键，如果当前node有children，也要将其全部加入到
      if (
        this.expanded.has(node.id) &&
        node.children
      ) {
        node.children.forEach((c) =>
          dfs(c, d + 1)
        );
      }
    };
    nodes.forEach((n) => dfs(n, depth));
    return res;
  }
  // -------- public API --------
  getVisible() {
    return this.visibleNodes;
  }
  // -------- expand (O(k)) --------
  expand(id: string) {
    if (this.expanded.has(id)) return;
    this.expanded.add(id);
    const index = this.visibleNodes.findIndex(
      (n) => n.id === id
    );
    if (index === -1) return;
    const node = this.nodeMap.get(id);
    if (!node?.children) return;
    const insertNodes = this.buildVisible(
      node.children,
      this.visibleNodes[index].depth + 1
    );
    this.visibleNodes.splice(
      index + 1,
      0,
      ...insertNodes
    );
  }
  // -------- collapse (O(k)) --------
  collapse(id: string) {
    if (!this.expanded.has(id)) return;
    this.expanded.delete(id);
    const index = this.visibleNodes.findIndex(
      (n) => n.id === id
    );
    if (index === -1) return;
    const baseDepth =
      this.visibleNodes[index].depth;
    let end = index + 1;
    while (
      end < this.visibleNodes.length &&
      this.visibleNodes[end].depth >
        baseDepth
    ) {
      end++;
    }
    this.visibleNodes.splice(
      index + 1,
      end - index - 1
    );
  }
  toggle(id: string) {
    if (this.expanded.has(id)) {
      this.collapse(id);
    } else {
      this.expand(id);
    }
  }
}

4️⃣ VirtualTree.tsx（Virtualization + UI）


xxxxxxxxxx
import { useEffect, useMemo, useState } from "react";
import { TreeNode } from "./types";
import { TreeStore } from "./treeStore";
const ROW_HEIGHT = 32;
const HEIGHT = 240;
const OVERSCAN = 5;
export default function VirtualTree({
  tree,
}: {
  tree: TreeNode[];
}) {
  const store = useMemo(
    () => new TreeStore(tree),
    [tree]
  );
  const [visible, setVisible] = useState(
    store.getVisible()
  );
  const [scrollTop, setScrollTop] =
    useState(0);
  const refresh = () =>
    setVisible([...store.getVisible()]);
  const start = Math.max(
    0,
    Math.floor(scrollTop / ROW_HEIGHT) -
      OVERSCAN
  );
  const end =
    start +
    Math.ceil(HEIGHT / ROW_HEIGHT) +
    OVERSCAN * 2;
  const slice = visible.slice(start, end);
  return (
    <div
      style={{
        height: HEIGHT,
        overflow: "auto",
        border: "1px solid #ddd",
      }}
      onScroll={(e) =>
        setScrollTop(e.currentTarget.scrollTop)
      }
    >
      <div
        style={{
          height: visible.length * ROW_HEIGHT,
          position: "relative",
        }}
      >
        {slice.map((node, i) => {
          const realIndex = start + i;
          const hasChildren =
            !!node.children?.length;
          return (
            <div
              key={node.id}
              onClick={() => {
                store.toggle(node.id);
                refresh();
              }}
              style={{
                position: "absolute",
                top: realIndex * ROW_HEIGHT,
                height: ROW_HEIGHT,
                lineHeight: `${ROW_HEIGHT}px`,
                left: node.depth * 16,
                cursor: "pointer",
                userSelect: "none",
              }}
            >
              {hasChildren
                ? "📁"
                : "📄"}{" "}
              {node.name}
            </div>
          );
        })}
      </div>
    </div>
  );
}

5️⃣ App.tsx


xxxxxxxxxx
import VirtualTree from "./VirtualTree";
import { treeData } from "./data";
export default function App() {
  return (
    <div style={{ padding: 40 }}>
      <VirtualTree tree={treeData} />
    </div>
  );
}

这一版你已经实现了什么？

你现在这个 Tree 已经具备：

✅ 生产级结构思想

TreeStore（类似 VS Code data layer）
visibleNodes（render layer）
expandedSet（state layer）

✅ 性能优化

❌ 不再 DFS 全树
❌ 不再重新 flatten
✅ expand O(k)
✅ collapse O(k)
✅ render O(window size)

✅ Virtualization

fixed height
overscan
absolute positioning
translate-less rendering

面试总结一句话（非常重要）

你可以这样收尾：

This implementation separates the tree into a data layer (TreeStore) and a view layer (visibleNodes). Instead of recomputing the whole tree on every interaction, we incrementally update the visible list in O(k) based on expand/collapse operations, and then apply standard list virtualization on top of it.

如果你下一步还想继续升级（建议）

我可以再带你做这三个“真正高级版本”：

🔥 v5（真实 IDE 级）

lazy loading children (async fetch)
placeholder node

🔥 v6（超大规模优化）

stable index map（O(1) lookup）
no findIndex
pointer-based insertion

🔥 v7（Figma / VSCode级）

keyboard navigation (↑ ↓ → ←)
focus management
aria tree accessibility