vue 虚拟DOM和diff算法

patching算法（diff算法）是虚拟dom技术的必然产物，通过新旧虚拟DOM作比对（即diff），将变化的地方更新在真实DOM上；另外，也需要diff高效的执行比对过程，从而降低时间复杂度O(n)。
vue2.0为了降低watcher的粒度，从细粒度转变为了中等粒度，每个组件只有一个watcher与之对应，只有引入diff才能精确找到发生变化的地方。
vue中diff执行的时刻是组件实例执行其更新函数时，会比对上一次渲染结果oldVNode和新的渲染结果newVNode，此过程称为patch。
diff过程整体遵循深度优先，同层比较的策略；两个节点之间比较会根据它们是否拥有子节点或者文本节点做不同操作；比较两组子节点是算法的重点，首先假设头尾节点可能相同做4次比对尝试，如果没有找到相同节点才会按照通用方式遍历查找，查找结束再按情况处理剩下的节点，如果newchildren先循环完毕，那么说明oldchildren还有剩余节点，说明这些都是要废弃的，是应该被删除的节点，这是不需要循环比对就可以知道需要将这些节点从DOM中删除；如果是oldchidren先循环万，那么说明new里面还有剩余的节点，说明这些都是新增的，直接将它们插入到DOM中就行了，借助key通常可以非常精确的找到相同节点，因此整个patch过程会非常高效。

用JavaScript 对象结构表示 DOM 树的结构；然后用这个树构建一个真正的 DOM 树，插到文档当中 当状态变更的时候，重新构造一棵新的对象树。然后用新的树和旧的树进行比较，记录两棵树差异，把所记录的差异应用到所构建的真正的DOM树上，视图就更新了。Virtual DOM 本质上就是在 JS 和 DOM 之间做了一个缓存。

https://www.cnblogs.com/fs0196/p/12416187.html
render函数用来描述虚拟dom时，需要一个构建虚拟dom数的工具就是createElement

为什么需要虚拟DOM，它有什么好处?

Web界面由DOM树(树的意思是数据结构)来构建，当其中一部分发生变化时，其实就是对应某个DOM节点发生了变化，虚拟DOM就是为了解决浏览器性能问题而被设计出来的。如前，若一次操作中有10次更新DOM的动作，虚拟DOM不会立即操作DOM，而是将这10次更新的diff内容保存到本地一个JS对象中，最终将这个JS对象一次性attch到DOM树上，再进行后续操作，避免大量无谓的计算量。所以，用JS对象模拟DOM节点的好处是，页面的更新可以先全部反映在JS对象(虚拟DOM)上，操作内存中的JS对象的速度显然要更快，等更新完成后，再将最终的JS对象映射成真实的DOM，交由浏览器去绘制。

我们已经完成了创建虚拟DOM并将其映射成真实DOM，这样所有的更新都可以先反应到虚拟DOM上，如何反应？需要用到Diff算法。

两棵树如果完全比较时间复杂度是O(n^3)，但参照《深入浅出React和Redux》一书中的介绍，React的Diff算法的时间复杂度是O(n)。要实现这么低的时间复杂度，意味着只能平层的比较两棵树的节点，放弃了深度遍历。这样做，似乎牺牲掉了一定的精确性来换取速度，但考虑到现实中前端页面通常也不会跨层移动DOM元素，这样做是最优的。

Diff操作
在实际代码中，会对新旧两棵树进行一个深度的遍历，每个节点都会有一个标记。每遍历到一个节点就把该节点和新的树进行对比，如果有差异就记录到一个对象中。
映射成真实DOM
虚拟DOM有了，Diff也有了，现在就可以将Diff应用到真实DOM上了。深度遍历DOM将Diff的内容更新进去。