虚拟 DOM 与 Diff 算法 - Vue3

Vue3 对虚拟 DOM 进行了全面重构，引入 PatchFlag 静态标记、Block Tree、最长递增子序列等优化手段，将 Diff 性能提升到一个新的高度。

一、前言

Vue2 的虚拟 DOM 和 Diff 算法已经相当高效，但 Vue3 并没有止步于此。面对大型应用中模板大量静态内容、少量动态节点的场景，Vue2 的全量 Diff 仍然存在优化空间。Vue3 通过编译时和运行时的协同优化，实现了"靶向更新"——只对比可能发生变化的节点，跳过静态内容的无关遍历。

本章将深入 Vue3 虚拟 DOM 的核心数据结构、Diff 算法的优化策略，以及 Block Tree 等创新设计。

二、Vue3 VNode 结构变化

2.1 VNode 类型细化

Vue3 对 VNode 的类型进行了更细粒度的划分，用 shapeFlag 和 patchFlag 两个位掩码字段替代了 Vue2 中大量的类型判断逻辑。

// packages/runtime-core/src/vnode.ts
const VNode = {
  __v_isVNode: true,
  type: null,           // 节点类型：string / Component / Text / Fragment 等
  props: null,          // 属性对象
  key: null,            // key
  children: null,       // 子节点
  component: null,      // 组件实例
  el: null,             // 对应的真实 DOM
  shapeFlag: 0,         // 节点形状标记（元素/组件/文本/子节点类型）
  patchFlag: 0,         // 补丁标记（动态内容的类型）
  dynamicChildren: null // Block Tree 动态子节点数组
}

2.2 ShapeFlag 位掩码

shapeFlag 用于标记 VNode 的类型和子节点类型，通过位运算快速判断：

// 节点类型
export const enum ShapeFlags {
  ELEMENT = 1,                    // 普通 HTML 元素
  FUNCTIONAL_COMPONENT = 1 << 1,  // 函数式组件
  STATEFUL_COMPONENT = 1 << 2,    // 有状态组件
  TEXT_CHILDREN = 1 << 3,         // 文本子节点
  ARRAY_CHILDREN = 1 << 4,        // 数组子节点
  SLOTS_CHILDREN = 1 << 5,        // 插槽子节点
  TELEPORT = 1 << 6,              // Teleport
  SUSPENSE = 1 << 7,              // Suspense
  COMPONENT_SHOULD_KEEP_ALIVE = 1 << 8,
  COMPONENT_KEPT_ALIVE = 1 << 9
}

// 使用示例：判断是否为组件
if (shapeFlag & ShapeFlags.COMPONENT) {
  // 处理组件逻辑
}

2.3 PatchFlag 静态标记

这是 Vue3 最核心的优化之一。编译器在编译阶段分析模板，为动态节点打上 patchFlag，运行时只对比标记的部分。

export const enum PatchFlags {
  TEXT = 1,              // 动态文本节点
  CLASS = 1 << 1,        // 动态 class
  STYLE = 1 << 2,        // 动态 style
  PROPS = 1 << 3,        // 动态属性（非 class/style）
  FULL_PROPS = 1 << 4,   // 动态 key 或含有 v-bind="obj"
  HYDRATE_EVENTS = 1 << 5,
  STABLE_FRAGMENT = 1 << 6,
  KEYED_FRAGMENT = 1 << 7,
  UNKEYED_FRAGMENT = 1 << 8,
  NEED_PATCH = 1 << 9,
  DYNAMIC_SLOTS = 1 << 10,
  DEV_ROOT_FRAGMENT = 1 << 11,
  HOISTED = -1,          // 静态提升节点，永远不会更新
  BAIL = -2              // 退出优化模式
}

三、编译时标记：PatchFlag 的工作原理

3.1 模板编译示例

<template>
  <div>
    <h1>静态标题</h1>
    <p>{{ message }}</p>
    <div :class="activeClass">动态 class</div>
    <input :value="inputValue" :placeholder="placeholderText">
  </div>
</template>

编译后的渲染函数：

import { createElementVNode as _createElementVNode, toDisplayString as _toDisplayString, openBlock as _openBlock, createElementBlock as _createElementBlock } from "vue"

// 静态提升：只创建一次
const _hoisted_1 = /*#__PURE__*/_createElementVNode("h1", null, "静态标题")

export function render(_ctx, _cache) {
  return (_openBlock(), _createElementBlock("div", null, [
    _hoisted_1,
    // PatchFlag: 1 (TEXT) - 只对比文本内容
    _createElementVNode("p", null, _toDisplayString(_ctx.message), 1 /* TEXT */),
    // PatchFlag: 2 (CLASS) - 只对比 class
    _createElementVNode("div", {
      class: _ctx.activeClass
    }, "动态 class", 2 /* CLASS */),
    // PatchFlag: 8 (PROPS) - 只对比 value 和 placeholder
    _createElementVNode("input", {
      value: _ctx.inputValue,
      placeholder: _ctx.placeholderText
    }, null, 8 /* PROPS */, ["value", "placeholder"])
  ]))
}

