B+ 树的插入与删除(Java 实现)

上周在某公众号看到一个掘金小册的推荐， 《MySQL 是怎样运行的：从根儿上理解 MySQL》 。购买后看了前几篇，真的写得非常好，看到索引后的章节，讲“表空间”的一章，稍微有点吃力了，因为这一章出现了太多名词，所以暂停了往下看。作者在前面讲索引时提到 B+ 树，但由于本小册主要是讲 MySQL 因此并没有细说 B+ 树如何插入、删除，于是我就自己搜了一下。

关于 B+ 树的资料，搜索出来肯定很多。但是有些内容的质量真是低下（而且我发现必应也会在搜索结果最底部推荐广告了），不过还是被我找到了一篇写得很棒的文章： 《B树和B+树的插入、删除图文详解》 。

这篇文章把 B+ 树的插入删除算法都写得挺详细了，而且有图例说明，强烈推荐。于是我就跟着文章的算法用 Java 尝试实现了 B+ 树这个数据结构。

在定义类时，我遇到一个问题，要不要让这个类实现 Map 接口？主要操作其实和 Map 非常像，都是通过 key 找到 value，或者将键值对存储起来。这不禁让我怀疑，都已经有 Map 了，为什么还需要 B+ 树这个结构？B+ 树在 MySQL 中是用作索引的，目的是通过一个 key 快速定位到对应的 value，使用 B+ 树的话，还需要从根节点开始进行二分搜索，并一直找到叶子结点，然后遍历叶子结点上的记录。这比起 Map 直接 hash 不是更慢吗？先看下插入删除算法，这个问题等下再想。下面将算法简要介绍一下（还是建议阅读前文推荐的文章）。

插入

m 阶 B+ 树每个结点最多能有 m-1 项记录，内结点最多有 m 个子孩子。

1. 先从根结点二分搜索定位到叶子结点，然后插入记录。
2. 如果该叶子结点记录数小于 m 则结束。
3. 否则该叶子结点需要分裂，前一半(m/2)保留在原来结点，后一半分到新结点(m 为奇数时，新结点多一个)。将新结点第一个记录(记为 up)插入到父结点中。up 的左右子孩子分别是原来的结点和分裂出来的新结点。将当前节点指向父结点。
4. 当前结点是父结点，记录数小于 m 则结束。
5. 否则该内结点需要分裂，前一半(m/2)保留在原来结点，然后一个记录(第m/2+1个,记为 up)插入到父结点中，剩下的分到新结点。up 的左右子孩子分别是原来的结点和新结点。将当前节点指向父结点。重复第 4 步。

插入0
【0】
 
插入1
【0,1】
 
插入2
【0,1,2】
 
插入3
【0,1,2,3】
 
插入4
【0,1,2,3,4(需要分裂)】
    【2】
    /   /
【0,1】 【 2,3,4】
 
插入5
     【2】
     /   /
【0,1】 【 2,3,4,5】
 
插入6
    【2】
    /   /
【0,1】 【 2,3,4,5,6(需要分裂)】
   【2   ,  4】
   /    |    /
【0,1】【 2,3】 【4,5,6】
 
插入7
    【2   ,  4】
    /    |     /
【0,1】 【 2,3】 【4,5,6,7】
 
 
插入8
     【2   ,  4】
     /    |      /
【0,1】 【 2,3】 【4,5,6,7,8(需要分裂)】
    【2   ,  4   ，  6 】
    /     |     |     /
【0,1】 【 2,3】 【4,5】【6，7，8】
 
插入9
    【2   ,  4   ，  6 】
    /     |      |     /
【0,1】 【 2,3】 【4,5】【6，7，8, 9】
 
插入10
     【2   ,  4   ，  6 】
    /     |       |    /
【0,1】 【 2,3】 【4,5】【6,7,8,9,10(需要分裂)】
 
     【2   ,  4   ，  6   ,    8 】
     /    |      |      |      /
【0,1】 【 2,3】 【4,5】【6,7】【8,9,10】
 
插入11
    【2   ,  4   ，  6   ,  8 】
    /     |       |    |      /
【0,1】 【 2,3】 【4,5】【6,7】【8,9,10,11】
 
插入12
    【2   ,  4   ，  6   ,   8 】
    /      |      |     |     /
【0,1】 【 2,3】 【4,5】【6,7】【8,9,10,11,12(需要分裂)】
 
     【2   ,  4   ，  6   ,   8   , 10 (需要分裂)】
     /     |     |      |      |      /
