DOM diff 算法是怎样的？

Diff算法 | Marvin

Diff算法的核心就是 针对具有相同父节点的同层新旧子节点进行比较，而不是使用逐层搜索递归遍历的方式。时间复杂度为O(n) 。 如何理解？ 说白点，就是 当新旧VNode树在同一层具有相同的VNode节点时，才会继续对其子节点进行比较。一旦旧 VNode树同层中的节点在新 VNode树中不存在或者是多余的，都会在新的真实 DOM 中进行添加或者删除。 下面就拿一副图进行解释。 从上面的示例图可以看到， Diff 算法中只会对同一层的元素进行比较，并且必须拥有相同节点元素，才会对其子节点进行比较，其他多余的同层节点都会一律做删除或添加操作。 接下来，我们就从源码角度来看看这过程到底是如何发生的。🤔 当数据发生改变时，set方法会让调用 Dep.notify通知所有订阅者 Watcher，订阅者就会调用 patch 给真实的DOM打补丁，更新相应的视图。 我们依然是从_update 方法入手，看看到底是如何操作的。 每一次更新模板时，都会先将渲染好的新 VNode树保存到实例的_vnode属性上，这样做的目的是为了下一次更新时，能获取到旧 VNode 树进行比较。 针对是否拥有旧的 VNode树，使用__patch__方法执行相应逻辑，也即执行了 patch 过程。 可以看到， 只有在浏览器的环境下才能进行patch过程，而实现 patch的，就是 createPatchFunction 方法，我们接着看下去。 好啦，对于 patch 比较过程，你也应该有了一个大概了解。现在就来简单总结一下上述代码。 当旧VNode树不存在时，直接根据新VNode树创建相应的真实DOM。 当旧VNode树存在时，则会调用sameVnode方法比较当前新旧节点是否相同。 当新旧节点是相同时，会调用patchVnode方法比较新旧节点（过程就是继续比较其子节点，递归下去～）。 当新旧节点是不同时，则会先按照新VNode节点创建新的真实DOM节点，再根据旧VNode节点将相应的真实DOM节点进行删除。 是不是很简单 🤔...那么问题来了，不是说 patch过程是使用 Diff 算法进行比较的吗？怎么还看不到，甭急，下面我会讲到哈。 在上面的总结中，我们是可以看到两个方法，分别是 sameVnode方法和 patchVnode