patching算法

虚拟DOM最核心的部分就是patch，它可以将vnode渲染成真实的DOM。
patch也可以叫做patching算法，通过它渲染真实DOM时，并不是暴力覆盖原有DOM，而是比对新旧两个vnode之间有什么不同，然后根据比对结果找出实际需要更新的节点进行更新，其实际作用就是在现有DOM上进行修改来实现更新视图的目的。
之所以要这么做，是因为DOM操作的执行速度远不如JavaScript的运算速度快，因此将大量的DOM操作搬运到js中，使用patching算法来计算出真正需要更新的节点，可以极大程度上减少DOM操作，从而提升性能。实际上是使用JavaScript的运算成本来替换DOM操作的执行成本，js的运算速度比DOM快的多。

patch介绍

patch不是暴力替换节点，而是在现有DOM上进行修改来达到渲染视图的目的。对现有DOM修改需要做三件事：1.创建新增节点。2.删除已经废弃的节点。3.修改需要更新的节点。

新增节点

只有那些因为状态改变而新增的节点在DOM中并不存在时，我们才需要创建一个节点并插入到DOM中。（通常发生在首次渲染）当oldVnode不存在时，直接使用vnode来创建元素渲染视图。
当vnode和oldVnode完全不是同一个节点时，需要使用vnode生成真实DOM并将其插入到视图当中。

删除节点

当一个节点只在oldVnode中存在时，需要把它从DOM中删除，渲染视图以vnode为标准，因此所有vnode中不存在的节点都属于被废弃的节点，需要删除掉。
当oldVnode和vnode完全不是同一个节点时，需要进行替换，替换过程是先将新创建的DOM节点插入到旧节点旁边然后再将旧节点删除。

更新节点

当新旧节点是相同的节点时，需要对两个节点进行细致的比对，然后对oldVnode在视图中所对应真实DOM节点进行更新，例如一个文本节点的文本内容不一样时，只需要把节点中的文本进行更新即可。

小结

创建节点

只有三种类型的节点会被创建并插入到DOM中：元素节点、注释节点和文本节点。
判断vnode是否是元素节点，只需要判断是否具有tag属性即可，调用当前环境下的createElement方法来创建真实的DOM元素，创建后接下来就是要把它插入到指定的父节点中。调用当前环境下的appendchild将一个元素插入到某个指定的父节点中，如果这个父节点已经被渲染到视图，那么把元素插入到它的下面会自动将元素插入到视图，元素节点通常会有子节点（children），所以当一个元素节点创建后，还需要将它的子节点创建出来插入到这个刚创建的节点下面，创建子节点的过程其实是一种递归。vnode里的children属性保存了当前节点的所有子虚拟节点，只需要将children属性循环一遍，将每个子节点都执行一遍创建的逻辑，即可完成。
如果不存在tag属性，isComment属性为true时，则该节点是一个注释节点，如果为false，则是一个文本节点。当要创建文本节点时，调用当前环境下的createTextNode方法创建真实的文本节点，如果是注释节点，则调用当前环境下的createComment来创建真实的注释节点并将其插入到指定的父节点中。

删除节点

function removeVnodes(vnodes,startIdx,endIdx){
    for(;startIdx<=endIdx;++startIdx){
        const ch = vnodes[startIdx]
        if(isDef(ch)){
            removeNode(ch.elm)    
        }
    }
}

这段代码实现的功能是删除vnodes数组中startIdx到endIdx位置的内容
removeNode用于删除视图中的某个单个节点，而removeVnodes用于删除一组指定的节点

     const nodeOps = {
        removeChild(node,child){
            node.removeChild(child)
        }
    }
    function removeNode(el){
        const parent = nodeOps.parentNode(el)
        if(isDef(parent)){
            nodeOps.removeChild(parent,el)
        }
    }

为什么要使用nodeOps对removeChild进行了封装，这里其实涉及了跨平台渲染的问题，我们写的Vue.js组件可以分别在IOS和Android环境中进行原生渲染。

更新节点

静态节点

在更新节点之前，需要判断新旧两个虚拟节点是否是静态节点，如果是，就可以不需要进行更新操作，直接跳过更新节点的过程。
静态节点指的是那些一旦渲染到页面上之后，无论状态发生了什么变化，都不会发生任何变化的节点。例如一个p元素节点里面包含一段文本

新虚拟节点有文本属性

当新旧两个虚拟节点不是静态节点但是拥有不同的属性时，需要以新虚拟节点为准来个更新视图，根据新节点是否有text属性，更新节点分为两种情况。如果有text属性，则直接调用setTextContent方法（浏览器中是node.textContent）将视图中的DOM节点中的内容文字改为新虚拟节点的text属性的文字。

