Vue 3 渲染器深度解析：Diff 算法与 DOM 移动策略

前情回顾：上一章我们了解到，当列表子节点发生变化时，渲染器会调用 patchChildren。那么，Vue 3 如何用最少的 DOM 操作完成列表更新呢？答案就在 Diff 算法中。

---

Diff 的策略选择：九种情况的决策

在进入 Diff 算法之前，我们需要理解 patchChildren 的分发逻辑。这个函数根据新旧子节点的类型决定采用何种策略。

新旧组合的九种可能

新旧 children 各有 3 种形态：Text（文本）、Array（数组）、Null（空）。

关键点：只有当新旧子节点都是数组时，才需要真正的 Diff 算法。其他 8 种都是简单的 DOM 操作（replace/mount/unmount）。

理解了这个决策树后，我们来看编译器如何优化这个过程。

编译时优化 vs 运行时兜底

// 伪代码
function patchChildren(n1, n2, container) {
  // 编译时已标记子节点类型？
  if (n2.patchFlag & KEYED_FRAGMENT) {
    patchKeyedChildren(...)     // 快速路径：有 key 的列表
    return
  } else if (n2.patchFlag & UNKEYED_FRAGMENT) {
    patchUnkeyedChildren(...)   // 快速路径：无 key 的列表
    return
  }

  // 运行时形状判断（手写 render 函数的兜底）
  if (n2.shapeFlag & TEXT_CHILDREN) {
    // 新是文本：卸载旧数组，设置文本
  } else if (n2.shapeFlag & ARRAY_CHILDREN) {
    // 新是数组：进行完整 diff
    patchKeyedChildren(n1.children, n2.children, ...)
  }
}

编译器在编译期就会通过 patchFlag 标记列表类型（有 key 或无 key），运行时直接走对应的快速路径。如果是手写 render 函数，则通过 shapeFlag 在运行时判断。

了解了策略分发后，我们先看最简单的情况：无 key 列表。

---

无 Key 列表：按索引对齐

当列表没有 key 时，Vue 采用最简单的策略：按索引对齐。

算法逻辑

// 伪代码
function patchUnkeyedChildren(oldChildren, newChildren) {
  const commonLength = Math.min(oldChildren.length, newChildren.length)

  // 公共长度内：逐个 patch
  for (let i = 0; i < commonLength; i++) {
    patch(oldChildren[i], newChildren[i], ...)
  }

  // 处理长度差异
  if (oldChildren.length > newChildren.length) {
    // 旧的多：卸载多余的
    unmountChildren(oldChildren.slice(commonLength))
  } else if (newChildren.length > oldChildren.length) {
    // 新的多：挂载新增的
    mountChildren(newChildren.slice(commonLength))
  }
}

优势：O(n) 复杂度，无需 Map、无需计算 LIS，效率很高。

劣势：完全无法保证节点身份复用。

为什么会有这个问题呢？让我们看一个具体场景。

状态复用的问题

场景：列表项重新排序
旧: [A, B, C]  →  新: [C, A, B]

按索引对齐的后果：
旧[0]=A patch 新[0]=C  →  A 被当成 C 处理
旧[1]=B patch 新[1]=A  →  B 被当成 A 处理
旧[2]=C patch 新[2]=B  →  C 被当成 B 处理

如果这些是有状态组件（如表单），内部状态会被错误复用！
A 的数据残留在了 C 的位置。

结论：无 key 策略仅适用于纯渲染型列表。有状态组件必须加 key。

无 key 的处理很简单。但当列表有 key 时，Vue 3 使用了一个更复杂但高效的算法。

---

有 Key 列表：快速 Diff 算法

当列表有 key 时，Vue 3 使用快速 Diff 算法。这个算法分三个阶段：双端预处理 + 乱序处理 + LIS 最小化移动。

双端预处理的工作原理

核心思想：用双指针从两端同时扫描，快速跳过已匹配的节点。

具体过程：

初始状态：
旧: [a][b] [c][d][e]
新: [a][b] [f][c][d][g]
     ↑                 ↑
     i=0           e1=4 e2=5

头部同步：
旧[0]=a 与 新[0]=a 匹配 ✓
旧[1]=b 与 新[1]=b 匹配 ✓
旧[2]=c 与 新[2]=f 不匹配 ✗ 停止
    → i 推进到 2

