我手写了一个 Java 内存数据库（三）：删除、合并与范围查询
我手写了一个 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()/2&&entries.size()>2){returnremove(key);// 删完还够，直接删}// 删完不够了，要借或合并...}}向兄弟借
优先看前兄弟，再后兄弟。有个重要前提：只能从同一个父节点下的兄弟借，不能跨父节点（previous.getParent() == parent）。
// 向前兄弟借最后一个if(previous!=null&&previous.getEntries().size()>tree.getOrder()/2&&previous.getEntries().size()>2&&previous.getParent()==parent){Entry<...>entry=previous.getEntries().get(previous.getEntries().size()-1);previous.getEntries().remove(entry);entries.add(0,entry);// 借过来的放首位remove(key);}// 向后兄弟借第一个elseif(next!=null&&next.getEntries().size()>tree.getOrder()/2&&next.getEntries().size()>2&&next.getParent()==parent){Entry<...>entry=next.getEntries().get(0);next.getEntries().remove(entry);entries.add(entry);// 借过来的放末尾remove(key);}画个图（M=4，最少 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(inti=previous.getEntries().size()-1;i>=0;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){Nodetemp=previous;temp.getPrevious().setNext(this);previous=temp.getPrevious();temp.setPrevious(null);temp.setNext(null);}else{tree.setHead(this);// 前兄弟是链表头previous.setNext(null);previous=null;}}合并后父节点的子节点少了一个，可能也不满足 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;// 根只剩一个子节点——树变矮了Noderoot=children.get(0);tree.setRoot(root);root.setParent(null);root.setRoot(true);}else{// 同样的套路：先借，借不了合并Nodeprevious=parent.getChildren().get(prevIdx);Nodenext=parent.getChildren().get(nextIdx);if(previous!=null&&previous.getChildren().size()>tree.getOrder()/2){// 从前兄弟借最后一个子节点Nodeborrow=previous.getChildren().remove(lastIdx);borrow.setParent(this);children.add(0,borrow);}elseif(next!=null&&next.getChildren().size()>tree.getOrder()/2){// 从后兄弟借第一个子节点Nodeborrow=next.getChildren().remove(0);borrow.setParent(this);children.add(borrow);}else{// 合并}parent.updateRemove(tree);// 递归向上}}}树变矮只发生在根节点——当根只剩一个子节点时，那个子节点晋升为新根。这是 B+ 树高度减少的唯一方式。
二、范围查询：B+ 树最大亮点
这是我最满意的部分。B+ 树之所以比 Hash、红黑树更适合做数据库索引，核心就是范围查询——叶子节点有双向链表，找到边界后沿链表扫就行。
我实现了三种范围查询，每种都用了自己写的二分查找变体。
searchless：找"最后一个小于等于 key 的位置"
标准二分只找"等于"，这个变体找边界：
publicintsearchless(List<Entry<...>>list,Comparablekey){intlow=0,high=list.size()-1,mid=0;while(low<=high){mid=(low+high)/2;if(list.get(mid).getKey().compareTo(key)<0){low=mid+1;}elseif(list.get(mid).getKey().compareTo(key)>0){high=mid-1;}else{low=mid;break;}}if(low<=0)return-1;returnlow-1;}searchmore：找"第一个大于等于 key 的位置"
publicintsearchmore(List<Entry<...>>list,Comparablekey){intlow=0,high=list.size()-1,mid=0;while(low<=high){mid=(low+high)/2;if(list.get(mid).getKey().compareTo(key)<0){low=mid+1;}elseif(list.get(mid).getKey().compareTo(key)>0){high=mid-1;}else{high=mid+1;break;}}if(high>=list.size()||low>=list.size())return-1;returnhigh<low?low:high;}这两个变体我反复调试了好几遍，边界条件确实容易出错。
小于查询 getLessThen
publicList<List>getLessThen(Comparablekey){List<List>list=newArrayList<>();intbind=searchless(entries,key);if(isLeaf){if(bind>=0){for(inti=0;i<=bind;i++){list.add(entries.get(i).getValue());}returnlist;}returnnull;}else{if(bind>=0){for(inti=0;i<=bind;i++){Listlist1=children.get(i).getLessThen(key);if(list1!=null)list.addAll(list1);}}else{// bind < 0 说明当前节点所有 entry 都比 key 大// 但最左子树可能还有更小的值Listlist1=children.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){intbind1=searchless(entries,key2);// 上界intbind2=searchmore(entries,key1);// 下界for(inti=bind2;i<=bind1&&bind2>=0;i++){list.add(entries.get(i).getValue());}}非叶子节点的处理稍微复杂：
else{intbind1=searchless(entries,key2);intbind2=searchmore(entries,key1);if(bind1<0){// 所有 entry > key2，走最左子树碰运气children.get(0).getMoreAndLessThen(key1,key2);}elseif(bind2<0){// 所有 entry < key1，走最右子树碰运气children.get(entries.size()-1).getMoreAndLessThen(key1,key2);}else{// 遍历 bind2-1 到 bind1 的子树for(inti=bind2-1>=0?bind2-1:bind2;i<=bind1;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 篇）