Diff 算法：最长递增子序列手推过程与 key 的双重作用

第15章：Diff 算法——最长递增子序列手推过程与 key 的双重作用

Vue 3 的 diff 算法在最坏情况下是 O(n log n)，而 React 在最坏情况下是 O(n³)——但 Vue 3 通过 Block Tree 让绝大多数真实场景的 diff 代价接近 O(k)，其中 k 是实际变化的动态节点数量，与模板总节点数无关。

本章核心问题：当一个列表发生乱序时，Vue 是如何用最少的 DOM 操作让旧 DOM 变成新 DOM 的？最长递增子序列在这里起什么作用？

读完本章你将理解：

• Vue 3 diff 的两个前提条件（Block Tree + patchFlag）
• 五步 diff 流程的每一步具体做了什么
• 最长递增子序列算法的完整手推过程（O(n log n)）
• key 在编译期和运行期的双重作用
• 为什么 index 作为 key 会引发隐性灾难

Level 1 · 你需要知道的（1-3年经验）

diff 的前提：大多数节点根本不需要 diff

理解 Vue 3 的 diff，先要理解它"不 diff 什么"。

Vue 3 的编译器会分析模板，将所有动态节点（绑定了变量的节点）收集到一个叫 dynamicChildren 的数组里。这个设计叫做 Block Tree。

<template>
  <div>              <!-- Block 根节点 -->
    <h1>标题</h1>    <!-- 静态，不进入 dynamicChildren -->
    <p>{{ text }}</p> <!-- 动态，进入 dynamicChildren -->
    <span class="box">说明</span>  <!-- 静态，不进入 dynamicChildren -->
    <img :src="imgUrl" />         <!-- 动态，进入 dynamicChildren -->
  </div>
</template>

更新时，渲染器只 diff dynamicChildren 里的 2 个节点，而不是模板里的全部 5 个节点。静态内容完全跳过。

对于一个有 1000 个节点、只有 3 个动态节点的组件，Block Tree 让 diff 的代价从 O(1000) 降到 O(3)。

key 是什么：两种不同场景的同一个答案

场景一：v-for 列表

没有 key 时，Vue 按位置复用：旧的第1项配新的第1项，旧的第2项配新的第2项……如果列表倒序，每个节点都要重新渲染。

有 key 时，Vue 按 key 值复用：旧的 key="3" 的节点配新的 key="3" 的节点，不管位置是否变了。如果列表倒序，只需要移动 DOM 节点，不需要重新渲染内容。

场景二：条件渲染

<template>
  <!-- 问题：切换时 input 会保留旧的输入值 -->
  <input v-if="isLogin" placeholder="用户名" />
  <input v-else placeholder="邮箱" />

  <!-- 解决：key 强制 Vue 销毁旧组件、创建新组件 -->
  <input v-if="isLogin" key="login" placeholder="用户名" />
  <input v-else key="register" placeholder="邮箱" />
</template>

实践建议：

为什么 index 作为 key 很危险

<template>
  <ul>
    <li v-for="(item, index) in list" :key="index">
      <input v-model="item.checked" />
      {{ item.name }}
    </li>
  </ul>
</template>

<script setup>
const list = ref([
  { id: 1, name: '苹果', checked: false },
  { id: 2, name: '香蕉', checked: true },
  { id: 3, name: '橙子', checked: false },
])

// 删除第一个元素
function removeFirst() {
  list.value.shift()
}
</script>

执行 removeFirst() 后：

删除前：
  key=0 → 苹果  (input: unchecked)
  key=1 → 香蕉  (input: checked)
  key=2 → 橙子  (input: unchecked)

删除后的期望结果：
  key=0 → 香蕉  (input: checked)    ← 应该是 checked
  key=1 → 橙子  (input: unchecked)

Vue 实际的 diff 行为（用 index 作为 key）：
  旧 key=0 (苹果) 对应新 key=0 (香蕉)  → 复用旧 DOM，只更新文字
  旧 key=1 (香蕉) 对应新 key=1 (橙子)  → 复用旧 DOM，只更新文字
  旧 key=2 (橙子) 没有对应 → 删除

结果：
  key=0 的 li 复用了"苹果"的 DOM：input 的 checked 状态还是 false！
  显示的是"香蕉"，但 input 是 unchecked 的！状态错乱！

