AI 生成的摘要
本文深入分析了 Vue 框架中的虚拟 DOM 更新机制，特别是组件创建和更新时的过程。主要通过对比新旧虚拟 DOM 的差异来更新真实 DOM，这个过程被称为 diff。Vue 使用一个 patch 函数实现了 diff，通过深度优先、逐层比较的方法，结合虚拟节点的 key 和 tag 来判断节点是否相同。在节点的比较过程中，为了最大限度地复用真实 DOM，Vue 使用双端对比策略，用两个指针分别指向子节点数组的头尾进行比对。针对节点移动的优化，文章探讨了 Vue 如何利用最长递增子序列找出需要最少移动的节点序列，有效减少了耗费资源的 DOM 操作。这一分析为开发者提供了深刻理解 Vue diff 算法及其性能优化策略的机会，有助于更有效地利用 Vue 进行应用开发。

当组件创建和更新时，vue 都会执行内部的 update 函数，该函数在内部调用 render 函数生成虚拟 dom ，组件会指向新树，然后 vue 将新旧两个虚拟 dom 对比，找到差异点，最终更新到真实 dom，对比差异的过程叫 diff，vue 内部通过一个 patch 函数来完成该过程。 在对比时，vue 采用深度优先、逐层比较的方式进行比对。在判断两个节点是否相同时，vue 通过虚拟节点的 key 和 tag 来进行判断。具体来说，首先对比根节点，如果相同则将旧节点的真实 dom 的引用挂到新节点，然后根据需要更新属性到真实 dom，然后再对比其子节点。

双端对比

对比其子节点时，vue 对每个子节点数组使用了两个指针，分别指向头尾，然后不断向中间靠拢来进行对比，这样做的目的是尽量服用真实 dom。如果发现相同，则进入和根节点一样的对比流程，如果发现不同，则移动真实 dom 到合适的位置。 vue 源码：

ts
function updateChildren(
  parentElm,
  oldCh,
  newCh,
  insertedVnodeQueue,
  removeOnly
) {
  let oldStartIdx = 0
  let newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newEndIdx = newCh.length - 1
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm

  // removeOnly is a special flag used only by <transition-group>
  // to ensure removed elements stay in correct relative positions
  // during leaving transitions
  const canMove = !removeOnly

  if (__DEV__) {
    checkDuplicateKeys(newCh)
  }

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(
        oldStartVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      )
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(
        oldEndVnode,
        newEndVnode,
        insertedVnodeQueue,
        newCh,
        newEndIdx
      )
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      patchVnode(
        oldStartVnode,
        newEndVnode,
        insertedVnodeQueue,
        newCh,
        newEndIdx
      )
      canMove &&
        nodeOps.insertBefore(
          parentElm,
          oldStartVnode.elm,
          nodeOps.nextSibling(oldEndVnode.elm)
        )
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(
        oldEndVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      )
      canMove &&
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      if (isUndef(oldKeyToIdx))
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
      if (isUndef(idxInOld)) {
        // New element
        createElm(
          newStartVnode,
          insertedVnodeQueue,
          parentElm,
          oldStartVnode.elm,
          false,
          newCh,
          newStartIdx
        )
      } else {
        vnodeToMove = oldCh[idxInOld]
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(
            vnodeToMove,
            newStartVnode,
            insertedVnodeQueue,
            newCh,
            newStartIdx
          )
          oldCh[idxInOld] = undefined
          canMove &&
            nodeOps.insertBefore(
              parentElm,
              vnodeToMove.elm,
              oldStartVnode.elm
            )
        } else {
          // same key but different element. treat as new element
          createElm(
            newStartVnode,
            insertedVnodeQueue,
            parentElm,
            oldStartVnode.elm,
            false,
            newCh,
            newStartIdx
          )
        }
      }
      newStartVnode = newCh[++newStartIdx]
    }
  }
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
    addVnodes(
      parentElm,
      refElm,
      newCh,
      newStartIdx,
      newEndIdx,
      insertedVnodeQueue
    )
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx)
  }
}

每轮循环尝试匹配新旧节点的 4 种组合。下面逐个分析。 主要判断顺序： 头头相同，patch 后指针移动

