虚拟 DOM 和 DIFF 算法

约 5401 字大约 18 分钟

2026-06-05

虚拟 DOM 配合 Diff 算法通过最小化真实 DOM 操作提升视图更新效率。Vue 3 在编译时借助静态提升、PatchFlags、Block Tree 和最长递增子序列等优化，大幅减少运行时无意义的节点对比，相比 Vue 2 的全量递归 Diff 性能更优。

虚拟 DOM

虚拟 DOM 本质上是用 JavaScript 对象来描述真实 DOM 结构的数据结构。

真实 DOM：浏览器提供的庞大、复杂的对象树，直接操作成本高（会触发重排和重绘）。
虚拟 DOM：轻量级的 JS 对象，操作成本低。

真实 HTML

<div id="app" class="container">
  <h1>Hello</h1>
</div>

对应的虚拟 DOM

const vnode = {
  tag: 'div',
  props: { id: 'app', class: 'container' },
  children: [
    { tag: 'h1', props: {}, children: ['Hello'] }
  ]
}

虚拟 DOM 是 Diff 算法的载体。当数据变化时，我们不直接操作真实 DOM，而是生成一棵新的虚拟 DOM 树，再通过 Diff 算法对比新旧虚拟树，找出最小差异，最终以最小的代价更新真实 DOM。

因此，“虚拟 DOM 比真实 DOM 快”这句话并不严谨。虚拟 DOM 本身只是一个便于对比差异的 JavaScript 对象，真正带来性能提升的，是 Diff 算法计算出的最小化更新策略。更准确的公式是：

高效的视图更新 = 虚拟 DOM + Diff 算法 + 最小化 DOM 操作

Diff 算法

Diff 算法就是一种对比算法，用于找到新旧虚拟 DOM 之间的最小差异，然后只对变化的部分执行真实 DOM 更新，跳过无需更新的节点，从而提升更新效率。

对比流程

Diff 算法整体采用深度优先遍历，并对子节点进行同层比较。从根节点开始，先比较当前节点，若可复用则递归进入子节点数组进行对比，子节点处理完毕后再回到当前层级处理下一个兄弟节点。

当组件内的响应式数据变化时，会触发 setter，通过 Dep.notify 通知所有订阅者（Watcher），最终调用 patch 方法进行新旧对比。

patch

patch 的核心作用是通过 sameVnode 判断新旧虚拟节点是否属于同一类型：

是：调用 patchVnode 进行深层比较与复用。
否：直接替换——移除旧节点对应的真实 DOM，创建并插入新节点。

function patch(oldVnode, newVnode) {
  if (sameVnode(oldVnode, newVnode)) {
    // 同一类型，深入比较
    patchVnode(oldVnode, newVnode)
  } else {
    // 类型不同，整体替换
    const parent = oldVnode.el.parentNode
    const el = createElm(newVnode)  // 根据新虚拟节点创建真实 DOM
    if (parent) {
      parent.insertBefore(el, oldVnode.el)  // 插入新节点
      parent.removeChild(oldVnode.el)       // 移除旧节点
    }
  }
}

function sameVnode(a, b) {
  return (
    a.key === b.key && // key 相同
    a.tag === b.tag    // 标签名相同
    sameInputType(a, b) // 当标签为input时，type相同
    // 其它条件 ......
  )
}

patchVnode

patchVnode 用于对比两个相同类型节点的自身属性、文本以及子节点。大致流程如下：

如果新旧节点引用完全一致（oldVnode === newVnode），直接返回。
如果新节点是文本节点（即 newVnode.text 存在），且与旧文本不同，则更新真实 DOM 的文本内容。
否则，新旧节点可能包含子节点：
- 新旧都有子节点：调用 updateChildren 进行首尾指针对比。
- 只有新节点有子节点：创建新子节点并插入真实 DOM。
- 只有旧节点有子节点：从真实 DOM 中移除旧子节点。
- 两者均无子节点：不做额外处理。

