L33 · Virtual DOM：节点复用与 keyed diff

🎯 本节目标：理解 Virtual DOM 的工作原理和 Vue 3 的 diff 策略
📦 本节产出：手写 mini vdom (mount + patch) + 理解前后缀同步与 LIS
🔗 前置钩子：L32 的响应式系统（触发更新后谁来更新 DOM？→ VDOM）
🔗 后续钩子：L34 将讲编译时如何标记静态节点减少 diff 范围

1. 为什么需要 Virtual DOM

Virtual DOM 用对象描述期望的界面，再由渲染器协调 DOM 更新。这是一种组织界面更新的方式，并不保证比直接 DOM 操作快，也不保证得到全局最少的 DOM 操作。Vue 稳定版还结合编译信息减少运行时工作。

2. VNode 数据结构

下面定义的是 mini 的元素 VNode，只支持 HTML 元素、字符串文本或元素子数组。真实 Vue 的 VNode 还支持组件、Text、Comment、Fragment 等类型，并带 shapeFlag / patchFlag 等内部字段；组件类型也不等于已经创建的组件实例。

typescript

// labs/mini-reactivity/mini-vdom.ts：第 3 节各段依次放进同一文件
export type Key = string | number
export type Props = Record<string, unknown> | null
export interface VNode {
  type: string
  props: Props
  children: string | VNode[] | null
  key: Key | null
  el: HTMLElement | null
}

3. 手写 mini VDOM

本实现不包含组件生命周期、SVG、事件修饰符、表单 DOM property 或编译器标记。它完成挂载、普通属性/样式/单个事件监听器更新，以及 children 在三种形态间的转换。每次渲染创建新的 VNode，不把同一个 VNode 放到多个位置。

3.1 创建 VNode

typescript

function checkKeys(children: VNode[]) {
  const keys = children.filter(child => child.key !== null).map(child => child.key)
  if (keys.length !== 0 && keys.length !== children.length) throw new Error('mini 列表不能混用有 key 和无 key 节点')
  if (new Set(keys).size !== keys.length) throw new Error('同级 key 必须唯一')
}
export function h(type: string, props: Props = null, children: VNode['children'] = null): VNode {
  const key = props?.key ?? null
  if (key !== null && typeof key !== 'string' && typeof key !== 'number') throw new Error('key 必须是字符串或数字')
  if (Array.isArray(children)) checkKeys(children)
  return { type, props, children, key, el: null }
}

3.2 mount：首次挂载

typescript

export function mount(vnode: VNode, container: HTMLElement, anchor: Node | null = null) {
  const el = vnode.el = document.createElement(vnode.type)
  patchProps(el, null, vnode.props)
  if (typeof vnode.children === 'string') el.textContent = vnode.children
  else if (Array.isArray(vnode.children)) {
    for (const child of vnode.children) mount(child, el)
  }
  container.insertBefore(el, anchor)
}
function unmount(vnode: VNode) { vnode.el?.remove() }

anchor 是插入位置。仅用 appendChild 会让“替换中间节点”跑到列表末尾。

3.3 patch：更新已有节点

typescript

export function patch(oldVNode: VNode, newVNode: VNode) {
  const oldEl = oldVNode.el
  if (!oldEl) throw new Error('旧 VNode 尚未挂载')
  if (oldVNode.type !== newVNode.type || oldVNode.key !== newVNode.key) {
    const parent = oldEl.parentElement
    if (!parent) throw new Error('旧节点不在容器中')
    mount(newVNode, parent, oldEl) // 在旧位置插入，再移除旧节点
    unmount(oldVNode)
    return
  }
  const el = newVNode.el = oldEl
  patchProps(el, oldVNode.props, newVNode.props)
  patchChildren(oldVNode, newVNode, el)
}

3.4 patchProps

挂载与更新共用同一条属性处理路径，避免 mount 支持 style 对象，而 patch 却把它写成 [object Object]。style 对象的键在这个 mini 中使用 CSS 的连字符形式，例如 background-color。

typescript

