【UCB CS 61B SP24】Lecture 17 - Data Structures 3: B-Trees学习笔记

本文以 2-3-4 树详细讲解了 B 树的概念，逐步分析其操作，并用 Java 实现了标准的 B 树。

1. 2-3 & 2-3-4 Trees

上一节课中讲到的二叉搜索树当数据是随机顺序插入的时候能够使得树变得比较茂密，如下图右侧所示，时间复杂度也就近似 $O(logn)$。但是当数据按顺序插入时，二叉搜索树就退化为了链表（每个节点都向同一侧倾斜），如下图左侧所示，这样时间复杂度就退化为 $O(n)$。有什么更优化的数据结构呢？

B 树（B-Trees）是一种自平衡的树数据结构，适用于在磁盘等存储设备上高效管理大量数据。它通过保持平衡来确保查找、插入、删除操作的时间复杂度为 $O(logn)$。B 树广泛应用于数据库和文件系统。

1.1 插入

假设我们现在有一颗还算完美的二叉搜索树，如下图右上角所示，接下来如果我们需要插入 {17, 18, 19, ...} 怎么办？我们可以通过在叶节点中“过度填充”来避免产生新的叶节点，也就是把插入的元素都塞到 16 节点中：

但是如果一个节点过于充斥，如下图所示，那么我们可能就得遍历节点中的所有元素才能找到我们想要的，这样效率同样会下降：

我们的解决方法是设定一个限制 $L$，表示一个节点中最多有几个键值，假设我们令 $L=3$，那么当节点中的键值已经到 {16, 17, 18, 19} 时就已经超过限制了，这时我们需要选择一个键值提升到父节点中。

我们会将中间键（记为 node[mid]）提升到父节点，在我们这个例子中键值数量为偶数，那么就选择中间偏左的键值 17，如下图所示：

仔细观察又会发现这样有个问题，那就是这时 16 在 {15, 17} 的右侧了，这就不是个合法的搜索树了。因此再提完中间键后我们需要将中间键的左右两部分分裂开变成两个节点，假设 node 表示提升键值前的原节点 {16, 17, 18, 19}，那么分裂操作就是将 node[0 ~ mid - 1] 与 node[mid + 1, node.size - 1] 分裂开。

因此我们会将 16 与 {18, 19} 分裂开，如下图所示，这样小于 15 的键值在左侧子节点（可以表示为 {15, 17}.children[0]），在 15 ~ 17 之间的键值在左侧第二个子节点（可以表示为 {15, 17}.children[1]），大于 17 的键值在右侧子节点（可以表示为 {15, 17}.children[2]）：

假设我们继续插入 {20, 21}，如下图所示，当插入 21 时，节点又爆满了，将中间靠左的键值 19 提升到父节点中，接着原节点分裂开：

我们继续插入 {25, 26}，流程如下图所示，可以看到当非叶子节点分裂时，还需要同步处理子节点的引用，即分裂非叶子节点 node[0 ~ mid - 1] 与 node[mid + 1, node.size - 1] 时，还需要顺带分裂 node.children[0, mid] 与 node.children[mid + 1, node.size - 1]（注意左半部分需要将 mid 包含进去才正确，可以结合图片理解）：

如果我们一直添加到根节点都塞满了怎么办？那么就同样将根节点中的中间键往上提，这时候就成为了新的根节点，树的高度在这时候才加了一层，即树的高度只有在分裂根时才会增加，此时树还是保持着完美的平衡：

我们此前设定的限制 $L=3$ 就最后就形成了这棵 2-3-4 树，当 $L=2$ 时我们称其为 2-3 树，这两种就是相对最常见的 B 树。

1.2 删除

B 树的删除与 BST 一样是比较复杂的，有多种情况需要讨论。

（1）如果要删除的节点为内部节点（无论节点中有几个键值），那么思想与 BST 类似，找到前驱（左子树最大键）或后继（右子树最小键）替换要删除的键值，然后递归删除叶子节点中的键：

在这种情况中我们找到了 18，最后将其删去，这样看起来很简单，因为如果我们从具有多个键值的叶子节点中删除某个值只需要简单将其删去即可。

（2）如果我们的叶子节点只有一个键，我们就不能简单地完全删除节点，因为根据 B 树的性质（先见第二小节），每个拥有 $k$ 个键值的节点（除叶子）都有 $k+1$ 个子节点，因此我们将留下一个必须填充的空节点：

如何填充空节点是比较复杂的，同样也有多种情况要讨论：

Case 1：空节点的相邻兄弟节点有多个键值（非常难的情况），如下图所示，我们用哪个键来填充呢？

解决思路为：

