面试官：MySQL索引为啥用B+树？

深藏阁楼爱情的钟 2024-04-06 09:29 93阅读 0赞

面试官： 你知道MySQL索引底层数据结构为啥用B+树？而不用B树、红黑树或者普通二叉树？

我： 这事谁知道作者咋想的？他可能是用B+树习惯了，个人爱好吧。

面试官： 你倒是挺看得开。今天的面试就先到这吧，后面有消息会主动联系你。

后面还可能有消息吗？

好吧，等我看看怎么总结的MySQL的八股文。

我： 要知道MySQL索引底层数据结构为啥用B+树，先要了解一下什么样的数据结构更适合建索引。

为了保证数据安全性，一般都是把数据存储在磁盘里面。当我们需要查询数据的时候，需要读取磁盘，就产生了磁盘IO，相比较内存操作，磁盘IO读取速度是非常慢的。

由于所需数据可能在磁盘并不是连续的，一次数据查询就需要多次磁盘IO，所以就需要我们设计的索引数据结构尽可能的减少磁盘IO次数。

再了解一下这几种二叉树的特性，以及优缺点，就知道哪种数据结构更适合建索引。

什么是二叉搜索树：

1、若左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
2、若右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
3、左、右子树也分别为二叉查找树；

![ba5073914510456a8a171c0ea58f7277.png][]

二叉搜索树查找数据的时间复杂度是O(logN)，如图所示，最多查找3次就可以查到所需数据。

理想很丰满，现实很骨感。极端情况下，二叉查找树可能退化成线性链表。

![2ab7a84e25a04583ac771a9647efa668.png][]  
链表的查找时间复杂度是O(N)，这时候最多需要7次才能查到所需数据。

该怎么办呢？于是我们就想到了给二叉树加一些限制条件，平衡一下左右子树，然后就引申出了很多平衡树：平衡二叉查找树、红黑树、B树、B+树。咱们分别说一下这几种树的优缺点，看哪种树最适合做索引。

什么是红黑树？

结点是红色或黑色  
根结点是黑色  
所有叶子都是黑色（叶子是NIL结点）  
每个红色结点的两个子结点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）  
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

![e14d83eff4a345c9929aa1e92ee6357b.png][]  
看蒙了没有？

这么多复杂的规则，就是为了保证从根节点到叶子节点的最长路径不超过最短路径的2倍。

当插入节点或者删除节点的时候，为了满足红黑树规则，可能需要变色和旋转，这是一个复杂且耗时的过程。

红黑树的优点： 限制了左右子树的树高，不会相差过大。

缺点： 规则复杂，一般人想要弄懂这玩意儿，就已经很费劲了，更别说使用了。

什么是B树？

我们知道，树的高度越高，查找次数越多，也就是磁盘IO次数越多，耗时越长， 我们能不能想办法降低树的高度，把二叉树变成N叉树？于是B树就来了。

对于一个m阶的B树：

根节点至少有2个子节点  
每个中间节点都包含k-1个元素和k个子节点，其中 m/2 <= k <= m  
每个叶子节点都包含k-1个元素，其中 m/2 <= k <= m  
中间节点的元素按照升序排列  
所有的叶子结点都位于同一层

![b4448b79a76b48b49c87aaa417e42ef5.png][]  
根节点（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树中两者都保存）  
叶子结点包含了全部元素的信息，并且叶子结点按照元素大小组成有序列表。

![8574a0810375408593062e2923882343.png][]

B+树这样设计有什么优点呢？

每个节点存储的元素更多，看起来比B树更矮胖，导致磁盘IO次数更少。

非叶子节点不存储数据，只存储索引，叶子节点存储全部数据。 这样设计导致每次查找都会查到叶子节点，效率更稳定，便于做性能优化。

叶子节点之间使用有序链表连接。 这样设计方便范围查找，只需要遍历链表中相邻元素即可，不再需要二次遍历二叉树。

很明显，B树和B+树就是为了文件检索系统设计的，更适合做索引结构。

面试官： 还得是你，就你总结的全，我都想不那么全，明天来上班吧，薪资double。

本文知识点总结：

![b4db1ceeaa11438c8b9657a7985b319c.png][]

[ba5073914510456a8a171c0ea58f7277.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/9b2e7d32842b4122b4587399858db860.png
[2ab7a84e25a04583ac771a9647efa668.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/60b0f619124f4c97b98da5ff37b62dfa.png
[e14d83eff4a345c9929aa1e92ee6357b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/6b22fb5da69a4cf78c7c31ef311b6eb7.png
[b4448b79a76b48b49c87aaa417e42ef5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/94bfb662aab841fa88cf327bed6179c2.png
[8574a0810375408593062e2923882343.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/545be4ad318b43d6a17e3e716c7c5ee0.png
[b4db1ceeaa11438c8b9657a7985b319c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/77ea3f1cd6ac44ff920ffc5fca19447a.png