为什么二叉查找树不行？

不是平衡的，有可能会退化为链表，查询效率慢。

为什么平衡二叉树不行？

平衡二叉树左右子树的树高不能超过1，和红黑树相比它是严格的平衡二叉树，平衡条件必须满足，不管是执行插入还是删除，不满足条件就要发生旋转来保持平衡。

• 旋转很消耗性能

• 每个节点存储的数据太小，查询一个节点对于磁盘来说就是一次IO，很消耗性能。

  红黑树为什么不行？

• 太高了，与平衡二叉树相比，红黑树的平衡性降低了，高度更高，树的高度越高，增删改查需要的磁盘IO就越多，会严重影响性能。

  多路平衡查找树(B-Tree)

  

二叉树不行，是由于每个节点存储的数据量太小，而分叉太少导致太深，多路平衡二叉树就弥补了不足。
二叉树是一种特殊的多路平衡查找树，二路的；图中为三路的。

一次磁盘IO可以查询4k的数据，我们一个节点可以放4k的数据，这样正好一次读取就可以把整个节点的数据都读出来。
**

为什么是B+Tree

特点：

• 叶子节点会存储非叶子节点的数据
• 非叶子节点不存储数据的关键信息，只保存关键字和叶子节点的引用
• 关键字对应的数据存储在叶子节点中
• 叶子节点是顺序排列的，相邻节点有顺序引用关系(双向链表)

放弃把关键字的数据放在叶子节点，肯定能让非叶子节点存储更多的关键字，这样就能更好的降低深度(因为能保存的数据多分的路，也就意味着相同的数据需要的层次就减少)

由于叶子节点包括了关键字的数据，并且是有序的，因此不管是在排序还是在范围查找都是很优秀的(秀儿~~）

选B+树的原因:

• B+Tree是多路平衡查找树，拥有B-Tree的优势
• B+Tree的扫库扫表能力强
• B+树磁盘读写能力强(磁盘每次读可以读4k的数据，MySQL使用B+Tree的时候，叶子节点的数据大小也为4k)
• B+Tree排序能力强(叶子节点是有序的，并且相邻的叶子节点有顺序引用关系)
• 查询稳定，因为数据都存储在了叶子节点中，每次都需要查到叶子节点才可以