• X 先把父节点的键值拿过来，然后父节点再从 X 的兄弟节点中拿一个键值过来；
• 如果 X 不是叶节点，再将其兄弟节点的一个子树拿过来（维持 B 树性质）。

结合例子看看，我们要删除 17，首先在右子树找到了后继键值 19，将其与 17 交换，然后删除 17，删除后留下了一个空节点，填充时从父节点拿来 21，父节点再从另一个兄弟节点拿来 22，由于空节点为叶节点，因此不进一步拿兄弟节点的子树：

Case 2：空节点右侧的所有兄弟节点都只有一个键值，但是父节点有多个键值（同样很困难），如下图所示：

解决思路为：

• X 和最右侧的兄弟节点把父节点的键值拿来，中间子节点的键值提到父节点中；
• 传递中间子节点的子树，以便每个节点都有正确的子节点

结合例子看看，我们要删除 3，首先在右子树中找到了后继键值 4，将其与 3 交换，然后删除 4，删除后留下了一个空节点，填充时右侧兄弟节点都只有一个键值，因此和最右边的兄弟节点 9 一起分别将父节点的键值拿来，然后将中间兄弟节点的键值提到父节点中，已经是叶节点了因此不用再调整子树了：

Case 3：父节点和所有兄弟节点都只有一个键值，这种简单点，解决思路就是将一个兄弟节点和父节点合并成一个节点，替换到 X 上，然后将空节点上移一层，如果空节点最终作为了根节点，那么直接删除空节点即可：

结合例子看看，我们要删除 6，首先在右子树中找到了后继键值 7，将其与 6 交换，然后删除 7，删除后留下了一个空节点，填充时右侧兄弟节点与父节点都只有一个键值，因此合并兄弟节点和父节点变为 {8, 9}，然后将空节点上移一层，此时空节点并不是根节点，回到了第一种情况（兄弟节点有多个键值），也就是先把父节点键值 7 拿来，然后父节点从有多个键值的子节点那把 4 拿来，空节点不是叶节点，最后再把兄弟节点的子树 5 拿来当自己的子树：

2. Java实现多阶B树

通过上面演示的 B 树我们能发现其具有以下特性，我们此处以 $m$ 阶 B 树为例进行概括：

• 节点容量：
  • 根节点：至少有1个键，最多 $m-1$ 个键。
  • 内部节点：至少 $\lceil m/2\rceil -1$个键，最多 $m-1$ 个键。
• 子节点数量：每个拥有 $k$ 个键值的节点（除叶子节点）都有 $k+1$ 个子节点。
• 平衡性：所有叶子节点位于同一层（相同深度），树是完全平衡的，无论怎么添加键值时间复杂度都为 $O(logn)$。
• 有序性：节点内的键按升序排列，子树遵循二叉搜索树性质。

总结一下 B 树的操作：

（1）查找

从根节点开始，逐层向下比较键值：

• 若找到目标键，返回 true。
• 否则，根据键的大小选择对应的子节点递归查找。
• 到达叶子节点仍未找到，返回 false。

（2）插入

1. 寻找插入位置：递归找到对应的叶子节点。
2. 插入键：将键插入叶子节点。
3. 分裂处理：
   • 若节点键数超过 $m-1$，则分裂：
     • 中间键提升到父节点；
     • 原节点分裂为两个子节点。
   • 递归检查父节点是否需要分裂，直到根节点。

（3）删除

1. 定位键：找到待删除键的位置。
2. 处理内部节点键：若键在内部节点，用前驱（左子树最大键）或后继（右子树最小键）替换，转为删除叶子节点中的键。
3. 删除叶子键：直接删除。
4. 处理下溢：
   • 借键：若兄弟节点有富余键，从兄弟借一个键并调整父节点；
   • 合并：若兄弟节点无富余，合并当前节点与兄弟，并递归调整父节点。

Java 实现 $m$ 阶 B 树代码如下，可以简单参考一下，不一定要完全看明白：

