[Tree]手撕B+树

Git 实现代码

自己的B+树实现总结。

定义

• 每个节点最多可以有 m 个元素
• 除根节点，每个节点最少有 (m/2) 个元素（也就是分裂时对半分）
• 如果根节点不是叶节点，那它最少有 2 个子节点
• 所有的叶节点都在同一层
• 相邻的叶节点之间用指针相连
• 某个元素对应子树中的元素都比它小，右侧元素子树都大于或等于它
• 非叶子节点只存放关键字和指向下一个孩子节点的索引，记录只存放在叶节点中

结构

B+树结构：

public class BPlusTree<V extends Comparable<V>, T> {
    // 阶数
    Integer degree;

    // 节点容量，也就是 degree + 1，因为在分裂之前还要留一个空间插入元素
    Integer maxNumber;

    Node<V, T> root;
    
    // 叶节点链表的起始节点
    LeafNode<V, T> start;

    // 内部类 非叶节点 BPlusNode, 叶节点 LeafNode（继承 Node）
    abstract class Node{}
    class BPlusNode extends Node{}
    class LeafNode extends Node{}

    // 插入
    Node insert(V key, T value);
    
    // 查询
    T find(V key);
}

比较关键的是三个内部类节点的结构：

abstract class Node<V extends Comparable<V>, T> {

    // 父节点
    Node<V, T> parent;


    // 子节点集合
    Node<V, T>[] childs;

    // 子节点数量
    Integer keyNumber;


    // 键集合
    Object[] keys;

    abstract T find(V key);

    abstract Node insert(V key, T value);
}

// find 和 findIndex 方法与 LeafNode 不同
class BPlusNode <V extends Comparable<V>, T> extends Node<V ,T> {
    // 没有新增属性，新增 2 个方法

    // 节点数量超过阶数，则拆分，向父节点插入拆分后的新节点，
    // 之后递归处理，检测父节点插入拆分后的新节点后是否需要继续拆分
    Node<V, T> insertParent(Node node1, Node node2, V key);

    // 遍历获取 keys 中第一个比 key 大的下标
    int findIndex(V key);

    // 先通过 findIndex() 获取下标 index，
    // 再选取 childs[index] 节点调用 find()，（向下递归调用）
    T find(V key);

    // 先通过 findIndex() 获取下标 index，
    // 再选取 childs[index] 节点调用 insert()，（向下递归调用）
    Node insert(V key, T value);
}

class LeafNode <V extends Comparable<V>, T> extends Node<V ,T> {
    // 叶节点需要存储具体数据
    Object[] values;
    
    // 搜索下标的方式为二分查找，其实可以合并到 find 中
    // 但考虑到 delete() 会使用到，就抽出复用
    int findIndex(V key);

    // 通过 findIndex 获取下标 index，如果存在则返回 values[index]
    // BPlusNode 的 find() 会递归到 LeafNode() 的 find()
    T find(V key);

    // 先插入元素，再判断是否需要拆分，
    // 拆分则调用 parent.insertParent()
    // BPlusNode 的 insert() 会递归到 LeafNode() 的 insert()
    Node insert(V key, T value);
}

操作

B+树通过节点的分裂操作来构建一棵索引树。

分裂其实只需要考虑两种情况，即有父节点和无父节点：

---

分裂时要考虑的细节：

比如说 insertParent() 方法中要考虑到，BPlusNode 拆分后要修改原节点中子节点的父节点指向。

不要忘记更新 root 节点。