当前位置：首页 > news >正文

数据结构 - 10（ B- 树 B+ 树 B* 树 4000 字详解）

news 来源：原创 2025/8/13 6:06:37

一：B- 树

1.1 B- 树的引入

在使用二叉搜索树对数据进行排序时，存在一个缺陷：随着数据量的增大，二叉搜索树的高度也会随之增加。虽然在数据量较小时，这种情况并不明显，但当数据量变得庞大时，树的高度可能会显著增加，而二叉搜索树的搜索效率依赖于其高度。我们应该如何提高二叉搜索树的排序效率呢？第一是提高 IO 的速度，第二是降低树的高度，由第二点就引入了一种新的数据结构 —— B- 树。

在这里插入图片描述

1.2 B- 树概念

1970年，R. Bayer 和 E. McCreight 提出了一种适合外部查找的树结构，称为 B 树，注意不要误读为 B 减树。一棵 M 阶（M > 2）的 B 树是一种平衡的多路搜索树，可以是空树或满足以下性质：

根节点至少有两个孩子。
每个非根节点至少包含 ⌈M / 2⌉ - 1 个关键字，至多包含 M - 1 个关键字，且这些关键字按升序排列。例如，当 M = 3 时，非根节点至少包含 1 个关键字，最多包含 2 个关键字。
每个非根节点至少有 ⌈M / 2⌉ 个孩子，至多有 M 个孩子。例如，当 M = 3 时，非根节点至少有 2 个孩子，最多有 3 个孩子。
在关键字 key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i] 和 key[i+1] 之间。
所有叶子节点都位于同一层上。

1.3 B- 树的插入分析

为了简单起见，假设 M = 3，即构建一棵三叉树。每个节点中存储两个关键字，这两个关键字可以将值域分割成三个部分，因此每个节点应有三个孩子，孩子节点的数量始终比关键字的数量多一个。为了简化后续实现，节点的结构设计为：

在这里插入图片描述
用序列 {53, 139, 75, 49, 145, 36, 101} ，这个序列中的数就是关键字，构建 B 树的过程如下：

在这里插入图片描述

在这里插入图片描述

最后插入

插入过程总结：

如果树为空，直接插入新节点，数组中的该节点将成为树的根节点。
如果树非空，首先找到待插入元素在树中的插入位置，注意找到的位置一定是在叶子节点中。
检查插入位置是否有效。如果待插入的元素已经存在于树中，则不进行插入。
根据插入排序的思想，将新元素插入到找到的节点中。
检测该节点是否满足B树的性质，即节点中的元素个数是否等于M。若小于M，则满足性质。
如果插入后节点不满足B树的性质，需要对该节点进行分裂：首先申请一个新节点，接着找到当前节点的中间位置，然后将该节点中间位置右侧的元素及其孩子节点移动到新节点中。最后将中间位置的元素和新节点插入到该节点的双亲节点中，并返回到步骤4。
如果分裂过程已经达到根节点位置，则插入过程结束。

1.4 B- 树的插入实现

1.4.1 B- 树的节点设计

class BTreeNode {int[] keys; // 存放当前节点中的关键字BTreeNode[] subs; // 存放当前节点的子节点BTreeNode parent; // 当前节点的父节点，用于在分裂时向上插入int size; // 当前节点中有效关键字的个数// 构造函数，初始化B树节点BTreeNode(int M) {keys = new int[M]; // 初始化关键字数组，大小为Msubs = new BTreeNode[M + 1]; // 初始化子节点数组，大小为M + 1（孩子节点比关键字多一个）size = 0; // 初始时有效关键字数量为0}
}

1.4.2 插入 key 的过程

先查找 key 是否在 B- 树中：

public Pair<BTreeNode, Integer> find(int key) {BTreeNode cur = root; // 从树的根节点开始查找BTreeNode parent = null; // 用于记录当前节点的父节点while (cur != null) { // 遍历树，直到找到该节点或到达空节点int index = 0; // 初始化索引，用于遍历当前节点的关键字while (index < cur.size) { // 遍历当前节点中的关键字if (key == cur.keys[index]) { // 如果找到了目标关键字return new Pair<BTreeNode, Integer>(cur, index); // 返回当前节点和关键字的位置} else if (key < cur.keys[index]) { // 如果目标关键字小于当前关键字break; // 说明应该在当前节点的左子树中查找} else {index++; // 否则继续检查下一个关键字}}parent = cur; // 更新父节点为当前节点cur = cur.subs[index]; // 查找当前节点的子节点}return new Pair<BTreeNode, Integer>(parent, -1); // 未找到目标关键字，返回父节点和-1
}

按照插入排序的思想插入关键字 key。在插入 key 的同时，可能还要插入新分裂出来的节点。