package CS61B.Lecture17;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** 标准 m 阶 B 树实现（支持插入、查找、删除）* 特性：* 1. 每个节点最多包含 m - 1 个键* 2. 根节点最少包含 1 个键，非根节点最少包含 ⌈m / 2⌉ - 1 个键* 3. 所有叶子节点位于同一层*/
public class BTree {private final int m;  // B 树的阶private Node root;public BTree(int m) {this.m = m;this.root = new Node(true);}/** 节点 */private static class Node {List<Integer> keys = new ArrayList<>();  // 存储键值（始终保持有序）List<Node> children = new ArrayList<>();  // 子节点引用（非叶子节点使用）boolean isLeaf;  // 是否为叶子节点Node(boolean isLeaf) {this.isLeaf = isLeaf;}}/** 核心操作：查找 */public boolean contains(int key) {return search(root, key) != null;}/** 递归查找实现 */private Integer search(Node node, int key) {// 找到当前节点中第一个不小于 key 的键的位置int i = 0;while (i < node.keys.size() && key > node.keys.get(i)) i++;if (i < node.keys.size() && key == node.keys.get(i)) {  // 在当前节点找到目标键return key;} else if (node.isLeaf) {return null;} else {  // 未找到但当前节点非叶子节点return search(node.children.get(i), key);  // 递归查找子节点}}/** 核心操作：插入 */public void insert(int key) {insert(root, key);// 根节点分裂处理if (root.keys.size() == m) {Node newRoot = new Node(false);newRoot.children.add(root);splitChild(newRoot, 0);root = newRoot;}}/** 递归插入实现 */private void insert(Node node, int key) {int i = node.keys.size() - 1;if (node.isLeaf) {// 叶子节点：直接插入while (i >= 0 && key < node.keys.get(i)) i--;  // 找到小于等于 key 的最大值位置node.keys.add(i + 1, key);  // 在其右侧插入 key} else {// 内部节点：找到子节点位置while (i >= 0 && key < node.keys.get(i)) i--;i++;  // 调整到正确的子节点索引，因为 node[i] 小于等于 key，node.children[i] 是小于 node[i] 的子树// 子节点已满时先分裂if (node.children.get(i).keys.size() == m - 1) {splitChild(node, i);if (key > node.keys.get(i)) i++;  // 分裂后可能需要调整目标子节点索引}insert(node.children.get(i), key);}}/** 分裂子节点（核心辅助方法） */private void splitChild(Node parent, int childIndex) {Node child = parent.children.get(childIndex);Node sibling = new Node(child.isLeaf);  // 与原节点在同一层int mid = m - 1 >> 1;  // 中间键索引// 将右半部分键移动到新节点sibling.keys.addAll(child.keys.subList(mid + 1, child.keys.size()));child.keys.subList(mid + 1, child.keys.size()).clear();  // 清除原节点右半部分// 非叶子节点：处理子节点引用if (!child.isLeaf) {sibling.children.addAll(child.children.subList(mid + 1, child.children.size()));child.children.subList(mid + 1, child.children.size()).clear();}// 将中间键提升到父节点，新节点在原节点的右边parent.keys.add(childIndex, child.keys.remove(mid));parent.children.add(childIndex + 1, sibling);}/** 核心操作：删除 */public void delete(int key) {delete(root, key);/*根节点为空时降低树高度，选择其第一个子节点作为新的根节点当根节点被删除到空时，唯一可能的场景是：根节点原本只有一个键，且该键被删除根节点此时仅剩一个子节点（因为如果根节点有多个子节点，它必须至少保留一个键来分隔子节点）*/if (root.keys.isEmpty() && !root.isLeaf) {root = root.children.get(0);}}/** 递归删除实现 */private void delete(Node node, int key) {int i = 0;while (i < node.keys.size() && key > node.keys.get(i)) i++;  // 找到大于等于 key 的最小值// Case 1: 当前节点包含目标键if (i < node.keys.size() && key == node.keys.get(i)) {if (node.isLeaf) {  // 如果为叶子节点的键则直接删除node.keys.remove(i);} else {  // 如果是内部节点则用前驱/后继替换后递归删除handleInternalKey(node, i);}}// Case 2: 目标键可能在子节点中else if (!node.isLeaf) {Node child = node.children.get(i);// 子节点键不足时先调整if (child.keys.size() < (m + 1) / 2) {// 尝试从左兄弟借键if (i > 0 && node.children.get(i - 1).keys.size() >= (m + 1) / 2) {borrowFromLeftSibling(node, i);}// 尝试从右兄弟借键else if (i < node.children.size() - 1 && node.children.get(i + 1).keys.size() >= (m + 1) / 2) {borrowFromRightSibling(node, i);}// 需要合并节点else {if (i < node.children.size() - 1) {mergeChildren(node, i);} else {mergeChildren(node, i - 1);i--;  // 合并后索引调整}}}delete(node.children.get(i), key);}}/** 处理内部节点键的删除，选择前驱后继时需要注意非根节点最少包含 ⌈m / 2⌉ - 1 个键的性质 */private void handleInternalKey(Node node, int index) {Node leftChild = node.children.get(index);Node rightChild = node.children.get(index + 1);// Case 1: 左子节点的键足够多，用前驱替换if (leftChild.keys.size() >= (m + 1) / 2) {int predecessor = getPredecessor(leftChild);node.keys.set(index, predecessor);delete(leftChild, predecessor);}// Case 2: 右子节点的键足够多，用后继替换else if (rightChild.keys.size() >= (m + 1) / 2) {int successor = getSuccessor(rightChild);node.keys.set(index, successor);delete(rightChild, successor);}// Case 3: 否则合并 leftChild 与 rightChild 两个子节点后递归删除else {int keyToDelete = node.keys.get(index);  // 合并后 node.keys.get(index) 可能已变更，需要提前保存mergeChildren(node, index);delete(leftChild, keyToDelete);  // 删除已下移到子节点的原键}}/** 获取左子树的最大键（前驱） */private int getPredecessor(Node node) {while (!node.isLeaf) {node = node.children.get(node.children.size() - 1);}return node.keys.get(node.keys.size() - 1);}/** 获取右子树的最小键（后继） */private int getSuccessor(Node node) {while (!node.isLeaf) {node = node.children.get(0);}return node.keys.get(0);}/** 从左兄弟借键 */private void borrowFromLeftSibling(Node parent, int childIndex) {Node child = parent.children.get(childIndex);Node leftSibling = parent.children.get(childIndex - 1);// 父节点键下移，左兄弟键上移child.keys.add(0, parent.keys.get(childIndex - 1));parent.keys.set(childIndex - 1, leftSibling.keys.remove(leftSibling.keys.size() - 1));// 移动子节点引用（非叶子节点）if (!child.isLeaf) {child.children.add(0, leftSibling.children.remove(leftSibling.children.size() - 1));}}/** 从右兄弟借键 */private void borrowFromRightSibling(Node parent, int childIndex) {Node child = parent.children.get(childIndex);Node rightSibling = parent.children.get(childIndex + 1);// 父节点键下移，右兄弟键上移child.keys.add(parent.keys.get(childIndex));parent.keys.set(childIndex, rightSibling.keys.remove(0));// 移动子节点引用（非叶子节点）if (!child.isLeaf) {child.children.add(rightSibling.children.remove(0));}}/** 合并 childIndex 与 childIndex + 1 两个位置的子节点 */private void mergeChildren(Node parent, int childIndex) {Node left = parent.children.get(childIndex);Node right = parent.children.get(childIndex + 1);// 提取父节点的键并下移int parentKey = parent.keys.get(childIndex);left.keys.add(parentKey);parent.keys.remove(childIndex);// 合并右子节点的键和子节点left.keys.addAll(right.keys);left.children.addAll(right.children);parent.children.remove(childIndex + 1);// 若父节点是根且无键，降低树高度if (parent == root && parent.keys.isEmpty()) {root = left;}}/** 打印 B 树结构 */public void printTree() {printTree(root, 0);}/** 递归打印 B 树结构 */private void printTree(Node node, int level) {StringBuilder indent = new StringBuilder();for (int i = 0; i < level; i++) {indent.append("│   "); // 每层缩进 4 个字符}// 打印当前节点键值System.out.print(indent);if (level > 0) {System.out.print("├── ");}System.out.print("[" + String.join(", ", node.keys.stream().map(Object::toString).toArray(String[]::new)) + "]");if (node.isLeaf) {System.out.print(" (Leaf)");}System.out.println();// 递归打印子节点for (int i = 0; i < node.children.size(); i++) {Node child = node.children.get(i);printTree(child, level + 1);}}/** 递归打印 B 树结构（添加箭头符号的增强版） */private void printTreeEnhancement(Node node, int level) {// 生成缩进前缀StringBuilder prefix = new StringBuilder();for (int i = 0; i < level; i++) {prefix.append(i == level - 1 ? "│   " : "    ");}// 打印当前节点System.out.print(prefix);if (level > 0) {System.out.print("└── ");}System.out.print("[" + String.join(", ", Arrays.toString(node.keys.stream().map(Object::toString).toArray(String[]::new)) + "]"));if (node.isLeaf) System.out.print(" (Leaf)");System.out.println();// 递归子节点for (int i = 0; i < node.children.size(); i++) {Node child = node.children.get(i);printTree(child, level + 1);}}/** 测试 */public static void main(String[] args) {BTree tree = new BTree(4);// 插入测试数据int[] keys = {10, 20, 30, 40, 50, 60, 70, 80, 90};for (int key : keys) tree.insert(key);// 验证存在性System.out.println("Contains 30: " + tree.contains(30));  // trueSystem.out.println("Contains 10: " + tree.contains(10));  // truetree.printTree();// 删除内部节点键tree.delete(30);System.out.println("Contains 30 after deletion: " + tree.contains(30));  // falsetree.printTree();// 边界测试：删除后树结构调整tree.delete(10);tree.delete(20);tree.delete(40);System.out.println("Contains 50: " + tree.contains(50));  // trueSystem.out.println("Contains 10 after deletion: " + tree.contains(10));  // false}
}