Vue.js 中的 DOM Diff 算法

发表于 更新于 分类于 Disqus：

上一篇我们熟悉了一下 Inferno.js 的 DOM Diff 算法。今天我们来看 Vue.js 框架的 DOM Diff 算法。

Vue.js 的作者没有编写自己的算法，而是使用了 Snabbdom，并做了适当的修改。

DOM Diff 的关键算法在 https://github.com/snabbdom/snabbdom/blob/v0.7.1/src/snabbdom.ts#L179。

同样，我们依然假设有原始的 DOM 集合A为 “dfibge”，更新后的集合B为 “igfheb”。

创建4个指针 oldStartIdx、oldEndIdx、newStartIdx、newEndIdx，初始分别指向A的起始点、结束点和B的起始点、结束点。显然：

1
2
3
4
oldStartIdx=0
oldEndIdx=5
newStartIdx=0
newEndIdx=5

第一步，比较 A[oldStartIdx] 和 B[newStartIdx]，如果相同，则 oldStartIdx++、newStartIdx++。
第二步，比较 A[oldEndIdx] 和 B[newEndIdx]，如果相同，则 oldEndIdx++、newEndIdx++。

在本例中，以上两步全部不满足，跳过。

第三步，比较 A[oldStartVnode] 和 B[newEndVnode]，如果相同，则节点发生了右移。
第四步，比较 A[oldEndIdx] 和 B[newStartIdx]，如果相同，则节点发生了左移。

在本例中，以上两步全部不满足，跳过。

第五步，在A中搜索 B[newStartIdx]，即 i，找到则把A中的 i 移到 A[oldStartVnode] 前面并 newStartIdx++、oldStartVnode++，否则则创建它。

在本例中，A变成 idfbge。

返回第一步。

可以看到这个算法类似于优化后的插入排序。按照此算法，A的变换路径为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
A:dfibge
B:igfheb

=>

A:idfbge
B:igfheb
  ^

=>

A:igdfbe
B:igfheb
   ^

=>

A:igfdbe
B:igfheb
    ^

=>

A:igfhdbe
B:igfheb
     ^

=>

A:igfhedb
B:igfheb
      ^

=>

A:igfhebd
B:igfheb
       ^
=>

A:igfheb
B:igfheb
       ^

用一句话概括此算法的核心就是：依次遍历B集合，在A集合中找到对应项，放到与在B集合中相同的位置上。只不过 Snabbdom 使用了双向同时遍历来进行优化。

事实上，React 的 DOM Diff 算法与此也是非常类似的，只不过受限于 Fiber，只进行了单向搜索。但是即便如此， React 也引入了优化策略，尽量使得更多的元素不必移动。从本质上来看，Inferno 和 React 都利用递增子序列来进行了优化，但是 Inferno 使用算法来保证是最大递增子序列，而 React 的子序列是一定从第一个元素开始的，因此不一定是最大子序列。这在尾部元素移动到首部的时候，差异表现得更明显。