根本原因：index 没有语义，它只代表位置，不代表"谁是谁"。

Level 2 · 它是怎么运行的（3-5年经验）

五步 diff 流程完整图解

Vue 3 的核心 diff 函数是 patchKeyedChildren，处理有 key 的列表。流程分五步：

新旧节点数组示例：
  旧: [A, B, C, D, E, F, G]
  新: [A, B, D, F, E, C, H, G]

────────────────────────────────────────────────────────
步骤 1：头部对比（从左向右，跳过相同前缀）
────────────────────────────────────────────────────────

  旧: [A, B, C, D, E, F, G]
       ↑                        i = 0
  新: [A, B, D, F, E, C, H, G]
       ↑

  比较：A == A？是。patch，i++
  比较：B == B？是。patch，i++
  比较：C == D？否。停止。

  结果：i = 2，头部 A,B 已处理

────────────────────────────────────────────────────────
步骤 2：尾部对比（从右向左，跳过相同后缀）
────────────────────────────────────────────────────────

  旧: [A, B, C, D, E, F, G]
                          ↑     e1 = 6
  新: [A, B, D, F, E, C, H, G]
                             ↑  e2 = 7

  比较：G == G？是。patch，e1--，e2--
  比较：F == H？否。停止。

  结果：e1 = 5（F 的位置），e2 = 6（H 的位置）
  后缀 G 已处理

  当前状态：
  旧: [A, B | C, D, E, F | G]   （未处理区间 [2, 5]）
  新: [A, B | D, F, E, C, H | G] （未处理区间 [2, 6]）

────────────────────────────────────────────────────────
步骤 3：检查旧序列是否耗尽（仅有新增节点）
────────────────────────────────────────────────────────

  条件：i > e1（旧序列耗尽）且 i <= e2（新序列还有节点）
  当前：i=2，e1=5，2 > 5？否。跳过此步骤。

────────────────────────────────────────────────────────
步骤 4：检查新序列是否耗尽（仅有删除节点）
────────────────────────────────────────────────────────

  条件：i > e2（新序列耗尽）且 i <= e1（旧序列还有节点）
  当前：i=2，e2=6，2 > 6？否。跳过此步骤。

────────────────────────────────────────────────────────
步骤 5：中间乱序部分处理
────────────────────────────────────────────────────────

  旧未处理区间：[C, D, E, F]（位置 2-5）
  新未处理区间：[D, F, E, C, H]（位置 2-6）

  5a. 建立新节点的 key → index 映射：
      { D:2, F:3, E:4, C:5, H:6 }

  5b. 遍历旧节点，在映射中查找可复用节点：
      C → 找到，新位置 5，标记可复用，记录 newIndexToOldIndexMap[5-2] = 2+1 = 3
      D → 找到，新位置 2，标记可复用，记录 newIndexToOldIndexMap[2-2] = 3+1 = 4
      E → 找到，新位置 4，标记可复用，记录 newIndexToOldIndexMap[4-2] = 4+1 = 5
      F → 找到，新位置 3，标记可复用，记录 newIndexToOldIndexMap[3-2] = 5+1 = 6
      （H 在旧节点中不存在，将被挂载为新节点）

  newIndexToOldIndexMap = [4, 6, 5, 3, 0]
  （0 表示"这是新节点，需要挂载"）

  5c. 计算 LIS（最长递增子序列）：
      输入: [4, 6, 5, 3, 0]
      输出: 位置 [1, 2] 对应的值 [6, 5]... 

      等等，[6, 5] 不是递增的。重新看：
      [4, 6, 5, 3, 0] 的 LIS 是 [4, 5] 或 [4, 6]
      位置是 [0, 2] 或 [0, 1]

      LIS 结果告诉我们：旧位置对应新位置 [0, 2] 的节点（D 和 E）
      不需要移动——只需要移动其他节点绕过它们

  5d. 从后向前遍历新序列未处理区间，执行 move 或 mount：
      H（newIndexToOldIndexMap=0）→ 新节点，mount
      C（不在 LIS 中）→ 移动到 F 前面
      E（在 LIS 中，位置稳定）→ 不移动
      F（不在 LIS 中）→ 移动到 E 前面
      D（在 LIS 中，位置稳定）→ 不移动