function patchVnode(oldVnode, newVnode) {
  const el = (newVnode.el = oldVnode.el) // 复用真实 DOM 引用
  const oldCh = oldVnode.children
  const newCh = newVnode.children

  // 同一对象无需处理
  if (oldVnode === newVnode) return

  // 新节点是文本节点
  if (newVnode.text != null) {
    if (oldVnode.text !== newVnode.text) {
      el.textContent = newVnode.text
    }
  } else {
    // 新节点有子节点
    if (oldCh && newCh) {
      // 新旧都有子节点，进入核心 diff
      if (oldCh !== newCh) {
        updateChildren(el, oldCh, newCh)
      }
    } else if (newCh) {
      // 只有新子节点：创建并添加
      addVnodes(el, null, newCh, 0, newCh.length - 1)
    } else if (oldCh) {
      // 只有旧子节点：删除旧子节点
      removeVnodes(el, oldCh, 0, oldCh.length - 1)
    }
    // 如果都没有子节点，什么也不做
  }
}

双端比较

updateChildren 是双端 Diff（首尾指针法）的核心，用于对同层的新旧子节点数组进行比较。维护四个指针：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx，在循环中执行以下逻辑：

首尾快速尝试（按顺序）：
- 旧头 vs 新头：相同则 patch 并向右移动两个头指针（无需移动 DOM）。
- 旧尾 vs 新尾：相同则 patch 并向左移动两个尾指针（无需移动 DOM）。
- 旧头 vs 新尾：相同则 patch，并将旧头对应的真实 DOM 移动到旧尾之后，然后旧头右移、新尾左移。
- 旧尾 vs 新头：相同则 patch，并将旧尾对应的真实 DOM 移动到旧头之前，然后旧尾左移、新头右移。
乱序查找：若上述四种比较均失败，则在旧子节点范围（oldStartIdx..oldEndIdx）中查找新头节点：
- 找到了：patch 后将该旧节点的真实 DOM 移动到旧头之前（未处理节点前），并将旧数组中该位置标记为 undefined（避免重复处理），只将 newStartIdx 右移。
- 未找到：视为新增节点，创建真实 DOM 并插入到旧头之前，newStartIdx 右移。
边界跳过：每次循环开始，若 oldStartIdx 或 oldEndIdx 指向 undefined，则直接向内移动该指针并跳过。
收尾处理：
- 若 oldStartIdx > oldEndIdx（旧节点先耗尽），剩余新节点均为新增，批量创建并插入。
- 若 newStartIdx > newEndIdx（新节点先耗尽），剩余旧节点（非 undefined）均需卸载删除。

示例推演：以下面新旧节点为例，真实 DOM 初始为 a, b, c, d, e。

<!-- 旧节点 -->
<ul>
  <li>a</li><li>b</li><li>c</li><li>d</li><li>e</li>
</ul>
<!-- 新节点 -->
<ul>
  <li>a</li><li>d</li><li>e</li><li>f</li>
</ul>

初始状态：

DOM: a b c d e
old: [a] b c d [e]    (os=0, oe=4)
new: [a] d e [f]      (ns=0, ne=3)

第一步：旧头 a vs 新头 a ，匹配。

无 DOM 移动，os++、ns++。

DOM: a b c d e
old: a [b] c d [e]   (os=1, oe=4)
new: a [d] e [f]     (ns=1, ne=3)

第二步：四种比较均不命中，查找新头 d 在旧范围 [b,c,d,e] 中，找到索引 3。
移动 d 对应的真实 DOM 到旧头 b 之前，将 old[3] 置为 undefined，ns++。

DOM: a d b c e
old: a [b] c undefined [e]   (os=1, oe=4)
new: a d [e] [f]             (ns=2, ne=3)

第三步：旧尾 e vs 新头 e ，匹配。

移动旧尾 e 的 DOM 到旧头 b 之前（即 d 之后），oe--、ns++。

DOM: a d e b c
old: a [b] c undefined e   (os=1, oe=3，oe 收缩后指向索引 3 是 undefined)
new: a d e [f]             (ns=3, ne=3)

注：下一轮循环开始前，oe 因指向 undefined 会继续左移至索引 2（c），范围变为 os=1, oe=2。

