Virtual DOM

为什么要应用Virtual DOM？

  • 将失去的变更告诉生成新的Virtual DOM树。将新的和旧的进行diff patch操作，缩小了间接通过DOM API去增删改查DOM的操作，进步开发效率。
  • All problem in computer science can be resolved by another level of indirection 软件开发中的所有问题都能够通过减少一层形象来解决。（关注点拆散）

Virtual DOM是分层思维的一种体现

  • 框架将DOM形象成Virtual DOM后能够利用在各个终端

Diff策略

1、 按tree层级diff（level by level）

  • 在Web UI中很少会呈现DOM层级会因为交互而产生更新
  • 在新旧节点之间按层级进行diff

2、 按类型进行diff

  • 不同类型的节点之间往往差别很大，为了晋升效率，只会对雷同类型节点进行diff
  • 不同类型会间接创立新类型节点，替换旧类型节点
  • 下图中，由上一层图形变为下一层图形。同层比拟，第二列五角星和三角形不同，尽管子节点的两个五角星雷同，然而也会间接将三个五角星间接销毁，替换为新的节点。


3、 列表Diff

  • 给列表元素设置key，能够晋升效率

Diff过程

  • 参考文章：详解Vue的Diff算法
  updateChildren(parentElm, oldCh, newCh) {    let oldStartIdx = 0, newStartIdx = 0    let oldEndIdx = oldCh.length - 1    let oldStartVnode = oldCh[0]    let oldEndVnode = oldCh[oldEndIdx]    let newEndIdx = newCh.length - 1    let newStartVnode = newCh[0]    let newEndVnode = newCh[newEndIdx]    let oldKeyToIdx    let idxInOld    let elmToMove    let before    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {      if (oldStartVnode == null) {   // 对于vnode.key的比拟，会把oldVnode = null        oldStartVnode = oldCh[++oldStartIdx]      } else if (oldEndVnode == null) {        oldEndVnode = oldCh[--oldEndIdx]      } else if (newStartVnode == null) {        newStartVnode = newCh[++newStartIdx]      } else if (newEndVnode == null) {        newEndVnode = newCh[--newEndIdx]      } else if (sameVnode(oldStartVnode, newStartVnode)) {        patchVnode(oldStartVnode, newStartVnode)        oldStartVnode = oldCh[++oldStartIdx]        newStartVnode = newCh[++newStartIdx]      } else if (sameVnode(oldEndVnode, newEndVnode)) {        patchVnode(oldEndVnode, newEndVnode)        oldEndVnode = oldCh[--oldEndIdx]        newEndVnode = newCh[--newEndIdx]      } else if (sameVnode(oldStartVnode, newEndVnode)) {        patchVnode(oldStartVnode, newEndVnode)        api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))        oldStartVnode = oldCh[++oldStartIdx]        newEndVnode = newCh[--newEndIdx]      } else if (sameVnode(oldEndVnode, newStartVnode)) {        patchVnode(oldEndVnode, newStartVnode)        api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)        oldEndVnode = oldCh[--oldEndIdx]        newStartVnode = newCh[++newStartIdx]      } else {        // 应用key时的比拟        if (oldKeyToIdx === undefined) {          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有key生成index表        }        idxInOld = oldKeyToIdx[newStartVnode.key]        if (!idxInOld) {          api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)          newStartVnode = newCh[++newStartIdx]        }        else {          elmToMove = oldCh[idxInOld]          if (elmToMove.sel !== newStartVnode.sel) {            api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)          } else {            patchVnode(elmToMove, newStartVnode)            oldCh[idxInOld] = null            api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)          }          newStartVnode = newCh[++newStartIdx]        }      }    }    if (oldStartIdx > oldEndIdx) {      before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)    } else if (newStartIdx > newEndIdx) {      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)    }  }
  • updateChildren代码剖析
  1. 循环成立条件：OldStart小于等于OldEnd && NewStart小于等于NewEnd时
  2. 判断VNode是否为null，是指针指向下一个节点

  3. 不是则依照 OS和NS（S|）、OE和NE（E|）、 OS和NE（\ ）、OE和NS（/）的程序进行比拟判断
    若雷同

     S| 节点地位不变，指针+1 E| 节点地位不变，指针-1 \  OldStart挪动到OldEnd之后，OldStart +1，  NewEnd -1 /  OldEnd挪动到OldStart之前，NewStart +1， OldEnd -1

    若不同，依据key生成OldStart和OldEnd之间的index表，查找元素是否在OldStart和OldEnd之间

     若有，间接挪动到OldStart前 若没有，创立后，挪动到OldStart前
  4. 判断如果NewStart > NewEnd，阐明新节点曾经遍历完，删除OldStart和OldEnd之间的DOM
    如果OldStart > OldEnd，阐明旧节点曾经遍历完，将多的新节点依据index增加到DOM中去
  • 例：如图，灰色示意Virtual DOM 深色示意实在的DOM

  • 四个指针

    • OldStartIdx 旧开始节点
    • OldEndIdx和 旧完结节点
    • NewStartIdx 新开始节点
    • NewEndIdx 新完结节点
  1. 判断OldStartIdx和NewStartIdx是否雷同。1和1雷同，两个Start指针都往右挪动一位（+1）
  2. 持续比拟OldStartIdx和NewStartIdx是否雷同。2和5不同，改为比拟OldEndIdx和NewEndIdx
  3. 6和6雷同，两个End指针都往左挪动一位（-1）。5和2不统一，改为比拟OldStartIdx和NewStartIdx
  4. 2和5不同，改为比拟OldEndIdx和NewEndIdx，也不同。改为比拟OldStartIdx和NewEndIdx（方向）。2和2雷同，将OldStartIdx对应的实在DOM挪动到OldEndIdx之后，同时OldStartIdx右移一位，NewEndIdx左移一位。
  5. 持续比拟Start，不同，比拟End，也不同。比拟OldStart和NewEnd，不同。比拟OldEnd和NewStart（/方向），雷同。挪动OldEnd对应的实在DOM到OldStart之前。同时OldEnd左移，NewStart右移。
  6. 持续循环，Start| End| / 四个方向，都不同。依据key生成OldStart和OldEnd之间的index表，查找7是否在OldStart和OldEnd之间。如果找到，间接挪到OldStart之前。找不到，则阐明是新节点，将7由VirtualDOM生成实在DOM后挪到OldStart之前。
  7. NewEnd左移，此时NewEnd小于NewStart，完结循环
  8. 删除OldStart和OldEnd之间的局部
  9. 新Virtual DOM已存在，DOM节点也已生成，销毁旧Virtual DOM列表
  10. 设置key之后，就不要遍历了。算法复杂度为O(n)，否则最坏状况为$O(n^2)$
  • vue2+中并没有残缺的patch过程，节点操作是在diff操作过程中同时进行的，晋升了增删改查DOM节点时的效率