// 采用插入排序的思想插入在cur节点中插入key以及分列出的sub孩子
void insertKey(BTreeNode cur, int key, BTreeNode sub) {int end = cur.size - 1; // 设置指向当前节点最后一个关键字的索引while (end >= 0 && key < cur.keys[end]) { // 寻找插入位置cur.keys[end + 1] = cur.keys[end]; // 将当前关键字向右移动cur.subs[end + 2] = cur.subs[end + 1]; // 将子节点向右移动end--; // 移动到下一个关键字}cur.keys[end + 1] = key; // 在合适位置插入新关键字cur.subs[end + 2] = sub; // 在合适位置插入分裂出的子节点cur.size++; // 更新当前节点的有效大小if (sub != null) { // 如果子节点不为空sub.parent = cur; // 将子节点的父节点指向当前节点}
}

1.4.3 B- 树的插入实现

boolean insert(int key) {// 检查树是否为空，如果为空，则初始化根节点并插入关键字if (root == null) {root = new BTreeNode(M);root.keys[0] = key;root.size = 1;return true;}// 查找插入位置，返回的键值对中如果值不为-1，说明该元素已存在Pair<BTreeNode, Integer> ret = find(key);if (ret.getValue() != -1) {return false; // 关键字已存在，不进行插入}// 获取待插入的当前节点BTreeNode cur = ret.getKey();int k = key; // 存储待插入的关键字BTreeNode sub = null; // 用于存放新分裂出的子节点while (true) {// 插入关键字及子节点insertKey(cur, k, sub);// 如果当前节点的大小未超过最大值，直接返回if (cur.size < M) {break;}// 当前节点需要分裂，找到中间位置int mid = (cur.size >> 1);BTreeNode newNode = new BTreeNode(M); // 创建新的节点int i = 0;int index = mid + 1; // 中间位置右侧开始// 将中间位置右侧的所有元素和子节点搬移到新节点中for (; index < cur.size; ++index) {newNode.keys[i] = cur.keys[index];newNode.subs[i++] = cur.subs[index];// 更新搬移的子节点的父节点if (cur.subs[index] != null) {cur.subs[index].parent = newNode;}}// 注意：新节点的子节点比当前节点多一个newNode.subs[i] = cur.subs[index];if (cur.subs[index] != null) {cur.subs[index].parent = newNode;}// 更新新节点和当前节点的大小newNode.size = i;cur.size = cur.size - i - 1;k = cur.keys[mid]; // 更新待插入的关键字为中间位置的元素// 如果当前节点为根节点，需创建新根节点if (cur == root) {root = new BTreeNode(M);root.keys[0] = k;root.subs[0] = cur;root.subs[1] = newNode;root.size = 1;cur.parent = root; // 更新父节点newNode.parent = root; // 更新新节点的父节点break;} else {// 继续向父节点插入sub = newNode;cur = cur.parent;}}return true; // 插入成功
}

1.5 B- 树的性能分析

对于一棵度为 M 的 B-树，每个节点的子节点数目在 $\frac{M}{2}$ 到 $M - 1$ 之间。因此，树的高度会在某个范围内，查找和插入操作最多需要 $O(\log_{M/2} N)$ 次比较。在找到目标节点后，可以通过二分查找快速定位到具体元素。

例如，对于 $\times 10^9$ 个节点的 B-树，如果度 $M$ 为 1024，则树的高度最多为 4。在620亿个元素中，只需进行少于 4 次比较即可找到目标节点。接着，利用二分查找可以迅速定位到该元素，这显著减少了磁盘读取的次数，提高了查找效率。

二：B+ 树和 B* 树

2.1 B+ 树

B+ 树是 B- 树的变体，属于多路搜索树，定义基本与B-树相同，但有以下不同之处：

非叶子节点的子树指针数量与关键字数量相同。
非叶子节点的子树指针 ( p[i] ) 指向的子树包含的关键字值范围为 ( [k[i], k[i+1}) )。
在所有叶子节点之间增加了链表，且链表是有序的，以便于叶子节点的遍历。
所有关键字仅在叶子节点中出现，不在非叶子节点中出现。

这些特性使得 B+ 树在范围查询和顺序访问时效率更高。

在这里插入图片描述

2.2 B* 树

B* 树是 B+ 树的变形，在 B+ 树的非根和非叶子节点再增加指向兄弟节点的指针。

在这里插入图片描述

2.3 总结

B- 树：多路搜索树，每个节点存储 M/2 到 M 个关键字，非叶子节点存储指向关键字范围的子节点，所有关键字在整个树中出现，仅出现一次，非叶子节点可以省；
B+ 树：在 B- 树基础上，为叶子节点增加链表指针，所有关键字都在叶子节点中出现，非叶子节点作为叶子节点的索引；B+树总是到达叶子节点才命中；
B* 树：在 B+ 树基础上，为非叶子节点也增加链表指针，将节点的最低利用率从 1/2 提高到 2/3。

一：B- 树

1.1 B- 树的引入

1.2 B- 树概念

1.3 B- 树的插入分析

1.4 B- 树的插入实现

1.4.1 B- 树的节点设计

1.4.2 插入 key 的过程

1.4.3 B- 树的插入实现

1.5 B- 树的性能分析

二：B+ 树和 B* 树

2.1 B+ 树

2.2 B* 树

2.3 总结

相关文章：