新虚拟节点无文本属性

如果新创建的虚拟节点没有text属性，那么它就是一个元素节点，元素节点通常因为是否存在children分为两种情况：1.有children的情况，看旧虚拟节点是否也有children，如果旧节点也有，要进行一个详细的比对，更新children可能会移动某个子节点的位置，也可能会删除或新增某个子节点。如果旧虚拟节点没有children时，则旧虚拟节点要么是个空标签，要么是个有文本的文本节点，如果是文本节点，则清空文本让它变成空标签，然后根据新的虚拟节点的children循环创建真实DOM将其插入到视图中的DOM节点下面。2.无children的情况，说明新创建的节点什么都没有是一个空节点，此时如果旧虚假节点有子节点就删除子节点，有文本就删除文本，最后达到视图是空标签的效果。

更新子节点

更新子节点大概分为四种情况：更新、新增、删除、移动

更新策略

1.创建子节点

新旧两个子节点列表是通过循环进行比对的，所以创建节点的操作是在循环体内执行的，其具体实现是在oldChildren（旧子节点列表）中寻找本次循环所指向的新子节点。如果在oldChidren中没有找到本次循环所指向的新子节点相同的节点，就说明这个是新增的节点，需要执行创建的操作，然后将新创建的节点插入到oldChildren中所有未处理节点之前。插在已处理之后会存在位置不对的情况。

2.更新子节点

当同一个节点同时存在于newChildren和oldChildren中需要执行更新操作。
如果两个节点是同一个节点并且位置相同时，这种情况下只需要进行更新节点的操作
如果oldChildren和本次循环所指向的新子节点的位置不一样时，除了对真实DOM进行更新操作外，还需要对真实DOM节点进行移动的操作。

3.移动子节点

通常时新旧节点是同一个节点，但是位置不同时需要进行移动。
使用node.insertBefore()可以将一个已有节点移动到一个指定的位置。
得知新虚拟节点的位置，从左到右循环newChildren这个列表，每循环一个节点，就去oldChildren中寻找与这个节点相同的节点进行处理，当前循环到的这个节点的左边都是处理过的，这个节点的位置是所有未处理节点的第一个节点，只把需要移动的节点移动到所有未处理节点的最前面，就可以实现目的。

4.删除子节点

当newChildren中所有的节点都被循环了一遍后，也就是循环结束后，如果oldChildren还存在没有被处理的节点，这些节点就是需要被删除的节点

优化策略

通常来说并不是所有的子节点位置都会发生移动，针对这些位置不变或者说位置可以预测地节点，不需要循环来查找，因为有个更快捷的方式。
存在一个场景，当只是修改了列表中某个数据的内容，没有新增和删除等，所以新老children中的所有节点的位置都是相同的，这时节点的位置是可以预测的，不需要进行循环查找。
只需要尝试使用相同位置的两个节点来比对是否是同一个节点。如果恰巧是同一个节点，就可以进入更新节点的操作，如果不是，再用循环的方式来查找。这样可以很大程度避免循环oldChildren来查找节点，从而使执行速度得到很大的提升。
有四种查找方式：新前和旧前/新后和旧后/新后和旧前/新前和旧后
新前：newChildren中所有未处理的第一个节点
新后：newChildren中所有未处理的最后一个节点
旧前：oldChildren中所有未处理的第一个节点
旧后：oldChildren中所有未处理的最后一个节点

新前和旧前/新后和旧后 ：如果是相同的节点，则不需要移动直接进行更新即可
新前和旧后/新后和旧前 : 如果是相同的节点，在更新完成后还需要移动节点

如果前面这四种查找方式都没查找到相同的节点，则使用循环。因为大部分情况下都可以找到相同的节点，所以节省了许多次循环操作。

哪些结点是未处理过的

4个下标：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx.
在循环体内，每处理一个节点，就将下标向指定的方向移动一个位置，通常情况下是对新旧两个节点进行更新操作，就相当于一次性处理两个节点，将新旧两个节点的下标都向指定方向移动一个位置。
开始位置所表示的节点被处理后，就向后移动一个位置；结束位置的节点被处理后，就向前移动一个位置。
当开始位置的下标大于结束位置的下标，说明所有的节点都遍历过了。

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){
    //做点什么
}

旧的先循环完毕，说明新的里面的有新增的节点，直接添加进去即可不需要再进行比对，如果新的先循环完毕，说明旧的里面的剩下的节点是需要删除的，直接删除就可以不需要再进行比对。