第四步：当前有效范围 [b, c]，新头为 f。四种比较全不匹配，且 f 未找到。
创建 f 的 DOM 并插入到旧头 b 之前，ns++ → ns=4 > ne，循环结束。

DOM: a d e f b c
old: a [b] [c] undefined e   (os=1, oe=2)
new: a d e [f] []          (ns>ne)

收尾：ns > ne，删除旧范围 os=1 到 oe=2 内的 b 和 c。
最终真实 DOM：a, d, e, f，与新虚拟 DOM 结构一致。

Diff 优化

上述 Diff 流程描述的是 Vue 2.x 时代建立起来的双端 Diff 算法，它在同层子节点对比中表现优秀，但也存在明显的性能瓶颈——每次更新都要递归遍历整棵虚拟 DOM 树，即便大量节点完全没有变化。Vue 3 在编译阶段做了大量工作，将优化前置到编译时，运行时只需处理真正变化的部分，从而实现了性能的大幅跃升。

静态提升

原理：将编译时确定的静态节点（不依赖任何响应式数据）提升到渲染函数外部，避免每次渲染时重复创建并对比。

在 Vue 2 中，即使是纯静态的 <div>static</div>，每次组件重新渲染时都会重新生成虚拟 DOM 节点，并在 Diff 中参与无意义的对比。Vue 3 的编译器能够识别出纯静态的子树，并将其提取到渲染函数之外：

// 编译前 - 模板
<div>
  <p>static text</p>
  <p>{{ dynamic }}</p>
</div>

// Vue 3 编译后（简化）
import { createElementVNode as _createElementVNode, toDisplayString as _toDisplayString } from 'vue'

// 静态节点被提升到函数外部
const _hoisted_1 = /*#__PURE__*/ _createElementVNode('p', null, 'static text', -1 /* HOISTED */)

export function render(_ctx, _cache) {
  return _createElementVNode('div', null, [
    _hoisted_1,  // 直接引用已创建的静态节点，不会重复创建
    _createElementVNode('p', null, _toDisplayString(_ctx.dynamic), 1 /* TEXT */)
  ])
}

优化后，静态节点只创建一次，后续渲染直接复用同一个虚拟节点对象。Diff 过程中，静态节点因为 patchFlag === -1 会被 patch 函数跳过直接返回，最终达到避免进行无用对比。

PatchFlags

原理：编译器在编译阶段分析每个节点的动态特性，并生成一个位掩码（PatchFlag）作为虚拟节点的元信息。运行时 Diff 可以根据这个标记快速跳过不需要对比的属性或子节点。

Vue 3 的 patch 函数在处理同一类型节点时，不再像 Vue 2 那样“盲目”地对比所有属性，而是依据 patchFlag 在 patchNode 进行按需对比：

编译前模板：

<template>
  <div>
    <h1>Welcome</h1>                <!-- 纯静态 -->
    <p>{{ userName }}</p>           <!-- 动态文本 -->
    <input :value="searchText" />   <!-- 动态属性 -->
  </div>
</template>

编译后渲染函数（简化）：

// 静态节点被提升，标记为 -1 (HOISTED)
const _hoisted_1 = /*#__PURE__*/ createElementVNode('h1', null, 'Welcome', -1)

export function render(_ctx, _cache) {
  return createElementVNode('div', null, [
    _hoisted_1,                                                   // 跳过 diff
    createElementVNode('p', null, toDisplayString(_ctx.userName), 1 /* TEXT */),
    createElementVNode('input', { value: _ctx.searchText }, null, 8 /* PROPS */, ['value'])
  ])
}

标记含义：

patchFlag = -1：静态提升节点，运行时完全跳过 Diff。
patchFlag = 1 (TEXT)：只有文本内容可能变化，Diff 时只对比 textContent。
patchFlag = 8 (PROPS) + dynamicProps = ['value']：只有 value 属性需要对比，其他属性（如 type）不参与 Diff。

Block Tree

