对DOM和Virtual DOM的理解

一、DOM

1. 概念

MDN：文档对象模型 (DOM) 是HTML和XML文档的编程接口。它提供了对文档的结构化的表述，并定义了一种方式可以使从程序中对该结构进行访问，从而改变文档的结构，样式和内容。DOM 将文档解析为一个由节点和对象（包含属性和方法的对象）组成的结构集合。简言之，它会将web页面和脚本或程序语言连接起来。

理解：DOM就是对文档（HTML/XML）操作的接口。在DOM的概念里，将文档各种节点抽象成了一颗节点树（根节点是document），可以用各种接口对这颗树进行修改，从而改变文档所展示出来的结果。并不是说DOM是一颗节点树（DOM 是HTML和XML文档的编程接口），而是因为这些接口的存在，才把文档构建成了一颗树。

2. DOM和JS的关系

区别：DOM 跟编程语言（ JS 等等）是互相独立的，DOM译为文档对象模型，只是一种模型、结构，很多语言都能使用。
联系：DOM + JS 能组成一个web页面。

3. 节点和节点树

DOM 的最小组成单位叫做节点（Node）。节点树/DOM树就是由节点组成的。浏览器提供一个原生节点对象 Node ，所有的节点都继承自这个对象，拥有一些共同的属性和方法，这是 DOM 操作的基础。
注意区分文档节点和文档元素：在HTML中，文档节点一般就是指根节点document，而文档元素就是指<html>元素，每个文档都只能有一个文档元素。
在HTML中，Node有7种类型：

Document：整个文档树的顶层节点
DocumentType：doctype标签（比如<!DOCTYPE html>）
Element：网页的各种HTML标签（比如<body>、<a>等）
Attr：网页元素的属性（比如class="right"）
Text：标签之间或标签包含的文本
Comment：注释
DocumentFragment：文档的片段

Node原型上定义了许多的方法和属性，document节点也是继承自Node的，所以才能这样使用 document.querySelector 方法等等，还有获取 document.getElementsByTagName(‘html’)[0].nodeType 属性等等。
说白了就是用接口提供的Node对象上的方法和属性来修改和查看DOM树，来对页面修改。

4.参考

http://luopq.com/2015/11/30/javascript-dom/

https://wangdoc.com/javascript/dom/general.html

https://developer.mozilla.org/zh-CN/docs/Web/API/Document_Object_Model/Introduction

《JavaScript高级程序设计》（点击查看大图）

二、Virtual DOM

1. 概念

用 JS 模拟 DOM 结构，将 DOM 变化的对比放在 JS 层来做，实际上VDOM就是 JS 对象。

使用Virtual DOM ：render Virtual DOM + diff O(template size) + 必要的 DOM 更新 O(DOM change)

2. 为什么要用Virtual DOM

性能上直接操作真实 DOM 代价高
在框架中使用 VDOM 可以为你掩盖底层的 DOM 操作，让你用更声明式的方式来描述你的目的，从而让你的代码更容易维护。

3. diff算法

最早用于解决LCS（最长公共子串）问题，找出两个序列之间的公共子序列。
在VDOM中使用传统diff算法，会跨级对比两个树之间的不同，时间复杂度为O(n³)。
在Vue中，diff 优化后只比较树的同层级，为O(n)。

实现方式：（这里只演示diff算法，具体的 VDOM 是如何更新的不演示）（在 diff 比较过程中，循环从两边向中间收拢）

1）首先列出新老节点比较的可能情况：
- 当新老 VNode 节点的 start 满足 sameVnode 时，直接 patchVnode 即可，同时新老 VNode 节点的开始索引都加 1。
- 当新老 VNode 节点的 end 满足 sameVnode 时，同样直接 patchVnode 即可，同时新老 VNode 节点的结束索引都减 1。
- 当老 VNode 节点的 start 和新 VNode 节点的 end 满足 sameVnode 时，说明这次数据更新后 oldStartVnode 到了 oldEndVnode 后面了。这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldEndVnode 的后面，同时老 VNode 节点开始索引加 1，新 VNode 节点的结束索引减 1。
- 当老 VNode 节点的 end 和新 VNode 节点的 start 满足 sameVnode 时，这说明这次数据更新后 oldEndVnode 到了 oldStartVnode 前面了。这时候在 patchVnode 后，还需要将当前真实 dom 节点移动到 oldStartVnode 的前面，同时老 VNode 节点结束索引减 1，新 VNode 节点的开始索引加 1。
- 如果都不满足以上四种情形，那说明没有相同的节点可以复用。这时候就找与newStartVnode 一致 :key 的旧的 VNode 节点，如果两者满足 sameVnode ，在进行 patchVnode 的同时会将这个真实 dom 移动到 oldStartVnode 对应的真实 dom 的前面；如果没有找到，就无法进行节点的复用，只能调用 createElm 创建一个新的 dom 节点放到当前 newStartIdx 的位置。
2）流程：

1、初始化：

2、第一次循环：找到旧节点末尾和新节点开头 (都是 D) 相同，复用 D 节点即可。同时旧节点的 endIndex 移动到了 C，新节点的 startIndex 移动到了 C。

3、第二次循环：同样是旧节点末尾和新节点开头 (都是 C) 相同，于是创建 C 节点，插到D节点后。同时旧节点的 endIndex 移动到了 B，新节点的 startIndex 移动到了 E。（为什么第一次是复用，第二次是创建了？因为 old 序列队尾就是D直接复用即可）

4、第三次循环：发现 patchVnode 的 4 种情形都不符合，于是在旧节点队列中查找当前的新节点 E，不存在，只能创建新的节点 E，插入到 C 节点后。同时新节点的 startIndex 移动到了 A。旧节点的 startIndex 和 endIndex 都保持不动。

5、第四次循环：新旧节点的开头 (都是 A) 相同，于是创建 A 节点，插入到 E 节点后面。同时旧节点的 startIndex 移动到了 B，新节点的 startIndex 移动到了 B。

6、第五次循环：同第四次循环，创建 B 节点插入到 A 节点后面。同时旧节点的 startIndex 移动到了 C，新节点的 startIndex 移动到了 F。这时候发现新节点的 startIndex 已经大于 endIndex 了。不再满足循环的条件了，因此结束循环。

7、循环结束后，若新节点数大于老节点数则需要创建多出来的节点加入到队列中，反之删除。至此整个 diff 过程就已经全部完成了。在本例中，新节点数大于旧节点数，需要创建 newStartIdx 和 newEndIdx 之间的所有节点。在实例中就是 F 节点，因此创建 F 节点加入到 B 节点后即可。