3.2 PatchFlag 对比逻辑

// packages/runtime-core/src/renderer.ts
const patchElement = (n1, n2, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized) => {
  const el = (n2.el = n1.el)
  const oldProps = n1.props || EMPTY_OBJ
  const newProps = n2.props || EMPTY_OBJ
  const patchFlag = n2.patchFlag

  // 如果存在 patchFlag，进行靶向更新
  if (patchFlag > 0) {
    // 包含动态属性
    if (patchFlag & PatchFlags.FULL_PROPS) {
      patchProps(el, n2, oldProps, newProps, parentComponent, isSVG)
    } else {
      // 动态 class
      if (patchFlag & PatchFlags.CLASS) {
        if (oldProps.class !== newProps.class) {
          hostPatchProp(el, 'class', null, newProps.class, isSVG)
        }
      }
      // 动态 style
      if (patchFlag & PatchFlags.STYLE) {
        hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG)
      }
      // 动态属性
      if (patchFlag & PatchFlags.PROPS) {
        const propsToUpdate = n2.dynamicProps
        for (let i = 0; i < propsToUpdate.length; i++) {
          const key = propsToUpdate[i]
          const prev = oldProps[key]
          const next = newProps[key]
          if (next !== prev || key === 'value') {
            hostPatchProp(el, key, prev, next, isSVG)
          }
        }
      }
    }

    // 动态文本
    if (patchFlag & PatchFlags.TEXT_CHILDREN) {
      if (n1.children !== n2.children) {
        hostSetElementText(el, n2.children)
      }
    }
  } else if (!optimized) {
    // 无 patchFlag，全量对比（fallback）
    patchProps(el, n2, oldProps, newProps, parentComponent, isSVG)
  }
}

四、Block Tree 与动态子节点追踪

4.1 问题背景

在 Vue2 中，Diff 算法需要遍历整棵 VNode 树来找到变化的节点。即使大部分节点是静态的，也需要逐一对比。

Vue3 引入了 Block 概念：将模板划分为多个 Block，每个 Block 追踪自身的动态子节点，更新时只需遍历动态子节点数组。

4.2 Block Tree 结构

4.3 Block 创建过程

// 编译后的代码使用 openBlock / createElementBlock
export function render(_ctx, _cache) {
  return (
    _openBlock(),
    _createElementBlock("div", null, [
      _createElementVNode("h1", null, "静态标题"),           // 静态，不追踪
      _createElementVNode("p", null, _toDisplayString(_ctx.msg), 1 /* TEXT */),  // 动态，加入 dynamicChildren
      _createElementVNode("span", { class: _ctx.cls }, null, 2 /* CLASS */)       // 动态，加入 dynamicChildren
    ])
  )
}

// openBlock 开启一个新的 Block 上下文
export function openBlock(disableTracking = false) {
  blockStack.push((currentBlock = disableTracking ? null : []))
}

// createElementBlock 创建 Block 节点
export function createElementBlock(type, props, children, patchFlag, dynamicProps, shapeFlag) {
  const vnode = createBaseVNode(
    type, props, children, patchFlag, dynamicProps, shapeFlag, true /* isBlockNode */
  )
  // 将当前 Block 的 dynamicChildren 保存到 vnode
  vnode.dynamicChildren = currentBlock || EMPTY_ARR
  // 关闭当前 Block
  blockStack.pop()
  currentBlock = blockStack[blockStack.length - 1] || null
  return vnode
}

// 创建普通 VNode 时，如果当前在 Block 内且是动态节点，则收集
export function createBaseVNode(type, props, children, patchFlag, dynamicProps, shapeFlag, isBlockNode = false) {
  const vnode = {
    type, props, key: props?.key, children,
    shapeFlag, patchFlag, el: null,
    dynamicChildren: null
  }

  // 如果不是 Block 节点本身，且当前在 Block 上下文内，且是动态节点
  if (!isBlockNode && currentBlock && patchFlag > 0) {
    currentBlock.push(vnode)
  }

  return vnode
}

4.4 Block Tree 的 Diff 过程

// packages/runtime-core/src/renderer.ts
const patchBlockChildren = (
  oldChildren,
  newChildren,
  fallbackContainer,
  parentComponent,
  parentSuspense,
  isSVG,
  slotScopeIds
) => {
  for (let i = 0; i < oldChildren.length; i++) {
    const oldVNode = oldChildren[i]
    const newVNode = newChildren[i]

    // 确定容器
    const container = oldVNode.el.parentNode

    // 直接 patch 动态子节点，无需遍历整棵树
    patch(
      oldVNode,
      newVNode,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      true // 启用优化模式
    )
  }
}

