MySQL系列--先行篇 : 为什么MySQL选择了B+树?
前言
接下来的一系列文章打算讲MySQL.
不知道你有没有和我同样的感觉,觉得树的算法是比较麻烦的事情.而MySQL的主要索引是B+树,为了之后能更好地专注MySQL本身的内容,所以把底层存储结构B+树的内容抽出来先单独分析.
为什么MySQL选择了B+树而不是B-树?
这是MySQL面试很常见的问题,想回答清楚就得对两种树的原理有一定了解.
这里的B-树,好像会有部分人念成"B减树".emm...其实B-Tree中间是连字符(hyphen)，不是减号(minus).每个程序员心中都该有点B树.
好了,这里先上结论.
-
B+树的平均高度更低,平均磁盘读写次数更少,而读磁盘,尤其是机械硬盘,是很消耗时间的. -
B+树的数据都在叶子节点上,在需要全盘扫描的时候,B+树的遍历更加方便,只需遍历叶子节点. -
B+树的叶子节点和相邻的节点使用链表相连,在需要范围查询的时候,B+树更为方便.
最主要的原因是第一点,其余两点是B+树的锦上添花.
接下来就具体分析,看看B+树是怎么实现这些优势的.
B-树
B-树本质上是一种多路搜索树.假设树的高度是M,那么一棵M阶的B-树有以下特点:
-
根节点至少有两个子节点 -
每个节点最多有M-1个key，并且以升序排列 -
位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间 -
其它节点至少有M/2个子节点
不负责任地声明一下,由于我并不打算亲自实现B树,所以没有验证过上面这些数字是否准确(关乎到树的平衡).不过本文用于理解B树和B+树的大概原理是足够的了.
可以把B树每个节点看成(key,data)的结构,key就是该节点的索引,data就是该节点存储的数据指针.
平衡过程
https://img2018.cnblogs.com/blog/1478697/201810/1478697-20181024202602879-462464021.gif
B+树
B+树是B树的一种变形树,其与B树的主要差异在于:
-
内节点只存key,不存data,数据只存在于叶子节点. -
每个叶子节点会通过链表与相邻的叶子节点相连.
平衡过程
https://img2018.cnblogs.com/blog/1478697/201810/1478697-20181024202602879-462464021.gif
B-树和B+树的区别
在MySQL中(innodb引擎),数据文件就是索引文件,以数据页为单位组织起来的,也就是说,MySQL的数据全部存在一棵B+树上.
B+树的每个节点就是一个数据页,而这些数据页存储的介质是磁盘.
读磁盘是很慢的操作,因此提高MySQL数据存取性能的关键点就在于减少磁盘的读写次数.也就是减少B+树节点的访问次数.
B+树的优点
-
磁盘读写次数更少 : 在B+树里面,由于 内节点不存储数据,因此每个内节点中能存放更多的key,在相同的数据量下,内节点数量更少, 树的高度更低,磁盘的读写时间开销更低. -
遍历更加方便 : 由于B+树的数据都存储在叶子结点中,内结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。 -
范围查找更加方便 : B+树的叶子节点通过链表与相邻的叶子节点相连,更适合于范围查找,而在数据库中基于范围的查询是非常频繁的.
B-树也不是完全没有优点,如果存储的数据就在根节点或者比较靠近根节点,那么查询的性能可能就接近O(1),而B+树每次都得访问到叶子节点才能找到目标.
不过这毕竟是少数情况,在数据库的应用中,B+树的性能还是远远优于B-树的,