# 简介

# 适合范围

大量数据存储在外部存储器（磁盘等），例如：文件系统，MySQL 索引等。
因为外部存储器 I／O 速度比较慢，如果使用二叉搜索树算法，其树的深度又比较高，则增加了读取数据的次数，从而增加了执行的时间。

# 局部性原理

访问磁盘中的数据，其附近的数据也将会被访问。
因为程序中的数据一般是集中存放的，所以通过预先读取数据，一般为按页读取，这样就减少读取磁盘的次数，从而减少执行的时间。

# B⁺ 树的特点

1. 非叶子节点只存放 router（相当于 key，与叶子节点 key 区分），叶子节点存放 key 和数据。
2. 叶子节点 x 的 nextNode 引用下一个叶子节点，把所有叶子节点通过链表连接起来。
3. key 的个数与度（degree）的关系: $n_k = degree - 1$。
4. 从根节点到叶节点的每条路径的树高都一样。
5. 除了根节点，其余所有节点包含 key 的数量至少满一半。

# B⁺ 树结构

非叶子节点 x 的字段：

1. x.n 当前存放 router 的个数；
2. x.routers 按升序存放：$x.router_1 < x.router_2 < \; ... \; < x.router_n$；
3. x.leaf = false，表明该节点是非叶子节点；
4. x.children，n + 1 个孩子节点的指针：$x.c_1, x.c_2, ... , x.c_n$。

叶子节点 x 的字段：

1. x.n 当前存放 key 的个数；
2. x.keys 按升序存放：$x.key_1 < x.key_2 < \; ... \; < x.key_n$；
3. x.leaf = true，表明该节点是叶子节点。

非叶子节点的 routers 和孩子节点的 key 关系：

$$key_1 \leq x.router_1 < key_2 \leq x.router_2 < key_3 \; ... \; < key_n \leq x.router_n < key_{n + 1}$$

# 搜索

从根节点开始搜索：

1. 如果 x 是非叶子节点，则 key 与第一个 $x.router_i$ 比较，如果 $key \leq x.router_i$，则从 $x.c_i$ 孩子节点中搜索；
2. 如果所有的 router 都比 key 小，则从最后一个孩子节点中搜索；
3. 如果 x 是叶子节点，就从 x.keys 里面查询是否存在该元素。

下面是 java 部分关键代码：

public D search(K key) {

    return search(root, key);

}

private D search(Node<K, D> node, K key) {

    if (node == null) {

        return null;

    }

    // find position

    int pos = getLocation(node, key);

    // search in leaf node

    if (node.isLeaf) {

        if (key.compareTo(node.keys[pos]) == 0) {

            return node.dataList[pos];

        }

        // not found

        return null;

    }

    // search in non-leaf node

    return search(node.children[pos], key);

}

private int getLocation(Node<K, D> node, K key) {

    int pos = 0;

    while (pos < node.keyLength && key.compareTo(node.keys[pos]) > 0) {

        pos++;

    }

    return pos;

}

# 时间复杂度

$O(t \cdot log_tn)$

# 插入

从根节点开始搜索，直到找到适合的叶子节点 y，先搜索 key 在叶子节点的位置，在叶子节点中插入：
如果叶子节点 y 还有剩余位置，则在对应位置直接插入 key 和对应的数据，操作完成。
否则，如果叶子节点 y 已经满了，则需要分裂该节点：

1. 分配新的节点 z；
2. 将节点 y 的前面一半保留在节点 y；
3. 将节点 y 的后面一半移到新节点 z；
4. key 的插入，看 key 的大小，再决定插在 y 还是 z；
5. y 节点的 nextNode 指针指向 z 节点；选取 y 节点的最后一个 $y.key_{last}$ 和新节点 z，插入父节点 x，x 节点是 y 和 z 的父节点；设置 z 节点的父节点；
6. 如果父节点也不够空间，则继续分裂，最坏的情况就是，叶子节点到根节点的路径上所有节点都需要分裂。

在非叶子节点的分裂，因为 router 的个数比孩子节点少 1 个，所以节点分裂时，就多出一个 router，因此，把这个多余的 router 和新节点插入到父节点上：

将多余的 router 直接移除，添加到父节点上；非叶子节点分离时，children 也会被分离，需要更新移到右边的 children 的 parent；children 比 router 移动多 1 个。

⚠️ 非叶子节点分裂时，children 的 parent 发生变化，children 的 parent 需要更新。

# 时间复杂度

$O(t \cdot log_tn)$

# 删除

先搜索到叶节点，在叶节点中删除命中的元素。

1. 在叶子节点中删除 key，如果删除后，key 的数量没有少于一半，则删除步骤结束。
2. 如果删除 key 后，key 的数量少于一半，则需要将树重新平衡。

# 参考

1. B⁺ - trees, Kerttu Pollari-Malmi