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 个子孩子。
- 先从根结点二分搜索定位到叶子结点，然后插入记录。
- 如果该叶子结点记录数小于 m 则结束。
- 否则该叶子结点需要分裂，前一半(m/2)保留在原来结点，后一半分到新结点(m 为奇数时，新结点多一个)。将新结点第一个记录(记为 up)插入到父结点中。up 的左右子孩子分别是原来的结点和分裂出来的新结点。将当前节点指向父结点。
- 当前结点是父结点，记录数小于 m 则结束。
- 否则该内结点需要分裂，前一半(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。
- 定位到要删除记录的叶子结点。若该叶子结点不含要删除的 key ，删除失败。否则删除该记录。
- 删除后该叶子结点记录数符合约束条件，则结束。
- 若该叶子结点的兄弟结点有富余(有富余是指，减少一个记录也符合约束条件)，则向兄弟结点借一个记录过来，同时更新父结点的 key(有可能要更新两个 key ，当删除的是中间叶结点的最小记录时)。将当前结点指向父结点，转第 5 步。
- 若该叶子结点的兄弟结点没有富余，则将该结点与兄弟节点合并，并删除他们在父节点的 key. 将当前结点指向父结点。
- 当前结点是父结点，若该结点符合约束条件，则结束。若该结点是根节点且记录数为 0 (子孩子个数为 1 ) ，则将根节点指向当前节点的子孩子，结束。
- 若该内结点的兄弟有富余，则将他们父结点的 key 下移，兄弟结点的 key 上移，将当前结点指向父结点。重复第 5 步。
- 若该内结点的兄弟没有富余，则将该结点、该结点的兄弟结点、及他们在父结点的 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());
}
}
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](https://www.harries.blog/img/qrcode_gzh.jpg)