五、最长递增子序列算法

5.1 算法引入背景

在 Vue2 的 Diff 中，对于无 key 的列表或需要移动节点的场景，采用的是"双端比较"策略。Vue3 在处理 有 key 的子节点数组 时，引入了最长递增子序列（LIS）算法来最小化 DOM 移动操作。

5.2 核心思想

当新旧子节点数组都有 key 时：

1. 构建新旧节点的 key 索引映射
2. 找出新节点数组在旧数组中的相对顺序
3. 计算最长递增子序列（LIS）
4. LIS 中的节点不需要移动，其余节点需要移动或创建/删除

5.3 算法实现

// packages/runtime-core/src/renderer.ts
function getSequence(arr) {
  const p = arr.slice()        // 记录前驱索引，用于回溯
  const result = [0]           // 存储递增子序列的索引
  let i, j, u, v, c
  const len = arr.length

  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI === 0) continue   // 0 表示新节点，不在旧序列中

    j = result[result.length - 1]
    if (arr[j] < arrI) {
      // 当前值大于序列末尾，直接追加
      p[i] = j
      result.push(i)
      continue
    }

    // 二分查找：找到 result 中第一个大于等于 arrI 的位置
    u = 0
    v = result.length - 1
    while (u < v) {
      c = (u + v) >> 1
      if (arr[result[c]] < arrI) {
        u = c + 1
      } else {
        v = c
      }
    }

    if (arrI < arr[result[u]]) {
      if (u > 0) {
        p[i] = result[u - 1]
      }
      result[u] = i
    }
  }

  // 回溯构建最长递增子序列
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }

  return result
}

5.4 Diff 过程图解

5.5 完整 Diff 流程

// 核心 Diff 逻辑（简化版）
const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1
  let e2 = l2 - 1

  // 1. 从头部开始同步
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized)
    } else {
      break
    }
    i++
  }

  // 2. 从尾部开始同步
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized)
    } else {
      break
    }
    e1--
    e2--
  }

  // 3. 处理剩余节点
  if (i > e1) {
    // 新节点有剩余，需要挂载
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
      while (i <= e2) {
        patch(null, c2[i], container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized)
        i++
      }
    }
  } else if (i > e2) {
    // 旧节点有剩余，需要卸载
    while (i <= e1) {
      unmount(c1[i], parentComponent, parentSuspense, true)
      i++
    }
  } else {
    // 4. 中间存在差异，使用 LIS 算法
    const s1 = i
    const s2 = i

    // 构建新节点的 key -> 索引映射
    const keyToNewIndexMap = new Map()
    for (i = s2; i <= e2; i++) {
      const nextChild = c2[i]
      if (nextChild.key != null) {
        keyToNewIndexMap.set(nextChild.key, i)
      }
    }

    // 遍历旧节点，找到可复用的节点
    const toBePatched = e2 - s2 + 1
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i]
      const newIndex = keyToNewIndexMap.get(prevChild.key)

      if (newIndex === undefined) {
        // 旧节点在新列表中不存在，卸载
        unmount(prevChild, parentComponent, parentSuspense, true)
      } else {
        // 记录旧节点索引（+1 是为了区分 0）
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized)
      }
    }

    // 计算最长递增子序列
    const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)
    let j = increasingNewIndexSequence.length - 1

    // 从后向前遍历，移动/挂载节点
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i
      const nextChild = c2[nextIndex]
      const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor

      if (newIndexToOldIndexMap[i] === 0) {
        // 新节点，需要挂载
        patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized)
      } else {
        if (i !== increasingNewIndexSequence[j]) {
          // 不在 LIS 中，需要移动
          move(nextChild, container, anchor, MoveType.REORDER)
        } else {
          // 在 LIS 中，保持不动
          j--
        }
      }
    }
  }
}

六、快速路径优化

6.1 文本节点快速路径

const processText = (n1, n2, container, anchor) => {
  if (n1 == null) {
    // 挂载文本节点
    n2.el = hostCreateText(n2.children)
    hostInsert(n2.el, container, anchor)
  } else {
    // 更新文本：直接修改 nodeValue
    const el = (n2.el = n1.el)
    if (n1.children !== n2.children) {
      hostSetText(el, n2.children)
    }
  }
}

6.2 静态节点快速路径

const patchElement = (n1, n2, ...) => {
  const el = (n2.el = n1.el)

  // HOISTED 标记：静态提升的节点，永远不会更新
  if (n2.patchFlag === PatchFlags.HOISTED) {
    if (n2.dynamicChildren) {
      // 即使是静态节点，如果包含 Block 子树，仍需处理
      patchBlockChildren(n1.dynamicChildren, n2.dynamicChildren, ...)
    }
    return // 跳过所有属性对比
  }

  // ... 正常 patch 逻辑
}

