简述

传统diff两棵树的算法时间复杂度很高，是O(n^3)，Vue与React都对它们的diff算法做了优化。

Vue diff

开始比较

  • 比较父节点是同一节点的那一层子节点
  • 最大的根节点一开始可以直接比较

比较流程

  • 先找到不需要移动的相同节点
  • 再找到需要移动的相同节点
  • 最后找不到，删除新建一个节点

修改DOM树
这里会存在三棵树，一颗页面DOM树，一颗是旧的VNode树，一颗是新的VNode树。页面DOM 树和旧VNode 树 节点一一对应的。进行比较的过程中不会对这两棵Vode树进行修改，而是以比较的结果直接对真实DOM进行修改

React diff

diff策略

  • Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
  • 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
  • 对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。
    React的diff分为tree diff、component diff、element diff

tree diff

对树进行分层比较，两棵树只会对同一层次的节点进行比较。即比较同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。
图片说明

component diff

  • 如果是同一类型的组件，则与tree diff一样
  • 如果类型不同，则替换组件下的所有子节点

element diff

当比较处于同一层级时，React提供了三种操作

  • 插入，即插入新节点
  • 移动，位置不同但是可以复用的节点则移动
  • 删除，不能复用或者不存在，则删除