迎面走来了你的面试官，身穿格子衫，挺着啤酒肚，发际线重大后移的中年男子。
手拿泡着枸杞的保温杯，胳膊夹着 MacBook，MacBook 上还贴着公司标语：“我爱加班”。
面试开始，直入正题。
面试官： 你晓得 MySQL 索引底层数据结构为啥用 B + 树？而不必 B 树、红黑树或者一般二叉树？
我： 这事谁晓得作者咋想的？他可能是用 B + 树习惯了，个人爱好吧。
面试官： 你倒是挺看得开。明天的面试就先到这吧，前面有音讯会被动分割你。
前面还可能有音讯吗？你们啥时候被动分割过我？
实话实说的被拒，八股文背得溜反而被录取。
好吧，等我看看一灯怎么总结的 MySQL 的八股文。
我： 要晓得 MySQL 索引底层数据结构为啥用 B + 树，先要理解一下什么样的数据结构更适宜建索引。
为了保证数据安全性，个别都是把数据存储在磁盘外面。当咱们须要查问数据的时候，须要读取磁盘，就产生了磁盘 IO，相比拟内存操作，磁盘 IO 读取速度是十分慢的。
因为所需数据可能在磁盘并不是间断的，一次数据查问就须要屡次磁盘 IO，所以就须要咱们设计的索引数据结构尽可能的缩小磁盘 IO 次数。
再理解一下这几种二叉树的个性，以及优缺点，就晓得哪种数据结构更适宜建索引。
什么是二叉搜寻树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也别离为二叉查找树；
二叉搜寻树查找数据的工夫复杂度是 O(logN)，如图所示，最多查找 3 次就能够查到所需数据。
现实很饱满，事实很骨感。极其状况下，二叉查找树可能进化成线性链表。
链表的查找时间复杂度是 O(N)，这时候最多须要 7 次能力查到所需数据。
该怎么办呢？于是咱们就想到了给二叉树加一些限度条件，均衡一下左右子树，而后就引申出了很多均衡树：均衡二叉查找树、红黑树、B 树、B+ 树。咱们别离说一下这几种树的优缺点，看哪种树最适宜做索引。
什么是红黑树？
- 结点是红色或彩色
- 根结点是彩色
- 所有叶子都是彩色（叶子是 NIL 结点）
- 每个红色结点的两个子结点都是彩色（从每个叶子到根的所有门路上不能有两个间断的红色结点）
- 从任一结点到其每个叶子的所有门路都蕴含雷同数目的彩色结点
看蒙了没有？
这么多简单的规定，就是为了保障从根节点到叶子节点的最长门路不超过最短门路的 2 倍。
当插入节点或者删除节点的时候，为了满足红黑树规定，可能须要变色和旋转，这是一个简单且耗时的过程。
红黑树的长处：
限度了左右子树的树高，不会相差过大。
毛病：
规定简单，个别人想要弄懂这玩意儿，就曾经很吃力了，更别说应用了。
什么是 B 树？
咱们晓得，树的高度越高，查找次数越多，也就是磁盘 IO 次数越多，耗时越长，
咱们能不能想方法升高树的高度，把二叉树变成 N 叉树？于是 B 树就来了。
对于一个 m 阶的 B 树：
- 根节点至多有 2 个子节点
- 每个两头节点都蕴含 k - 1 个元素和 k 个子节点，其中 m/2 <= k <= m
- 每个叶子节点都蕴含 k - 1 个元素，其中 m/2 <= k <= m
- 两头节点的元素依照升序排列
- 所有的叶子结点都位于同一层
根节点（8）有两个子节点，左子节点（3 5）和右子节点（11 15）。
左子节点（3 5）中有 2 个元素和 3 个子节点。
元素是 3 和 5，依照升序排列。
子节点是（1 2）、（4）、（6 7），
而（1 2）中元素小于 3，（4）中的元素在 3 和 5 两头，（6 7）的元素大于 5，合乎 B 树特色。
B 树这样的设计有哪些长处呢？
高度更低，每个节点含有多个元素，查找的时候一次能够把一个节点中的所有元素加载到内存中作比拟，两种改良都大大减少了磁盘 IO 次数。
什么是 B + 树？
相比拟 B 树，B+ 树又做了如下约定：
- 有 k 个子节点的两头节点就有 k 个元素（B 树中是 k - 1 个元素），也就是子节点数量 = 元素数量。
每个元素不保留数据，只用来索引，所有数据都保留在叶子节点。 - 所有的两头节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
- 非叶子节点只保留索引，不保留数据。（B 树中两者都保留）
- 叶子结点蕴含了全副元素的信息，并且叶子结点依照元素大小组成有序列表。
B+ 树这样设计有什么长处呢？
- 每个节点存储的元素更多，看起来比 B 树更矮胖，导致磁盘 IO 次数更少。
- 非叶子节点不存储数据，只存储索引，叶子节点存储全副数据。
这样设计导致每次查找都会查到叶子节点，效率更稳固，便于做性能优化。 - 叶子节点之间应用有序链表连贯。
这样设计不便范畴查找，只须要遍历链表中相邻元素即可，不再须要二次遍历二叉树。
很显著，B 树和 B + 树就是为了文件检索系统设计的，更适宜做索引构造。
面试官： 还得是你，就你总结的全，我都想不那么全，今天来下班吧，薪资 double。
本文知识点总结：
文章继续更新，能够微信搜一搜「一灯架构」第一工夫浏览更多技术干货。