Vue3-Diff算法详解

一、虚拟节点树的生成流程

在阐述Diff算法之前，先简单聊下虚拟节点树的生成过程。

vue-sfc模块是Vue3的模板编译模块，在一个.vue文件内，顶层的<template>内的模板将被编译成一个组件节点。组件节点有一个render函数，用于创建后代节点。当这些节点中存在组件节点时，则又会创建这个组件节点的后代节点。一棵虚拟节点树便由组件节点的render函数来创建节点且连接而成。

1.节点的起始-根节点

正常的Vue3项目，起始文件一般如下：

import { createApp } from 'vue';
import App from './App.vue';

const app = createApp(App);
app.mount('#app');

2个简单小点如下:

• App组件用于创建根节点
• mount时并没有一次性创建完整棵虚拟节点树，而是通过组件节点的render函数逐个创建。即每个组件渲染一部分节点，最后将所有组件的节点连接起来

2.节点的生成时机-渲染函数(render)

渲染一个组件节点时，会调用组件节点的render函数，并生成一系列后代节点。如果这些节点中存在组件节点，则继续调用这些组件节点的render函数。不断调用组件节点的render函数，直到某个组件节点的render函数不创建任何组件节点为止。

从根节点开始，像这样不断调用组件节点的render函数，直至最下层的组件节点。再将所有组件节点生成的后代节点，以树结构连接起来，便形成一棵虚拟节点树。

3.虚拟节点的渲染顺序-深度优先算法

在render函数创建一系列后代节点后，还需要对节点进行渲染。渲染则是以深度优先的形式逐个渲染的，如下所示：

二、节点的更新流程

只有当App节点挂载那一刻起，初始虚拟节点树创建且挂载，此时所有的组件节点都会被打上一个isMouted标记，标识是否挂载。在此之后的主动或被动触发组件节点的render函数，都是更新，不会重新挂载。

简单总结，只有第一次触发组件的render函数，是去挂载组件。后续的触发render函数，都是更新节点。

1.生成子节点

重新触发render函数而创建的后代节点不会直接进行节点替换。而是通过Diff算法，以一种打补丁的形式去修正已经存在的节点。

2.以深度优先的形式比较更新前后节点

同虚拟节点树的创建流程一样，重新触发render函数创建的新节点也是以深度优先的形式同原节点逐个比较更新。假如存在如下情形：

则更新流程如下:

• 重新触发Comp组件的render函数，创建【A, B，C, D】节点
• 比较A节点是否变更
• 比较C节点是否变更
• 挂载D节点
• 比较B节点是否变更

三、Diff算法的意义

1.虚拟节点与真实dom元素的绑定

虚拟节点树在创建的同时，也在创建对应的dom元素。每个虚拟节点都有一个el属性用于保存节点对用的dom元素。前文已经说过，虚拟节点的渲染是以深度优先的形式逐个渲染的，因此可以很轻松的创建出一棵dom树。

假如存在以下模板:

<div>
  <span>1111</span>
  <div></div>
</div>

则对应的节点树如下:

- VNode(div)
  - VNode(span)
    - VNode(1111)
  - VNode(div)

因此创建dom元素的顺序如下:

• 渲染VNode(div)节点，创建div元素
• 渲染VNode(span)节点，创建span元素
• 渲染VNode(1111)文本节点，创建文本元素1111
• 渲染VNode(div)节点，创建div元素

2.Diff算法对于页面的优化

为什么需要使用Diff算法？重新触发render函数时，直接将原始节点卸载掉，然后挂载新的节点，这个流程简单而清晰，那么为什么需要使用Diff算法来动态更新呢？

一个Web页面在创建太多dom元素时，是存在性能瓶颈的。Diff算法的目的正是尽可能的减少性能的开销，优化一个项目的使用体验。

使用Diff算法去更新某个节点时，其主要的作用对象不是这个虚拟节点，而是这个节点所绑定的dom元素。前文说过，更新流程是在已经存在的虚拟节点树上打补丁，本质是通过更新前后的节点差异来表达不同，并作用到对应的dom元素上，而不是直接创建新的dom元素，这样便大大减少了创建dom元素所带来的性能开销。

四、Diff算法实现原理

下面我将以如下更新前后2个节点列表来解释虚拟算法的实现原理：

1.左比较

从左向右进行比较，此时A节点可以复用，则直接更新A节点即可。

2.右比较

从右向左比较，此时H节点可以复用，直接更新即可

3.插入和卸载

通过上述2个步骤，此时存在2种特殊情况，即

• 旧节点全部更新，新节点还有剩余，剩余新节点全部挂载

  

  此时M,N节点为更新后新加入的节点，只要在对应位置挂载即可。

• 新节点全部更新，旧节点还有剩余，剩余旧节点全部卸载

  

  此时M,N节点为更新后不存在的节点，直接卸载即可。

4.乱序比较

说完上述3个步骤，紧接着前面的示例继续阐述。比较完前后2端的可复用节点后，剩下的节点则是乱序的，因此需要在乱序的节点中找到可复用节点。

1).构建新key-index映射表

针对还没有比较的新节点，创建key-index映射表，上述示例对应映射表如下:

{
    G:1,
    F:2,
    C:3,
    M:4,
    I:5,
    B:6
}

这一步是为了记录新节点的对应位置。

2).循环遍历旧节点列表与新节点列表比较并记录

循环遍历所有未比较的旧节点，如果新节点中存在可复用的节点，则记录对应的位置关系，如下所示：

这儿简单阐述下这个数组的作用：假如遍历到B节点时，发现新节点列表中也存在B，此时可以通过key-index映射表获取到B节点的下标位置6，因此在数组对应位置插入旧节点的位置，这个数组保存了新旧节点的位置关系。

此时D,E节点未找到可复用的节点，直接卸载。如下:

3).挂载节点与移动节点

此时根据位置数组生成最大稳定升序序列，这个示例比较特殊，此时是[5]。在正常的情况，如[1，2，4，3，5]，则会生成[0, 1, 2, 4]。获取到最大稳定序列，则只需要移动不稳定的那些节点，就可以将序列的位置调整完毕。

0表示没有匹配到复用元素，需要挂载。因此除开0外，这个数组全是降序。

流程如下:

从右到左遍历新节点的乱序列表，此时为[G,F,C,M,I,B]，遍历到B时，由于B在稳定序列中，则B不用移动。稳定序列是[5]，B在乱序列表中的下标是5。

遍历到M，I节点时，则需要插入，因为旧节点不存在能复用的节点。

遇到C，F，G节点时，则需要移动位置。这儿需要注意的是，新节点不会直接替换旧节点，而是以补丁的形式去修正旧节点，因此旧节点中的C,F,G节点的位置需要调整为新节点的位置。至于这几个节点的复用更新，在4.2步骤中就已经完成。

五、题外话

Vue3的Diff算法，从实现上来说并不算复杂，但却能极大的减少在更新页面时的性能开销。虽然Diff算法能避免绝大多数场景因创建dom元素带来的性能开销，但一个页面dom元素过多时，纯粹的节点比较也会浪费性能。

因此Vue3在Diff算法外，还增加了诸如PatchFlag和动态节点数组等辅助属性来实现节点快速比较，不比较静态节点。而在一个项目中，静态的元素通常是占绝大多数的。