摘要：通過深度優先遍歷兩棵樹，每層節點進行對比，記錄下每個節點的差異。所以可以對那棵樹也進行深度優先遍歷，遍歷的時候從步驟二生成的對象中找出當前遍歷的節點差異，然后進行操作。

把一個div元素的屬性打印出來，如下：

可以看到僅僅是第一層，真正DOM的元素是非常龐大的，這也是DOM加載慢的原因。
相對于DOM對象，原生的JavaScript對象處理起來更快，而且更簡單。DOM樹上的結構、屬性信息都可以用JavaScript對象表示出來：

var element = {
  tagName: "ul", // 節點標簽名
  props: { // DOM的屬性，用一個對象存儲鍵值對
    id: "list"
  },
  children: [ // 該節點的子節點
    {tagName: "li", props: {class: "item"}, children: ["Item 1"]},
    {tagName: "li", props: {class: "item"}, children: ["Item 2"]},
    {tagName: "li", props: {class: "item"}, children: ["Item 3"]},
  ]
}

上面對應的HTML寫法是：

  
Item 1
  
Item 2
  
Item 3

DOM樹的信息可以用JavaScript對象表示出來，則說明可以用JavaScript對象去表示樹結構來構建一棵真正的DOM樹。

狀態變更->重新渲染整個視圖的方式可以用新渲染的對象樹去和舊的樹進行對比，記錄這兩棵樹的差異。兩者的不同之處就是我們需要對頁面真正的DOM操作，然后把它們應用在真正的DOM樹上，頁面就變更了。這樣可以做到：視圖的結構確實是整個全新渲染了，但是最后操作DOM的只有變更不同的地方。

用JavaScript對象結構表示DOM樹的結構，然后用這個樹構建一個真正的DOM樹，插到文檔當中

當狀態變更的時候，重新構建一棵新的對象樹。然后用新的樹和舊的樹進行比較，記錄兩棵樹的差異

把2所記錄的差異應用到步驟1所構建的的真正的DOM樹上，視圖就更新了

Virtual DOM本質就是在JS和DOM之間做了一個緩存，JS操作Virtual DOM，最后再應用到真正的DOM上。

步驟一：用JS對象模擬虛擬DOM樹

用JavaScript來表示一個DOM節點，則需要記錄它的節點類型、屬性、子節點：
element.js

function Element (tagName, props, children) {
  this.tagName = tagName
  this.props = props
  this.children = children
}

module.exports = function (tagName, props, children) {
  return new Element(tagName, props, children)
}

上面的DOM結構可以表示為：

var el = require("./element")

var ul = el("ul", {id: "list"}, [
  el("li", {class: "item"}, ["Item 1"]),
  el("li", {class: "item"}, ["Item 2"]),
  el("li", {class: "item"}, ["Item 3"])
])

現在ul只是一個JavaScript對象表示的DOM結構，頁面上并沒有這個結構。可以根據這個ul構建真正的

：

Element.prototype.render = function () {
  var el = document.createElement(this.tagName) // 根據tagName構建
  var props = this.props

  for (var propName in props) { // 設置節點的DOM屬性
    var propValue = props[propName]
    el.setAttribute(propName, propValue)
  }

  var children = this.children || []

  children.forEach(function (child) {
    var childEl = (child instanceof Element)
      ? child.render() // 如果子節點也是虛擬DOM，遞歸構建DOM節點
      : document.createTextNode(child) // 如果字符串，只構建文本節點
    el.appendChild(childEl)
  })

  return el
}

render方法會根據tagName構建一個真正的DOM節點，然后設置這個節點的屬性，最后遞歸地把自己的子節點也構建起來。所以需要：

var ulRoot = ul.render()
document.body.appendChild(ulRoot)

上面的ulRoot是真正的DOM節點，把它塞進文檔中，這樣body里面就有了真正的

的DOM結構：

  
Item 1
  
Item 2
  
Item 3

步驟二：比較兩棵虛擬DOM樹的差異

比較兩棵DOM樹的差異是Virtual DOM算法最核心的部分，就是diff算法。兩棵樹的完全diff算法是一個時間復雜度為O(n^3)的問題。但在前端中，很少會跨越層級地移動DOM元素。所以Virtual DOM只會對同一層級的元素進行對比：

上面的div只會和同一層級的div對比，第二層級的只會跟第二層級對比。這樣算法復雜度就可以達到O(n)。

a.深度優先遍歷，記錄差異
在實際的代碼中，會對新舊兩棵樹進行一個深度優先的遍歷，這樣每個節點都會有一個唯一的標記：

在深度優先遍歷的時候，每遍歷到一個節點就把該節點和新的樹進行對比。如果有差異的話就記錄到一個對象里面。

