共计 1339 个字符，预计需要花费 4 分钟才能阅读完成。
小白升级巨匠第 1 篇文章，开始写一些有深度的文章了
先举荐一个数据结构可视化工具网站，用于 B + 树可视化查看
Data Structure Visualizations
面试技术岗的时候，面试官问你：
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+ 树更适宜简单的查问场景，如范畴查问。