B树与B+树

B+树引出

在MySQL中,如果我们设置了主键, 那么对于该列表中的数据就有了一个索引,插入表中数据的主键值不能重复,而且不能为空.
那当我们插入数据的时候, 它是如何通过索引来判断主键值是否重复的呢?
我们想到它肯定是进行了一个查找, 关于查找那就是哈希或者二叉搜索树查找比较快啊, 但MySQL是用B+树来实现查找的.

为什么哈希和二叉树不行呢?

在MySQL中,我们可以查找范围内的数据,比如 大于3且小于5 的数据, 那在哈希中 我们只能查找某个值的数据,或者余数相同的数据,不能实现范围查找.
同样的, 二叉搜索树也是一样, 不能得出范围. 还有就是二叉搜索树的访问速度也慢, 因为二叉搜索树要进行多次比较 才能得出数据, 每次比较都要访问磁盘,多次访问磁盘效率自然很低.

要了解B+树,首先我们得知道B树.

什么是B树

B树与二叉搜索树很像, 可以把它理解为一个 N 叉搜索树, 如图:

它一个节点可以对应多个key, 每个key都是一条数据,比如我们定义一个学生表,每个学生都有姓名和 id, 那 25 可能就代表 ‘张三’ 25 这么一条数据.
通过上图我们可以看出它的子节点是按照范围来确定的, 比如第一个节点, 它存的key是 25 30 50 70 , 那它可以分出5个节点, 节点key的范围分别为:
小于25
大于25且小30
大于30且小于50
大于50且小于70
大于70
这样相比二叉搜索树, B树的高度更矮, 这就意味着查询次数更少, 访问磁盘更少,效率高了一点.

什么是B+树

B+树也是N叉搜索树, 只不过是对B树进行了改进.
我们来画个B+树:

从图中我们可以知道它的特点 :

1.一个节点可以存储N个key, N个key划分出N个区间(B树是N+1个区间)
2.每个节点的key值都会在子节点中存在 (同时key值是子节点的最大值)(这里保证了树的高度统一)
3.B+树的叶子节点是首尾相连的,相当于链表(便于范围查找)
4.在B+树这里, 我们只在叶子节点处存储完整数据,而非叶子节点只存储key值(大大节省了空间)

B+树的优点

它的优点即是它的特点, 这里再概括一下:

1. 当前一个节点保存了更多的key时, 最终树的高度是更矮的,减少了IO访问次数,提高了效率(与B树一样)

2. B+树所有查询所经历的IO访问次数一样(这样可以让程序员对代码运行速率有所把控)

3. B+树的叶子节点构成一个链表, 此时方便范围查询.

4. 由于数据都在叶子节点上, 非叶子节点只存储key, 导致非叶子节点占空间比较少, 这些非叶子节点就可能在内存中缓存(或者缓存一部分), 这样又进一步减少IO访问次数.