传统diff
计算两棵树形结构差异并进行转换，传统diff算法的做法：循环递归每一个节点
比如左侧树a节点依次进行对比，a->e、a->d、a->b、a->c、a->a，左侧其他节点也是，算法复杂度能达到O(n^2), 查完差异后还要计算最小转换方式，最终达到的算法复杂度是O(n^3)
React dom diff
React diff算法是深度优先遍历的比较算法，用于当状态变更时，比较新旧虚拟dom树，局部更新变化的节点，提高渲染效率。
为了优化react diff算法的复杂度，react根据经验提出三点前提：
- 跨层级的移动dom场景较少，可忽略不计,所以react实现的是diff的同层级比较
- 两种不同类型的元素会产生不同的树
- 开发者可以通过key属性来告知哪些元素可以在不同的渲染下保持不变。
依据这三点，有三种比较策略
- 树比较，tree diff 不同的元素类型的树直接替换，不再遍历子节点
- component diff：可以通过key来告知哪些组件需要刷新
- element diff: 处理文本替换
优点：降低diff复杂度，由原来O(n^3)降低到O(n) 缺点：
Diff算法
具体流程：
- 真实dom与虚拟dom之间存在一个映射关系，这个映射关系依靠初始化是的JSX建立完成
- 当虚拟dom发生变化后，就会根据差距计算生成patch，这个patch是一个结构化数据，内容包含了增加、更新、移除等；
- 最后再根据patch去更新真实的dom，反馈到用户的界面上
更新时机
触发更新、进行差异对比的时机。更新发生在setState、Hooks等调用操作后。
遍历算法
diff 算法采用了深度优先遍历算法。因为广度优先遍历可能会导致组件的生命周期时序错乱，而深度优先遍历算法就可以解决这个问题
优化策略
React分别从树、组件及元素三个层面进行复杂度优化
- 树比对，忽略节点跨层级操作的场景。树比对的手法是非常暴力的，两棵树只对同一层次的节点进行比较，如果节点已经不存在了，该节点及其子节点会被完全删掉，不会用于进一步对比
- 如果组件的类型一致，则默认为相似的树结构，否则默认为不同的树结构
- 同一层级的子节点，可以通过标记key的方式进行对比
React 16引入的Fiber设计，Fiber机制下节点与树分别采用FiberNode与FiberTree进行重构。FiberNode采用双链表的结构，可以直接找到兄弟节点与子节点，使得整个更新过程可以暂停恢复。
Fiber机制下，整个更新过程由current与workInProgress两株树双缓冲完成，当workInProgress更新完成后，通过修改current相关指针指向的节点，直接抛弃老树
尽量减少将最后一个节点移动到列表首部的操作
vue dom diff
与react diff大同小异，比较只会在同层级进行，不会跨层级比较 不同的是，vue是两端到中间的对比，react是从左到右依次进行对对比。比方说把最后一个节点移到第一个，react会依次移动前三个节点到对应位置，而vue会在首尾对比时，只移动最后一个节点到第一位。
扩展
key的作用
dom diff的时候比较新旧虚拟dom。
如果在旧虚拟dom找到新虚拟dom相同的key: 如果内容不变，直接使用之前的真实dom；若改变，生成新的真实dom，随后替换页面之前的真实dom。
如果在旧虚拟dom中没有找到新虚拟dom相同的key，就会生成新的真实dom渲染到页面。
为什么key最好不要用index
逆序添加、逆序删除等破坏顺序的操作，会产生虚拟dom和真实dom中key对不上的问题，产生很多没有必要的真实dom更新。
不加key
采用遍历的方式对比新旧节点