48｜多路查找树：B+树的插入与删除操作详解

王健伟

你好，我是王健伟。
上节课我们详细讲解了多路查找树中的 B 树，这节课我们来聊一聊 B+ 树。B+ 树有人理解为 B 树的升级，有人理解为 B 树的变形（变体），都可以。性质上来看，B+ 树与 B 树基本相同，但还是有一些不同点的。
B+ 树的所有非叶子节点中的数据都会包含在叶子节点中。
B+ 树的所有叶子节点相连，从而构成了一个数据从小到大排列的链表（虽然绘制时	常绘制成一个单链表，但实际应用中，往往实现成一个双链表以方便对数据的查找）。
下面，我带你看一看 B+ 树都有哪些操作。
B+ 树的插入操作B+ 树的插入操作和 B 树非常类似。在这里看一个 B+ 树节点插入的步骤。假如要按顺序给出如下数据创建一棵 4 阶 B+ 树：
11，12，6，5，13，7，3，4，2，1，9，8，10
4 阶 B+ 树同样遵循每个节点最少有 1 个数据，最多有 3 个数据。创建的步骤如下：
因为当前并不存在 B+ 树，所以以 11 为根创建一棵 B+ 树。
插入 12，因为 12 大于 11，所以 12 位于 11 的右侧，与 11 共用一个节点。
插入 6，因为 6 小于 11，所以 6 位于 11 的左侧，与 11、12 共用一个节点。
插入 5，因为 5 小于 6，所以 5 位于 6 的左侧，此时注意，5、6、11、12 共用一个节点。但因为 4 阶 B+ 树最多有 3 个数据，因此这个节点必须要进行拆分（分裂），拆分的原则与 B 树一样—取这几个数据中间（⌈m/2⌉）的那个数据并作为根节点，剩余的数据分别做这个节点的左孩子和右孩子节点。讲解 B 树时取了第 2 个数据作为根节点，在这里取第 3 个数据作为根节点（4 个数据中，第 2 个或者第 3 个数据都可以看成是中间的数据）。对于 5、6、11、12，取第 3 个数据 11 作为根节点，将数据 5、6 所代表的节点作为 11 的左孩子，将 12 所代表的节点作为 11 的右孩子。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

B+树是一种多路查找树，相较于B树有一些不同之处。B+树的所有非叶子节点中的数据都会包含在叶子节点中，而所有叶子节点相连，构成了一个数据从小到大排列的链表。本文详细讲解了B+树的插入和删除操作，以创建和维护B+树的步骤演示为例。通过插入数据并进行节点拆分，展示了B+树的动态变化过程。文章还提到了B+树在不同资料中的表述和实现存在差异，但都是正确的实现方式。B+树相对于B树的优势在于其所有非叶子节点中的数据都包含在叶子节点中，以及叶子节点相连构成有序链表，这使得B+树更适合范围查询。文章还提出了思考题，引导读者深入思考B+树的优势和如何利用B+树实现数据记录的范围查询。整体而言，本文深入浅出地介绍了B+树的特点和操作，为读者提供了深入理解和实现B+树的基础知识。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68

立即购买

登录后留言

全部留言(1)

最新
精选

Rookie
怎么没有b+树的代码
作者回复: 总要留给大家一些空间，老师也不好全大包大揽
2023-06-07归属地：广东



收起评论