const booleanAttrs = new Set(['disabled', 'checked', 'selected', 'multiple', 'readonly', 'required', 'autofocus', 'hidden', 'open'])
function patchProp(el: HTMLElement, key: string, previous: unknown, next: unknown) {
  if (key === 'key') return // 仅用于协调身份，不是 DOM attribute
  if (/^on[A-Z]/.test(key)) {
    const event = key.slice(2).toLowerCase()
    if (typeof previous === 'function') el.removeEventListener(event, previous as EventListener)
    if (typeof next === 'function') el.addEventListener(event, next as EventListener)
  } else if (key === 'style') {
    el.removeAttribute('style')
    if (typeof next === 'string') el.style.cssText = next
    else if (next && typeof next === 'object') {
      for (const [name, value] of Object.entries(next)) {
        if (value !== null && value !== undefined) el.style.setProperty(name, String(value))
      }
    }
  } else if (next === null || next === undefined) {
    el.removeAttribute(key)
  } else if (booleanAttrs.has(key.toLowerCase())) {
    if (next || next === '') el.setAttribute(key, '')
    else el.removeAttribute(key)
  } else {
    el.setAttribute(key, String(next)) // aria-* 等普通属性保留字符串 false/true
  }
}
function patchProps(el: HTMLElement, previous: Props, next: Props) {
  const oldProps = previous || {}
  const newProps = next || {}
  for (const key of Object.keys(newProps)) {
    if (!Object.is(newProps[key], oldProps[key])) patchProp(el, key, oldProps[key], newProps[key])
  }
  for (const key of Object.keys(oldProps)) {
    if (!(key in newProps)) patchProp(el, key, oldProps[key], null)
  }
}

props 应按本例创建新对象；如果直接原地改旧 style 对象，两份 VNode 会共享同一引用，无法再从旧值判断变化。布尔属性只覆盖 booleanAttrs 列出的常见项；真实 Vue 的 DOM patch 还区分 attribute 与 property，不能把此函数当作所有表单控件的实现。

3.5 patchChildren

typescript

function patchChildren(oldVNode: VNode, newVNode: VNode, el: HTMLElement) {
  const oldChildren = oldVNode.children
  const newChildren = newVNode.children
  if (typeof newChildren === 'string') {
    if (newChildren !== oldChildren) el.textContent = newChildren
  } else if (Array.isArray(newChildren)) {
    if (Array.isArray(oldChildren)) diffChildren(oldChildren, newChildren, el)
    else {
      el.textContent = ''
      for (const child of newChildren) mount(child, el)
    }
  } else {
    el.textContent = '' // 数组/文本 → null 都要清除
  }
}
function diffChildren(previous: VNode[], next: VNode[], el: HTMLElement) {
  const oldKeyed = previous.length > 0 && previous[0]!.key !== null
  const newKeyed = next.length > 0 && next[0]!.key !== null
  if (oldKeyed && newKeyed) {
    const oldByKey = new Map(previous.map(node => [node.key, node]))
    const newKeys = new Set(next.map(node => node.key))
    for (const node of previous) if (!newKeys.has(node.key)) unmount(node)
    let anchor: Node | null = null
    for (let index = next.length - 1; index >= 0; index--) {
      const node = next[index]!
      const old = oldByKey.get(node.key)
      if (old) patch(old, node)
      else mount(node, el, anchor)
      if (node.el!.nextSibling !== anchor) el.insertBefore(node.el!, anchor)
      anchor = node.el!
    }
  } else if (!oldKeyed && !newKeyed) {
    const common = Math.min(previous.length, next.length)
    for (let index = 0; index < common; index++) patch(previous[index]!, next[index]!)
    for (let index = common; index < previous.length; index++) unmount(previous[index]!)
    for (let index = common; index < next.length; index++) mount(next[index]!, el)
  } else {
    el.textContent = '' // key 模式切换，或与空数组互换
    for (const node of next) mount(node, el)
  }
}

这个 keyed 分支用映射保持身份，再从后向前放到目标位置；没有实现 LIS，也不承诺移动次数最少。第 4 节解释真实 Vue 在此基础上如何减少移动。

继续在 L31 的实验目录运行 npm install -D vite@6，新增下面两个文件。该页面用 L32 mini effect 驱动自己的渲染器，不与商城的 Vue 挂载点混用：

html

<!-- labs/mini-reactivity/index.html -->
<!doctype html>
<html lang="zh-CN"><head><meta charset="UTF-8"><title>mini VDOM 实验</title></head>
<body><div id="app"></div><script type="module" src="/vdom-demo.ts"></script></body></html>

typescript

// labs/mini-reactivity/vdom-demo.ts
import { ref, effect } from './mini-reactivity'
import { h, mount, patch, type VNode } from './mini-vdom'
const container = document.querySelector<HTMLElement>('#app')!
const count = ref(0)
let previous: VNode | undefined
effect(() => {
  const keys = count.value % 2 ? ['F', 'C', 'D', 'E'] : ['C', 'D', 'E', 'F']
  const tree = h('section', null, [
    h('h1', null, `计数 ${count.value}`),
    h('button', { onClick: () => { count.value++ } }, '增加并重排'),
    h('ul', null, keys.map(key => h('li', { key }, key))),
  ])
  if (previous) patch(previous, tree)
  else mount(tree, container)
  previous = tree
})

运行 npx vite --host 127.0.0.1 --port 5175 --strictPort，点击按钮观察文本与列表顺序；在 Elements 中确认 li 复用。类型检查可运行 npx tsc --noEmit --target ES2022 --module NodeNext --moduleResolution NodeNext mini-reactivity.ts mini-vdom.ts vdom-demo.ts。