最长递增子序列（LIS）算法完整手推

输入：[5, 3, 4, 0, 7, 2, 1, 6]

目标：找出最长递增子序列，并记录这些元素在原数组中的位置（不是值）

算法使用两个辅助数组

• tails[]：维护"当前已知的、长度为 i+1 的递增子序列中，最小的末尾值"
• position[]：记录每个元素是以哪个 tails 位置结尾的
• predecessor[]：记录每个元素的前驱位置（用于回溯还原路径）

手推过程（Patience Sorting + 二分搜索）

初始：tails = []，predecessor = []

元素 5（位置0）：
  tails 为空，直接追加。tails = [5]
  position[0] = 0（在 tails 的位置0结尾）

元素 3（位置1）：
  3 < tails[0]=5，二分找到位置0，替换。tails = [3]
  position[1] = 0

元素 4（位置2）：
  4 > tails[0]=3，追加。tails = [3, 4]
  position[2] = 1
  predecessor[2] = 1（前驱是位置1的元素3）

元素 0（位置3）：
  0 < tails[0]=3，二分找到位置0，替换。tails = [0, 4]
  position[3] = 0

元素 7（位置4）：
  7 > tails[1]=4，追加。tails = [0, 4, 7]
  position[4] = 2
  predecessor[4] = 2（前驱是位置2的元素4）

元素 2（位置5）：
  tails[0]=0 < 2 <= tails[1]=4，二分找到位置1，替换。tails = [0, 2, 7]
  position[5] = 1
  predecessor[5] = 3（前驱是位置3的元素0）

元素 1（位置6）：
  tails[0]=0 < 1 <= tails[1]=2，二分找到位置1，替换。tails = [0, 1, 7]
  position[6] = 1
  predecessor[6] = 3（前驱是位置3的元素0）

元素 6（位置7）：
  tails[1]=1 < 6 <= tails[2]=7，二分找到位置2，替换。tails = [0, 1, 6]
  position[7] = 2
  predecessor[7] = 6（前驱是位置6的元素1）

回溯还原 LIS 路径

最终 tails = [0, 1, 6]，长度为 3（LIS 长度为 3）
最后一个确定在 LIS 末尾的元素：位置7（值6）

回溯：
  7（值6）← predecessor[7] = 6（值1）
  6（值1）← predecessor[6] = 3（值0）
  3（值0）← predecessor[3] = -1（无前驱，起点）

LIS 对应的原数组位置（倒序）：3, 6, 7
LIS 对应的值：0, 1, 6

验证：0 < 1 < 6，是递增的。✓
但等等，最长的应该是 [3, 4, 7] = 长度3，[0, 1, 6] 也是长度3。
两者都是有效的 LIS，算法选择了 [0, 1, 6] 这组。

在 Vue Diff 中的实际应用

LIS 的意义：LIS 中的位置对应的节点"在相对顺序上已经正确"
只需要移动 LIS 之外的节点，LIS 内的节点保持不动

对于 newIndexToOldIndexMap = [4, 6, 5, 3, 0]：
  LIS（按位置）：
  位置0的4 < 位置1的6 → [4, 6] 是长度2的LIS
  或位置0的4 < 位置2的5 → [4, 5] 也是长度2的LIS

  选 LIS = 位置[0, 1]（值[4, 6]）：
  → 对应新序列中位置2的D和位置3的F不需要移动
  → C（新位置5）需要移动
  → E（新位置4）需要移动
  → H（新位置6，值0）需要挂载

  最终操作：mount H, move C, move E（D和F不动）
  只需 3 次 DOM 操作，而不是 5 次

无 key 的 diff：按位置对比

无 key 列表（或刻意不使用 key）的 diff 使用 patchUnkeyedChildren：

function patchUnkeyedChildren(c1, c2, container, anchor) {
  const oldLength = c1.length
  const newLength = c2.length
  const commonLength = Math.min(oldLength, newLength)

  // 按位置逐一对比
  for (let i = 0; i < commonLength; i++) {
    patch(c1[i], c2[i], container, anchor)
  }

  if (oldLength > newLength) {
    // 旧节点多余，卸载
    unmountChildren(c1, commonLength)
  } else {
    // 新节点多余，挂载
    mountChildren(c2, container, anchor, commonLength)
  }
}