ts
patchVnode(oldStartVnode, newStartVnode, ...)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
  • 最理想的情况：新旧列表一致，只是内容变了。
  • 比如：[A, B, C] → [A, B, C]，或者 [A, B] → [A, B, C] 直接 patch（更新）两个节点，两个头指针向右推进。

什么是 patch？ patchVnode 的主要职责就是对两个 vnode（旧 vnode 和新 vnode）做处理，最终目的是“最小化 DOM 操作”，更新对应的真实 DOM 节点（elm）。

尾尾相同

ts
patchVnode(oldEndVnode, newEndVnode, ...)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
  • 情况类似上面，只是更新发生在尾部
  • 比如：[A, B, C] → [X, B, C]，可以从尾部更新 C 直接 patch（更新）两个节点，两个尾指针向左收缩 旧头 = 新尾（节点右移）
ts
patchVnode(oldStartVnode, newEndVnode, ...)
    // 移动 DOM
nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
  • 旧头元素被移到新尾部了，只要移动 DOM。
  • 例如：[A, B, C] → [B, C, A]，A 从头部移到了尾部。 patch 后 移动，旧头指针向右推进，新尾指针向左收缩

怎么移动？ parent.insertBefore(elm, reference)

旧尾 = 新头（节点左移）

ts
patchVnode(oldEndVnode, newStartVnode, ...)
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
  • 旧尾元素被移到新头部了。
  • 例如：[A, B, C] → [C, A, B]，C 从尾部移到了头部。 不匹配，则建立 key-to-index map 没有匹配的情况：查找  key （fallback）
ts
if (isUndef(oldKeyToIdx)) {
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
    }
    const idxInOld = oldKeyToIdx[newStartVnode.key]
    if (isUndef(idxInOld)) {
      // 新节点是全新的，创建插入
      createElm(newStartVnode, ...)
      nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm)
    } else {
      const vnodeToMove = oldCh[idxInOld]
      if (sameVnode(vnodeToMove, newStartVnode)) {
        patchVnode(vnodeToMove, newStartVnode, ...)
        oldCh[idxInOld] = undefined
        nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
      } else {
        // key 相同但 vnode 不同 → 直接创建新 vnode
        createElm(newStartVnode, ...)
        nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm)
      }
    }
    newStartVnode = newCh[++newStartIdx]
  • 前 4 种情况都不匹配，查找 key 是否有一样的。 有一样的就拿来 patch + 移动，否则就是新增 循环结束后的清理阶段
  • 还有新节点没处理 → 全部插入
  • 还有旧节点没处理 → 全部删除
oldCh:  [oldStart →     …     ← oldEnd]
newCh:  [newStart →     …     ← newEnd]

1. oldStart == newStart → patch + 向右推进
2. oldEnd == newEnd     → patch + 向左推进
3. oldStart == newEnd   → patch + 移动 oldStart 到末尾
4. oldEnd == newStart   → patch + 移动 oldEnd 到开头
5. fallback（key 查找）：
   - 有 → patch + 移动
   - 无 → create + 插入

当旧头 (oldStartVnode) 等于新尾 (newEndVnode) 时，为什么把节点移动到“旧尾”的后面？不是应该移到“新尾”吗？

  1. 当前 DOM 是旧的，我们还没完成更新。
  2. 因为我们是双端比对，并不是立即更新所有节点位置，而是随着指针移动逐步更新。

最长递增子序列

vue 源码：

