我手写了一个 Java 内存数据库（二）：B+ 树的插入与分裂

我手写了一个 Java 内存数据库二B 树的插入与分裂上一篇搭好了节点和查询框架。这篇写 B 树最核心的部分——插入和节点分裂。这块我调了最久分裂的边界条件特别多。插入的整体思路B 树插入分两步从根节点一路向下找到应该插入的叶子节点如果叶子节点满了分裂成两个把分裂向上传播给父节点听起来简单但分裂传播到根节点时树要长高边界条件不少。向下路由找目标叶子非叶子节点不存数据只负责路由。我根据 key 的大小选择子树if(isLeaf){// 到叶子了执行插入}else{if(key.compareTo(entries.get(0).getKey())0){children.get(0).insertOrUpdate(key,obj,tree,obligate);}elseif(key.compareTo(entries.get(entries.size()-1).getKey())0){children.get(children.size()-1).insertOrUpdate(key,obj,tree,obligate);}else{for(inti0;ientries.size();i){if(entries.get(i).getKey().compareTo(key)0entries.get(i1).getKey().compareTo(key)0){children.get(i).insertOrUpdate(key,obj,tree,obligate);break;}}}}三种情况比最小还小走最左子树比最大还大走最右子树中间的线性扫描找。中间部分后来我意识到也可以用二分但当时数据量不大就没优化。叶子节点插入要不要分裂到了叶子节点先看还有没有位置if(isLeaf){floatper0;if(obligate){pertree.getPer();// 默认 0.1预留 10%}intorder(int)(tree.getOrder()*(1-per));if(contains(key)||entries.size()order){insertOrUpdate(key,obj);if(parent!null)parent.updateInsert(tree,obligate);}else{// 满了分裂}}预留空间的设计obligate这个参数是我后来加的。批量插入时发现如果节点刚好满到 M后续几乎每次插入都触发分裂性能抖得厉害。于是加了一个 10% 的预留空间实际可用容量 M × (1 - 0.1) M × 0.9提前分裂虽然多占一点空间但减少了后续的分裂频率。后来查资料发现MySQL InnoDB 的页分裂策略也有类似思路算是歪打正着。分裂我调得最久的部分当叶子节点满了把它拆成两个分裂前M4已满要插入 key9 ┌─────────────────┐ │ 3 | 7 | 12 | 18 │ ← 插入 9 后变成 5 个 key └─────────────────┘ 分裂后 左节点 右节点 ┌───────┐ ┌───────────┐ │ 3 | 7 │ │ 9 | 12 | 18 │ └───────┘ └───────────┘ ↑ ↑ └─── 双向链表 ───┘代码NodeleftnewNode(true);NoderightnewNode(true);// 维护双向链表——这块最容易出 bugif(previous!null){previous.setNext(left);left.setPrevious(previous);}if(next!null){next.setPrevious(right);right.setNext(next);}if(previousnull){tree.setHead(left);// 原来是链表头更新头指针}left.setNext(right);right.setPrevious(left);previousnull;nextnull;// 先插入新 key再按大小分配insertOrUpdate(key,obj);intleftSize(order1)/2(order1)%2;intrightSize(order1)/2;for(inti0;ileftSize;i){left.getEntries().add(entries.get(i));}for(inti0;irightSize;i){right.getEntries().add(entries.get(leftSizei));}左右分配是(order 1) / 2向上取整给左边。比如 order4插入后 5 个 key左 3 右 2。链表维护是最容易出 bug 的地方。我当时调试了很久主要问题是分裂后 previous/next 的指向容易搞乱特别是链表头节点的处理。分裂后挂到父节点还是长出新的根分裂完要把新节点挂到父节点上分两种情况有父节点if(parent!null){intindexparent.getChildren().indexOf(this);parent.getChildren().remove(this);left.setParent(parent);right.setParent(parent);parent.getChildren().add(index,left);parent.getChildren().add(index1,right);setEntries(null);setChildren(null);parent.updateInsert(tree,obligate);// 父节点可能也要分裂setParent(null);}没有父节点——说明是根节点在分裂else{isRootfalse;NodeparentnewNode(false,true);// 新根非叶子tree.setRoot(parent);left.setParent(parent);right.setParent(parent);parent.getChildren().add(left);parent.getChildren().add(right);setEntries(null);setChildren(null);parent.updateInsert(tree,obligate);}根节点分裂意味着树长高了一层。B 树就是这样一个节点一个节点地长高的。父节点也可能分裂级联传播updateInsert里判断父节点的子节点数是否超限protectedvoidupdateInsert(BPTreetree,booleanobligate){validate(this,tree);intorder(int)(tree.getOrder()*(1-per));if(children.size()order){// 父节点也满了继续分裂NodeleftnewNode(false);NoderightnewNode(false);intleftSize(order1)/2(order1)%2;intrightSize(order1)/2;for(inti0;ileftSize;i){left.getChildren().add(children.get(i));left.getEntries().add(newSimpleEntry(children.get(i).getEntries().get(0).getKey(),null));children.get(i).setParent(left);}for(inti0;irightSize;i){right.getChildren().add(children.get(leftSizei));right.getEntries().add(newSimpleEntry(children.get(leftSizei).getEntries().get(0).getKey(),null));children.get(leftSizei).setParent(right);}// 然后和叶子分裂一样挂到祖父节点或建新根...}}分裂会从叶子向根传播直到某个父节点能容纳为止。最坏情况下一直传播到根树高 1。validate关键字校准这个函数我踩了一个大坑。分裂之后非叶子节点的关键字必须反映子节点的最小 key不然路由会出错。我一开始忘了同步查了半天发现查询结果不对。protectedstaticvoidvalidate(Nodenode,BPTreetree){if(node.getEntries().size()node.getChildren().size()){for(inti0;inode.getEntries().size();i){Comparablekeynode.getChildren().get(i).getEntries().get(0).getKey();if(node.getEntries().get(i).getKey().compareTo(key)!0){node.getEntries().remove(i);node.getEntries().add(i,newSimpleEntry(key,null));if(!node.isRoot()){validate(node.getParent(),tree);// 递归向上校准}}}}elseif(...){// 关键字数量完全不对重建node.getEntries().clear();for(inti0;inode.getChildren().size();i){Comparablekeynode.getChildren().get(i).getEntries().get(0).getKey();node.getEntries().add(newSimpleEntry(key,null));}if(!node.isRoot())validate(node.getParent(),tree);}}这篇的坑总结链表维护——分裂时 previous/next 指向容易搞错特别是头节点validate 忘调——非叶子节点关键字没同步导致路由错误分裂时先插入再分配——不是先分配再插入顺序搞反会丢数据上一篇上一篇[我手写了一个Java内存数据库一起因与架构]下一篇插入和分裂搞定了。下一篇写删除借节点、合并节点比插入更复杂和范围查询B 树最大的优势所在。下一篇[我手写了一个 Java 内存数据库三删除、合并与范围查询]系列我手写了一个 Java 内存数据库共 4 篇