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 树节点类

1. import java.util.ArrayList;
2. import java.util.List;
4. class BTreeNode<T extends Comparable<T>> {
5.     int t;  // 最小度数
6.     List<T> keys;  // 存储键
7.     List<BTreeNode<T>> children;  // 存储子节点
8.     boolean leaf;  // 是否为叶子节点
10.     BTreeNode(int t, boolean leaf) {
11.         this.t = t;
12.         this.leaf = leaf;
13.         this.keys = new ArrayList<>();
14.         this.children = new ArrayList<>();
15.     }
17.     // 查找键
18.     int findKey(T k) {
19.         int idx = 0;
20.         while (idx < keys.size() && keys.get(idx).compareTo(k) < 0) {
21.             idx++;
22.         }
23.         return idx;
24.     }
26.     // 插入非满节点
27.     void insertNonFull(T k) {
28.         int i = keys.size() - 1;
30.         if (leaf) {
31.             keys.add(null);
32.             while (i >= 0 && keys.get(i).compareTo(k) > 0) {
33.                 keys.set(i + 1, keys.get(i));
34.                 i--;
35.             }
36.             keys.set(i + 1, k);
37.         } else {
38.             while (i >= 0 && keys.get(i).compareTo(k) > 0) {
39.                 i--;
40.             }
41.             if (children.get(i + 1).keys.size() == 2 * t - 1) {
42.                 splitChild(i + 1, children.get(i + 1));
43.                 if (keys.get(i + 1).compareTo(k) < 0) {
44.                     i++;
45.                 }
46.             }
47.             children.get(i + 1).insertNonFull(k);
48.         }
49.     }
51.     // 分裂子节点
52.     void splitChild(int i, BTreeNode<T> y) {
53.         BTreeNode<T> z = new BTreeNode<>(y.t, y.leaf);
54.         for (int j = 0; j < t - 1; j++) {
55.             z.keys.add(y.keys.remove(t));
56.         }
57.         if (!y.leaf) {
58.             for (int j = 0; j < t; j++) {
59.                 z.children.add(y.children.remove(t));
60.             }
61.         }
62.         children.add(i + 1, z);
63.         keys.add(i, y.keys.remove(t - 1));
64.     }
65. }

复制代码

4.2 B 树类

1. public class BTree<T extends Comparable<T>> {
2.     private BTreeNode<T> root;
3.     private int t;  // 最小度数
5.     public BTree(int t) {
6.         this.root = new BTreeNode<>(t, true);
7.         this.t = t;
8.     }
10.     // 插入键
11.     public void insert(T k) {
12.         BTreeNode<T> r = root;
13.         if (r.keys.size() == 2 * t - 1) {
14.             BTreeNode<T> s = new BTreeNode<>(t, false);
15.             s.children.add(r);
16.             s.splitChild(0, r);
17.             root = s;
18.             s.insertNonFull(k);
19.         } else {
20.             r.insertNonFull(k);
21.         }
22.     }
24.     // 删除键
25.     public void delete(T k) {
26.         if (root == null) {
27.             return;
28.         }
29.         root.delete(k);
30.         if (root.keys.isEmpty()) {
31.             root = root.leaf ? null : root.children.get(0);
32.         }
33.     }
35.     // 查找键
36.     public boolean search(T k) {
37.         return root == null ? false : root.search(k) != null;
38.     }
39. }

复制代码

4.3 B 树节点删除方法

