MySQL索引底层为什么用B+树？看完这篇文章，轻松应对面试。 ...

迎面走来了你的面试官，身穿格子衫，挺着啤酒肚，发际线严重后移的中年男子。
手拿泡着枸杞的保温杯，胳膊夹着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树：
<ol>根节点至少有2个子节点
每个中间节点都包含k-1个元素和k个子节点，其中 m/2