概念
DIFF 算法即两颗虚拟 DOM 树做 DIFF，比较两颗树的差异性，只更新产生变化的节点，渲染更新后的节点到真实的 DOM，以节约资源。
用户每次修改数据后都会引起页面元素重排和重绘，渲染真实的 DOM 开销较大，非常消耗性能。相对于真实 DOM 对象，js对象（即虚拟DOM）处理起来更快，而且更简单。 通过 DIFF 算法对比新旧 virtual DOM 之间的差异，可以批量的、最小化的执行 DOM 操作，从而提高性能。
我们先根据真实 DOM 生成一颗 virtual DOM，当 virtual DOM 某个节点的数据改变后会生成一个新的Vnode，然后 Vnode 和 oldVnode 作对比，发现有不一样的地方就直接修改在真实的 DOM 上，然后使 oldVnode 的值更新为 Vnode。
DIFF 的过程就是调用名为 patch 的函数，比较新旧节点，一边比较一边给真实的 DOM 打补丁。
比较的方式
diff时间复杂度分析：
常规：O(n^3) 遍历树1； 遍历树2； 排序； 1000个节点，十亿的量级。
优化：O(n) 只比较同一层级 ；tag不相同，直接删掉重建； 通过key来标识区分相同节点。
在采取diff算法比较新旧节点的时候，比较只会在同层级进行, 不会跨层级比较。若对 DOM 树进行跨层比较，即进行完全遍历，算法的时间复杂度与节点个数呈指数级增长。
同时Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计，所以diff的算法只做同层比较，若 Vnode 做了跨层移动，则直接删除 oldVnode, 再新建一个 new Vnode。
DIFF流程图
当用户操作数据发生改变的时候，set方法会让调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁，更新相应的视图。
具体分析
在 Vue 中，diff 算法主要聚焦于 vDOM 更新过程中的三个关键函数，分别是 patch、patchVNode、updateChildren。
patch
patch：比对两个虚拟dom时会有三种操作：删除、新增、更新
入参为旧节点和新节点，首先判断新老节点是否为同一个节点，判断方法即比较他们的 key 值、tag 值（标签类型）是否相同，若为同一个节点则执行 patchVnode 方法进行打补丁更新。
以下的代码是 Vue 源码中相关函数的精简伪代码，api 指的是原生的DOM操作函数集合。
function patch (oldVnode, vnode) {
// some code
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode)
} else {
const oEl = oldVnode.el // 当前oldVnode对应的真实元素节点
let parentEle = api.parentNode(oEl) // 父元素
createEle(vnode) // 根据Vnode生成新元素
if (parentEle !== null) {
api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
api.removeChild(parentEle, oldVnode.el) // 移除以前的旧元素节点
oldVnode = null
}
}
// some code
return vnode
}
function sameVnode (a, b) {
return (
a.key === b.key && // key值
a.tag === b.tag && // 标签名
a.isComment === b.isComment && // 是否为注释节点
// 是否都定义了data，data包含一些具体信息，例如onclick , style
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b) // 当标签是<input>的时候，type必须相同
)
}
patchVnode
patchVnode：比较两个VNode三种类型操作 属性更新、文本更新、子节点更新
patchVnode (oldVnode, vnode) {
const el = vnode.el = oldVnode.el
let i, oldCh = oldVnode.children, ch = vnode.children
if (oldVnode === vnode) return
if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
api.setTextContent(el, vnode.text)
}else {
updateEle(el, vnode, oldVnode)
if (oldCh && ch && oldCh !== ch) {
updateChildren(el, oldCh, ch)
}else if (ch){
createEle(vnode) //create el's children dom
}else if (oldCh){
api.removeChildren(el)
}
}
}
updateChildren
updateChildren：用一种较高效的方式对比新旧两个VNode的children，得出最小操作补丁。四指针双循环执行方式。
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
var oldStartIdx = 0;
var newStartIdx = 0;
var oldEndIdx = oldCh.length - 1;
var oldStartVnode = oldCh[0];
var oldEndVnode = oldCh[oldEndIdx];
var newEndIdx = newCh.length - 1;
var newStartVnode = newCh[0];
var newEndVnode = newCh[newEndIdx];
var 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
var canMove = !removeOnly;
if (process.env.NODE_ENV !== 'production') {
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);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
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);
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);
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(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
四指针双循环：
保证 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 前提下，执行如下循环算法：
- oldStartVNode 和 newStartVnode 满足 sameVnode 的条件，进行 patchVnode， 两个头指针右移。
- oldEndVnode 和 newEndVnode 满足 sameVnode，进行 patchVnode，两个尾指针左移。
- oldStartVnode 和 newEndVnode 满足 sameVnode, 进行 patchVnode，同时把头元素插入到 children nodes 尾部。++oldStartIdx，--newEndIdx。
- sameVnode(oldEndVnode, newStartVnode)。--oldStartIdx，++newEndIdx。
不符合以上四种情况，则直接寻找 oldCh 中是否存在和 newStartVnode 相同的节点，并移动到最前。
找不到和 newStartVnode 一致的节点，则调用 createElm 创建一个新的 DOM 节点。
循环结束后，处理剩余节点，
若 oldStartIdx > oldEndIdx 此时旧的 Vnode 节点已经遍历结束，但是新的节点还没遍历结束，则将剩余的 Vnode（>=0） 按照对应的下标插入到真实的DOM中去。
若 newStartIdx > newEndIdx, 此时新的 Vnode 已经遍历完成，但是老的节点还未遍历结束，说明需要在真实的 DOM 中把多余的老的Vnode节点删除。
图解直接看文档吧，配合源码食用更佳：https://www.cnblogs.com/lilicat/p/13448827.html