区块树，编译器将模板分割成若干结构稳定的“区块”（Block），每个区块会收集其内部所有动态子节点到一个数组中（dynamicChildren）。运行时 Diff 时，只遍历这个数组，从而完全跳过静态节点，将时间复杂度从整棵树规模降低到动态节点数量。

模板中包含静态和动态内容：

<template>
  <div>
    <h1>Title</h1>                <!-- 静态 -->
    <p>{{ msg }}</p>              <!-- 动态文本 -->
    <button @click="inc">+1</button>   <!-- 动态事件 -->
  </div>
</template>

编译后的渲染函数：

import { openBlock, createBlock, createElementVNode, toDisplayString } from 'vue'

export function render(_ctx, _cache) {
  // 开启一个区块，所有在这个区块内创建的元素都会自动收集到 dynamicChildren 中
  openBlock()
  
  // createBlock 返回一个特殊的虚拟节点，它会保存当前区块收集到的动态子节点数组
  return createBlock('div', null, [
    createElementVNode('h1', null, 'Title'),                         // 静态，不会被收集
    createElementVNode('p', null, toDisplayString(_ctx.msg), 1),     // TEXT 标记，被收集
    createElementVNode('button', { onClick: _ctx.inc }, '+1', 8, ['onClick'])  // PROPS 标记，被收集
  ])
}

运行时产生的区块结构：

// 区块虚拟节点（Block VNode）
const blockVNode = {
  tag: 'div',
  children: [ /* 三个子节点 */ ],
  dynamicChildren: [
    { tag: 'p', children: 'hello', patchFlag: 1 },       // 动态文本节点
    { tag: 'button', props: { onClick: fn }, patchFlag: 8, dynamicProps: ['onClick'] }
  ]
}

运行时效果：

每个 Block 的 dynamicChildren 数组直接指向其内部所有动态节点（跳过静态节点）。
当 Block 内部响应式数据变化时，只遍历该 Block 的 dynamicChildren 进行 Diff。
如果 Block 结构完全不变（例如 v-if 分支未切换），甚至不需要对比 dynamicChildren 的顺序。

对于 v-for 的特殊处理：由于 v-for 生成的节点数量不固定，不能使用 dynamicChildren 的线性遍历。Vue 3 会为 v-for 创建一个单独的 Block，并回退到最长递增子序列优化的完整 Diff 算法。

当处理 v-for 列表更新时，新旧子节点数组可能发生重排序。Vue 2 的双端 Diff 通过多次移动节点来调整顺序，但在某些场景下会产生不必要的 DOM 移动。Vue 3 引入了一种更数学化的方法：先找出那些不需要移动的节点（它们在新旧列表中的相对顺序已经正确），然后只移动其他节点。这个“不需要移动的节点集合”正是最长递增子序列（Longest Increasing Subsequence）。

最长递增子序列

核心思路

遍历新子节点数组，找到每个节点在旧子节点数组中的位置（通过 key 映射），得到一个位置数组。
计算这个位置数组的最长递增子序列。该子序列对应的节点，在新旧列表中已经保持相同的相对顺序，因此不需要移动。
仅移动不属于该子序列的节点，将其插入到正确位置。

例子：

旧子节点顺序：[a, b, c, d, e] （索引：0, 1, 2, 3, 4）
新子节点顺序：[a, c, d, e, b]

步骤 1：建立旧节点 key 到索引的映射

keyToIndex = { a:0, b:1, c:2, d:3, e:4 }

步骤 2：遍历新节点，生成“新节点在旧列表中的索引”数组

newIndexToOldIndex = [
  a → 0,
  c → 2,
  d → 3,
  e → 4,
  b → 1
]
// 得到数组 [0, 2, 3, 4, 1]

步骤 3：计算 [0, 2, 3, 4, 1] 的最长递增子序列

递增子序列：一个子序列，其中每个元素都比前一个大（严格递增）。

可能的递增子序列：[0, 2, 3, 4]（长度 4）、[0, 1]（长度 2）等。
最长的是 [0, 2, 3, 4]，对应的索引为 [0, 1, 2, 3]（即新节点数组中第 0、1、2、3 个元素）。

