DIFF算法浅析
在虚拟dom中diff的实现。
分别从4个方面：
DIFF抽象概念（概述、时间复杂性分析）
在Vue2中的实现（版本2.6.11、必要性、执行方式）
在React中的实现（版本16.13.1，必要性、执行方式）
对比总结（React中diff与vue中diff的对?）
1. DIFF抽象概念
diff是广泛的概念，如git diff，js对象 diff等。两棵树做diff，即虚拟DOM中的diff算法。
diff算法的必要性：渲染真实DOM的开销是很大的，轻微的操作都可能导致页面重新排版，非常耗性能。 相对于DOM对象，js对象处理起来更快，而且更简单。 通过diff算法对比新旧vdom之间的差异，可以批量的、最小化的执行 dom操作，从而提高性能。
diff时间复杂度分析：
常规：O(n^3) 遍历树1； 遍历树2； 排序； 1000个节点，十亿的量级。
优化：O(n) 只比较同一层级 ；tag不相同，直接删掉重建； 通过key来标识区分相同节点。
1. 只比较同一层级。
Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
如图左，只比较同一层级的，即相同颜色的层级。如右图，左侧P3在右侧的P标签下，不做移动，而是做新增操作和删除操作。
2.tag不相同，直接删掉重建。
拥有不同类型的两个组件将会生成不同的树形结构。
如上图，D和G节点的子节点相同，但是tag不同，则整棵树都重新删除重建。
3.通过key来标识区分相同节点。
开发者可以通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定。
左图没有key值，所以老的节点全部删除，新的节点再全部创建。右图添加key值，所以只需要酱A移动到B，将C移动到D，就可以得到与新树一样的老树。
2.在VUE2中的实现
vue 版本2.6.11
必要性分析：
vue 1中有细粒度的数据变化侦测，不需要虚拟DOM的，但是细粒度造成了大量开销，只适合中小型项目。 vue 2中为了降低Watcher粒度，每个组件只有一个Watcher实例，状态变化时只能通知到组件，只有引入diff才能精确找到发生变化的地方。 vue 2的diff算法，位于patch.js文件中，该算法来源于snabbdom。
在vue2中的执行方式：
diff过程整体遵循深度优先、同层比较的策略。 当数据发生改变时，会调用Dep.notify通知所有Watcher，调用patch给真实的DOM打补丁，更新相应的视图。 patch两个节点之间比较会根据它们是否拥有子节点或者文本节点做不同操作。 比较两组子节点是重点：首先假设头尾节点可能相同，做4次比对尝试，如果没有找到相同节点则遍历查找，查找结束再按情况处理剩下的节点。 借助key通常可以非常精确找到相同节点。
patch：比对两个虚拟dom时会有三种操作：删除、新增、更新
patchVnode：比较两个VNode三种类型操作 属性更新、文本更新、子节点更新
updateChildren：用一种较高效的方式对比新旧两个VNode的children，得出最小操作补丁。双循环执行方式。
接下来对于updateChildren做一个图解分析
在新老两组VNode节点的头尾两侧都有一个变量标记，在遍历过程中这几个变量都会向中间靠拢。 当oldStartIdx > oldEndIdx或者newStartIdx > newEndIdx时结束循环
循环开始
当 oldStartVnode和newStartVnode 满足sameVnode，直接将该 VNode节点进行patchVnode
当 oldEndVnode和newEndVnode 满足sameVnode，直接将该 VNode节点进行patchVnode
如果oldStartVnode与newEndVnode满足sameVnode。说明oldStartVnode已经到oldEndVnode 后面，进行patchVnode的同时还需要将真实DOM节点移动到oldEndVnode后面。
如果oldEndVnode与newStartVnode满足sameVnode，说明oldEndVnode到oldStartVnode前面，进行patchVnode的同时要将oldEndVnode对应DOM移动到oldStartVnode对应DOM的前面。
如果以上情况均不符合，则在oldVNode中找与newStartVnode相同的节点，若存在执行patchVnode，同时将elmToMove移动到oldStartIdx对应的DOM的前面。
当然也有可能newStartVnode在oldVNode节点中找不到一致的sameVnode，这个时候会调用 createElm创建一个新的DOM节点。
循环结束，处理剩下的节点。
当oldStartIdx > oldEndIdx，这个时候旧的VNode节点已经遍历完了，但是新的节点还没有。新的VNode节点实际上比老的VNode节点多，需要将剩下的VNode对应的DOM根据下标插入到真实DOM 中。
当结束时newStartIdx > newEndIdx时，说明新的VNode节点已经遍历完了，但是老的节点还有剩余，需要在真实dom中，将区间为[oldStartIdx, oldEndIdx]的多余节点删掉。