ts
const patchKeyedChildren = (
  c1: VNode[],
  c2: VNodeArrayChildren,
  container: RendererElement,
  parentAnchor: RendererNode | null,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  namespace: ElementNamespace,
  slotScopeIds: string[] | null,
  optimized: boolean,
) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1 // prev ending index
  let e2 = l2 - 1 // next ending index

  // 1. sync from start
  // (a b) c
  // (a b) d e
  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,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    } else {
      break
    }
    i++
  }

  // 2. sync from end
  // a (b c)
  // d e (b c)
  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,
        parentComponent,
        parentSuspense,
        namespace,
        slotScopeIds,
        optimized,
      )
    } else {
      break
    }
    e1--
    e2--
  }

  // 3. common sequence + mount
  // (a b)
  // (a b) c
  // i = 2, e1 = 1, e2 = 2
  // (a b)
  // c (a b)
  // i = 0, e1 = -1, e2 = 0
  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] = optimized
            ? cloneIfMounted(c2[i] as VNode)
            : normalizeVNode(c2[i])),
          container,
          anchor,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
        i++
      }
    }
  }

  // 4. common sequence + unmount
  // (a b) c
  // (a b)
  // i = 2, e1 = 2, e2 = 1
  // a (b c)
  // (b c)
  // i = 0, e1 = 0, e2 = -1
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i], parentComponent, parentSuspense, true)
      i++
    }
  }

  // 5. unknown sequence
  // [i ... e1 + 1]: a b [c d e] f g
  // [i ... e2 + 1]: a b [e d c h] f g
  // i = 2, e1 = 4, e2 = 5
  else {
    const s1 = i // prev starting index
    const s2 = i // next starting index

    // 5.1 build key:index map for newChildren
    const keyToNewIndexMap: Map<PropertyKey, number> = new Map()
    for (i = s2; i <= e2; i++) {
      const nextChild = (c2[i] = optimized
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      if (nextChild.key != null) {
        if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
          warn(
            `Duplicate keys found during update:`,
            JSON.stringify(nextChild.key),
            `Make sure keys are unique.`,
          )
        }
        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
    // used to track whether any node has moved
    let maxNewIndexSoFar = 0
    // works as Map<newIndex, oldIndex>
    // Note that oldIndex is offset by +1
    // and oldIndex = 0 is a special value indicating the new node has
    // no corresponding old node.
    // used for determining longest stable subsequence
    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) {
        // all new children have been patched so this can only be a removal
        unmount(prevChild, parentComponent, parentSuspense, true)
        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, parentComponent, parentSuspense, true)
      } else {
        newIndexToOldIndexMap[newIndex - s2] = i + 1
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex
        } else {
          moved = true
        }
        patch(
          prevChild,
          c2[newIndex] as VNode,
          container,
          null,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
        patched++
      }
    }

    // 5.3 move and mount
    // generate longest stable subsequence only when nodes have moved
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)
      : EMPTY_ARR
    j = increasingNewIndexSequence.length - 1
    // looping backwards so that we can use last patched node as anchor
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i
      const nextChild = c2[nextIndex] as VNode
      const anchorVNode = c2[nextIndex + 1] as VNode
      const anchor =
        nextIndex + 1 < l2
          ? // #13559, fallback to el placeholder for unresolved async component
            anchorVNode.el || anchorVNode.placeholder
          : parentAnchor
      if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(
          null,
          nextChild,
          container,
          anchor,
          parentComponent,
          parentSuspense,
          namespace,
          slotScopeIds,
          optimized,
        )
      } else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor, MoveType.REORDER)
        } else {
          j--
        }
      }
    }
  }
}
  • c1: 旧 children 列表（VNode[])
  • c2: 新 children 列表（VNode[])
  • container: 当前 DOM 容器 从头和尾开始同步相同节点（双端 diff）
ts
// sync from start
while (i <= e1 && i <= e2) {
  if (isSameVNodeType(c1[i], c2[i])) {
    patch(...)
    i++
  } else break
}

// sync from end
while (i <= e1 && i <= e2) {
  if (isSameVNodeType(c1[e1], c2[e2])) {
    patch(...)
    e1--
    e2--
  } else break
}

目的：尽早对比出头尾一致部分，减少中间需要 diff 的范围。

处理新增或删除节点

ts
if (i > e1) {
  // 全是新增节点，直接 addVnodes
  while (i <= e2) insert(...)
} else if (i > e2) {
  // 全是删除节点，直接 removeVnodes
  while (i <= e1) unmount(...)
}

处理中间乱序部分 + 移动逻辑 建立 key -> newIndex 映射

ts
const keyToNewIndexMap = new Map()
for (i = s2; i <= e2; i++) {
  const nextChild = c2[i]
  keyToNewIndexMap.set(nextChild.key, i)
}

遍历旧 children，尝试复用新节点

ts
for (i = s1; i <= e1; i++) {
  const prevChild = c1[i]
  const newIndex = keyToNewIndexMap.get(prevChild.key)
  if (newIndex === undefined) {
    remove(prevChild)
  } else {
    patch(prevChild, c2[newIndex])
    newIndexToOldIndexMap[newIndex - s2] = i + 1
  }
}