步骤 4：确定哪些节点不需要移动

最长递增子序列 [0, 2, 3, 4] 对应新节点 [a, c, d, e]。这些节点在旧列表中的相对顺序（0 < 2 < 3 < 4）保持不变，因此它们不需要移动。

唯一不在子序列中的节点是 b（对应新数组索引 4，旧索引 1）。b 需要被移动到 e 之后。

最终只需要一次 DOM 移动：将 b 插入到 e 后面。而 Vue 2 的双端 Diff 可能需要多次移动。

算法实现

计算最长递增子序列在 Vue3 中使用了 getSequence 函数，其算法思想使用了贪心 + 二分法 + 前驱回溯，时间复杂度 $O(N \log N)$ 。

getSequence()
/**
 * 获取最长递增子序列 (Longest Increasing Subsequence, LIS) 的索引数组
 * 
 * 核心思想
 * 1. 贪心算法：为了让递增子序列尽可能长，我们应该贪心地让每个长度的子序列的“末尾元素”尽可能小。
 *    末尾元素越小，后续元素能接在它后面的概率就越大。
 * 2. 二分查找：由于我们维护的“各长度子序列的最小末尾元素”是严格单调递增的，
 *    因此可以使用二分查找，将传统动态规划 O(N^2) 的时间复杂度降低到 O(N log N)。
 * 3. 前驱回溯：标准的贪心+二分只能求出 LIS 的“长度”，为了还原出“具体的序列”，
 *    我们需要额外记录每个元素在构成 LIS 时的“前一个元素”的索引（前驱），最后通过链表回溯还原。
 * 
 * @param {number[]} arr - 数字索引数组（代表新节点在旧节点中的索引，0 表示新增节点）
 * @returns {number[]} - 最长递增子序列在原数组中的索引集合
 */
function getSequence(arr) {
  const len = arr.length
  if (len === 0) return []
  
  // 贪心
  // result 数组用于维护“不同长度递增子序列的最小末尾元素”的【索引】。
  // result[j] = i 表示：在所有长度为 j+1 的递增子序列中，末尾元素 arr[i] 是最小的。
  // 注意：result 中存储的是索引，而不是具体的值。因为 arr[result[0...end]] 对应的值是严格单调递增的，这是能使用二分查找的前提。
  // 初始化时，假设第一个元素（索引0）构成长度为1的子序列。
  const result = [0]
  
  // 前驱回溯
  // p 数组用于记录每个元素在最终 LIS 中的“前驱索引”。
  // p[i] = j 表示：在构成当前最长递增子序列时，元素 arr[i] 前面的那个元素是 arr[j]。
  // 初始化为 -1，表示没有前驱（即它是子序列的第一个元素）。
  const p = new Array(len).fill(-1)
  
  for (let i = 0; i < len; i++) {
    const val = arr[i]
    
    // 【Vue 特殊处理】
    // 跳过占位值 0。在 Vue 的 Diff 过程中，0 代表这是一个全新创建的节点（还没有对应的真实 DOM）。
    // 新节点不存在“移动”的概念，因此不参与 LIS（求最少移动次数）的计算。
    if (val === 0) continue
    
    // 二分查找
    // 目标：在 result 数组中，找到第一个 arr[result[pos]] >= val 的位置（即 left）。
    // 因为 result 对应的值是单调递增的，所以可以使用二分查找快速定位。
    let left = 0
    let right = result.length - 1
    while (left <= right) {
      const mid = (left + right) >> 1 // 位运算代替除以2，向下取整
      const midVal = arr[result[mid]] // 取出 result 中索引对应的实际值
      
      if (midVal < val) {
        // 中间值小于当前值，说明目标位置在右侧
        left = mid + 1
      } else {
        // 中间值大于等于当前值，说明目标位置在左侧或就是当前位置
        right = mid - 1
      }
    }
    // 循环结束时，left 就是第一个 >= val 的位置（即替换位置）。
    // 如果 left === result.length，说明 val 比所有末尾都大，应该追加到末尾。
    
    // 更新 result (贪心策略) 
    if (left === result.length) {
      // 【贪心思想体现：扩展长度】
      // 当前值比所有已有子序列的末尾都大，说明我们可以得到一个更长的递增子序列。
      // 将当前索引追加到 result 末尾，LIS 长度 +1。
      result.push(i)
    } else {
      // 【贪心思想体现：优化末尾】
      // 当前值较小，可以替换掉原来那个较大的末尾值。
      // 这样在“相同长度”下，我们得到了一个“更小的末尾值”，使得未来子序列变长的可能性更大。
      result[left] = i
    }
    
    // 记录前驱 (为回溯做准备)
    if (left > 0) {
      // 如果当前元素不是接在长度为 1 的子序列后面（即 left > 0），
      // 那么它的前驱就是“上一个长度（left）”的子序列的最小末尾元素，即 result[left - 1]。
      // 这一步将离散的节点通过 p 数组串联成了一条链表。
      p[i] = result[left - 1]
    }
  }
  
  // 回溯重建 LIS 索引数组
  // 此时 result 数组中存储的已经是 LIS 最后一个元素的索引（在 result 末尾），
  // 但 result 前面的元素并不是真正的 LIS 序列（因为被贪心替换过）。
  // 我们需要从最后一个元素开始，利用 p 数组（前驱链表）一步步往前找，还原出真正的 LIS。
  
  let u = result.length      // LIS 的总长度
  let v = result[u - 1]      // LIS 最后一个元素在原数组中的索引
  
  // 从后往前倒序填充 result 数组
  while (u-- > 0) {
    result[u] = v            // 将当前找到的正确索引放入 result
    v = p[v]                 // 沿着前驱链继续往前找上一个元素的索引
  }
  
  // 最终 result 数组中存储的就是完整的最长递增子序列在原数组中的【索引】
  return result
}

