传统 diff 算法
传统 diff 算法通过循环递归对所有节点两两对比，时间复杂度是 O(n^2)，再对树的编辑（插入，替换，删除）进行一次遍历，因此时间复杂度是 O(n^3)，其中 n 是节点总数，假设我们要展示 1000 个节点，那么我们就要依次执行上十亿次的比较,效率十分低效。在前端渲染场景来说成本过高
React diff 算法
在 React 中通过三个策略，将 O(n^3)复杂度的问题转换成 O(n)复杂度的问题
策略一：WebUI 中 DOM 节点跨层级的移动特别少，可以忽略不急策略二：拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构策略三：对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。基于以上策略，React 分别对 tree diff，component diff 以及 element diff 进行算法优化。
tree diff
React 通过 updateDepth 对 Virtual dom 树进行层级控制，只会对相同层级的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在时，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。
<code>updateChildren: function(nextNestedChildrenElements, transaction, context) {
updateDepth++;
var errorThrown = true;
try {
this._updateChildren(nextNestedChildrenElements, transaction, context);
errorThrown = false;
} finally {
updateDepth--;
if (!updateDepth) {
if (errorThrown) {
clearQueue();
} else {
processQueue();
}
}
}
}/<code>
出现了 DOM 跨层级的移动操作，如下图。A 节点整个被移动到了 D 节点下，React 只会考虑同层级节点的位置变换，而对于不同层级的节点，只有创建和删除操作。当根节点发现子节中 A 消失了，就会直接销毁 A；当 D 发现多了一个子节点 A，则会创建新的 A（包括子节点）作为子节点。此时，diff 的执行情况：
delete A -> create A -> create B -> create C
component diff
如果是同一个类型的组件，则按照原策略进行 Virtual DOM 比较。如果不是同一类型的组件，则将其判断为 dirty component，从而替换整个组价下的所有子节点。如果是同一个类型的组件，有可能经过一轮 Virtual DOM 比较下来，并没有发生变化。如果我们能够提前确切知道这一点，那么就可以省下大量的 diff 运算时间。因此，React 允许用户通过 shouldComponentUpdate()来判断该组件是否需要进行 diff 算法分析。如下图所示，当组件 D 变为组件 G 时，即使这两个组件结构相似，一旦 React 判断 D 和 G 是不用类型的组件，就不会比较两者的结构，而是直接删除组件 D，重新创建组件 G 及其子节点。虽然当两个组件是不同类型但结构相似时，进行 diff 算法分析会影响性能，但是毕竟不同类型的组件存在相似 DOM 树的情况在实际开发过程中很少出现，因此这种极端因素很难在实际开发过程中造成重大影响。
element diff
当节点属于同一层级时，diff 提供了 3 种节点操作，分别为 INSERT_MARKUP(插入)，MOVE_EXISTING(移动)，REMOVE_NODE(删除)。
INSERT_MARKUP：新的组件类型不在旧集合中，即全新的节点，需要对新节点进行插入操作。MOVE_EXISTING：旧集合中有新组件类型，且 element 是可更新的类型，这时候就需要做移动操作，可以复用以前的 DOM 节点。REMOVE_NODE：旧组件类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者旧组件不在新集合里的，也需要执行删除操作。<code>// 新节点插入操作
function makeInsertMarkup(markup, afterNode, toIndex) {
return {
type: ReactMultichildUpdateTypes.INSERT_MARKUP,
content: markup,
fromIndex: null,
fromNode: nuLL,
toIndex: toIndex, // 插入位置
afterNode: afterNode // 记录下一个节点
};
}
function makeMove(child, afterNode, toIndex) {
return {
type: ReactMultichildUpdateTypes.MOVE_EXISTING,
content: null,
fromIndex: child._mountIndex, // 移动起始位置
fromNode: ReactReconciler.getNativeNode(child), // 记录移动的节点
toIndex: toIndex, // 移动结束位置
afterNode: afterNode // 记录下一个节点
};
}
function makeRemove(child, node) {
return {
type: ReactMultichildUpdateTypes.REMOVE_NODE,
content: null,
fromIndex: child._mountIndex,
fromNode: node, // 记录移动的节点
toIndex: null,
afterNode: null
};
}/<code>
旧集合中包含节点 A，B，C 和 D，更新后的新集合中包含节点 B，A，D 和 C，此时新旧集合进行 diff 差异化对比，发现 B!=A，则创建并插入 B 至新集合，删除旧集合 A;以此类推,创建并插入 A，D 和 C，删除 B，C 和 D。
React 发现这类操作烦琐冗余，因为这些都是相同的节点，但由于位置发生变化，导致需要进行繁杂低效的删除，创建操作，其实只要对这些节点进行位置移动即可。React 提出了优化策略：允许开发者对同一层级的同组子节点，添加唯一 key 进行区分
现在 diff 的运作方式：
首先,对新集合中的节点进行循环遍历 for( name in nextchildren)，通过唯一的 key 判断，新旧集合中是否存在相同的节点 if( prevChild === nextChild)，如果存在相同节点，则进行移动操作，但在移动前需要将当前节点在旧集合中的位置与 lastIndex 进行比较 if( prevChild._mountIndex < lastIndex),否则不执行该操作。这是一种顺序优化手段, lastIndex 一直在更新，表示访问过的节点在旧集合中最右的位置(即最大的位置)如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在旧集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作。只有当访问的节点比 lastIndex 小时，才需要进行移动操作。
如下图：