// diff 函數，對比兩棵樹
function diff (oldTree, newTree) {
  var index = 0 // 當前節點的標志
  var patches = {} // 用來記錄每個節點差異的對象
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// 對兩棵樹進行深度優先遍歷
function dfsWalk (oldNode, newNode, index, patches) {
  // 對比oldNode和newNode的不同，記錄下來
  patches[index] = [...]

  diffChildren(oldNode.children, newNode.children, index, patches)
}

// 遍歷子節點
function diffChildren (oldChildren, newChildren, index, patches) {
  var leftNode = null
  var currentNodeIndex = index
  oldChildren.forEach(function (child, i) {
    var newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count) // 計算節點的標識
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍歷子節點
    leftNode = child
  })
}

例如，上面的div和新的div有差異，當前的標記是0，那么：

patches[0] = [{difference}, {difference}, ...] // 用數組存儲新舊節點的不同

同理p是patches[1]，ul是patches[3]，以此類推

b.差異類型

對DOM操作會有的差異：

替換掉原來的節點，例如把上面的div換成了section

移動、刪除、新增子節點，例如上面的div的子節點，把p和ul順序互換

修改了節點的屬性

對于文本節點，文本內容可能會改變。例如修改上面的文本節點2內容為Virtual DOM2

所以定義了幾種差異類型：

var REPLACE = 0
var REORDER = 1
var PROPS = 2
var TEXT = 3

對于節點的替換，判斷新舊節點的tagName和是不是一樣，如果不一樣就替換掉。如div換成section，記錄如下：

patches[0] = [{
  type: REPALCE,
  node: newNode // el("section", props, children)
}]

如果給div新增了屬性id為container，記錄如下：

patches[0] = [{
  type: REPALCE,
  node: newNode // el("section", props, children)
}, {
  type: PROPS,
  props: {
    id: "container"
  }
}]

如果修改文本節點，如上面的文本節點2，記錄如下：

patches[2] = [{
  type: TEXT,
  content: "Virtual DOM2"
}]

c.列表對比算法

上面如果把div中的子節點重新排序，看如p，ul，div的順序換成了div，p，ul。按照同層進行順序對比的話，它們都會被替換掉，這樣DOM開銷非常大。而實際上只需要通過節點移動就可以的了。
假設現在可以英文字母唯一得標志每一個子節點：
舊的節點順序：
a b c d e f g h i
現在對節點進行刪除、插入、移動的操作。新增j節點，刪除e節點，移動h節點：
新的節點順序：
a b c h d f g i j
現在知道了新舊的順序，求最小的插入、刪除操作（移動可以看成是刪除和插入操作的結合）。這個問題抽象出來其實是字符串的最小編輯距離問題(Edition Distance)，最常見的算法是Levenshtein Distance，
通過動態規劃求解，時間復雜度為O(M*N)。而我們只需要優化一些常見的移動操作，犧牲一定的DOM操作，讓算法時間復雜度達到線性的O((max(M,N)))。
獲取某個父節點的子節點的操作，就可以記錄如下：

patches[0] = [{
  type: REORDER,
  moves: [{remove or insert}, {remove or insert}, ...]
}]

由于tagName是可以重復的，所以不能用這個來進行對比。需要給子節點加上一盒唯一標識key，列表對比的時候，使用key進行對比，這樣就能復用舊的DOM樹上的節點。
通過深度優先遍歷兩棵樹，每層節點進行對比，記錄下每個節點的差異。完整的diff算法訪問：https://github.com/livoras/si...

步驟三：把差異應用到真正的DOM樹上
因為步驟一所構建的JavaScript對象樹和render出來的真正的DOM樹的信息、結構是一樣的。所以可以對那棵DOM樹也進行深度優先遍歷，遍歷的時候從步驟二生成的patches對象中找出當前遍歷的節點差異，然后進行DOM操作。

function patch (node, patches) {
  var walker = {index: 0}
  dfsWalk(node, walker, patches)
}

function dfsWalk (node, walker, patches) {
  var currentPatches = patches[walker.index] // 從patches拿出當前節點的差異

  var len = node.childNodes
    ? node.childNodes.length
    : 0
  for (var i = 0; i < len; i++) { // 深度遍歷子節點
    var child = node.childNodes[i]
    walker.index++
    dfsWalk(child, walker, patches)
  }

  if (currentPatches) {
    applyPatches(node, currentPatches) // 對當前節點進行DOM操作
  }
}

applyPatches，根據不同類型的差異對當前節點進行 DOM 操作：

function applyPatches (node, currentPatches) {
  currentPatches.forEach(function (currentPatch) {
    switch (currentPatch.type) {
      case REPLACE:
        node.parentNode.replaceChild(currentPatch.node.render(), node)
        break
      case REORDER:
        reorderChildren(node, currentPatch.moves)
        break
      case PROPS:
        setProps(node, currentPatch.props)
        break
      case TEXT:
        node.textContent = currentPatch.content
        break
      default:
        throw new Error("Unknown patch type " + currentPatch.type)
    }
  })
}

完整patch代碼訪問：https://github.com/livoras/si...