标签：数据 entry 优势 static 加载 父节点 try 除了 插入
一颗m阶B+树满足以下几个条件：
1.除根节点外的节点的关键字个数最大为m-1,最小为m/2
2.除叶节点外的每个节点的孩子节点的数目为该节点关键字个数加一，这些孩子节点的的关键字的范围与父节点关键字的大小对应（这个看图才看的清楚）
3.叶子节点存放着所有的关键字，叶子节点间按关键字的大小用指针相互连接。内部节点以叶子节点的关键字的最小值作为索引
B+树相较于B树最大的优势在于数据全部都存在于叶子节点，叶子节点间以指针相互连接，这样在进行按照索引的范围查找的时候就只需要遍历前后指针就可以完成，而B树要一个一个索引去进行查找，效率差别很大。
B+树相较于hash的优势在于B+树不用一次将数据全部加载到内存，而是先确定要查询索引的地址，将对应的地址的索引加载到内存。而hash需要将全部的数据一次性加载到内存才能完成查找。
首先定义一个节点类
1 import java.util.List;
2
3 /*节点类*/
4 public class Node {
5
6 //节点的子节点
7 private List nodes;
8 //节点的键值对
9 private List keyAndValue;
10 //节点的后节点
11 private Node nextNode;
12 //节点的前节点
13 private Node previousNode;
14 //节点的父节点
15 private Node parantNode;
16
17 public Node( List nodes, List keyAndValue, Node nextNode,Node previousNode, Node parantNode) {
18 this.nodes = nodes;
19 this.keyAndValue = keyAndValue;
20 this.nextNode = nextNode;
21 this.parantNode = parantNode;
22 this.previousNode = previousNode;
23 }
24
25 boolean isLeaf() {
26 return nodes==null;
27 }
28
29 boolean isHead() {
30 return previousNode == null;
31 }
32
33 boolean isTail() {
34 return nextNode == null;
35 }
36
37 boolean isRoot() {
38 return parantNode == null;
39 }
40
41
42 List getNodes() {
43 return nodes;
44 }
45
46 void setNodes(List nodes) {
47 this.nodes = nodes;
48 }
49
50
51 List getKeyAndValue() {
52 return keyAndValue;
53 }
54
55 // public void setKeyAndValue(List KeyAndValue) {
56 // this.keyAndValue = KeyAndValue;
57 // }
58
59 Node getNextNode() {
60 return nextNode;
61 }
62
63 void setNextNode(Node nextNode) {
64 this.nextNode = nextNode;
65 }
66
67 Node getParantNode() {
68 return parantNode;
69 }
70
71 void setParantNode(Node parantNode) {
72 this.parantNode = parantNode;
73 }
74
75 Node getPreviousNode() {
76 return previousNode;
77 }
78
79 void setPreviousNode(Node previousNode) {
80 this.previousNode = previousNode;
81 }
82 }
定义一个存储关键字和数据的类
1 public class KeyAndValue implements Comparable{
2 /*存储索引关键字*/
3 private int key;
4 /*存储数据*/
5 private Object value;
6
7 @Override
8 public int compareTo(KeyAndValue o) {
9 //根据key的值升序排列
10 return this.key - o.key;
11 }
12
13 public int getKey() {
14 return key;
15 }
16
17 public void setKey(int key) {
18 this.key = key;
19 }
20
21 public Object getValue() {
22 return value;
23 }
24
25 public void setValue(Object value) {
26 this.value = value;
27 }
28
29 KeyAndValue(int key, Object value) {
30 this.key = key;
31 this.value = value;
32 }
33 }
最后是具体的实现代码
1 import java.util.*;
2
3
4 public class Btree {
5 private static final String NODE = "NODE";
6 static final String INT = "INT";
7 private static final String PRENODE = "PRENODE";
8 private static final String NEXTNODE = "NEXTNODE";
9 //B+树的阶数
10 private int rank;
11 //根节点
12 private Node root;
13 //头结点
14 private Node head;
15
16 Btree(int rank) {
17 this.rank = rank;
18 }
19
20 public Node getRoot() {
21 return root;
22 }
23
24 public void insert(KeyAndValue entry) {
25 List keyAndValues1 = new ArrayList();
26 //插入第一个节点
27 if (head == null) {
28 keyAndValues1.add(entry);
29 head = new Node(null, keyAndValues1, null, null, null);
30 root = new Node(null, keyAndValues1, null, null, null);
31 } else {
32 Node node = head;
33 //遍历链表，找到插入键值对对应的节点
34 while (node != null) {
35 List keyAndValues = node.getKeyAndValue();
36 int exitFlag = 0;
37 //如果插入的键的值和当前节点键值对集合中的某个键的值相等，则直接替换value
38 for (KeyAndValue KV : keyAndValues) {
39 if (KV.getKey() == entry.getKey()) {
40 KV.setValue(entry.getValue());
41 exitFlag = 1;
42 break;
43 }
44 }
45 //如果插入的键已经有了，则退出循环
46 if (exitFlag == 1) {
47 break;
48 }
49 //如果当前节点是最后一个节点或者要插入的键值对的键的值小于下一个节点的键的最小值，则直接插入当前节点
50 if (node.getNextNode() == null || node.getNextNode().getKeyAndValue().get(0).getKey() >= entry.getKey()) {
51 splidNode(node, entry);
52 break;
53 }
54 //移动指针
55 node = node.getNextNode();
56 }
57 }
58 }
59
60
61 //判断是否需要拆分节点
62 private void splidNode(Node node, KeyAndValue addkeyAndValue) {
63 List keyAndValues = node.getKeyAndValue();
64
65 if (keyAndValues.size() == rank - 1) {
66 //先插入待添加的节点
67 keyAndValues.add(addkeyAndValue);
68 Collections.sort(keyAndValues);
69 //取出当前节点的键值对集合
70 //取出原来的key-value集合中间位置的下标
71 int mid = keyAndValues.size() / 2;
72 //取出原来的key-value集合中间位置的键
73 int midKey = keyAndValues.get(mid).getKey();
74 //构造一个新的键值对，不是叶子节点的节点不存储value的信息
75 KeyAndValue midKeyAndValue = new KeyAndValue(midKey, "");
76 //将中间位置左边的键值对封装成集合对象
77 List leftKeyAndValues = new ArrayList();
78 for (int i = 0; i ) {
79 leftKeyAndValues.add(keyAndValues.get(i));
80 }
81 //将中间位置右边边的键值对封装成集合对象
82 List rightKeyAndValues = new ArrayList();
83 //如果是叶子节点则在原节点中保留上移的key-value，否则原节点删除上移的key-value
84 int k;
85 if (node.isLeaf()) {
86 k = mid;
87 } else {
88 k = mid + 1;
89 }
90 for (int i = k; i ) {
91 rightKeyAndValues.add(keyAndValues.get(i));
92 }
93 //对左右两边的元素重排序
94 Collections.sort(leftKeyAndValues);
95 Collections.sort(rightKeyAndValues);
96 //以mid为界限将当前节点分列成两个节点，维护前指针和后指针
97 Node rightNode;
98 Node leftNode;
99 // if (node.isLeaf()) {
100 //如果是叶子节点维护前后指针
101 rightNode = new Node(null, rightKeyAndValues, node.getNextNode(), null, node.getParantNode());
102 leftNode = new Node(null, leftKeyAndValues, rightNode, node.getPreviousNode(), node.getParantNode());
103 rightNode.setPreviousNode(leftNode);
104 // } else {
105 // //如果不是叶子不维护前后指针
106 // rightNode = new Node(null, rightKeyAndValues, null, null, node.getParantNode());
107 // leftNode = new Node(null, leftKeyAndValues, null, null, node.getParantNode());
108 // }
109 //如果当前分裂的节点有孩子节点,设置分裂后节点和孩子节点的关系
110 if (node.getNodes() != null) {
111 //取得所有地孩子节点
112 List nodes = node.getNodes();
113 List leftNodes = new ArrayList();
114 List rightNodes = new ArrayList();
115 for (Node childNode : nodes) {
116 //取得当前孩子节点的最大键值
117 int max = childNode.getKeyAndValue().get(childNode.getKeyAndValue().size() - 1).getKey();
118 if (max midKeyAndValue.getKey()) {
119 //小于mid处的键的数是左节点的子节点
120 leftNodes.add(childNode);
121 childNode.setParantNode(leftNode);
122 } else {
123 //大于mid处的键的数是右节点的子节点
124 rightNodes.add(childNode);
125 childNode.setParantNode(rightNode);
126 }
127 }
128 leftNode.setNodes(leftNodes);
129 rightNode.setNodes(rightNodes);
130 }
131
132 //当前节点的前节点
133 Node preNode = node.getPreviousNode();
134 //分裂节点后将分裂节点的前节点的后节点设置为左节点
135 if (preNode != null) {
136 preNode.setNextNode(leftNode);
137 }
138
139 //当前节点的后节点
140 Node nextNode = node.getNextNode();
141 //分裂节点后将分裂节点的后节点的前节点设置为右节点
142 if (nextNode != null) {
143 nextNode.setPreviousNode(rightNode);
144 }
145
146 //如果由头结点分裂，则分裂后左边的节点为头节点
147 if (node == head) {
148 head = leftNode;
149 }
150
151 //父节点的子节点
152 List childNodes = new ArrayList();
153 childNodes.add(rightNode);
154 childNodes.add(leftNode);
155 //分裂
156 //当前节点无父节点
157 if (node.getParantNode() == null) {
158 //父节点的键值对
159 List parentKeyAndValues = new ArrayList();
160 parentKeyAndValues.add(midKeyAndValue);
161 //构造父节点
162 Node parentNode = new Node(childNodes, parentKeyAndValues, null, null, null);
163 //将子节点与父节点关联
164 rightNode.setParantNode(parentNode);
165 leftNode.setParantNode(parentNode);
166 //当前节点为根节点
167 root = parentNode;
168 } else {
169 Node parentNode = node.getParantNode();
170 //将原来的孩子节点（除了被拆分的节点）和新的孩子节点（左孩子和右孩子）合并之后与父节点关联
171 childNodes.addAll(parentNode.getNodes());
172 //移除正在被拆分的节点
173 childNodes.remove(node);
174 //将子节点与父节点关联
175 parentNode.setNodes(childNodes);
176 rightNode.setParantNode(parentNode);
177 leftNode.setParantNode(parentNode);
178 if (parentNode.getParantNode() == null) {
179 root = parentNode;
180 }
181 //当前节点有父节点,递归调用拆分的方法,将父节点拆分
182 splidNode(parentNode, midKeyAndValue);
183 }
184 } else {
185 keyAndValues.add(addkeyAndValue);
186 //排序
187 Collections.sort(keyAndValues);
188 }
189 }
190
191
192 //打印B+树
193 void printBtree(Node root) {
194 if (root == this.root) {
195 //打印根节点内的元素
196 printNode(root);
197 System.out.println();
198 }
199 if (root == null) {
200 return;
201 }
202
203 //打印子节点的元素
204 if (root.getNodes() != null) {
205 //找到最左边的节点
206 Node leftNode = null;
207 Node tmpNode = null;
208 List childNodes = root.getNodes();
209 for (Node node : childNodes) {
210 if (node.getPreviousNode() == null) {
211 leftNode = node;
212 tmpNode = node;
213 }
214 }
215
216 while (leftNode != null) {
217 //从最左边的节点向右打印
218 printNode(leftNode);
219 System.out.print("|");
220 leftNode = leftNode.getNextNode();
221 }
222 System.out.println();
223 printBtree(tmpNode);
224 }
225 }
226
227 //打印一个节点内的元素
228 private void printNode(Node node) {
229 List keyAndValues = node.getKeyAndValue();
230 for (int i = 0; i ) {
231 if (i != (keyAndValues.size() - 1)) {
232 System.out.print(keyAndValues.get(i).getKey() + ",");
233 } else {
234 System.out.print(keyAndValues.get(i).getKey());
235 }
236 }
237 }
238
239 public Object search(int key, Node node, String mode) {
240
241 //如果是叶子节点则直接取值
242 if (node.isLeaf()) {
243 List keyAndValues = node.getKeyAndValue();
244 for (KeyAndValue keyAndValue : keyAndValues) {
245 if (keyAndValue.getKey() == key) {
246 switch (mode) {
247 case NODE:
248 return node;
249 case INT:
250 return keyAndValue.getValue();
251 }
252 }
253 }
254 return null;
255 }
256
257
258 List nodes = node.getNodes();
259 //如果寻找的key小于节点的键的最小值
260 int minKey = node.getKeyAndValue().get(0).getKey();
261 if (key minKey) {
262 for (Node n : nodes) {
263 List keyAndValues = n.getKeyAndValue();
264 //找到子节点集合中最大键小于父节点最小键节点
265 if (keyAndValues.get(keyAndValues.size() - 1).getKey() minKey) {
266 return search(key, n, mode);
267 }
268 }
269 }
270 //如果寻找的key大于节点的键的最大值
271 int maxKey = getMaxKeyInNode(node);
272 if (key >= maxKey) {
273 for (Node n : nodes) {
274 List keyAndValues = n.getKeyAndValue();
275 //找到子节点集合中最小键大于等于父节点最小大键节点
276 if (keyAndValues.get(0).getKey() >= maxKey) {
277 return search(key, n, mode);
278 }
279 }
280 }
281
282 //如果寻找的key在最大值和最小值之间，首先定位到最窄的区间
283 int min = getLeftBoundOfKey(node, key);
284 int max = getRightBoundOfKey(node, key);
285
286
287 //去所有的子节点中找键的范围在min和max之间的节点
288 for (Node n : nodes) {
289 List kvs = n.getKeyAndValue();
290 //找到子节点集合中键的范围在min和max之间的节点
291 if (kvs.get(0).getKey() >= min && kvs.get(kvs.size() - 1).getKey() max) {
292 return search(key, n, mode);
293 }
294 }
295 return null;
296 }
297
298
299 public boolean delete(int key) {
300 System.out.println("delete:" + key);
301 System.out.println();
302
303 //首先找到要删除的key所在的节点
304 Node deleteNode = (Node) search(key, root, NODE);
305 //如果没找到则删除失败
306 if (deleteNode == null) {
307 return false;
308 }
309
310 if (deleteNode == root) {
311 delKeyAndValue(root.getKeyAndValue(), key);
312 return true;
313 }
314
315 if (deleteNode == head && isNeedMerge(head)) {
316 head = head.getNextNode();
317 }
318
319 return merge(deleteNode, key);
320 }
321
322
323 //平衡当前节点和前节点或者后节点的数量，使两者的数量都满足条件
324 private boolean balanceNode(Node node, Node bratherNode, String nodeType) {
325 if (bratherNode == null) {
326 return false;
327 }
328 List delKeyAndValues = node.getKeyAndValue();
329 if (isMoreElement(bratherNode)) {
330 List bratherKeyAndValues = bratherNode.getKeyAndValue();
331 int bratherSize = bratherKeyAndValues.size();
332 //兄弟节点删除挪走的键值对
333 KeyAndValue keyAndValue = null;
334 KeyAndValue keyAndValue1;
335 switch (nodeType) {
336 case PRENODE:
337 keyAndValue = bratherKeyAndValues.remove(bratherSize - 1);
338 keyAndValue1 = getKeyAndValueinMinAndMax(node.getParantNode(), keyAndValue.getKey(), getMinKeyInNode(node));
339 keyAndValue1.setKey(keyAndValue.getKey());
340 break;
341 case NEXTNODE:
342 keyAndValue = bratherKeyAndValues.remove(0);
343 keyAndValue1 = getKeyAndValueinMinAndMax(node.getParantNode(), getMaxKeyInNode(node), keyAndValue.getKey());
344 keyAndValue1.setKey(bratherKeyAndValues.get(0).getKey());
345 break;
346 }
347 //当前节点添加从前一个节点得来的键值对
348 delKeyAndValues.add(keyAndValue);
349
350 //对键值对重排序
351 Collections.sort(delKeyAndValues);
352 return true;
353 }
354 return false;
355 }
356
357 public boolean merge(Node node, int key) {
358 List delKeyAndValues = node.getKeyAndValue();
359 //首先删除该key-vaule
360 delKeyAndValue(delKeyAndValues, key);
361 //如果要删除的节点的键值对的数目小于节点最大键值对数目*填充因子
362 if (isNeedMerge(node)) {
363 Boolean isBalance;
364 //如果左节点有富余的键值对，则取一个到当前节点
365 Node preNode = getPreviousNode(node);
366 isBalance = balanceNode(node, preNode, PRENODE);
367 //如果此时已经平衡，则已经删除成功
368 if (isBalance) return true;
369
370 //如果右兄弟节点有富余的键值对，则取一个到当前节点
371 Node nextNode = getNextNode(node);
372 isBalance = balanceNode(node, nextNode, NEXTNODE);
373
374 return isBalance || mergeNode(node, key);
375 } else {
376 return true;
377 }
378 }
379
380 //合并节点
381 //key 待删除的key
382 private boolean mergeNode(Node node, int key) {
383 if (node.isRoot()) {
384 return false;
385 }
386 Node preNode;
387 Node nextNode;
388 Node parentNode = node.getParantNode();
389 List childNodes = parentNode.getNodes();
390 List childNodes1 = node.getNodes();
391 List parentKeyAndValue = parentNode.getKeyAndValue();
392 List keyAndValues = node.getKeyAndValue();
393
394 if (node.isLeaf()) {
395 if (parentKeyAndValue.size() == 1 && parentNode != root) {
396 return true;
397 }
398 preNode = getPreviousNode(node);
399 nextNode = getNextNode(node);
400 if (preNode != null) {
401 List preKeyAndValues = preNode.getKeyAndValue();
402 keyAndValues.addAll(preKeyAndValues);
403 if (preNode.isHead()) {
404 head = node;
405 node.setPreviousNode(null);
406 } else {
407 preNode.getPreviousNode().setNextNode(node);
408 node.setPreviousNode(preNode.getPreviousNode());
409 }
410 //将合并后节点的后节点设置为当前节点的后节点
411 preNode.setNextNode(node.getNextNode());
412 KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, getMinKeyInNode(preNode), key);
413 delKeyAndValue(parentKeyAndValue, keyAndValue.getKey());
414 if (parentKeyAndValue.isEmpty()) {
415 root = node;
416 } else {
417 //删除当前节点
418 childNodes.remove(preNode);
419 }
420 Collections.sort(keyAndValues);
421 merge(parentNode, key);
422 return true;
423 }
424
425 if (nextNode != null) {
426 List nextKeyAndValues = nextNode.getKeyAndValue();
427 keyAndValues.addAll(nextKeyAndValues);
428 if (nextNode.isTail()) {
429 node.setPreviousNode(null);
430 } else {
431 nextNode.getNextNode().setPreviousNode(node);
432 node.setNextNode(nextNode.getNextNode());
433 }
434
435 KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, key, getMinKeyInNode(nextNode));
436 delKeyAndValue(parentKeyAndValue, keyAndValue.getKey());
437 if (parentKeyAndValue.isEmpty()) {
438 root = node;
439 node.setParantNode(null);
440 } else {
441 //删除当前节点
442 childNodes.remove(nextNode);
443 }
444 Collections.sort(keyAndValues);
445 merge(parentNode, key);
446 return true;
447 }
448 //前节点和后节点都等于null那么是root节点
449 return false;
450 } else {
451 preNode = getPreviousNode(node);
452 nextNode = getNextNode(node);
453 if (preNode != null) {
454 //将前一个节点和当前节点还有父节点中的相应Key-value合并
455 List preKeyAndValues = preNode.getKeyAndValue();
456 preKeyAndValues.addAll(keyAndValues);
457 int min = getMaxKeyInNode(preNode);
458 int max = getMinKeyInNode(node);
459 //父节点中移除这个key-value
460 KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, min, max);
461 parentKeyAndValue.remove(keyAndValue);
462 if (parentKeyAndValue.isEmpty()) {
463 root = preNode;
464 node.setParantNode(null);
465 preNode.setParantNode(null);
466 } else {
467 childNodes.remove(node);
468 }
469 assert nextNode != null;
470 preNode.setNextNode(nextNode.getNextNode());
471 //前节点加上一个当前节点的所有子节点中最小key的key-value
472 KeyAndValue minKeyAndValue = getMinKeyAndValueInChildNode(node);
473 assert minKeyAndValue != null;
474 KeyAndValue keyAndValue1 = new KeyAndValue(minKeyAndValue.getKey(), minKeyAndValue.getValue());
475 preKeyAndValues.add(keyAndValue1);
476 List preChildNodes = preNode.getNodes();
477 preChildNodes.addAll(node.getNodes());
478 //将当前节点的孩子节点的父节点设为当前节点的后节点
479 for (Node node1 : childNodes1) {
480 node1.setParantNode(preNode);
481 }
482 Collections.sort(preKeyAndValues);
483 merge(parentNode, key);