算法——B 树

引言

本文整理了B-树的实现,方便以后查阅。算法相关的文章均收录于<算法系列文章>

B 树

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
package bbm.tree;

/**
* B树是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。B树,概括来说是
* 一个一般化的二叉查找树一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同,B树适用于读写相对大的数据块的存储系统,例如磁盘。B树减少
* 定位记录时所经历的中间过程,从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
*
* @author bbm
*/
public class BTree {
private static final int t = 5;
Node root;

public BTree() {
Node root = new Node();
root.leaf = true;
// write-disk root
this.root = root;
}

/**
* 搜索 B 树和搜索二叉树很像,但是它没法做到 2 路选择,而是一个多路选择
* 它将返回节点 y 和与 key 相等的下标 i,即 y.keys[i] = key, 如果 key 不存在的话,则返回 null
*/
private SearchResult search(Node x, int key) {
int i = 0;
while (i < x.keySize && key > x.keys[i]) {
i++;
}
if (i < x.keySize && key == x.keys[i]) {
return new SearchResult(x, i);
} else if (x.leaf) {
return null;
} else {
// read-disk x.children[i]
return search(x.children[i], key);
}
}

public SearchResult search(int key) {
return search(root, key);
}

/**
* 使用此函数来拆分 x.children[i],它为一个满节点,主要分两步
* 1. 新建一个节点 z,将 x.children[i] 的后半段拷贝进 z,包括 keys 和 children
* 2. 在 x 节点的 keys 中插入 x.children[i] 和 z 的中间 key,并将 z 插入到 x 的 children 中
*/
private void splitChild(Node x, int i) {
Node z = new Node();
Node y = x.children[i];
z.leaf = y.leaf;
z.keySize = t - 1;
for (int j = 0; j < t - 1; j++) {
z.keys[j] = y.keys[t + j];
y.keys[t + j] = 0;
}
if (!y.leaf) {
for (int j = 0; j < t; j++) {
z.children[j] = y.children[t + j];
y.children[t + j] = null;
}
}
y.keySize = t - 1;
for (int j = x.keySize; j >= i + 1; j--) {
x.children[j + 1] = x.children[j];
}
x.children[i + 1] = z;
for (int j = x.keySize - 1; j >= i; j--) {
x.keys[j + 1] = x.keys[j];
}
x.keys[i] = y.keys[t - 1];
y.keys[t - 1] = 0;
x.keySize = x.keySize + 1;
// write-disk x
// write-disk y
// write-disk z
}

/**
* 插入过程要保证在查找合适位置的过程中将所有已满的节点进行拆分,从 root 节点出发,沿着树向下遍历,必要时通过 split child 进行拆分
*/
public void insert(int k) {
Node r = root;
if (root.keySize == 2 * t - 1) {
// 该步保证,插入过程中 root 节点肯定不是满节点
Node s = new Node();
root = s;
s.leaf = false;
s.keySize = 0;
s.children[0] = r;
// 该步实际上会将 r.keys[t-1] 拷贝到 s 的 keys 中,并将 r 的 children 拆分
splitChild(s, 0);
insertNonFull(s, k);
} else {
insertNonFull(r, k);
}
verify();
}

/**
* 将关键字 k 插入到 x 节点中,假设 x 不是满的,{@link BTree#insert(int)} 和 {@link BTree#splitChild(bbm.tree.BTree.Node, int)}
* 将保证该假设成立
*/
private void insertNonFull(Node x, int k) {
int i = x.keySize - 1;
if (x.leaf) {
// 只有叶子结点才能往 keys 插入新值
while (i >= 0 && k < x.keys[i]) {
x.keys[i + 1] = x.keys[i];
i--;
}
x.keys[i + 1] = k;
x.keySize += 1;
// disk-write x
} else {
// 不是叶子结点,看看 k 应该属于哪个 child node
while (i >= 0 && k < x.keys[i]) {
i--;
}
i = i + 1;
// disk-read x.children[i]
if (x.children[i].keySize == 2 * t - 1) {
// 这一步保证当 k 要插入到一个子节点时,该节点绝对不是一个满节点
splitChild(x, i);
// 拆分之后,要查看一下 key 应该插入到拆分之后的哪个新 node 中
if (k > x.keys[i]) {
i++;
}
}
insertNonFull(x.children[i], k);
}
}

/**
* 考虑到根结点的特殊性,对根结点为1,并且两个子结点都是t-1的情况进行了特殊的处理:
* 先对两个子结点进行合并,然后把原来的根删除,把树根指向合并后的子结点y。
* 这样B树的高度就减少了1。这也是B树高度唯一会减少的情况。
*/
public void delete(int k) {
Node r = root;
if (r.keySize == 1 && !r.leaf) {
// disk read r.children[0]
// disk read r.children[1]
Node y = r.children[0];
Node z = r.children[1];
if (y.keySize == z.keySize && y.keySize == t - 1) {
mergeChild(r, 0, y, z);
root = y;
deleteNonOne(y, k);
} else {
deleteNonOne(r, k);
}
} else {
deleteNonOne(r, k);
}
verify();
}

private void mergeChild(Node r, int i, Node y, Node z) {
y.keySize = 2 * t - 1;
for (int j = t; j < 2 * t - 1; j++) {
y.keys[j] = z.keys[j - t];
}
y.keys[t - 1] = r.keys[i];
if (!y.leaf) {
for (int j = t; j < 2 * t; j++) {
y.children[j] = z.children[j - t];
}
}
for (int j = i + 1; j < r.keySize; j++) {
r.children[j] = r.children[j + 1];
}
for (int j = i; j < r.keySize - 1; j++) {
r.keys[j] = r.keys[j + 1];
}

r.keySize -= 1;
r.keys[r.keySize] = 0;
r.children[r.keySize + 1] = null;
// disk-write y
// disk-write z
// disk-write x
}

private void deleteNonOne(Node x, int k) {
int i = 0;
if (x.leaf) {
// 当 x 是叶子结点,找到 k 所在的位置,将其删除,并将 k 之后的 keys 左移
while (i < x.keySize && k > x.keys[i]) {
i++;
}
if (i < x.keySize && k == x.keys[i]) {
for (int j = i + 1; j < x.keySize; j++) {
x.keys[j - 1] = x.keys[j];
}
x.keySize -= 1;
x.keys[x.keySize] = 0;
// disk-write x
} else {
System.out.println(k + ": key not exist in tree");
}
} else {
while (i < x.keySize && k > x.keys[i]) {
i++;
}
// disk-read x.children[i]
Node y = x.children[i];
Node z = null;
if (i < x.keySize) {
// disk-read x.children[i]
z = x.children[i + 1];
}
if (i < x.keySize && k == x.keys[i]) {
// 如果找到的 k 不处于叶子结点中,我们需要为其找到替换者以保持每个非 root 节点的 key size > t-1
if (y.keySize > t - 1) {
// 如果小于 k 的子 node key size > t -1 用其最大的 key 替换待删除的 k
int newK = searchPredecessor(y);
deleteNonOne(y, newK);
x.keys[i] = newK;
} else if (z.keySize > t - 1) {
// 如果大于 k 的子 node key size > t -1 用其最小的 key 替换待删除的 k
int newK = searchSuccessor(z);
deleteNonOne(z, newK);
x.keys[i] = newK;
} else {
// 如果两边的子 node key size 都不够大,就把它们两个合并,然后在删除 k
mergeChild(x, i, y, z);
deleteNonOne(y, k);
}
} else {
Node p = null;
if (i > 0) {
// disk-read x.children[i - 1]
p = x.children[i - 1];
}
if (y.keySize == t - 1) {
// 如果 k 节点所处的 node 节点太少的话,我们得从两边借一个节点挪进去
if (i > 0 && p.keySize > t - 1) {
// 左边的 node children 多,就借一个
shift2RightChild(x, i - 1, p, y);
} else if (i < x.keySize && z.keySize > t - 1) {
// 右边的 node children 多,就借一个
shift2LeftChild(x, i, y, z);
} else if (i > 0) {
// 左右节点的子节点都不够,如果有左节点,则左节点和 y 合并
mergeChild(x, i - 1, p, y);
y = p;
} else {
// 左右节点的子节点都不够,如果有右节点,则右节点和 y 合并
mergeChild(x, i, y, z);
}
}
deleteNonOne(y, k);
}
}
}

private void shift2LeftChild(Node x, int i, Node left, Node right) {
left.keys[left.keySize] = x.keys[i];
left.keySize += 1;
x.keys[i] = right.keys[0];
right.keySize -= 1;
for (int j = 0; j < right.keySize; j++) {
right.keys[j] = right.keys[j + 1];
}
right.keys[right.keySize] = 0;
if (!right.leaf) {
left.children[left.keySize] = right.children[0];
for (int j = 0; j <= right.keySize; j++) {
right.children[j] = right.children[j + 1];
}
right.children[right.keySize + 1] = null;
}
// disk-write x
// disk-write y
// disk-write z
}

private void shift2RightChild(Node x, int i, Node left, Node right) {
right.keySize += 1;
for (int j = right.keySize - 1; j > 0; j--) {
right.keys[j] = right.keys[j - 1];
}
right.keys[0] = x.keys[i];
x.keys[i] = left.keys[left.keySize - 1];
if (!right.leaf) {
for (int j = right.keySize - 1; j >= 0; j--) {
right.children[j + 1] = right.children[j];
}
right.children[0] = left.children[left.keySize];
left.children[left.keySize] = null;
}
left.keySize -= 1;
left.keys[left.keySize] = 0;
// disk-write x
// disk-write y
// disk-write z
}

private void verify() {
if (root == null) {
return;
}
verifyFromNode(root);
}

private void verifyFromNode(Node x) {
if (x != root && x.keySize < (t - 1)) {
throw new RuntimeException("节点关键字小于 t-1");
}
if (x.keySize > (2 * t - 1)) {
throw new RuntimeException("节点关键字大于 2 * t - 1");
}
for (int i = 1; i < x.keySize; i++) {
if (x.keys[i - 1] > x.keys[i]) {
throw new RuntimeException("节点 keys 不是升序");
}
}
if (!x.leaf) {
for (int i = 0; i < x.keySize; i++) {
if (x.children[i].keys[x.children[i].keySize - 1] > x.keys[i]) {
throw new RuntimeException("左子节点的 max key 比当前 key 大");
}
if (x.children[i + 1].keys[0] < x.keys[i]) {
throw new RuntimeException("右子节点的 min key 比当前 key 小");
}
}
}
}

private int searchPredecessor(Node z) {
Node x = z;
int i = x.keySize;
while (!x.leaf) {
// disk-read x.children[i]
x = x.children[i];
i = x.keySize;
}
return x.keys[x.keySize - 1];
}

private int searchSuccessor(Node z) {
Node x = z;
while (!x.leaf) {
// disk-read x.children[0]
x = x.children[0];
}
return x.keys[0];
}

public Node getRoot() {
return root;
}

public static class Node {
int[] keys = new int[2 * t - 1];
int keySize;
Node[] children = new Node[2 * t];
boolean leaf;
}

public static class SearchResult {
Node node;
int index;

public SearchResult(Node node, int index) {
this.node = node;
this.index = index;
}
}
}

