你的面试官正朝你走来，一个身穿格子衬衫、啤酒肚、发际线严重后退的中年男人。手里拿着泡了枸杞子的保温杯，胳膊下夹着一台MacBook，MacBook上贴着公司标语：“我爱加班”。采访开始，开门见山。面试官：你知道MySQL索引底层数据结构为什么要用B+树吗？代替B树，红黑树还是普通的二叉树？我：谁知道作者对此有何看法？他可能习惯用B+树，个人喜好。采访者：你的思想很开放。今天的采访先过来，等有消息我再联系你。后面有消息吗？你什么时候主动联系我的？说真话的被拒，背八股的作文溜走的被录取了。好吧，等我看一登如何总结MySQL八字随笔。我：要知道MySQL索引的底层数据结构为什么使用B+树，首先要了解什么样的数据结构更适合做索引。为了保证数据安全，数据一般都存储在磁盘上。当我们需要查询数据时，需要读取磁盘，这就产生了磁盘IO。与内存操作相比，磁盘IO读取速度非常慢。由于需要的数据在磁盘上可能不是连续的，一次数据查询需要多次磁盘IO，所以我们需要设计一种索引数据结构，尽可能减少磁盘IO的次数。多了解这几种二叉树的特点，以及它们的优缺点，你就会知道哪种数据结构更适合做索引。什么是二叉搜索树：如果左子树不为空，则左子树上所有节点的值都小于其根节点的值；如果右子树不为空，则右子树上所有节点的值都大于其根节点的值；左右子树也是二叉搜索树；二叉查找树查找数据的时间复杂度为O(logN)，如图所示，最多查找3次即可找到所需数据。理想很丰满，现实很骨感。在极端情况下，二叉搜索树可能会退化为线性链表。链表的查找时间复杂度为O(N)。这时候最多需要7次才能找到需要的数据。我们对于它可以做些什么呢？于是想到给二叉树加一些约束，平衡左右子树，然后扩展出很多平衡树：平衡二叉查找树、红黑树、B树、B+树。下面说说这几种树的优缺点，看看哪种树最适合做索引。什么是红黑树？节点是红色或黑色根节点是黑色所有叶子都是黑色的（叶子是NIL节点）每个红色节点的两个孩子都是黑色的（从每个叶子到根连续红色节点的所有路径上不能有两个孩子）所有路径来自它的每个叶子的任何节点都包含相同数量的黑色节点，看到了吗？设计了这么多复杂的规则，就是为了保证从根节点到叶节点的最长路径不超过最短路径的两倍。在插入或删除节点时，为了满足红黑树规则，可能需要改变颜色和旋转，这是一个复杂且耗时的过程。红黑树的优点：左右子树的树高有限，相差不会太大。缺点：规则复杂，普通人想要看懂这个东西就已经很困难了，更别说使用了。什么是B树？我们知道树高越高，查找次数越多，也就是磁盘IO次数越多，耗时越长。能不能想办法降低树的高度，把二叉树变成N叉树呢？于是B树来了。对于m阶B树：根节点至少有2个子节点，每个中间节点包含k-1个元素和k个子节点，其中m/2<=k<=m，每个叶节点包含k-1元素，其中m/2<=k<=m中间节点的元素按升序排列所有叶子节点都位于同一层根节点（8）有两个子节点，左子节点（35）和右子节点（1115）。左子节点(35)中有2个元素和3个子节点。元素是3和5，按升序排列。子节点为(12)、(4)、(67)，(12)中的元素小于3，(4)中的元素在3~5之间，(67)中的元素)都大于5，符合B树的特点。B树这样的设计有什么优势？高度较低，每个节点包含多个元素。查找时，可以一次将一个节点中的所有元素加载到内存中进行比较。这两项改进都大大减少了磁盘IO的数量。B+树是什么？B+树与B树相比，做了如下约定：有k个子节点的中间节点有k个元素（B树中有k-1个元素），即子节点数=元素数。每个元素不存储数据，仅用于索引，所有数据都存储在叶子节点中。所有中间节点元素也都存在于子节点中，子节点是子节点元素中最大（或最小）的元素。非叶子节点只存储索引，不存储数据。（都保存在B树中）叶子节点包含所有元素的信息，叶子节点按照元素的大小组成一个有序列表。B+树设计的优点是什么？每个节点存储更多元素，看起来比B树更块，从而减少磁盘IO。非叶子节点不存储数据，只有索引，叶子节点存储所有数据。这种设计使得每次搜索都能找到叶节点，这样效率更高，也更容易优化性能。叶节点通过有序链表连接。这种设计方便了范围搜索。只需要遍历链表中相邻的元素，不再需要遍历二叉树两次。显然，B-树和B+树是为文件检索系统设计的，更适合做索引结构。面试官：还是得是你。就您的总结而言，我认为它还不够完整。明天来上班，工资翻倍。本文知识点总结：文章持续更新中，大家可以在微信搜索“一光架构”第一时间阅读更多技术干货。
