B树及其Java实现详解

一、引言

B树是一种多路平衡查找树，广泛应用于数据库和文件系统的索引结构中。与传统的二叉搜索树相比，B树通过在每个节点存储多个键值对，减少了树的高度，从而降低了磁盘I/O操作的次数，提高了数据检索效率。B树的每个节点最多可以有m个子节点，其中m是B树的阶数。

二、B树的结构与性质

1、节点结构

B树的每个节点包含以下属性：

• 键值列表：存储键值对的列表。
• 子节点列表：存储子节点的列表。
• 叶子节点标志：标识该节点是否为叶子节点。
• 最小度数：节点的最小度数t，决定了节点中键值对的最小和最大数量。

2、性质

• 平衡性：所有叶子节点到根节点的距离相同。
• 键值范围：每个节点中的键值对按顺序排列，非叶子节点的键值用于分隔子树。
• 子节点数量：非叶子节点的子节点数量等于键值对数量加1。

三、B树的操作

1、插入操作

1.1、插入过程

• 寻找插入位置：从根节点开始，根据键值大小向下查找，直到找到合适的叶子节点。
• 插入键值：将新键值插入到叶子节点的键值列表中。
• 节点分裂：如果插入后叶子节点的键值对数量超过最大值，则需要分裂节点。分裂时，将中间键值提升到父节点，并将节点分成两个子节点。

2、删除操作

2.1、删除过程

• 寻找删除位置：从根节点开始，查找要删除的键值所在的位置。
• 删除键值：如果键值在叶子节点中，直接删除；如果在非叶子节点中，用其后继或前驱键值替换，并在相应的子树中删除替换的键值。
• 节点合并：删除后，如果节点的键值对数量小于最小值，则需要合并节点。

3、搜索操作

• 搜索过程：从根节点开始，根据键值大小向下查找，直到找到目标键值或到达叶子节点。在节点内使用二分查找法定位键值。

四、B树的Java实现

1、节点类实现

import java.util.ArrayList;
import java.util.List;class BTreeNode<T extends Comparable<T>> {int t;  // 最小度数List<T> keys;  // 存储键List<BTreeNode<T>> children;  // 存储子节点boolean leaf;  // 是否为叶子节点BTreeNode(int t, boolean leaf) {this.t = t;this.leaf = leaf;this.keys = new ArrayList<>();this.children = new ArrayList<>();}// 查找键int findKey(T k) {int idx = 0;while (idx < keys.size() && keys.get(idx).compareTo(k) < 0) {idx++;}return idx;}// 插入非满节点void insertNonFull(T k) {int i = keys.size() - 1;if (leaf) {keys.add(null);while (i >= 0 && keys.get(i).compareTo(k) > 0) {keys.set(i + 1, keys.get(i));i--;}keys.set(i + 1, k);} else {while (i >= 0 && keys.get(i).compareTo(k) > 0) {i--;}if (children.get(i + 1).keys.size() == 2 * t - 1) {splitChild(i + 1, children.get(i + 1));if (keys.get(i + 1).compareTo(k) < 0) {i++;}}children.get(i + 1).insertNonFull(k);}}// 分裂子节点void splitChild(int i, BTreeNode<T> y) {BTreeNode<T> z = new BTreeNode<>(y.t, y.leaf);for (int j = 0; j < t - 1; j++) {z.keys.add(y.keys.remove(t));}if (!y.leaf) {for (int j = 0; j < t; j++) {z.children.add(y.children.remove(t));}}children.add(i + 1, z);keys.add(i, y.keys.remove(t - 1));}
}

2、B树类实现

class BTree<T extends Comparable<T>> {int t;  // 最小度数BTreeNode<T> root;  // 根节点BTree(int t) {this.t = t;this.root = new BTreeNode<>(t, true);}// 插入键值void insert(T k) {if (root.keys.size() == 2 * t - 1) {BTreeNode<T> newRoot = new BTreeNode<>(t, false);newRoot.children.add(root);newRoot.splitChild(0, root);int i = 0;if (newRoot.keys.get(0).compareTo(k) < 0) {i++;}newRoot.children.get(i).insertNonFull(k);root = newRoot;} else {root.insertNonFull(k);}}// 删除键值void delete(T k) {// 删除操作的实现较为复杂，涉及到节点的合并和调整// 这里省略具体实现，可参考相关资料}// 搜索键值BTreeNode<T> search(T k) {return search(root, k);}private BTreeNode<T> search(BTreeNode<T> node, T k) {int i = 0;while (i < node.keys.size() && node.keys.get(i).compareTo(k) < 0) {i++;}if (i < node.keys.size() && node.keys.get(i).compareTo(k) == 0) {return node;}if (node.leaf) {return null;} else {return search(node.children.get(i), k);}}
}

五、使用示例

以下是一个简单的B树使用示例，演示了如何插入和搜索键值：

public class BTreeDemo {public static void main(String[] args) {BTree<Integer> bTree = new BTree<>(3);  // 创建一个最小度数为3的B树// 插入键值bTree.insert(10);bTree.insert(20);bTree.insert(30);bTree.insert(40);bTree.insert(50);bTree.insert(60);bTree.insert(70);// 搜索键值BTreeNode<Integer> node = bTree.search(40);if (node != null) {System.out.println("找到键值40");} else {System.out.println("未找到键值40");}}
}

六、总结

B树作为一种高效的平衡查找树，通过在每个节点存储多个键值对，减少了树的高度，降低了磁盘I/O操作的次数，提高了数据检索效率。在数据库和文件系统中，B树被广泛应用于索引结构。掌握B树的结构和操作对于理解和优化数据库索引具有重要意义。

---

版权声明：本博客内容为原创，转载请保留原文链接及作者信息。