测试 BTree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package bbm.tree;

import java.util.*;

import org.junit.jupiter.api.Test;

/**
* @author bbm
*/
class BTreeTest {
@Test
public void testBTree() {
int treeSize = 10000;
System.err.println("Building tree...");
BTree tree = new BTree();
Random rand = new Random(System.currentTimeMillis());
List<Integer> insertSet = new ArrayList<>();
int i;
for (i = 0; i < treeSize; ++i) {
int val = rand.nextInt(treeSize) + 1;

try {
tree.insert(val);
insertSet.add(val);
System.err.println("(Inserting value " + val + ")");
} catch (Exception var11) {
var11.printStackTrace();
System.exit(1);
}
}
System.out.println(insertSet.toString());
//insertSet.forEach(tree::insert);

System.err.println();
System.err.println("Searching in tree...");

for (int data : insertSet) {
BTree.SearchResult result = tree.search(data);
if (result == null || result.node.keys[result.index] != data) {
throw new RuntimeException("Search error");
}
}

for (i = 0; i < 100; i++) {
int val = rand.nextInt(treeSize * 10) + 1;
if (!insertSet.contains(val)) {
if (tree.search(val) != null) {
throw new RuntimeException("Search error");
}
}
}

System.err.println();
System.err.println("Churning tree...");

Collections.shuffle(insertSet);
List<Integer> insertSet2 = new ArrayList<>();
insertSet.forEach(data -> {
System.err.println("(Removing value " + data + ")");
tree.delete(data);
int newVal = rand.nextInt(treeSize) + 1;
System.err.println("(Inserting value " + newVal + ")");
tree.insert(newVal);
insertSet2.add(newVal);
});

System.err.println();
System.err.println("Clear tree...");
insertSet2.forEach(data -> {
System.err.println("(Removing value " + data + ")");
tree.delete(data);
});
if (tree.getRoot() != null && tree.getRoot().keySize != 0) {
System.err.println("Not clean!!!!!!!!!!!");
} else {
System.err.println("All tests passed.");
}
}
}

参考内容

[1] 《算法导论》

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者: 贝克街的流浪猫
  • 本文链接: https://www.beikejiedeliulangmao.top/algorithm/b-tree/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
  • 创作声明: 本文基于上述所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。