我手写了一个 Java 内存数据库三删除、合并与范围查询上一篇写了插入与分裂。这篇拆解两个主题删除时的借位与合并整个项目里最绕的部分以及范围查询B 树最大亮点。一、删除最绕的部分删除比插入复杂得多。插入最多就是分裂、传播逻辑是单向的。但删除要判断删完够不够不够的话先向兄弟借借不了再合并合并之后父节点可能又不够了……一路递归上去。整体流程1. 从根向下找到目标叶子节点 2. 删除 key 3. 如果剩余 key 数 M/2 a. 先看兄弟节点能不能借一个 b. 借不了就合并 4. 合并可能触发父节点也不满足条件递归向上叶子节点删除publicbooleanremove(Comparablekey,BPTreetree){if(isLeaf){if(!contains(key))returnfalse;if(isRoot){returnremove(key);// 既是叶子又是根直接删}if(entries.size()tree.getOrder()/2entries.size()2){returnremove(key);// 删完还够直接删}// 删完不够了要借或合并...}}向兄弟借优先看前兄弟再后兄弟。有个重要前提只能从同一个父节点下的兄弟借不能跨父节点previous.getParent() parent。// 向前兄弟借最后一个if(previous!nullprevious.getEntries().size()tree.getOrder()/2previous.getEntries().size()2previous.getParent()parent){Entry...entryprevious.getEntries().get(previous.getEntries().size()-1);previous.getEntries().remove(entry);entries.add(0,entry);// 借过来的放首位remove(key);}// 向后兄弟借第一个elseif(next!nullnext.getEntries().size()tree.getOrder()/2next.getEntries().size()2next.getParent()parent){Entry...entrynext.getEntries().get(0);next.getEntries().remove(entry);entries.add(entry);// 借过来的放末尾remove(key);}画个图M4最少 2 个 key借位前 ┌──────┐ ┌──────┐ ┌──────┐ │ 3 | 7│ │ 12 │ │18 |25│ └──────┘ └──────┘ └──────┘ 前兄弟 当前 后兄弟 (够借) (要删12) (也够) 向前兄弟借 7 ┌────┐ ┌──────┐ ┌──────┐ │ 3 │ │ 7 │ │18 |25│ └────┘ └──────┘ └──────┘合并兄弟也不富裕时只能合并// 与前兄弟合并if(previous!null(previous.getEntries().size()tree.getOrder()/2||previous.getEntries().size()2)previous.getParent()parent){// 把前兄弟的 entries 全搬过来for(intiprevious.getEntries().size()-1;i0;i--){entries.add(0,previous.getEntries().get(i));}remove(key);previous.setParent(null);previous.setEntries(null);parent.getChildren().remove(previous);// 维护链表——又是最容易出 bug 的地方if(previous.getPrevious()!null){Nodetempprevious;temp.getPrevious().setNext(this);previoustemp.getPrevious();temp.setPrevious(null);temp.setNext(null);}else{tree.setHead(this);// 前兄弟是链表头previous.setNext(null);previousnull;}}合并后父节点的子节点少了一个可能也不满足 M/2 的要求所以要递归调用parent.updateRemove(tree)。updateRemove非叶子节点的平衡protectedvoidupdateRemove(BPTreetree){validate(this,tree);if(children.size()tree.getOrder()/2||children.size()2){if(isRoot){if(children.size()2)return;// 根只剩一个子节点——树变矮了Noderootchildren.get(0);tree.setRoot(root);root.setParent(null);root.setRoot(true);}else{// 同样的套路先借借不了合并Nodepreviousparent.getChildren().get(prevIdx);Nodenextparent.getChildren().get(nextIdx);if(previous!nullprevious.getChildren().size()tree.getOrder()/2){// 从前兄弟借最后一个子节点Nodeborrowprevious.getChildren().remove(lastIdx);borrow.setParent(this);children.add(0,borrow);}elseif(next!nullnext.getChildren().size()tree.getOrder()/2){// 从后兄弟借第一个子节点Nodeborrownext.getChildren().remove(0);borrow.setParent(this);children.add(borrow);}else{// 合并}parent.updateRemove(tree);// 递归向上}}}树变矮只发生在根节点——当根只剩一个子节点时那个子节点晋升为新根。这是 B 树高度减少的唯一方式。二、范围查询B 树最大亮点这是我最满意的部分。B 树之所以比 Hash、红黑树更适合做数据库索引核心就是范围查询——叶子节点有双向链表找到边界后沿链表扫就行。我实现了三种范围查询每种都用了自己写的二分查找变体。searchless找最后一个小于等于 key 的位置标准二分只找等于这个变体找边界publicintsearchless(ListEntry...list,Comparablekey){intlow0,highlist.size()-1,mid0;while(lowhigh){mid(lowhigh)/2;if(list.get(mid).getKey().compareTo(key)0){lowmid1;}elseif(list.get(mid).getKey().compareTo(key)0){highmid-1;}else{lowmid;break;}}if(low0)return-1;returnlow-1;}searchmore找第一个大于等于 key 的位置publicintsearchmore(ListEntry...list,Comparablekey){intlow0,highlist.size()-1,mid0;while(lowhigh){mid(lowhigh)/2;if(list.get(mid).getKey().compareTo(key)0){lowmid1;}elseif(list.get(mid).getKey().compareTo(key)0){highmid-1;}else{highmid1;break;}}if(highlist.size()||lowlist.size())return-1;returnhighlow?low:high;}这两个变体我反复调试了好几遍边界条件确实容易出错。小于查询 getLessThenpublicListListgetLessThen(Comparablekey){ListListlistnewArrayList();intbindsearchless(entries,key);if(isLeaf){if(bind0){for(inti0;ibind;i){list.add(entries.get(i).getValue());}returnlist;}returnnull;}else{if(bind0){for(inti0;ibind;i){Listlist1children.get(i).getLessThen(key);if(list1!null)list.addAll(list1);}}else{// bind 0 说明当前节点所有 entry 都比 key 大// 但最左子树可能还有更小的值Listlist1children.get(0).getLessThen(key);if(list1!null)list.addAll(list1);}returnlist.size()0?null:list;}}举例查所有 15 的[10 | 20] / | \ [3|5|7] [10|12] [20|25|30] ↑ ↑ 全部符合 部分符合10,12 结果3, 5, 7, 10, 12Between 查询 getMoreAndLessThen同时用两个二分变体定位上下界if(isLeaf){intbind1searchless(entries,key2);// 上界intbind2searchmore(entries,key1);// 下界for(intibind2;ibind1bind20;i){list.add(entries.get(i).getValue());}}非叶子节点的处理稍微复杂else{intbind1searchless(entries,key2);intbind2searchmore(entries,key1);if(bind10){// 所有 entry key2走最左子树碰运气children.get(0).getMoreAndLessThen(key1,key2);}elseif(bind20){// 所有 entry key1走最右子树碰运气children.get(entries.size()-1).getMoreAndLessThen(key1,key2);}else{// 遍历 bind2-1 到 bind1 的子树for(intibind2-10?bind2-1:bind2;ibind1;i){children.get(i).getMoreAndLessThen(key1,key2);}}}为什么从bind2 - 1开始这个我调了很久才想通。searchmore找到的是第一个 key1 的 entry但它的前一个子树的最右叶子可能也有符合条件的值。必须多看一个子树才不会漏。举例查 5 key 25[10 | 20] / | \ [3|5|7] [10|12] [20|25|30] ↑ ↑ ↑ 部分符合 全部符合 部分符合 结果7, 10, 12, 20这篇的坑总结删除后的链表维护——和分裂一样容易搞错指向searchless/searchmore 的边界——low 0还是low 0返回 -1 还是真的下标调了好多遍Between 查询漏子树——bind2 - 1这个偏移量是踩了坑才发现的递归向上时 validate 漏调——和插入一样的问题关键字没同步就路由错了上一篇上一篇[我手写了一个 Java 内存数据库二B 树的插入与分裂]下一篇B 树的增删查都写完了。最后一篇把它组装起来——索引引擎Table B 树怎么配合、SQL 解析、软删除以及对整个项目的反思。下一篇[我手写了一个 Java 内存数据库四索引引擎、SQL 解析与总结]系列我手写了一个 Java 内存数据库共 4 篇