点击刷新
-
定义
一颗m阶B+树满足以下几个条件：
1.除根节点外的节点的关键字个数最大为m-1,最小为m/2
2.除叶节点外的每个节点的孩子节点的数目为该节点关键字个数加一，这些孩子节点的的关键字的范围与父节点关键字的大小对应（这个看图才看的清楚）
3.叶子节点存放着所有的关键字，叶子节点间按关键字的大小用指针相互连接。内部节点以叶子节点的关键字的最小值作为索引
-
B+树的优势
B+树相较于B树最大的优势在于数据全部都存在于叶子节点，叶子节点间以指针相互连接，这样在进行按照索引的范围查找的时候就只需要遍历前后指针就可以完成，而B树要一个一个索引去进行查找，效率差别很大。
B+树相较于hash的优势在于B+树不用一次将数据全部加载到内存，而是先确定要查询索引的地址，将对应的地址的索引加载到内存。而hash需要将全部的数据一次性加载到内存才能完成查找。
-
B+树代码实现
首先定义一个节点类
1 import java.util.List; 2 3 /*节点类*/ 4 public class Node { 5 6 //节点的子节点 7 private List<Node> nodes; 8 //节点的键值对 9 private List<KeyAndValue> keyAndValue; 10 //节点的后节点 11 private Node nextNode; 12 //节点的前节点 13 private Node previousNode; 14 //节点的父节点 15 private Node parantNode; 16 17 public Node( List<Node> nodes, List<KeyAndValue> 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<Node> getNodes() { 43 return nodes; 44 } 45 46 void setNodes(List<Node> nodes) { 47 this.nodes = nodes; 48 } 49 50 51 List<KeyAndValue> getKeyAndValue() { 52 return keyAndValue; 53 } 54 55 // public void setKeyAndValue(List<KeyAndValue> 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<KeyAndValue>{ 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<KeyAndValue> 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<KeyAndValue> 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<KeyAndValue> 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<KeyAndValue> leftKeyAndValues = new ArrayList<>(); 78 for (int i = 0; i < mid; i++) { 79 leftKeyAndValues.add(keyAndValues.get(i)); 80 } 81 //将中间位置右边边的键值对封装成集合对象 82 List<KeyAndValue> 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 < rank; 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<Node> nodes = node.getNodes(); 113 List<Node> leftNodes = new ArrayList<>(); 114 List<Node> 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<Node> childNodes = new ArrayList<>(); 153 childNodes.add(rightNode); 154 childNodes.add(leftNode); 155 //分裂 156 //当前节点无父节点 157 if (node.getParantNode() == null) { 158 //父节点的键值对 159 List<KeyAndValue> 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<Node> 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<KeyAndValue> keyAndValues = node.getKeyAndValue(); 230 for (int i = 0; i < keyAndValues.size(); 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<KeyAndValue> 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<Node> nodes = node.getNodes(); 259 //如果寻找的key小于节点的键的最小值 260 int minKey = node.getKeyAndValue().get(0).getKey(); 261 if (key < minKey) { 262 for (Node n : nodes) { 263 List<KeyAndValue> 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<KeyAndValue> 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<KeyAndValue> 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<KeyAndValue> delKeyAndValues = node.getKeyAndValue(); 329 if (isMoreElement(bratherNode)) { 330 List<KeyAndValue> 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<KeyAndValue> 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<Node> childNodes = parentNode.getNodes(); 390 List<Node> childNodes1 = node.getNodes(); 391 List<KeyAndValue> parentKeyAndValue = parentNode.getKeyAndValue(); 392 List<KeyAndValue> 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<KeyAndValue> 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<KeyAndValue> 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<KeyAndValue> 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<Node> 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); 484 return true; 485 } 486 487 if (nextNode != null) { 488 //将后一个节点和当前节点还有父节点中的相应Key-value合并 489 List<KeyAndValue> nextKeyAndValues = nextNode.getKeyAndValue(); 490 nextKeyAndValues.addAll(keyAndValues); 491 492 int min = getMaxKeyInNode(node); 493 int max = getMinKeyInNode(nextNode); 494 //父节点中移除这个key-value 495 KeyAndValue keyAndValue = getKeyAndValueinMinAndMax(parentNode, min, max); 496 parentKeyAndValue.remove(keyAndValue); 497 childNodes.remove(node); 498 if (parentKeyAndValue.isEmpty()) { 499 root = nextNode; 500 nextNode.setParantNode(null); 501 } else { 502 childNodes.remove(node); 503 } 504 nextNode.setPreviousNode(node.getPreviousNode()); 505 //后节点加上一个当后节点的所有子节点中最小key的key-value 506 KeyAndValue minKeyAndValue = getMinKeyAndValueInChildNode(nextNode); 507 assert minKeyAndValue != null; 508 KeyAndValue keyAndValue1 = new KeyAndValue(minKeyAndValue.getKey(), minKeyAndValue.getValue()); 509 nextKeyAndValues.add(keyAndValue1); 510 List<Node> nextChildNodes = nextNode.getNodes(); 511 nextChildNodes.addAll(node.getNodes()); 512 //将当前节点的孩子节点的父节点设为当前节点的后节点 513 for (Node node1 : childNodes1) { 514 node1.setParantNode(nextNode); 515 } 516 Collections.sort(nextKeyAndValues); 517 merge(parentNode, key); 518 return true; 519 } 520 return false; 521 } 522 } 523 524 //得到当前节点的前节点 525 private Node getPreviousNode(Node node) { 526 if (node.isRoot()) { 527 return null; 528 } 529 530 Node parentNode = node.getParantNode(); 531 //得到兄弟节点 532 List<Node> nodes = parentNode.getNodes(); 533 List<KeyAndValue> keyAndValues = new ArrayList<>(); 534 for (Node n : nodes) { 535 List<KeyAndValue> list = n.getKeyAndValue(); 536 int maxKeyAndValue = list.get(list.size() - 1).getKey(); 537 if (maxKeyAndValue < getMinKeyInNode(node)) { 538 keyAndValues.add(new KeyAndValue(maxKeyAndValue, n)); 539 } 540 } 541 Collections.sort(keyAndValues); 542 if (keyAndValues.isEmpty()) { 543 return null; 544 } 545 return (Node) keyAndValues.get(keyAndValues.size() - 1).getValue(); 546 } 547 548 549 //得到当前节点的后节点 550 private Node getNextNode(Node node) { 551 if (node.isRoot()) { 552 return null; 553 } 554 555 Node parentNode = node.getParantNode(); 556 //得到兄弟节点 557 List<Node> nodes = parentNode.getNodes(); 558 List<KeyAndValue> keyAndValues = new ArrayList<>(); 559 for (Node n : nodes) { 560 List<KeyAndValue> list = n.getKeyAndValue(); 561 int minKeyAndValue = list.get(0).getKey(); 562 if (minKeyAndValue > getMaxKeyInNode(node)) { 563 keyAndValues.add(new KeyAndValue(minKeyAndValue, n)); 564 } 565 } 566 Collections.sort(keyAndValues); 567 if (keyAndValues.isEmpty()) { 568 return null; 569 } 570 return (Node) keyAndValues.get(0).getValue(); 571 } 572 573 574 private int getMinKeyInNode(Node node) { 575 List<KeyAndValue> keyAndValues = node.getKeyAndValue(); 576 return keyAndValues.get(0).getKey(); 577 } 578 579 private int getMaxKeyInNode(Node node) { 580 List<KeyAndValue> keyAndValues = node.getKeyAndValue(); 581 return keyAndValues.get(keyAndValues.size() - 1).getKey(); 582 } 583 584 585 private int getLeftBoundOfKey(Node node, int key) { 586 int left = 0; 587 List<KeyAndValue> keyAndValues = node.getKeyAndValue(); 588 for (int i = 0; i < keyAndValues.size(); i++) { 589 if (keyAndValues.get(i).getKey() <= key && keyAndValues.get(i + 1).getKey() > key) { 590 left = keyAndValues.get(i).getKey(); 591 break; 592 } 593 } 594 return left; 595 } 596 597 private int getRightBoundOfKey(Node node, int key) { 598 int right = 0; 599 List<KeyAndValue> keyAndValues = node.getKeyAndValue(); 600 for (int i = 0; i < keyAndValues.size(); i++) { 601 if (keyAndValues.get(i).getKey() <= key && keyAndValues.get(i + 1).getKey() > key) { 602 right = keyAndValues.get(i + 1).getKey(); 603 break; 604 } 605 } 606 return right; 607 } 608 609 610 private void delKeyAndValue(List<KeyAndValue> keyAndValues, int key) { 611 for (KeyAndValue keyAndValue : keyAndValues) { 612 if (keyAndValue.getKey() == key) { 613 keyAndValues.remove(keyAndValue); 614 break; 615 } 616 } 617 } 618 619 //找到node的键值对中在min和max中的键值对 620 private KeyAndValue getKeyAndValueinMinAndMax(Node node, int min, int max) { 621 if (node == null) { 622 return null; 623 } 624 List<KeyAndValue> keyAndValues = node.getKeyAndValue(); 625 KeyAndValue keyAndValue = null; 626 for (KeyAndValue k : keyAndValues) { 627 if (k.getKey() > min && k.getKey() <= max) { 628 keyAndValue = k; 629 break; 630 } 631 } 632 return keyAndValue; 633 } 634 635 // private KeyAndValue getMaxKeyAndValueInChildNode(Node node) { 636 // if (node.getNodes() == null || node.getNodes().isEmpty()) { 637 // return null; 638 // } 639 // List<KeyAndValue> sortKeyAndValues = new ArrayList<>(); 640 // List<Node> childNodes = node.getNodes(); 641 // for (Node childNode : childNodes) { 642 // List<KeyAndValue> keyAndValues = childNode.getKeyAndValue(); 643 // KeyAndValue maxKeyAndValue = keyAndValues.get(keyAndValues.size() - 1); 644 // sortKeyAndValues.add(maxKeyAndValue); 645 // } 646 // Collections.sort(sortKeyAndValues); 647 // return sortKeyAndValues.get(sortKeyAndValues.size() - 1); 648 // } 649 650 private KeyAndValue getMinKeyAndValueInChildNode(Node node) { 651 if (node.getNodes() == null || node.getNodes().isEmpty()) { 652 return null; 653 } 654 List<KeyAndValue> sortKeyAndValues = new ArrayList<>(); 655 List<Node> childNodes = node.getNodes(); 656 for (Node childNode : childNodes) { 657 List<KeyAndValue> keyAndValues = childNode.getKeyAndValue(); 658 KeyAndValue minKeyAndValue = keyAndValues.get(0); 659 sortKeyAndValues.add(minKeyAndValue); 660 } 661 Collections.sort(sortKeyAndValues); 662 return sortKeyAndValues.get(0); 663 } 664 665 private boolean isNeedMerge(Node node) { 666 if (node == null) { 667 return false; 668 } 669 List<KeyAndValue> keyAndValues = node.getKeyAndValue(); 670 return keyAndValues.size() < rank / 2; 671 } 672 673 //判断一个节点是否有富余的键值对 674 private boolean isMoreElement(Node node) { 675 return node != null && (node.getKeyAndValue().size() > rank / 2); 676 } 677 }
测试代码：
1 public class Main { 2 3 public static void main(String[] args) { 4 Btree btree = new Btree(4 ); 5 KeyAndValue keyAndValue = new KeyAndValue(1,"123"); 6 KeyAndValue keyAndValue1 = new KeyAndValue(2,"123"); 7 KeyAndValue keyAndValue2 = new KeyAndValue(3,"123"); 8 KeyAndValue keyAndValue3 = new KeyAndValue(4,"123"); 9 KeyAndValue keyAndValue4 = new KeyAndValue(5,"123"); 10 KeyAndValue keyAndValue5 = new KeyAndValue(6,"123"); 11 KeyAndValue keyAndValue6 = new KeyAndValue(7,"12300"); 12 KeyAndValue keyAndValue7 = new KeyAndValue(8,"546"); 13 KeyAndValue keyAndValue8 = new KeyAndValue(9,"123"); 14 KeyAndValue keyAndValue9 = new KeyAndValue(10,"123"); 15 KeyAndValue keyAndValue10 = new KeyAndValue(11,"123"); 16 KeyAndValue keyAndValue11 = new KeyAndValue(12,"123"); 17 KeyAndValue keyAndValue12 = new KeyAndValue(13,"123"); 18 KeyAndValue keyAndValue14 = new KeyAndValue(15,"12345"); 19 KeyAndValue keyAndValue15 = new KeyAndValue(16,"12345"); 20 KeyAndValue keyAndValue16 = new KeyAndValue(17,"12345"); 21 KeyAndValue keyAndValue17 = new KeyAndValue(18,"12345"); 22 KeyAndValue keyAndValue18 = new KeyAndValue(19,"12345"); 23 KeyAndValue keyAndValue19 = new KeyAndValue(20,"12345"); 24 KeyAndValue keyAndValue20 = new KeyAndValue(21,"12345"); 25 26 btree.insert(keyAndValue); 27 btree.insert(keyAndValue5); 28 btree.insert(keyAndValue9); 29 btree.insert(keyAndValue1); 30 btree.insert(keyAndValue7); 31 btree.insert(keyAndValue10); 32 btree.insert(keyAndValue17); 33 btree.insert(keyAndValue2); 34 btree.insert(keyAndValue14); 35 btree.insert(keyAndValue16); 36 btree.insert(keyAndValue11); 37 btree.insert(keyAndValue12); 38 btree.insert(keyAndValue3); 39 btree.insert(keyAndValue8); 40 btree.insert(keyAndValue18); 41 btree.insert(keyAndValue15); 42 btree.insert(keyAndValue4); 43 btree.insert(keyAndValue19); 44 btree.insert(keyAndValue6); 45 btree.insert(keyAndValue20); 46 47 48 btree.printBtree(btree.getRoot()); 49 50 btree.delete(1); 51 btree.printBtree(btree.getRoot()); 52 53 btree.delete(0); 54 btree.printBtree(btree.getRoot()); 55 56 btree.delete(2); 57 btree.printBtree(btree.getRoot()); 58 59 btree.delete(11); 60 btree.printBtree(btree.getRoot()); 61 62 btree.delete(3); 63 btree.printBtree(btree.getRoot()); 64 65 btree.delete(4); 66 btree.printBtree(btree.getRoot()); 67 68 btree.delete(5); 69 btree.printBtree(btree.getRoot()); 70 71 btree.delete(9); 72 btree.printBtree(btree.getRoot()); 73 74 btree.delete(6); 75 btree.printBtree(btree.getRoot()); 76 77 btree.delete(13); 78 btree.printBtree(btree.getRoot()); 79 80 btree.delete(7); 81 btree.printBtree(btree.getRoot()); 82 83 btree.delete(10); 84 btree.printBtree(btree.getRoot()); 85 86 btree.delete(18); 87 btree.printBtree(btree.getRoot()); 88 89 btree.delete(8); 90 btree.printBtree(btree.getRoot()); 91 92 btree.delete(12); 93 btree.printBtree(btree.getRoot()); 94 95 btree.delete(20); 96 btree.printBtree(btree.getRoot()); 97 98 btree.delete(19); 99 btree.printBtree(btree.getRoot()); 100 101 btree.delete(15); 102 btree.printBtree(btree.getRoot()); 103 104 btree.delete(17); 105 btree.printBtree(btree.getRoot()); 106 107 108 110 } 111 }
测试结果：
8,12 3,6|10|15,18,20| 1,2|3,4,5|6,7|8,9|10,11|12,13|15,16,17|18,19|20,21| delete:1 8,12 4,6|10|15,18,20| 2,3|4,5|6,7|8,9|10,11|12,13|15,16,17|18,19|20,21| delete:0 8,12 4,6|10|15,18,20| 2,3|4,5|6,7|8,9|10,11|12,13|15,16,17|18,19|20,21| delete:2 12 6,8,10|15,18,20| 3,4,5|6,7|8,9|10,11|12,13|15,16,17|18,19|20,21| delete:11 12 6,8|15,18,20| 3,4,5|6,7|8,9,10|12,13|15,16,17|18,19|20,21| delete:3 12 6,8|15,18,20| 4,5|6,7|8,9,10|12,13|15,16,17|18,19|20,21| delete:4 18 8,15|18,20| 5,6,7|8,9,10|12,13|15,16,17|18,19|20,21| delete:5 18 8,15|18,20| 6,7|8,9,10|12,13|15,16,17|18,19|20,21| delete:9 18 8,15|18,20| 6,7|8,10|12,13|15,16,17|18,19|20,21| delete:6 12,15,18,20 7,8,10|12,13|15,16,17|18,19|20,21| delete:13 10,15,18,20 7,8|10,12|15,16,17|18,19|20,21| delete:7 15,18,20 8,10,12|15,16,17|18,19|20,21| delete:10 15,18,20 8,12|15,16,17|18,19|20,21| delete:18 15,17,20 8,12|15,16|17,19|20,21| delete:8 17,20 12,15,16|17,19|20,21| delete:12 17,20 15,16|17,19|20,21| delete:20 17 15,16|17,19,21| delete:19 17 15,16|17,21| delete:15 16,17,21 delete:17 16,21
© 著作权归作者所有
举报
发表评论
0/200
