简单 Diff 算法：核心思路
简单 Diff 算法的核心是通过两层 for 循环，遍历新旧节点数组，利用 key 属性匹配可复用的节点，并记录一个 lastIndex 值来判断哪些节点需要移动。
基本数据结构
// 旧节点
const oldChildren = [
{ type: 'p', key: '1', children: 'hello' },
{ type: 'p', key: '2', children: 'vue' },
{ type: 'p', key: '3', children: 'template' },
]
// 新节点（顺序从 1,2,3 → 3,1,2）
const newChildren = [
{ type: 'p', key: '3', children: 'template' },
{ type: 'p', key: '1', children: 'hello' },
{ type: 'p', key: '2', children: 'vue' },
]
typescript
第一步：找到可复用节点并判断是否需要移动
function simpleDiff(oldChildren: VNode[], newChildren: VNode[], container: HTMLElement) {
let lastIndex = 0 // 记录旧节点中的最大索引
for (let i = 0; i < newChildren.length; i++) {
const newVNode = newChildren[i]
let find = false // 标记是否在旧节点中找到可复用节点
for (let j = 0; j < oldChildren.length; j++) {
const oldVNode = oldChildren[j]
if (newVNode.key === oldVNode.key) {
// 找到可复用节点
find = true
// 更新节点内容
patch(oldVNode, newVNode, container)
if (j < lastIndex) {
// j < lastIndex → 需要移动
// 获取锚点：当前新节点的前一个节点
const prevVNode = newChildren[i - 1]
if (prevVNode) {
const anchor = prevVNode.el!.nextSibling
insert(newVNode.el!, container, anchor)
}
} else {
// j >= lastIndex → 不需要移动，更新 lastIndex
lastIndex = j
}
break // 找到匹配后跳出内层循环
}
}
// find 仍为 false → 新增节点（旧节点中没有该 key）
if (!find) {
const prevVNode = newChildren[i - 1]
let anchor: Node | null = null
if (prevVNode) {
anchor = prevVNode.el!.nextSibling
} else {
// 新节点是第一个子节点，用容器的 firstChild 作为锚点
anchor = container.firstChild
}
patch(null, newVNode, container, anchor)
}
}
}
typescript
lastIndex 的工作原理
以 旧: [1, 2, 3] → 新: [3, 1, 2] 为例：
外层循环 i=0: 新节点 key=3
内层循环 j=0: key=1 不匹配
内层循环 j=1: key=2 不匹配
内层循环 j=2: key=3 匹配！j=2 >= lastIndex=0，不需要移动
更新 lastIndex = 2
外层循环 i=1: 新节点 key=1
内层循环 j=0: key=1 匹配！j=0 < lastIndex=2，需要移动
将 key=1 的 DOM 移动到 key=3 的后面
外层循环 i=2: 新节点 key=2
内层循环 j=1: key=2 匹配！j=1 < lastIndex=2，需要移动
将 key=2 的 DOM 移动到 key=1 的后面
text
核心规则：在旧节点中的索引小于 lastIndex 的节点需要移动，大于等于的则不需要。
第二步：处理新增节点
当内层循环遍历完所有旧节点后 find 仍为 false，说明这是一个全新的节点：
if (!find) {
const prevVNode = newChildren[i - 1]
let anchor: Node | null = null
if (prevVNode) {
// 插入到前一个节点的后面
anchor = prevVNode.el!.nextSibling
} else {
// 新节点是第一个子节点
anchor = container.firstChild
}
patch(null, newVNode, container, anchor)
}
typescript
关键点是确定插入位置（锚点 anchor）。新增节点需要插入到正确位置，锚点就是前一个新节点对应的真实 DOM 的下一个兄弟节点。
第三步：删除多余节点
遍历完新节点后，还需要检查旧节点中是否有被删除的节点：
// 在外层循环结束后，遍历旧节点查找需要删除的节点
for (let i = 0; i < oldChildren.length; i++) {
const oldVNode = oldChildren[i]
const has = newChildren.find(vnode => vnode.key === oldVNode.key)
if (!has) {
// 新节点中没有该 key → 删除
unmount(oldVNode)
}
}
typescript
insert 方法和 anchor 参数
移动和新增操作都需要 insert 方法的 anchor 参数，用于指定插入位置：
const options = {
insert(el: HTMLElement, parent: HTMLElement, anchor: Node | null = null) {
// insertBefore 的第二个参数为 null 时等同于 appendChild
parent.insertBefore(el, anchor)
},
}
typescript
patch 和 mountElement 方法也需要增加 anchor 参数，在挂载新元素时将其插入到正确位置。
简单 Diff 算法的局限性
| 方面 | 说明 |
|---|---|
| 优点 | 实现简单，逻辑清晰，能正确处理移动、新增、删除 |
| 缺点 | 移动策略不够优——只要 j < lastIndex 就移动，可能产生不必要的 DOM 操作 |
| 复杂度 | O(n*m)，双层循环 |
Vue3 实际使用的是更高效的快速 Diff 算法，它借鉴了 inferno 的思路，通过头尾预处理和最长递增子序列进一步减少 DOM 操作。但简单 Diff 是理解更复杂算法的基础。
本节完整流程
遍历新节点数组
├── 对每个新节点，遍历旧节点数组找 key 匹配
│ ├── 找到 → patch 更新内容
│ │ ├── j < lastIndex → 需要移动（insertBefore）
│ │ └── j >= lastIndex → 不移动，更新 lastIndex
│ └── 没找到 → find=false → 新增节点
│ └── 计算锚点位置，patch 挂载
└── 遍历结束后
└── 遍历旧节点，删除新节点中不存在的节点
text
↑