1. class BTreeNode<T extends Comparable<T>> {
2.     // 其他方法省略
4.     // 删除键
5.     void delete(T k) {
6.         int idx = findKey(k);
7.         if (idx < keys.size() && keys.get(idx).compareTo(k) == 0) {
8.             if (leaf) {
9.                 keys.remove(idx);
10.             } else {
11.                 deleteFromNonLeaf(idx);
12.             }
13.         } else {
14.             if (leaf) {
15.                 return;
16.             }
17.             boolean flag = (idx == keys.size());
18.             if (children.get(idx).keys.size() < t) {
19.                 fill(idx);
20.             }
21.             if (flag && idx > keys.size()) {
22.                 children.get(idx - 1).delete(k);
23.             } else {
24.                 children.get(idx).delete(k);
25.             }
26.         }
27.     }
29.     // 从非叶子节点删除
30.     void deleteFromNonLeaf(int idx) {
31.         T k = keys.get(idx);
32.         if (children.get(idx).keys.size() >= t) {
33.             T pred = getPred(idx);
34.             keys.set(idx, pred);
35.             children.get(idx).delete(pred);
36.         } else if (children.get(idx + 1).keys.size() >= t) {
37.             T succ = getSucc(idx);
38.             keys.set(idx, succ);
39.             children.get(idx + 1).delete(succ);
40.         } else {
41.             merge(idx);
42.             children.get(idx).delete(k);
43.         }
44.     }
46.     // 获取前驱
47.     T getPred(int idx) {
48.         BTreeNode<T> cur = children.get(idx);
49.         while (!cur.leaf) {
50.             cur = cur.children.get(cur.keys.size());
51.         }
52.         return cur.keys.get(cur.keys.size() - 1);
53.     }
55.     // 获取后继
56.     T getSucc(int idx) {
57.         BTreeNode<T> cur = children.get(idx + 1);
58.         while (!cur.leaf) {
59.             cur = cur.children.get(0);
60.         }
61.         return cur.keys.get(0);
62.     }
64.     // 填充子节点
65.     void fill(int idx) {
66.         if (idx != 0 && children.get(idx - 1).keys.size() >= t) {
67.             borrowFromPrev(idx);
68.         } else if (idx != keys.size() && children.get(idx + 1).keys.size() >= t) {
69.             borrowFromNext(idx);
70.         } else {
71.             if (idx != keys.size()) {
72.                 merge(idx);
73.             } else {
74.                 merge(idx - 1);
75.             }
76.         }
77.     }
79.     // 从前一个子节点借
80.     void borrowFromPrev(int idx) {
81.         BTreeNode<T> child = children.get(idx);
82.         BTreeNode<T> sibling = children.get(idx - 1);
83.         for (int i = child.keys.size() - 1; i >= 0; i--) {
84.             child.keys.set(i + 1, child.keys.get(i));
85.         }
86.         if (!child.leaf) {
87.             for (int i = child.children.size() - 1; i >= 0; i--) {
88.                 child.children.set(i + 1, child.children.get(i));
89.             }
90.         }
91.         child.keys.set(0, keys.get(idx - 1));
92.         if (!child.leaf) {
93.             child.children.set(0, sibling.children.remove(sibling.children.size() - 1));
94.         }
95.         keys.set(idx - 1, sibling.keys.remove(sibling.keys.size() - 1));
96.     }
98.     // 从下一个子节点借
99.     void borrowFromNext(int idx) {
100.         BTreeNode<T> child = children.get(idx);
101.         BTreeNode<T> sibling = children.get(idx +
103. 1);
104.         child.keys.add(keys.get(idx));
105.         if (!child.leaf) {
106.             child.children.add(sibling.children.remove(0));
107.         }
108.         keys.set(idx, sibling.keys.remove(0));
109.     }
111.     // 合并子节点
112.     void merge(int idx) {
113.         BTreeNode<T> child = children.get(idx);
114.         BTreeNode<T> sibling = children.get(idx + 1);
115.         child.keys.add(keys.remove(idx));
116.         for (int i = 0; i < sibling.keys.size(); i++) {
117.             child.keys.add(sibling.keys.get(i));
118.         }
119.         if (!child.leaf) {
120.             for (int i = 0; i < sibling.children.size(); i++) {
121.                 child.children.add(sibling.children.get(i));
122.             }
123.         }
124.         children.remove(sibling);
125.     }
127.     // 查找键
128.     BTreeNode<T> search(T k) {
129.         int idx = findKey(k);
130.         if (idx < keys.size() && keys.get(idx).compareTo(k) == 0) {
131.             return this;
132.         }
133.         if (leaf) {
134.             return null;
135.         }
136.         return children.get(idx).search(k);
137.     }
138. }

复制代码

5. 示例测试

1. public class Main {
2.     public static void main(String[] args) {
3.         BTree<Integer> bTree = new BTree<>(3);
5.         bTree.insert(10);
6.         bTree.insert(20);
7.         bTree.insert(5);
8.         bTree.insert(6);
9.         bTree.insert(12);
10.         bTree.insert(30);
11.         bTree.insert(7);
12.         bTree.insert(17);
14.         System.out.println("B树创建成功。");
16.         if (bTree.search(6)) {
17.             System.out.println("找到键 6");
18.         } else {
19.             System.out.println("未找到键 6");
20.         }
22.         bTree.delete(6);
23.         if (bTree.search(6)) {
24.             System.out.println("找到键 6");
25.         } else {
26.             System.out.println("未找到键 6");
27.         }
28.     }
29. }

复制代码

6. 运行结果

运行上述代码将演示 B 树的插入和删除操纵。B 树将按次序插入键，然后删除键 6 并举行查找验证。
7. 总结

本文具体先容了 B 树的数据结构及其在 Java 中的实现，包罗插入、删除和查找操纵。通过明白和实践这些内容，可以资助你更好地把握 B 树的实现和应用。盼望本文对你有所资助，如有任何疑问或发起，接待留言讨论。