【高阶数据结构】B+树

文章目录

1. B+树的概念
2. B+树的查找
3. B-树 VS B+树
4. B+ 树的插入分析

1. B+树的概念

B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了一些改进优化。

一棵m阶的B+树需满足下列条件：

每个分支结点最多有m棵子树(孩子结点)。
非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。
（前面这两条其实还跟B树是一样的）
结点的子树个数与关键字个数相等。
结点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
所有叶子节点增加一个链接指针链接在一起
所有关键字及其映射数据都在叶子节点出现

大家可以对照着图理解一下这几条性质。

B+树的特性：

1. 所有关键字都出现在叶子节点的链表中，且链表中的元素都是有序的。
2. 查找不可能在分支节点中命中。
3. 分支节点相当于是叶子节点的索引（仅含有其子树根结点中最大/最小关键码，我们这里图中是最小的），叶子节点才是存储数据的数据层（与B树不同）。

2. B+树的查找

B+树的查找上面有提到——查找不可能在分支节点中命中，如果能找到，应该在叶子节点的链表中：

还是这棵B+树为例，比如我们要查找33
从根结点开始33比5大，往后走，比28也大，再往后走，但是比65小。
所以如果33存在的话，应该在28的子树中。
所以进入28的子树中，然后比较比28大，比35小，所以再往这一层的28的子树p1中找，这就进入到叶子结点的链表中，往后遍历就找到了33。（如果查找的是28也要进入到叶子结点的链表中查找，即使分支结点中存在）
那如果查找34（找不到），也是一样的，最终走到叶子结点的链表中，但是没有这个元素，所以就找不到。