【0,1】 【 2,3】 【4,5】【6,7】【8,9】 【10,11,12】
 
                   【6】
                  /       /
     【  2  ,  4   】      【 8  , 10 】
     /    |      /         /   |     /
【0,1】 【 2,3】 【4,5】【6,7】【8,9】 【10,11,12】

​删除

约束条件：每个结点最少的记录记为 minElementPerNode, 该值默认为 m/2​。

1. 定位到要删除记录的叶子结点。若该叶子结点不含要删除的 key ，删除失败。否则删除该记录。​
2. 删除后该叶子结点记录数符合约束条件，则结束。​
3. 若该叶子结点的兄弟结点有富余(有富余是指，减少一个记录也符合约束条件)，则向兄弟结点借一个记录过来，同时更新父结点的 key(有可能要更新两个 key ，当删除的是中间叶结点的最小记录时)。将当前结点指向父结点，转第 5 步。​
4. 若该叶子结点的兄弟结点没有富余，则将该结点与兄弟节点合并，并删除他们在父节点的 key. 将当前结点指向父结点。​
5. 当前结点是父结点，若该结点符合约束条件，则结束。若该结点是根节点且记录数为 0 (子孩子个数为 1 ) ，则将根节点指向当前节点的子孩子，结束。​
6. 若该内结点的兄弟有富余，则将他们父结点的 key 下移，兄弟结点的 key 上移，将当前结点指向父结点。重复第 5 步。​
7. 若该内结点的兄弟没有富余，则将该结点、该结点的兄弟结点、及他们在父结点的 key(记为 down) 合并为一个节点，删除父结点原本那个 down 节点的左右子孩子，合并后的节点作为 down 那个位置的子孩子。将当前结点指向父结点，重复第 5 步。​

m=5, minElementPerNode=2
－－－－－－－－－－－－－－例１－－－－－－－－－－－－－－
                      【6】
                    /       /
     【  2   ,  4   】      【 8 , 10 】
     /     |       /      /     |    /
【0,1】 【 2,3】 【4,5】 【6,7】【8,9】 【10,11,12】
 
删除 0
                  　　  【6】
              　　　  /       /
     　　　【  2  , 4 】       【  8  ,  10 】
    　　　 /    |     /    　   /     |     /
【1(需要合并)】【 2,3】【4,5】【6,7】【8,9】 【10,11,12】
                 【6】
                /     /
      【4(需要合并)】   【 8 , 10 】
          /    /       /    |    /
   【1,2,3】 【4,5】【6,7】【8,9】 【10,11,12】​
​
            　　　　【】(root需要下移)
                   /
          【 4 , 6 ,   8  ,  10 】
         /    |    |      |     /
   【1,2,3】【4,5】【6,7】【8,9】 【10,11,12】​
 
   root-【4  ,  6  ,   8  , 10 】
         /    |     |      |    /
   【1,2,3】【4,5】【6,7】【8,9】 【10,11,12】​
 
删除 1
        【4  ,  6  ,   8  ,   10 】
         /    |     |      |     /
     【2,3】【4,5】【6,7】【8,9】 【10,11,12】​
 
删除 8
        【 4 ,  6  ,  　 8   , 　　　　10 】
          /   |     |    　　　 |    　　 /
     【2,3】【4,5】【6,7】【9(可向右兄弟借)】 【10,11,12】​  
       【  4 ,  6  ,  9   ,   11 】
         /    |     |     |      /
     【2,3】【4,5】【6,7】【9,10】 【11,12】​
 
－－－－－－－－－－－－－－例２－－－－－－－－－－－－－－
 
                  【6】
                 /       /
   【  2   ,  4   】      【  8 ,  10  , 12 】
   /     |       /       /     |      |     /
【0,1】 【 2,3】 【4,5】【6,7】【8,9】 【10,11】【12,13,14】
删除0
                     【6】
                   /       /
     【  2  ,  4  】      【  8 ,   10 ,  12 】
     /     |      /      /    |       |    /
  【1】 【 2,3】 【4,5】【6,7】【8,9】 【10,11】【12,13,14】
　　^
  兄弟结点没有富余，需要合并：
            【6】
           /     /
    【  4  】     【 8  ,  10  ,  12 】
     /     /       /    |     |     /
