文章插图
文章插图
文章插图
文章插图
B+树是很基础的概念，也是面试里面的常考题，一定要掌握 。今天我们就来聊聊这个话题 。
要弄明白B+数，首先要了解B-树
B-树就是B树，中间的横线不是减号 。千万别念成：B减树，那就丢人现眼了
文章插图
文章插图
既然这样，为什么索引不直接使用二叉树来实现呢？二叉树的查询复杂度是O(logN)，性能已经足够高，难道B-树可以更快？
其实从算法上进，二叉树确实可以 。但是，我们不得不考虑一个现实问题：
文章插图
数据库索引是存储在磁盘上的，当数据量比较大时，索引的大小可能有几个G，甚至更多 。
当我们利用索引查询时，不可能把索引全部加载到内存里 。只能逐一加载每一个磁盘页 。这里的磁盘页对应着索引树的节点 。
文章插图
如果我们使用二叉树，会怎么样呢？假设树的高度是4，要查找的值是10，那么流程如下：
文章插图
第1次磁盘IO：
文章插图
第2次磁盘IO：
文章插图
第3次磁盘IO：
文章插图
第4次磁盘IO：
文章插图
我们可以看到：磁盘的IO次数，是由树的高度决定的
既然如此，为了减少磁盘IO次数，我们就需要把原本“瘦高”的树，变得“矮胖”一些，这就是B-树 。
文章插图
B树是一种多路平衡查找树，它的一个节点最多包含K个孩子，K称为树的阶 。这里，K的大小取决于磁盘页的大小 。
下面具体介绍一下B-树（Balance Tree），一个K阶的B-树具有以下几个特征：
（1）根结点至少有两个孩子 。
（2）每个中间节点都包含m-1个元素和m个孩子，其中 k/2 <= m <= k
（3）每一个叶子节点都包含m-1个元素，其中 k/2 <= m <= k
（4）所有的叶子结点都位于同一层 。
（5）每个节点中的元素从小到大排列，节点当中m-1个元素正好是m个孩子包含的元素的值域分划 。
文章插图
我们以一个3阶的B-数为例，来看一下B-树的具体结构 。树中的具体元素和刚才的二叉树一样 。
文章插图
我们重点看一下（2, 6）这个节点 。该节点有2和6两个元素 。又有3个孩子：1，（3, 5）和8 。其中 1 < 2，（3, 5）在2, 6之间，8大于（3, 5） 。刚好符合上面的几条特征 。
文章插图
文章插图
假设要查询的值是5：
【什么是B+树，这下懂了... | 干货分享】第1次磁盘IO：
文章插图
在内存中定位（和9比较）：
文章插图
第2次磁盘IO：
文章插图
在内存中定位（和2，6比较）：
文章插图
第3次磁盘IO：
推荐阅读
- 大厂的 SDK 写法，偷学到了
- 迷迭香与什么相克,鸡肉与菊花相克
- 洋甘菊茶什么时间喝最好,德国洋甘菊和罗马洋甘菊怎么保存
- 6步傻瓜式点击在树莓派上安好Win11
- go-micro的安装和使用
- 不要为难别人的句子?为难别人就是为难自己的句子
- 九阳龙头净水器好不好?九阳净水器什么型号好
- 上官婉儿被称为什么?上官婉儿生活作风
- 立足|你靠什么在单位立足？
- 为什么陈宫一直跟着吕布?为什么陈宫不跟随曹操