6.3 Fragment 优化

Vue3 的 Fragment 节点（多根节点）也有专门的优化路径：

const processFragment = (n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized) => {
  const fragmentStartAnchor = n2.el = n1 ? n1.el : hostCreateText('')
  const fragmentEndAnchor = n2.anchor = n1 ? n1.anchor : hostCreateText('')

  const { patchFlag, dynamicChildren } = n2

  if (patchFlag > 0) {
    // STABLE_FRAGMENT：子节点顺序不变，直接 patchBlockChildren
    patchBlockChildren(
      n1.dynamicChildren,
      dynamicChildren,
      container,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds
    )
  } else {
    // 非稳定 Fragment，全量 Diff
    patchChildren(n1, n2, container, fragmentEndAnchor, ...)
  }
}

七、Mermaid 图表：Vue3 Diff 完整流程

八、代码示例：手动触发 Diff 观察

<script setup>
import { ref, nextTick } from 'vue'

const items = ref([
  { id: 1, text: 'A' },
  { id: 2, text: 'B' },
  { id: 3, text: 'C' },
  { id: 4, text: 'D' },
  { id: 5, text: 'E' }
])

const shuffle = () => {
  // 随机打乱顺序，触发 Diff
  items.value = items.value
    .map(value => ({ value, sort: Math.random() }))
    .sort((a, b) => a.sort - b.sort)
    .map(({ value }) => value)
}

const reverse = () => {
  items.value = [...items.value].reverse()
}

const removeMiddle = () => {
  items.value = items.value.filter((_, i) => i !== 2)
}

// 观察 DOM 操作
nextTick(() => {
  const observer = new MutationObserver((mutations) => {
    mutations.forEach((mutation) => {
      console.log('DOM 变化:', mutation.type, mutation.target)
    })
  })
  observer.observe(document.querySelector('.list'), {
    childList: true,
    subtree: true
  })
})
</script>

<template>
  <div>
    <div class="controls">
      <button @click="shuffle">随机打乱</button>
      <button @click="reverse">反转</button>
      <button @click="removeMiddle">删除中间项</button>
    </div>
    <ul class="list">
      <li v-for="item in items" :key="item.id">
        {{ item.text }}
      </li>
    </ul>
  </div>
</template>

九、常见问题

Q1：为什么 Vue3 的 Diff 比 Vue2 快？

核心差异：

优化点	Vue2	Vue3
静态内容	每次更新都遍历	PatchFlag 标记，直接跳过
属性对比	全量对比所有属性	只对比标记的动态属性
列表 Diff	双端比较	双端比较 + LIS 算法
动态节点查找	遍历整棵树	Block Tree 直接定位

Q2：什么情况下 PatchFlag 会失效？

以下情况编译器无法生成优化标记：

• 使用非编译时 render 函数（手写 h()）
• 模板过于动态（如 <div v-bind="obj"> 使用 FULL_PROPS）
• 使用了不支持优化的指令

Q3：手写 render 函数能否享受 PatchFlag 优化？

可以手动传入 patchFlag：

import { createElementVNode, openBlock, createElementBlock, PatchFlags } from 'vue'

function render(ctx) {
  return (
    openBlock(),
    createElementBlock('div', null, [
      createElementVNode('p', null, ctx.msg, 1 /* TEXT */),
      createElementVNode('div', { class: ctx.cls }, null, 2 /* CLASS */)
    ])
  )
}

Q4：最长递增子序列的时间复杂度是多少？

Vue3 的 LIS 实现使用二分查找优化，时间复杂度为 O(n log n)，空间复杂度为 O(n)。

十、总结

Vue3 的虚拟 DOM 优化是编译时和运行时的协同成果：

1. PatchFlag 静态标记：编译时标记动态节点类型，运行时靶向更新
2. Block Tree：将模板分块，只追踪和遍历动态子节点
3. 静态提升：静态节点提升到渲染函数外，只创建一次
4. 最长递增子序列：最小化列表 Diff 中的 DOM 移动操作
5. ShapeFlag 位掩码：快速判断节点类型，减少分支判断

这些优化使得 Vue3 在保持声明式开发体验的同时，运行时性能接近原生 JavaScript 操作。

十一、思考题

1. 为什么 Vue3 选择最长递增子序列算法而不是 Vue2 的双端比较来处理列表中间部分？

2. 设计一个场景，验证 Block Tree 相比全量 Diff 的性能提升。

3. 如果手写渲染函数，如何正确使用 openBlock 和 createElementBlock 来创建 Block Tree？

4. 分析以下模板的编译结果，指出每个节点的 PatchFlag：

   <template>
     <div>
       <span :id="dynamicId">{{ text }}</span>
       <p class="static">静态内容</p>
       <input v-model="inputValue">
     </div>
   </template>