这个算法非常简单，O(n) 时间。但没有任何复用优化，适合节点数量少且不包含有状态子组件的场景。

key 的双重作用：编译期与运行期

key 在编译器中的作用（静态分析阶段）：

<template>
  <!-- 有 key 的 v-for：编译为 KEYED_FRAGMENT -->
  <div v-for="item in list" :key="item.id">{{ item.name }}</div>

  <!-- 无 key 的 v-for：编译为 UNKEYED_FRAGMENT -->
  <div v-for="item in list">{{ item.name }}</div>
</template>

编译结果（简化）：
  // 有 key
  createVNode(Fragment, null, renderList(list, item =>
    createElementVNode('div', { key: item.id }, item.name)
  ), PatchFlags.KEYED_FRAGMENT)  ← 64 位的 patchFlag

  // 无 key
  createVNode(Fragment, null, renderList(list, item =>
    createElementVNode('div', null, item.name)
  ), PatchFlags.UNKEYED_FRAGMENT)  ← 128 位的 patchFlag

patchFlag 不同 → 运行时选择不同的 diff 函数：
  KEYED_FRAGMENT   → patchKeyedChildren()    （五步流程）
  UNKEYED_FRAGMENT → patchUnkeyedChildren()  （按位置对比）

key 在运行时 diff 中的作用：

步骤5的核心代码（简化）：
  // 建立新节点 key → 新位置的映射
  const keyToNewIndexMap = new Map()
  for (let i = s2; i <= e2; i++) {
    const newChild = c2[i]
    if (newChild.key != null) {
      keyToNewIndexMap.set(newChild.key, i)
    }
  }

  // 遍历旧节点，在映射中查找
  for (let i = s1; i <= e1; i++) {
    const oldChild = c1[i]
    const newIndex = keyToNewIndexMap.get(oldChild.key)
    if (newIndex === undefined) {
      unmount(oldChild)  // 旧节点在新序列中不存在 → 卸载
    } else {
      newIndexToOldIndexMap[newIndex - s2] = i + 1  // 记录可复用关系
      patch(oldChild, c2[newIndex], ...)  // 复用，更新内容
    }
  }

Level 3 · 设计文档与源码（资深开发者）

patchKeyedChildren 源码关键实现

// packages/runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, container, parentAnchor, ...) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1
  let e2 = l2 - 1

  // Step 1: sync from start
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i]))
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, null, ...)
    } else {
      break
    }
    i++
  }

  // Step 2: sync from end
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[e2] as VNode) : normalizeVNode(c2[e2]))
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, null, ...)
    } else {
      break
    }
    e1--
    e2--
  }

  // Step 3: common sequence + mount
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
      while (i <= e2) {
        patch(null, c2[i] = ..., container, anchor, ...)
        i++
      }
    }
  }
  // Step 4: common sequence + unmount
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i], ...)
      i++
    }
  }
  // Step 5: unknown sequence
  else {
    const s1 = i
    const s2 = i

    // 5.1 build key:index map for newChildren
    const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
    for (i = s2; i <= e2; i++) {
      const nextChild = (c2[i] = ...) as VNode
      if (nextChild.key != null) {
        keyToNewIndexMap.set(nextChild.key, i)
      }
    }

    // 5.2 loop through old children left to be patched and try to patch
    // matching nodes & remove nodes that are no longer present
    let j
    let patched = 0
    const toBePatched = e2 - s2 + 1
    let moved = false
    let maxNewIndexSoFar = 0
    const newIndexToOldIndexMap = new Array(toBePatched)
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i]
      if (patched >= toBePatched) {
        unmount(prevChild, ...)
        continue
      }
      let newIndex
      if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key)
      } else {
        // key-less node, try to locate a key-less node of the same type
        for (j = s2; j <= e2; j++) {
          if (newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j] as VNode)) {
            newIndex = j
            break
          }
        }
      }
      if (newIndex === undefined) {
        unmount(prevChild, ...)
      } else {
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex
        } else {
          moved = true  // 检测到需要移动（新位置出现了倒退）
        }
        patch(prevChild, c2[newIndex] as VNode, container, null, ...)
        patched++
      }
    }

    // 5.3 move and mount
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)  // 计算 LIS
      : EMPTY_ARR
    j = increasingNewIndexSequence.length - 1

    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i
      const nextChild = c2[nextIndex] as VNode
      const anchor = nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor

      if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(null, nextChild, container, anchor, ...)
      } else if (moved) {
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor, MoveType.REORDER)
        } else {
          j--  // 在 LIS 中，不需要移动
        }
      }
    }
  }
}

