React 15 中，虚拟 DOM （Virtual DOM）的结构是树结构。

按照传统的树结构 diff 算法，时间复杂度为，这对于需要频繁对比树结构的变化而言，消耗太大。
Facebook 的 React 团队，提出三个前提、分别进行三步对比，把时间复杂度降为

三个前提：

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

三步对比：tree diff、component diff、 element diff

diff 算法过程

tree diff

基于前提一，React 对树进行分层比较，两棵树只会对同一层次的节点进行比较。

既然 DOM 节点跨层级的移动操作少到可以忽略不计，针对这一现象，React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。 当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。

function updateChildren (nextNestedChildrenElements, transaction, context) {
  updateDepth++;
  var errorThrown = true;
  try {
    this._updateChildren(nextNestedChildrenElements, transaction, context);
    errorThrown = false;
  } finally {
    updateDepth--;
    if (!updateDepth) {
      if (errorThrown) {
        clearQueue();
      } else {
        processQueue();
      }
    }
  }
}

那我要是就想对 DOM 节点进行跨层级的移动操作，React diff 会怎么处理呢？

如下图，A 节点（包括其子节点）整个被移动到 D 节点下，由于 React 只会简单的考虑同层级节点的位置变换，而对于不同层级的节点，只有创建和删除操作。

1. 当根节点发现子节点中 A 消失了，就会直接销毁 A；
2. 当 D 发现多了一个子节点 A，则会创建新的 A（包括子节点）作为其子节点。此时，React diff 的执行情况：create A -> create B -> create C -> delete A

由于这种操作影响 React 性能，因此 React 官方建议不要进行 DOM 节点跨层级的操作。

在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。 例如，可以通过 CSS 隐藏或显示节点，而不是真的移除或添加 DOM 节点。

component diff

基于前提二，判断新旧组件是否是由同一个类创建，是则为同类型的组件。

1. 如果不是同类型，判断新组件为 dirty component，替换组件下所有子节点。
2. 如果是同类型，则进行 element diff。

   对于同一类型的组件，有可能其 Virtual DOM 没有任何变化，如果能够确切的知道这点那可以节省大量的 diff 运算时间，因此 React 允许用户使用shouldComponentUpdate() 来判断该组件是否需要进行 diff。

如下图，当 component D 改变为 component G 时，即使这两个 component 结构相似。
一旦 React 判断 D 和 G 是不同类型的组件，就不会比较二者的结构，而是直接删除 component D，重新创建 component G 以及其子节点。
虽然当两个 component 是不同类型但结构相似时，React diff 会影响性能，但正如 React 官方博客所言：不同类型的 component 是很少存在相似 DOM tree 的机会，因此这种极端因素很难在实现开发过程中造成重大影响的。

element diff

当节点处于同一层级时，React diff 提供了三种节点操作，分别为：**INSERT_MARKUP(插入)**、**MOVE_EXISTING(移动)**和 **REMOVE_NODE(删除)**

• 插入：组件 C 不在集合(A,B)中，需要插入
• 移动：
  • 组件 D 已经在集合(A,B,C,D)里了，且集合更新时，D 没有发生更新**(以及 key 不变)**，只是位置改变，这时移动组件 D
  • 借助 key 没有更新，来考虑复用原来组件，移动原理组件位置即可
• 删除：
  • 组件 D 在集合(A,B,D)中，但 D 的节点已经更改，所以需要删除旧的 D，再创建新的 D
  • 组件 D 之前在 集合(A,B,D)中，但集合变成新的集合(A,B)了，D 就需要被删除

React 通过设置唯一 key的策略，对 element diff 进行算法优化

1. 没有唯一 key 的情况下

如下图，老集合中包含节点：A、B、C、D，更新后的新集合中包含节点：B、A、D、C，此时新老集合进行 diff 差异化对比，发现B != A，则创建并插入 B 至新集合，删除老集合 A。

旧的 A B C D 全删除了，新创建了 B A D C，这样性能损耗大

1. 有唯一 key 的情况下

参考资料

《深入理解React虚拟DOM 》