4. Diff 算法核心

4.1 同级比较原则

Vue 的常规 patch 按同层子节点协调，不去全树搜索“这个节点是否搬到了另一层”。这是实用的匹配策略，不能由此推导整个 Vue diff 恒为 O(n)。

按该源码流程估算，对稳定、唯一 key 的同层列表，扫描与建映射是线性工作，未知区间的二分 LIS 是 O(m log m)，还没有计入递归 patch 和真实 DOM 成本；无 key 混合匹配存在更高的查找开销。下文按 Vue 3.5.43 的 patchKeyedChildren 解释。固定版本 renderer.ts

4.2 Vue 3 的五步 Diff

4.3 前后缀同步 + LIS 详细示例

旧: [A, B, C, D, E, F, G]
新: [A, B, F, C, D, E, G]

1. 前缀：A/A、B/B 相同，patch；C/F 不同，停止。
2. 后缀：G/G 相同，patch；F/E 不同，停止。
3. 未知区间：旧 [C,D,E,F]，新 [F,C,D,E]。
4. 新 key → 新绝对索引：F→2，C→3，D→4，E→5。
5. 扫描旧区间并 patch 相同 key，同时记录“新位置对应的旧索引 + 1”：
   新位置顺序       F  C  D  E
   旧索引 + 1      [6, 3, 4, 5]
6. LIS 的值为 [3,4,5]，对应新位置 [1,2,3]，也就是 C/D/E。
7. 从后向前处理：E、D、C 保留相对顺序；把已有 F 移动到 C 前面。

这里 F 原本就存在，执行的是移动，不是新建 F。映射数组中的 0 才代表新节点；只有检测到相对顺序变化时，Vue 才需要求 LIS。该前缀/后缀同步也不同于 Vue 2 每轮比较四种首尾组合的完整双端算法。

LIS 保留最多可维持相对顺序的复用节点，从而减少该同层区间中需要移动的节点；它不是整个 DOM 更新流程的全局最优证明。

5. key 的重要性

vue

<!-- 无 key：默认按位置更新，适合不依赖节点/组件状态的简单展示 -->
<div v-for="item in list">{{ item.name }}</div>

<!-- 稳定业务 key：同层身份与对应数据关联 -->
<div v-for="item in list" :key="item.id">{{ item.name }}</div>

无 key	有 key
按索引逐个 patch	按 key 精确匹配
删除首项后，后续内容按原位置更新	删除对应节点，其余身份可复用，仍可能需要 patch
有内部状态时可能与期望业务项错位	唯一且稳定的 key 才能保持期望身份

6. 本节总结

检查清单

[ ] 理解 VNode 描述目标界面，渲染器协调 DOM 更新
[ ] 能描述 VNode 数据结构
[ ] 能手写 h() / mount() / patch() / patchProps() / patchChildren()
[ ] 理解同级比较与 keyed diff 的复杂度边界
[ ] 能描述 Vue 3 的五步 diff 策略
[ ] 理解 LIS 如何减少同层复用节点的移动
[ ] 理解 key 在 diff 中的关键作用

Git 提交

bash

git add .
git commit -m "L33: Virtual DOM - mount/patch/diff + LIS 算法"

🔬 深度专题

📖 D11 · Virtual DOM 与 diff — 列表增删或排序时，index key 为什么容易让状态错位？

🔗 → 下一节

L34 将讲编译器如何在编译时标记 PatchFlag 和 Block Tree——在符合优化条件的路径上缩小运行时需要检查的范围。

L33 · Virtual DOM：节点复用与 keyed diff ​

1. 为什么需要 Virtual DOM ​

2. VNode 数据结构 ​

3. 手写 mini VDOM ​

3.1 创建 VNode ​

3.2 mount：首次挂载 ​

3.3 patch：更新已有节点 ​

3.4 patchProps ​

3.5 patchChildren ​

4. Diff 算法核心 ​

4.1 同级比较原则 ​

4.2 Vue 3 的五步 Diff ​

4.3 前后缀同步 + LIS 详细示例 ​

5. key 的重要性 ​

6. 本节总结 ​

检查清单 ​

Git 提交 ​

🔬 深度专题 ​

🔗 → 下一节 ​

L33 · Virtual DOM：节点复用与 keyed diff

1. 为什么需要 Virtual DOM

2. VNode 数据结构

3. 手写 mini VDOM

3.1 创建 VNode

3.2 mount：首次挂载

3.3 patch：更新已有节点

3.4 patchProps

3.5 patchChildren

4. Diff 算法核心

4.1 同级比较原则

4.2 Vue 3 的五步 Diff

4.3 前后缀同步 + LIS 详细示例

5. key 的重要性

6. 本节总结

检查清单

Git 提交

🔬 深度专题

🔗 → 下一节