getSequence 函数的完整实现（LIS 核心）

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice()    // 前驱数组（记录路径）
  const result = [0]       // result[i] = arr 中的索引，result 按 arr[result[i]] 递增
  let i, j, u, v, c
  const len = arr.length

  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {  // 0 表示新节点，跳过
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j        // 记录前驱
        result.push(i)  // 追加
        continue
      }
      // 二分搜索：找到 result 中第一个 arr[result[u]] >= arrI 的位置
      u = 0
      v = result.length - 1
      while (u < v) {
        c = (u + v) >> 1  // 右移1位 = 除以2（向下取整）
        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
}

isSameVNodeType：什么情况下可以复用节点

// packages/runtime-core/src/vnode.ts
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
  return n1.type === n2.type && n1.key === n2.key
}

这个函数就两行。type 相同（同种节点）且 key 相同（同一个逻辑节点），才能复用。

这意味着：

• <div key="1"> vs <span key="1">：type 不同，不能复用，会销毁重建
• <div key="1"> vs <div key="2">：key 不同，不能复用，会销毁重建
• <div key="1"> vs <div key="1">：可以复用，只更新内容

为什么 Math.random() 作为 key 比没有 key 更糟糕

// 错误写法（每次渲染都生成新的 key）
<li v-for="item in list" :key="Math.random()">{{ item.name }}</li>

分析：

• 没有 key：Vue 使用 patchUnkeyedChildren，按位置复用，旧节点的 DOM 会被复用（即使内容更新）
• 随机 key：每次渲染，每个节点的 key 都不同。Vue 在旧节点中找不到匹配的 key，全部卸载再全部挂载

没有 key 的更新（列表 [A, B, C] → [A, B, D]）：
  位置0：patch(A, A) → DOM 复用，更新内容
  位置1：patch(B, B) → DOM 复用，更新内容
  位置2：patch(C, D) → DOM 复用，只更新内容（文本）
  总计：0 次 DOM 销毁/创建

随机 key 的更新（列表 [A, B, C] → [A, B, D]）：
  旧 key=[随机1, 随机2, 随机3]
  新 key=[随机4, 随机5, 随机6]
  所有旧节点 key 找不到匹配 → 全部卸载
  所有新节点 → 全部挂载
  总计：3 次 DOM 销毁 + 3 次 DOM 创建 = 6 次 DOM 操作

Level 4 · 边界与陷阱（全体适用）

陷阱1：对象引用相等不等于节点可复用

// 错误理解：以为同一个对象引用就不会重新渲染
const item = reactive({ id: 1, name: '苹果' })
const list = ref([item, item])  // 同一个对象出现两次

// 在模板中：
// <div v-for="x in list" :key="x.id">{{ x.name }}</div>
// 两个节点的 key 都是 1！

// Vue 会警告：Duplicate keys detected
// 行为：第二个节点会覆盖第一个，渲染结果不可预测

陷阱2：key 的类型不匹配导致找不到复用节点

// 后端返回数字 id
const list = [{ id: 1 }, { id: 2 }]

// 模板中
// <div v-for="item in list" :key="item.id">

// 问题：有时后端 API 变更，id 变成了字符串
const list2 = [{ id: '1' }, { id: '2' }]

// isSameVNodeType 检查：
// 旧 key = 1（数字）vs 新 key = '1'（字符串）
// 1 !== '1'  → Vue 认为这是不同节点 → 全部销毁重建！

// 解决：显式转换 key 类型
// :key="String(item.id)"  或  :key="Number(item.id)"

陷阱3：moved 优化——并非所有列表都需要计算 LIS

