前言

diff 是 Vue 执行种的一个重要过程，是深入学习 Vue 时不容忽视的部分。

本篇文章暂时仅分析 Vue2 的 diff 基本原理，后续考虑补充源码分析和其他框架，如 React、Vue3 的 diff 相关内容，视情况而定。

是什么

在学习 Diff 算法之前，我们需要先了解几个概念。

1. Virtual DOM

虚拟 DOM（Virtual DOM）是一种将浏览器 DOM 的信息存储在 JavaScript 内存中的方法，是以 JavaScript 对象表示的抽象化的 DOM。

相比于操作 DOM，通过 JavaScript 操作 Virtual DOM 的开销要小得多。

2. VNode

Virtual DOM 为 DOM 的抽象表示。相同的，VNode 就是是 DOM 节点的抽象表示，是 Virtual DOM 的节点。

VNode 同样也是一个 JavaScript 对象，包括这个 DOM 节点的所有属性内容。

3. AST

AST（Abstract Syntax Tree），即抽象语法树，是源代码语法结构的一种抽象表示（树状形式）。树上的每个节点均代表源代码的一种结构。

Vue 通过编译将模板转换为 AST ，再将 AST 转换为渲染函数，执行渲染函数得到新的 VNode，将其与旧的 VNode 比对，对更改的部分进行更新、替换，最后渲染到页面上。

渲染流程

这个比对新旧 VNode，并进行更新、替换的过程就是 diff 的过程。diff 的结果是得到一个新的 VNode 树，用于页面渲染。

为什么

我们不妨设想一下不进行 Diff 的情况。这种情况下我们每次更新页面数据，都需要对页面整体的 DOM 进行渲染，这个消耗是非常大的。

而 Diff 的作用，就是找到新旧 DOM 的最小差异，尽量减少更新量，最大程度地降低渲染消耗。

那么，Vue 使用 Diff 的理由也就显而易见了，就是为了减少性能消耗。

基本逻辑

传统的 Diff 算法会递归处理每一个节点，计算量非常大。

将两颗树中所有的节点一一对比需要 O(n²)的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为 O(n),同理添加新节点的复杂度也是 O(n),合起来 diff 两个树的复杂度就是 O(n³)

而 React 和 Vue2 的 diff 算法规则大致相同，仅在同级的 VNode 之间做比较计算，递归进行，最终实现整个 DOM 树的更新。

出自《React’s diff algorithm》

diff 算法一般包括几个主要的逻辑，以 3 层嵌套的 DOM 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 简化vdom结构如下
{
  name: 'root',
  children: [
    {
      name: 'branch-A',
      children: [{ name: 'leaf-A-1', children: [] }],
    },
    {
      name: 'branch-B',
      children: [],
    },
  ],
};

图示如下

base

1. 不同节点类型的比较

我们想在二级节点 branch-A 下追加一个三级子节点 leaf-A-2，如下图所示：

B

这种情况仅生成节点 leaf-A-2 并插入到 branch-A 的子节点列表。

2. 删除节点

3. 更新节点

Key 的作用

参考

  1. 你不知道的 Virtual DOM（一）
  2. 【Vue 原理】Diff - 白话版
  3. 《Vue 不看源码懂原理》系列——Vue 的 diff 算法不难懂
  4. 通俗易懂的 vue 虚拟（Virtual ）DOM 和 diff 算法
  5. 极客时间 《Vue 开发实战 10 | 理解虚拟 DOM 及 key 属性的作用》
  6. Vue2 Diff 算法深入解读
  7. 深入浅出 React（四）：虚拟 DOM Diff 算法解析
  8. 聊一聊 Diff 算法（React、Vue2.x、Vue3.x）