尾部同步：
旧[4]=e 与 新[5]=g 不匹配 ✗ 停止
   → e1=4, e2=5 保持

中间乱序区域：
旧[2..4] = c d e
新[2..5] = f c d g

这个预处理过程大幅减少了需要处理的节点数量。现在我们来看具体的三个阶段。

阶段 1：头部同步

// 伪代码
while (i <= e1 && i <= e2) {
  if (isSameVNodeType(oldChildren[i], newChildren[i])) {
    patch(oldChildren[i], newChildren[i], ...)
    i++
  } else {
    break  // 遇到不同节点，停止
  }
}

效果：列表末尾追加元素时（如分页加载），头部全部命中，只需处理尾部新增。

头部同步完成后，接着处理尾部。

阶段 2：尾部同步

// 伪代码
while (i <= e1 && i <= e2) {
  if (isSameVNodeType(oldChildren[e1], newChildren[e2])) {
    patch(oldChildren[e1], newChildren[e2], ...)
    e1--
    e2--
  } else {
    break
  }
}

效果：列表头部插入元素时（如消息列表顶部推送），尾部全部命中。

经过双端同步后，可能出现两种简单情况，可以直接处理。

阶段 3：简单情况的快速处理

经过双端同步，可能出现两种简单情况：

// 情况一：仅新增
if (i > e1 && i <= e2) {
  // 旧节点用完了，新节点还有
  // 直接挂载新增节点
  for (; i <= e2; i++) {
    mount(newChildren[i], ...)
  }
}

// 情况二：仅删除
else if (i > e2 && i <= e1) {
  // 新节点用完了，旧节点还有
  // 直接卸载多余节点
  for (; i <= e1; i++) {
    unmount(oldChildren[i], ...)
  }
}

// 情况三：中间乱序，进入通用 Diff
else {
  // 进入复杂处理...
}

效果：80% 的实际场景在这两个简单情况就解决了，无需触发 LIS 算法。

但如果双端预处理后仍有中间乱序区域，就需要进入更复杂的处理流程。

---

乱序处理：建立索引映射

当无法通过双端预处理完全覆盖时（如 [a,b,c,d] → [a,c,b,e,d]），进入通用乱序 Diff。

建立映射表

// 伪代码
// Step 1：为新节点建立 key→index 的快速查找
const keyToNewIndexMap = new Map()
for (let i = startNew; i <= endNew; i++) {
  if (newChildren[i].key != null) {
    keyToNewIndexMap.set(newChildren[i].key, i)
  }
}

// Step 2：遍历旧节点，查找可复用的新节点
const newIndexToOldIndexMap = new Array(newNodeCount).fill(0)
// 注意：用 0 表示新节点，oldIndex+1 表示可复用（避免 0 歧义）

let patched = 0  // 已处理新节点数
let moved = false // 是否需要移动

for (let i = startOld; i <= endOld; i++) {
  const oldVNode = oldChildren[i]

  // 关键优化：早期终止
  if (patched >= newNodeCount) {
    unmount(oldVNode, ...)  // 剩余旧节点直接卸载
    continue
  }

  let newIndex
  if (oldVNode.key != null) {
    newIndex = keyToNewIndexMap.get(oldVNode.key)
  } else {
    // 无 key 兜底：线性查找（性能退化，但有保障）
    for (let j = startNew; j <= endNew; j++) {
      if (isSameVNodeType(oldVNode, newChildren[j])) {
        newIndex = j
        break
      }
    }
  }

  if (newIndex === undefined) {
    unmount(oldVNode, ...)
  } else {
    newIndexToOldIndexMap[newIndex - startNew] = i + 1  // +1 避免 0 歧义

    // 检测是否需要移动
    if (newIndex >= maxNewIndexSoFar) {
      maxNewIndexSoFar = newIndex
    } else {
      moved = true  // 发现逆序：后续需要移动 DOM
    }

    patch(oldVNode, newChildren[newIndex], ...)
    patched++
  }
}

关键变量解析：

变量	含义
keyToNewIndexMap	新列表的快速查找表（O(1) 查找）
newIndexToOldIndexMap	映射关系表（记录每个新节点来自哪个旧节点）
patched	计数器（避免后续无效 Map 查找）
moved	标志（是否发现逆序关系）

时序重点：此阶段只 Patch 不 Move！DOM 位置还未改变，只是节点内容更新了。

