小白晋级大师第1篇文章，开始写一些有深度的文章了
先推荐一个数据结构可视化工具网站，用于B+树可视化查看
面试技术岗的时候，面试官问你：
mysql索引底层用的是B+树结构，为什么不用B树、二叉树、红黑树呢？
这里其实就是比较各种数据结构的优劣点，最后说明为什么要用B+树结构；
假设数据查询场景：现在有100W的数据存储，查询其中的一条，应该用哪种存储结构呢？
二叉查找树
二叉查找树即有序二叉树，满足二叉树的性质，具有下面特点：
- 任意节点左子树不为空时，左子树值小于根节点值
- 右子树不为空时，右子树值大于根节点值；
依次存入数据，如果数据是递增的，则原二叉树退化为链表结构，如图
这种情况下，查询的时间复杂度就是O(n)了
AVL树
AVL树即平衡二叉查找树，通过平衡因子差值判断是否平衡，再用旋转来实现树的平衡。左右子树的树高差不超过1。在执行插入删除操作时，对不满足条件的子树，通过旋转保持平衡。性能开销主要在旋转操作上，由此可以知道AVL树适合查询多，插入删除少的场景
如图，我创建了一棵AVL树，感兴趣的可以在网站上看一下插入过程和旋转调整平衡的过程。
AVL树需要维持树的平衡，而维护这种平衡的开销要大于获得的收益，实际应用中不多
红黑树
红黑树是一种二叉查找树，每个节点新增一个存储位标记是red或black，通过任何一条从根节点到叶子节点路径上，各个节点着色方式的限制，确保没有一条路径比其他路径长2倍，红黑树性质：
- 根节点是黑色，每个节点非红即黑；
- 叶子节点都是黑色
- 如果一个节点是红色，那它的子节点都是黑色
- 任意节点到叶子节点的路径都包含相同数目的黑色节点
如图是红黑树的可视化：
AVL树和红黑树一样，随着记录数的增加，树的高度会不断增加，查询次数也会增加。
文章开头我们说的要查询100w条数据中的一条，就需要20次搜索，搜索效率不高，查询次数分析如下
$$ 2^{20} = 1048576 $$
B-树
即B树，和红黑树相比，B树的树高远远小于红黑树的高度。B树是为了和磁盘交互而设计的平衡多路查找树，操作效率有磁盘的访问次数决定，树高越小，磁盘I/O时间越短。
B树性质：
- 非叶子节点上最多有M个子节点，且M>2；
- 根节点的子节点数目为[2, M]；
- 每个节点存放至少M/2-1，至多M-1个关键字
- 非叶子节点关键字数目=指向子节点的指针个数-1；
- 所有叶子节点位于同一层
对比红黑树可以发现，每个节点上可以存储更多的数据，且树高固定，数据插入之后横向扩展。即每一次查询只需要搜索3次就行。搜索效率大大提高了。接着我们再来看看B+树
B+树
说一下B+树的性质：
- 非叶子节点的子树指针 和 关键字 个数一样；
- 非叶子节点的子树指针，指向闭区间[k[i], k[i+1]]，即B树不允许关键字重复，B+树允许
- 为所有叶子节点增加一个链指针；
- 非叶子节点作为索引，叶子节点才存储关键字
- 所有关键字存储在叶子节点
B+树比起B树的优点有：
- 只在叶子节点存储数据，16k的内存可以存下更多数据，降低树高
- 冗余索引，方便查找；
- B+树叶子节点增加了双向链表，方便范围查询；
于是，回到开头的问题，100W的数据，B+树只需要3次或4次I/O查询就能定位到了，且相比较B树，B+树更适合复杂的查询场景，如范围查询。
