B 树详解及其 Java 实现
B 树详解及其 Java 实现
1. 引言
B 树是一种平衡树数据结构，广泛应用于数据库和文件系统中。它是一种多路搜索树，其中每个节点可以有多个子节点和多个键。本文将详细介绍 B 树的结构、性质、操作及其 Java 实现。
2. B 树的结构与性质
2.1 B 树的定义
B 树是一种自平衡的树数据结构，具有以下性质：
- 每个节点最多有
m个子节点（m为 B 树的阶）。 - 除根节点和叶子节点外，每个节点至少有
⌈m/2⌉个子节点。 - 所有叶子节点都在同一层。
- 每个节点包含
n个键（⌈m/2⌉ - 1 <= n <= m - 1）。 - 节点的键按升序排列，节点的子节点按键值大小分区。
2.2 B 树的应用
B 树广泛应用于数据库和文件系统中，其优点包括：
- 平衡性：所有叶子节点都在同一层，保证查找、插入和删除操作的时间复杂度为
O(log n)。 - 高效性：适用于磁盘存储，减少磁盘 I/O 操作。
- 扩展性：支持动态增删数据，适合处理大规模数据。
3. B 树的操作
3.1 插入操作
插入操作包括以下步骤：
- 查找插入位置。
- 将键插入到相应的节点。
- 如果节点键数超过最大值，则进行分裂操作。
3.2 删除操作
删除操作包括以下步骤：
- 查找要删除的键。
- 从节点中删除键。
- 如果节点键数低于最小值，则进行合并或借用操作。
4. B 树的 Java 实现
以下是 B 树的完整 Java 实现，包括插入和删除操作。
4.1 B 树节点类
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));
}
}4.2 B 树类
public class BTree<T extends Comparable<T>> {
private BTreeNode<T> root;
private int t; // 最小度数
public BTree(int t) {
this.root = new BTreeNode<>(t, true);
this.t = t;
}
// 插入键
public void insert(T k) {
BTreeNode<T> r = root;
if (r.keys.size() == 2 * t - 1) {
BTreeNode<T> s = new BTreeNode<>(t, false);
s.children.add(r);
s.splitChild(0, r);
root = s;
s.insertNonFull(k);
} else {
r.insertNonFull(k);
}
}
// 删除键
public void delete(T k) {
if (root == null) {
return;
}
root.delete(k);
if (root.keys.isEmpty()) {
root = root.leaf ? null : root.children.get(0);
}
}
// 查找键
public boolean search(T k) {
return root == null ? false : root.search(k) != null;
}
}4.3 B 树节点删除方法
class BTreeNode<T extends Comparable<T>> {
// 其他方法省略
// 删除键
void delete(T k) {
int idx = findKey(k);
if (idx < keys.size() && keys.get(idx).compareTo(k) == 0) {
if (leaf) {
keys.remove(idx);
} else {
deleteFromNonLeaf(idx);
}
} else {
if (leaf) {
return;
}
boolean flag = (idx == keys.size());
if (children.get(idx).keys.size() < t) {
fill(idx);
}
if (flag && idx > keys.size()) {
children.get(idx - 1).delete(k);
} else {
children.get(idx).delete(k);
}
}
}
// 从非叶子节点删除
void deleteFromNonLeaf(int idx) {
T k = keys.get(idx);
if (children.get(idx).keys.size() >= t) {
T pred = getPred(idx);
keys.set(idx, pred);
children.get(idx).delete(pred);
} else if (children.get(idx + 1).keys.size() >= t) {
T succ = getSucc(idx);
keys.set(idx, succ);
children.get(idx + 1).delete(succ);
} else {
merge(idx);
children.get(idx).delete(k);
}
}
// 获取前驱
T getPred(int idx) {
BTreeNode<T> cur = children.get(idx);
while (!cur.leaf) {
cur = cur.children.get(cur.keys.size());
}
return cur.keys.get(cur.keys.size() - 1);
}
// 获取后继
T getSucc(int idx) {
BTreeNode<T> cur = children.get(idx + 1);
while (!cur.leaf) {
cur = cur.children.get(0);
}
return cur.keys.get(0);
}
// 填充子节点
void fill(int idx) {
if (idx != 0 && children.get(idx - 1).keys.size() >= t) {
borrowFromPrev(idx);
} else if (idx != keys.size() && children.get(idx + 1).keys.size() >= t) {
borrowFromNext(idx);
} else {
if (idx != keys.size()) {
merge(idx);
} else {
merge(idx - 1);
}
}
}
// 从前一个子节点借
void borrowFromPrev(int idx) {
BTreeNode<T> child = children.get(idx);
BTreeNode<T> sibling = children.get(idx - 1);
for (int i = child.keys.size() - 1; i >= 0; i--) {
child.keys.set(i + 1, child.keys.get(i));
}
if (!child.leaf) {
for (int i = child.children.size() - 1; i >= 0; i--) {
child.children.set(i + 1, child.children.get(i));
}
}
child.keys.set(0, keys.get(idx - 1));
if (!child.leaf) {
child.children.set(0, sibling.children.remove(sibling.children.size() - 1));
}
keys.set(idx - 1, sibling.keys.remove(sibling.keys.size() - 1));
}
// 从下一个子节点借
void borrowFromNext(int idx) {
BTreeNode<T> child = children.get(idx);
BTreeNode<T> sibling = children.get(idx +
1);
child.keys.add(keys.get(idx));
if (!child.leaf) {
child.children.add(sibling.children.remove(0));
}
keys.set(idx, sibling.keys.remove(0));
}
// 合并子节点
void merge(int idx) {
BTreeNode<T> child = children.get(idx);
BTreeNode<T> sibling = children.get(idx + 1);
child.keys.add(keys.remove(idx));
for (int i = 0; i < sibling.keys.size(); i++) {
child.keys.add(sibling.keys.get(i));
}
if (!child.leaf) {
for (int i = 0; i < sibling.children.size(); i++) {
child.children.add(sibling.children.get(i));
}
}
children.remove(sibling);
}
// 查找键
BTreeNode<T> search(T k) {
int idx = findKey(k);
if (idx < keys.size() && keys.get(idx).compareTo(k) == 0) {
return this;
}
if (leaf) {
return null;
}
return children.get(idx).search(k);
}
}5. 示例测试
public class Main {
public static void main(String[] args) {
BTree<Integer> bTree = new BTree<>(3);
bTree.insert(10);
bTree.insert(20);
bTree.insert(5);
bTree.insert(6);
bTree.insert(12);
bTree.insert(30);
bTree.insert(7);
bTree.insert(17);
System.out.println("B树创建成功。");
if (bTree.search(6)) {
System.out.println("找到键 6");
} else {
System.out.println("未找到键 6");
}
bTree.delete(6);
if (bTree.search(6)) {
System.out.println("找到键 6");
} else {
System.out.println("未找到键 6");
}
}
}6. 运行效果
运行上述代码将演示 B 树的插入和删除操作。B 树将按顺序插入键，然后删除键 6 并进行查找验证。
7. 总结
本文详细介绍了 B 树的数据结构及其在 Java 中的实现，包括插入、删除和查找操作。通过理解和实践这些内容，可以帮助你更好地掌握 B 树的实现和应用。希望本文对你有所帮助，如有任何疑问或建议，欢迎留言讨论。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-08-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
