分类
Java

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
--------------例1--------------
                      【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】​

--------------例2--------------

                  【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】
     ^
合并后内结点【4】不符合约束条件,兄弟结点有富余,需要调整,父结点下移,兄弟结点上移。
                    【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

集合类都实现了 CloneableSerializable 接口,所以我也将这个 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());
        }
    }

“B+ 树的插入与删除(Java 实现)”上的1条回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

[/鼓掌] [/难过] [/调皮] [/白眼] [/疑问] [/流泪] [/流汗] [/撇嘴] [/抠鼻] [/惊讶] [/微笑] [/得意] [/大兵] [/坏笑] [/呲牙] [/吓到] [/可爱] [/发怒] [/发呆] [/偷笑] [/亲亲]