建立好映射关系后，我们需要解决一个关键问题：如何最小化 DOM 移动次数？答案是最长递增子序列（LIS）。

---

最长递增子序列：最小化 DOM 移动

这是算法的精华：找出不需要移动的节点，只移动必须移动的。

核心思想

具体分析：

场景：旧[a, b, c, d, e] → 新[a, c, e, b, d]

c 和 e 在新旧列表中的相对顺序没变（旧[2]→新[1]，旧[4]→新[2]）
b 和 d 的相对顺序被打乱了

策略：
固定 c、e 不动，只移动 b、d = 2 次移动
如果全部移动 = 4 次移动（浪费）

LIS 的作用：找出原本就按顺序排列的最长子集
这些节点不需要移动，作为移动的参照点。

理解了 LIS 的作用后，我们来看具体的计算算法。

getSequence 函数：O(n log n) 的贪心算法

getSequence 函数使用贪心算法配合二分查找来计算 LIS：

// 伪代码
function getSequence(arr) {
  // arr 是 newIndexToOldIndexMap，存储的是 oldIndex 序列
  // 目标：找出递增子序列的索引

  const result = [0] // 记录 LIS 的索引
  const p = arr.slice() // 前驱数组：记录回溯链路

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 0) continue // 新节点，跳过

    if (arr[i] > arr[result.at(-1)]) {
      // 当前值比 LIS 最后一个大，直接追加
      p[i] = result.at(-1)
      result.push(i)
    } else {
      // 二分查找：找到第一个 >= arr[i] 的位置，替换
      // 这样做的目的是"保持 result 尽可能小"，为后续元素留出空间
      const pos = binarySearch(result, arr, arr[i])
      p[i] = result[pos - 1]
      result[pos] = i
    }
  }

  // 回溯：通过前驱数组 p 还原真正的 LIS 链路
  let u = result.length
  let v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }

  return result
}

三个关键步骤：

1. 贪心追加或替换：尽量让 result 的值更小，为后续元素留出空间
2. 记录前驱链路：p 数组记录每个位置的"上一个索引"
3. 回溯还原：倒序遍历 p 数组，得到正确的 LIS 索引序列

具体演示

输入数组：arr = [3, 5, 2, 4]

Step 1: i=0, arr[0]=3
  result = [0]（存索引 0，值为 3）
  p[0] = undefined

Step 2: i=1, arr[1]=5
  5 > 3，追加
  result = [0, 1]
  p[1] = 0

Step 3: i=2, arr[2]=2
  2 < 3，替换 result[0]
  result = [2, 1]（此时对应值 [2, 5]，不是真实 LIS）
  p[2] = undefined

Step 4: i=3, arr[3]=4
  2 < 4 < 5，替换 result[1]
  result = [2, 3]
  p[3] = 2

回溯：
  v = result[1] = 3，result[1] = 3
  v = p[3] = 2，result[0] = 2
  返回 [2, 3]，对应值 [2, 4]

最终 LIS = [2, 4]（对应的原索引 [2, 3]）

*为什么需要回溯？

因为在替换过程中，result 数组会暂时处于乱序状态。只有通过 p 数组的链路，才能还原出真正递增的 LIS。

计算好 LIS 后，就可以进行最后的 DOM 调整了。

---

移动与挂载：倒序遍历

有了 LIS，我们就知道哪些节点不需要移动。现在进行最后的 DOM 调整。

// 伪代码
const lis = moved ? getSequence(newIndexToOldIndexMap) : []
let lisPointer = lis.length - 1

// 从后往前遍历新节点
for (let i = newNodeCount - 1; i >= 0; i--) {
  const nextIndex = startNew + i
  const nextVNode = newChildren[nextIndex]

  // 锚点：当前节点的下一个（已处理，位置正确）
  const anchor = nextIndex + 1 < newChildren.length
    ? newChildren[nextIndex + 1].el
    : parentAnchor

  if (newIndexToOldIndexMap[i] === 0) {
    // 新节点，挂载
    mount(nextVNode, container, anchor, ...)
  } else if (moved) {
    // 需要移动？判断是否在 LIS 中
    if (lisPointer < 0 || i !== lis[lisPointer]) {
      // 不在 LIS 中，移动
      move(nextVNode, container, anchor, ...)
    } else {
      // 在 LIS 中，跳过移动
      lisPointer--
    }
  }
}