console.log(getSequence([0,2,3,5]))

算法演示

以 arr = [1, 3, 2, 4, 7, 6] 为例，逐步执行上述算法：

i	val	result (存储索引)	操作	p[i]
0	1	[0]	初始化	-
1	3	[0,1]	追加 i=1	p[1]=0
2	2	[0,2]	替换 result[1]=2	p[2]=0
3	4	[0,2,3]	追加 i=3	p[3]=2
4	7	[0,2,3,4]	追加 i=4	p[4]=3
5	6	[0,2,3,5]	替换 result[3]=5	p[5]=3

最终回溯：

result = [0,2,3,5]，对应值 arr[0]=1, arr[2]=2, arr[3]=4, arr[5]=6
LIS 值序列为 [1,2,4,6]（长度 4）

算法找到了一个长度为 4 的递增子序列，虽然原始数组中还有 [1,3,4,7] 也是长度为 4，但贪心策略选择了末尾更小的子序列 [1,2,4,6]，因为这样更有利于后续扩展（尽管本例中已无后续元素）。

Vue2 与 Vue3 Diff 差异

Vue3 在 Diff 算法上相比 Vue2 进行了编译时 + 运行时的全方位重构，不再是单纯的“双端比较 + 递归全量对比”，而是利用编译时信息大幅减少运行时需要对比的节点数量。

对比维度	Vue2 Diff	Vue3 Diff
对比策略	全量递归，所有节点都会参与 Diff	区块（Block）隔离 + 动态节点收集，只对比动态节点
静态节点处理	每次 render 都会重新创建并参与 Diff	静态提升（Hoisted），只创建一次，Diff 完全跳过
属性对比	无差别对比所有属性	通过 `PatchFlags` 按需对比（如只对比文本、只对比特定 props）
列表 Diff	双端比较（首尾指针法），需要多次移动 DOM	最长递增子序列（LIS）算法，先找到最少移动节点，再移动剩余节点
`v-for` 处理	与普通节点一致，参与双端比较	单独生成 Block，回退到完整的 LIS Diff（因为节点数量不固定）
时间复杂度（最坏）	O(N²)（大量乱序移动）	O(N log N)（LIS 的二分查找主导）