newIndexToOldIndexMap 是关键数组：

  • 值表示：新节点在旧列表中的位置（+1，0表示新插入）
  • 后面将用这个数组计算最长递增子序列

为什么需要“最长递增子序列”？

在两个 vnode 列表中（旧列表 c1 和新列表 c2），Vue 想要知道：

  • 哪些节点是复用的（即相同类型+相同 key）？
  • 哪些需要卸载？（旧节点在新列表中找不到）
  • 哪些需要新建？（新节点在旧列表中找不到）
  • 哪些复用节点需要移动？ 重点就在于“尽量减少移动操作”。

Vue 是怎么使用LIS的？

  1. Vue 在 patchKeyedChildren 的“第 5 步”中处理复杂的 diff 情况，也就是列表中间有变动的情况。
  2. 它建立了一个 newIndexToOldIndexMap 数组，记录新列表每个元素对应的旧位置（没有旧位置的就是新节点，值为 0）。
  3. 然后，通过这个数组计算出一个 最长递增子序列，这表示：这些节点在新列表中的顺序在旧列表中是“稳定的”，不需要移动。
  4. 剩下那些不在 LIS 中的旧节点，就需要执行 move()。
ts
function getSequence(arr: number[]): number[] {
  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) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      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
}

假设

ts
arr = [5, 3, 4, 8, 6, 7]

最长递增子序列是：[3, 4, 6, 7]，即索引 [1, 2, 4, 5] → getSequence(arr) 返回 [1, 2, 4, 5]。 函数内部变量

ts
const p = arr.slice()       // 记录每个元素的前驱索引，用于最后追溯路径
const result = [0]          // 存储构成递增子序列的索引（索引来自 arr）
  • p[ i ] : 表示 arr[i] 的前一个索引是谁（形成路径）
  • result: 是当前发现的“最长递增子序列”的索引序列
ts
for (i = 0; i < len; i++) {
  const arrI = arr[i]
  if (arrI !== 0) {
    ...
  }
}

Vue 中传入的 arr 可能含有 0 —— 表示是新节点（没有旧位置），忽略它们。只处理非 0 元素。

ts
j = result[result.length - 1]   // 最后一个索引
if (arr[j] < arrI) {
  p[i] = j
  result.push(i)
  continue
}
  • 如果 arrI 比当前 LIS 的最后一个值大，那就可以直接接上 → 更新 p[i] = j（记录前驱）
  • 并把当前 i 加入到 result 中 如果并不大于，那么
ts
u = 0
v = result.length - 1
while (u < v) {
  // 取 u 和 v 的中间位置，赋值给 c。>> 1：是右移一位，相当于除以 2（向下取整）
  c = (u + v) >> 1
  if (arr[result[c]] < arrI) {
    u = c + 1
  } else {
    v = c
  }
}
  • 用 二分法找出第一个大于等于 arrI 的位置（贪心+优化）
  • 也就是：我们尝试“替换掉更大但没用的尾巴”，保持 result 尽可能小
ts
if (arrI < arr[result[u]]) {
  if (u > 0) {
    p[i] = result[u - 1]
  }
  result[u] = i
}
  • 如果找的位置 arr[result[u]] 大于 arrI，就替换掉
  • p[i] = result[u - 1] → 记录当前值接在谁后面
ts
u = result.length
v = result[u - 1]
while (u-- > 0) {
  result[u] = v
  v = p[v]
}
  • 倒着从 result 的最后一个索引开始
  • 每次向前追溯到 p[v]（即前驱）
  • 最终恢复出完整的 LIS
ts
// 输入
arr = [2, 5, 3, 7, 4, 8]
// 输出
[0, 2, 4, 5]   // 即 [2, 3, 4, 8]

这里最长递增子序列结束，找出不需要移动的节点序列，其余的节点则通过 insert 来移动。

  • 这些“递增”的新节点，其在旧列表中的位置是有序的；
  • 说明它们在 DOM 中本来就是按顺序的；
  • 所以我们只移动其他“打乱顺序”的节点；
  • 能够达到最小移动代价。
ts
<!-- 初始 DOM -->
<div>A</div>
<div>B</div>
<div>C</div>
<div>D</div>


-------------

<div>A</div>
<div>C</div>
<div>B</div>
<div>D</div>
  • A 和 D 没变
  • B 和 C 顺序互换了
  • 最长递增子序列是 [A, D]