【1,2,3】【4,5】【6,7】【8,9】 【10,11】【12,13,14】
　　　　 ^
合并后内结点【４】不符合约束条件，兄弟结点有富余，需要调整，父结点下移，兄弟结点上移。
                    【8】
                  /       /
      【  4 ,  6 】      【 10 , 12 】
      /    |    /       /     |     /
【1,2,3】【4,5】【6,7】【8,9】 【10,11】【12,13,14】

Java实现的一些细节问题

先看下如何用 Java 实现 B+ 树的吧：

代码在 GitHub 上，这里我让这个类直接继承了 AbstractMap 也就是实现了 Map 接口。

B+ 树在数据库中用作索引，索引文件是存储在磁盘上的，一个结点是”一页”，B+ 树的结构是树比较矮、宽，定位到叶子结点需要遍历的结点更少，也就是能够减少磁盘 IO。上文的问题中，其实其他 Map 也不是直接从一个 Key 就能拿到对应的 Value, 比如 HashMap 内部也是数组和链表(或树)。

继承的好处

这里直接继承了 AbstractMap, 许多不是核心的方法，比如 isEmpty , putAll , keySet 等都不用自己再实现一遍了，直接使用父类的已有实现就行。

AbstractMap 中许多方法都依赖于 entrySet() 的实现，而且用到了许多的迭代器，比如 keySet()、values() 返回的容器的迭代器都依赖于 entrySet 的迭代器，equals() 也依赖于 entrySet 的迭代器进行遍历比较 —— 凡是涉及到遍历迭代的地方，都可以使用 entrySet().iterator() 来实现。这也是 Java 中迭代器模式的普遍应用。

Cloneable, Serializable

集合类都实现了 Cloneable ， Serializable 接口，所以我也将这个 BplusTree 类实现了这两个接口。

Cloneable

克隆的规则是，基本类型的变量，复制值，引用类型的变量，复制引用。对于本类中一些 root, entrySet 等变量，按照默认的 clone 规则，那么新 clone 出来的对象和原来的对象其实是同一棵树，那么修改新对象会影响原本的树。因此参考其他集合类的做法，克隆完成后，将新克隆的树结构重置，然后将原本对象的键值对全部 put 到新对象 —— 这样新对象的树结构可能和原树不一样，不过 equals 比较是一样的（因为 equals 默认是迭代比较，迭代的结果是一样的）。

    @SuppressWarnings("unchecked")
    @Override
    public Object clone() {
        BplusTree<K, V> clone;
        try {
            clone = (BplusTree<K, V>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
        clone.root = clone.min = null;
        clone.size = clone.modCount = 0;
        clone.entrySet = null;
        clone.putAll(this);
        return clone;
    }

clone() 方法是 Object 的 protected 方法，且会抛 CloneNotSupportedException 异常。这里重写为不抛异常的 public 方法，这样外部才能直接调用；因为实现了 Cloneable 接口，CloneNotSupportedException 也不可能抛出，所以方法签名就去掉了。

Serializable

实现该接口表示对象可序列化，IDE会提示指明 serialVersionUID 字段。

当序列化到 ObjectOutputStream 流中，默认会把实例的类信息、所有非 transient 非 static 的字段、实例的父类信息等都写入到流。这里和 clone 类似地，我们也重写了序列化方式，只需要保留 final 的几个字段信息：maxChildren, minElementPerNode, comparator，然后写入 size, size 个 键值对就行了。反序列化时，把 final 信息先读出来，然后将 size 个键值对 put 到反序列化出来的新对象中，就 OK 了。

看下字段修饰符：

    /**
     * 根节点
     */
    private transient Node<K, V> root;
    /**
     * 最小的结点
     */
    private transient Node<K, V> min;
    /**
     * 阶数
     * m阶B+树内个节点最多存放m-1项数据
     */
    private final int maxChildren;
    private final int minElementPerNode;
    private final Comparator<? super K> comparator;
    private transient int size;
    private transient int modCount;
    private transient Set<Map.Entry<K, V>> entrySet;

    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
        s.defaultWriteObject();
        s.writeInt(size);
        for (Entry<K, V> entry : entrySet()) {
            s.writeObject(entry.getKey());
            s.writeObject(entry.getValue());
        }
    }
 
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();
        int size = s.readInt();
        for (int i = 0; i < size; i++) {
            put((K) s.readObject(), (V) s.readObject());
        }
    }