为什么倒序遍历？

具体原因：

正序遍历的问题：
前面节点移动后，后面的锚点失效

倒序遍历的优势：
后面的节点先处理，位置已确定
前面的节点可以用「后面的节点」作为 insertBefore 的锚点
每个操作都有有效的参照点

可视化：

新列表：[a][b][e][c][d][h]
                    ↑
            后面的节点（已处理）

倒序处理：
[h] 需要挂载，使用 parentAnchor
[d] 在 LIS 中，skip
[c] 在 LIS 中，skip
[e] 不在 LIS 中，move 到 [h] 前
[b] 在 LIS 中，skip
[a] 在 LIS 中，skip

结果：所有操作都以已处理的节点为参照，始终有效

理解了倒序遍历的原理后，让我们用一个完整的例子串联所有步骤。

---

完整流程演示

现在用具体数组追踪从开始到结束的所有步骤。

旧: a b c d e f g
新: a b e c d h f g

【Step 1】头部同步
i=0: a=a ✓, i=1: b=b ✓, i=2: c≠e ✗ 停止
→ i=2

【Step 2】尾部同步
e1=6, e2=7: g=g ✓
e1=5, e2=6: f=f ✓
e1=4, e2=5: e≠h ✗ 停止
→ e1=4, e2=5

【Step 3】中间乱序区域
旧[2..4] = c d e
新[2..5] = e c d h

keyToNewIndexMap = { e:2, c:3, d:4, h:5 }

【Step 4】遍历旧节点，建立映射
- 旧[2]=c: 查询 Map，newIndex=3
  newIndexToOldIndexMap[1] = 3
- 旧[3]=d: newIndex=4
  newIndexToOldIndexMap[2] = 4
- 旧[4]=e: newIndex=2
  newIndexToOldIndexMap[0] = 5
  检测到逆序（2 < 4），moved=true

newIndexToOldIndexMap = [5, 3, 4, 0]

【Step 5】计算 LIS
输入：[5, 3, 4, 0]
LIS([5, 3, 4, 0]) = [1, 2]
对应 oldIndex = [3, 4]（c, d 保持不动）

【Step 6】倒序回溯移动
i=3 (h): newIndexToOldIndexMap[3]=0 → mount(h)
i=2 (d): i=2 in lis[1..2]? 是 → skip
i=1 (c): i=1 in lis[1..2]? 是 → skip
i=0 (e): i=0 in lis? 否 → move(e)

结果：
1 次 mount(h) + 1 次 move(e) = 最小操作数

看完具体例子后，让我们用流程图总结整个算法。

---

算法流程总览

---

复杂度分析

阶段	时间复杂度	说明
头部同步	O(n)	单次遍历
尾部同步	O(n)	单次遍历
Key Map 构建	O(n)	遍历新列表
遍历旧节点	O(n)	包含 O(1) Map 查找
LIS 计算	O(n log n)	贪心 + 二分
移动/挂载	O(n)	倒序遍历

整体复杂度：O(n log n)，瓶颈在 LIS 计算。但 LIS 通常只在乱序时触发，大多数场景下是 O(n)。

了解了算法的时间复杂度后，我们来总结三个关键优化点。

---

总结：三个关键优化

优化 1：双端预处理

减少乱序区域：

• 头尾同步跳过已匹配节点
• 快速处理纯新增/纯删除场景
• 80% 实际列表在此阶段完成

优化 2：patched 计数器

避免无效查找：

• 新节点全部处理完后，剩余旧节点直接批量卸载
• 无需继续执行 Map 查找，性能提升显著

优化 3：LIS 最小化移动

精准定位稳定节点：

• 找出相对顺序不变的最长子序列
• 这些节点作为锚点保持不动
• 只移动不在 LIS 中的节点

---

核心结论

Vue 3 Diff 算法通过双端预处理减少乱序区域，利用最长递增子序列找出稳定节点，最小化 DOM 移动操作。

设计哲学：编译期给出优化提示（patchFlag），运行时用最小代价完成更新。

---

下一章预告：本章我们理解了 Diff 算法如何通过预处理和 LIS 实现最小化 DOM 操作。但还有一个问题：当响应式数据变化时，是谁触发了整个更新流程？下一章，我们将进入 Vue 3 的异步调度系统和组件更新机制。

---