virtual Dom的diff算法

diff 在virtual dom上应用，在传统的diff算法上，增加以下几个策略

1. web UI中DOM节点跨层级操作特别少，可以忽略不计
2. 相同类的两个组件可以生成相似的，tree，不同类的组件生成不同的tree
3. 同层级的一组子节点，他们可以通过唯一的ID进行区分。

diff算法基于以上三种策略，分别有了treediff、Component diff以及element diff

• tree diff
  基于策略一，对树进行同层级比较，两颗树只比较同一层级的节点进行比较，当发现节点不存在，直接删除，而当有不同层级的节点发生改变时，也只有创建和删除，比如A下面有B、C 两级，然后把B移动到C下面，则发生的顺序是这样的：在C下创建B，在A下删除B，所以这种不是我们想象中直接移动B到C，所以要尽量减少跨层级的节点操作

• Component diff
  如果是相同类型的组件，则按照原策略进行比较，开发人员也可以通过shouldComponentUpdate来优化，是否要更新，如果是不同的类型组件，则直接删除就组件，然后创建新的组件

• element diff
  当节点处于同一层级时，diff有三种节点操作：插入（旧的没有，新的有）、移动（新旧都有）和删除（新的有，旧的没有）
  这里我们要注意移动这种情况，比如 旧：A 　Ｂ　Ｃ　Ｄ，新：B A D Ｃ，则是操作是删除A，新建B A Ｃ Ｄ　，创建A D Ｃ，所以这里react提供一个KEY，可以做优化，如果添加key，比较的时候可以通过Key来区分，就可以识别出来原来A也在旧tree中，只需要做移动操作即可。
  下面同样以 旧：A 　Ｂ　Ｃ　Ｄ，新：B A D Ｃ为例，来详细说明一下，说明两个变量lastIndex（初始值：0,一直在更新，表示访问过的节点在旧集合中最右的位置），MountIndex（组件在旧集合中位置），lastIndex = Math.max（lastIndex，MountIndex）；当lastIndex > moutIndex时候才移动
  首先取到新集合B，然后通过key在旧集合中寻找，发现有存在B，此时mountIndex = 1 > lastIndex，所以不移动，然后lastIndex更新为1。
  然后从新集合去A，A的mountIndex = 0 < lastIndex,所以移动A，lastIndex还是1，
  之后从新集合中取D，D的moutIndex = 3 > lastIndex 1，所以不移动，lastIndex更新为3，
  最后从新集合中取C，C的mountIndex = 2 < lastIndex ,所以要移动，移动C，完成。
  以上主要是对已存在的元素节点不同位置移动，如果新集合中存在新的元素节点，则是直接插入，然后lastIndex保持不变。

以上就是整个diff算法的运行过程，当然diff算法还存在不足之处，比如旧： A B C D ，新： D A B C ,然后就出现D不变，ABC分别移动到后面去，所以在开发过程中要尽量减少从队尾直接移动到列表首部的操作。

经过diff算法之后，我们知道哪些节点、属性需要删除、更新和创建，那么到了最后一步就是 Patch，就是把diff后需要更新的内容，更新到真实的节点上，通过react Patch方法来处理，方法非常简单： 通过遍历差异队列，通过更新类型进行相应的操作，包括新节点的插入，已有节点的移动和移除等。

至此整个diff算法讲述完毕