// Vue 3 有一个提前退出优化：
// 如果在遍历旧节点时，newIndex 始终递增（没有出现倒退）
// 则 moved = false，跳过 LIS 计算（getSequence 不会被调用）

// 场景：纯新增（在末尾追加）
// 旧: [A, B, C]  新: [A, B, C, D, E]
// 经过步骤1-4后，D 和 E 在步骤3直接被挂载
// 步骤5根本不需要执行

// 场景：纯删除（删除末尾）
// 旧: [A, B, C, D]  新: [A, B]
// 经过步骤1-2后，C 和 D 在步骤4直接被卸载

// 只有"乱序"场景才会走到步骤5且 moved=true
// 只有此时才会计算 LIS（O(n log n)）

陷阱4：Transition 和 TransitionGroup 中 key 的特殊语义

<template>
  <!-- ❌ 错误：切换路由时没有 key，Transition 动画可能不触发 -->
  <Transition name="fade">
    <RouterView />
  </Transition>

  <!-- ✓ 正确：用路由路径作为 key，每次路由变化触发新旧节点过渡 -->
  <Transition name="fade">
    <RouterView :key="$route.fullPath" />
  </Transition>

  <!-- TransitionGroup 中 key 是必须的 -->
  <TransitionGroup name="list">
    <li v-for="item in list" :key="item.id">{{ item.name }}</li>
  </TransitionGroup>
  <!-- 没有 key，TransitionGroup 无法确定哪个节点是新增的、哪个是删除的 -->
</template>

陷阱5：Fragment 的 diff 类型与 v-for key 的关系

// v-for 不加 key → UNKEYED_FRAGMENT → patchUnkeyedChildren（按位置）
// v-for 加 key   → KEYED_FRAGMENT   → patchKeyedChildren（五步流程）

// 混合情况：
// <template v-for="item in list">  ← Fragment 外层
//   <dt :key="item.id + '-dt'">{{ item.name }}</dt>
//   <dd :key="item.id + '-dd'">{{ item.desc }}</dd>
// </template>

// 这里每个 Fragment 内部有 key，但 Fragment 本身作为 v-for 的一项
// 需要给 <template> 本身加 :key="item.id"，否则 Fragment 层是无 key diff

陷阱6：超大列表的 diff 性能与虚拟滚动

LIS 算法是 O(n log n)，但当 n = 10000 时（超大列表），即使是 O(n log n) 也需要几十毫秒，足以造成帧卡顿。

// 误解：Vue 的 diff 多快都可以应对任何列表
// 现实：10000 个节点的乱序 diff 在低端设备上可能需要 50-100ms

// 正确做法：超大列表使用虚拟滚动
// 只渲染可见区域的 DOM 节点（通常 20-50 个）
// 滚动时替换内容，而不是渲染全部节点

// 推荐库：
// - @tanstack/vue-virtual
// - vue-virtual-scroller

// 如果列表是静态的（内容不变），使用 v-once 完全跳过 diff：
// <li v-for="item in staticList" :key="item.id" v-once>{{ item.name }}</li>

本章小结

1. Block Tree 是 Vue 3 diff 的最大优化：通过编译期收集动态节点到 dynamicChildren，让运行时 diff 只处理真正变化的节点，使 diff 代价从 O(模板总节点数) 降到 O(动态节点数)。

2. 五步 diff 流程层层过滤：头部相同前缀和尾部相同后缀的节点通过线性扫描跳过；只有中间真正乱序的部分才走到最复杂的第五步（key 映射 + LIS）。

3. LIS 的作用是最小化移动次数：LIS 中的节点（相对顺序已正确）不需要移动，只有 LIS 之外的节点才需要执行 DOM 移动操作；在最好情况下，所有节点都在 LIS 中，移动次数为零。

4. key 在编译期决定 diff 策略，在运行期决定节点复用：有 key 的 v-for 生成 KEYED_FRAGMENT patchFlag，触发五步流程；运行时的 key→index 映射让 O(n) 时间内找到可复用节点成为可能。

5. index 作为 key 是结构性错误：它破坏了 key 的语义（key 应该表达"谁是谁"，而不是"在第几位"），导致列表操作（删除、倒序）时组件状态与渲染内容不匹配；只有纯展示的静态列表才能勉强接受 index 作为 key。