数据结构 - 10（ B- 树 && B+ 树 && B* 树 4000 字详解 ）

一：B- 树

1.1 B- 树的引入

在使用二叉搜索树对数据进行排序时，存在一个缺陷：随着数据量的增大，二叉搜索树的高度也会随之增加。虽然在数据量较小时，这种情况并不明显，但当数据量变得庞大时，树的高度可能会显著增加，而二叉搜索树的搜索效率依赖于其高度。我们应该如何提高二叉搜索树的排序效率呢？第一是提高 IO 的速度，第二是降低树的高度，由第二点就引入了一种新的数据结构 —— B- 树。

1.2 B- 树概念

1970年，R. Bayer 和 E. McCreight 提出了一种适合外部查找的树结构，称为 B 树，注意不要误读为 B 减树。一棵 M 阶（M > 2）的 B 树是一种平衡的多路搜索树，可以是空树或满足以下性质：

1. 根节点至少有两个孩子。
2. 每个非根节点至少包含 ⌈M / 2⌉ - 1 个关键字，至多包含 M - 1 个关键字，且这些关键字按升序排列。例如，当 M = 3 时，非根节点至少包含 1 个关键字，最多包含 2 个关键字。
3. 每个非根节点至少有 ⌈M / 2⌉ 个孩子，至多有 M 个孩子。例如，当 M = 3 时，非根节点至少有 2 个孩子，最多有 3 个孩子。
4. 在关键字 key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i] 和 key[i+1] 之间。
5. 所有叶子节点都位于同一层上。

1.3 B- 树的插入分析

为了简单起见，假设 M = 3，即构建一棵三叉树。每个节点中存储两个关键字，这两个关键字可以将值域分割成三个部分，因此每个节点应有三个孩子，孩子节点的数量始终比关键字的数量多一个。为了简化后续实现，节点的结构设计为：

用序列 {53, 139, 75, 49, 145, 36, 101} ，这个序列中的数就是关键字，构建 B 树的过程如下：

插入过程总结：

1. 如果树为空，直接插入新节点，数组中的该节点将成为树的根节点。
2. 如果树非空，首先找到待插入元素在树中的插入位置，注意找到的位置一定是在叶子节点中。
3. 检查插入位置是否有效。如果待插入的元素已经存在于树中，则不进行插入。
4. 根据插入排序的思想，将新元素插入到找到的节点中。
5. 检测该节点是否满足B树的性质，即节点中的元素个数是否等于M。若小于M，则满足性质。
6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：首先申请一个新节点，接着找到当前节点的中间位置，然后将该节点中间位置右侧的元素及其孩子节点移动到新节点中。最后将中间位置的元素和新节点插入到该节点的双亲节点中，并返回到步骤4。
7. 如果分裂过程已经达到根节点位置，则插入过程结束。

1.4 B- 树的插入实现

1.4.1 B- 树的节点设计

class BTreeNode {
    int[] keys; // 存放当前节点中的关键字
    BTreeNode[] subs; // 存放当前节点的子节点
    BTreeNode parent; // 当前节点的父节点，用于在分裂时向上插入
    int size; // 当前节点中有效关键字的个数

    // 构造函数，初始化B树节点
    BTreeNode(int M) {
        keys = new int[M]; // 初始化关键字数组，大小为M
        subs = new BTreeNode[M + 1]; // 初始化子节点数组，大小为M + 1（孩子节点比关键字多一个）
        size = 0; // 初始时有效关键字数量为0
    }
}

1.4.2 插入 key 的过程

1. 先查找 key 是否在 B- 树中：

public Pair<BTreeNode, Integer> find(int key) {
    BTreeNode cur = root; // 从树的根节点开始查找
    BTreeNode parent = null; // 用于记录当前节点的父节点
    while (cur != null) { // 遍历树，直到找到该节点或到达空节点
        int index = 0; // 初始化索引，用于遍历当前节点的关键字
        while (index < cur.size) { // 遍历当前节点中的关键字
            if (key == cur.keys[index]) { // 如果找到了目标关键字
                return new Pair<BTreeNode, Integer>(cur, index); // 返回当前节点和关键字的位置
            } else if (key < cur.keys[index]) { // 如果目标关键字小于当前关键字
                break; // 说明应该在当前节点的左子树中查找
            } else {
                index++; // 否则继续检查下一个关键字
            }
        }
        parent = cur; // 更新父节点为当前节点
        cur = cur.subs[index]; // 查找当前节点的子节点
    }
    return new Pair<BTreeNode, Integer>(parent, -1); // 未找到目标关键字，返回父节点和-1
}

2. 按照插入排序的思想插入关键字 key。在插入 key 的同时，可能还要插入新分裂出来的节点。

// 采用插入排序的思想插入在cur节点中插入key以及分列出的sub孩子
void insertKey(BTreeNode cur, int key, BTreeNode sub) {
    int end = cur.size - 1; // 设置指向当前节点最后一个关键字的索引
    while (end >= 0 && key < cur.keys[end]) { // 寻找插入位置
        cur.keys[end + 1] = cur.keys[end]; // 将当前关键字向右移动
        cur.subs[end + 2] = cur.subs[end + 1]; // 将子节点向右移动
        end--; // 移动到下一个关键字
    }
    cur.keys[end + 1] = key; // 在合适位置插入新关键字
    cur.subs[end + 2] = sub; // 在合适位置插入分裂出的子节点
    cur.size++; // 更新当前节点的有效大小
    if (sub != null) { // 如果子节点不为空
        sub.parent = cur; // 将子节点的父节点指向当前节点
    }
}

1.4.3 B- 树的插入实现

boolean insert(int key) {
    // 检查树是否为空，如果为空，则初始化根节点并插入关键字
    if (root == null) {
        root = new BTreeNode(M);
        root.keys[0] = key;
        root.size = 1;
        return true;
    }
    
    // 查找插入位置，返回的键值对中如果值不为-1，说明该元素已存在
    Pair<BTreeNode, Integer> ret = find(key);
    if (ret.getValue() != -1) {
        return false; // 关键字已存在，不进行插入
    }
    
    // 获取待插入的当前节点
    BTreeNode cur = ret.getKey();
    int k = key; // 存储待插入的关键字
    BTreeNode sub = null; // 用于存放新分裂出的子节点
    while (true) {
        // 插入关键字及子节点
        insertKey(cur, k, sub);
        
        // 如果当前节点的大小未超过最大值，直接返回
        if (cur.size < M) {
            break;
        }

        // 当前节点需要分裂，找到中间位置
        int mid = (cur.size >> 1);
        BTreeNode newNode = new BTreeNode(M); // 创建新的节点
        int i = 0;
        int index = mid + 1; // 中间位置右侧开始

        // 将中间位置右侧的所有元素和子节点搬移到新节点中
        for (; index < cur.size; ++index) {
            newNode.keys[i] = cur.keys[index];
            newNode.subs[i++] = cur.subs[index];
            // 更新搬移的子节点的父节点
            if (cur.subs[index] != null) {
                cur.subs[index].parent = newNode;
            }
        }
        
        // 注意：新节点的子节点比当前节点多一个
        newNode.subs[i] = cur.subs[index];
        if (cur.subs[index] != null) {
            cur.subs[index].parent = newNode;
        }
        
        // 更新新节点和当前节点的大小
        newNode.size = i;
        cur.size = cur.size - i - 1;
        k = cur.keys[mid]; // 更新待插入的关键字为中间位置的元素

        // 如果当前节点为根节点，需创建新根节点
        if (cur == root) {
            root = new BTreeNode(M);
            root.keys[0] = k;
            root.subs[0] = cur;
            root.subs[1] = newNode;
            root.size = 1;
            cur.parent = root; // 更新父节点
            newNode.parent = root; // 更新新节点的父节点
            break;
        } else {
            // 继续向父节点插入
            sub = newNode;
            cur = cur.parent;
        }
    }
    return true; // 插入成功
}

1.5 B- 树的性能分析

对于一棵度为 M 的 B-树，每个节点的子节点数目在 $\frac{M}{2}$ 到 $M-1$ 之间。因此，树的高度会在某个范围内，查找和插入操作最多需要 $O({\log }_{M/2}N)$ 次比较。在找到目标节点后，可以通过二分查找快速定位到具体元素。

例如，对于 $N=62\times 10^9$ 个节点的 B-树，如果度 $M$ 为 1024，则树的高度最多为 4。在620亿个元素中，只需进行少于 4 次比较即可找到目标节点。接着，利用二分查找可以迅速定位到该元素，这显著减少了磁盘读取的次数，提高了查找效率。

二：B+ 树和 B* 树

2.1 B+ 树

B+ 树是 B- 树的变体，属于多路搜索树，定义基本与B-树相同，但有以下不同之处：

1. 非叶子节点的子树指针数量与关键字数量相同。
2. 非叶子节点的子树指针 ( p[i] ) 指向的子树包含的关键字值范围为 ( [k[i], k[i+1}) )。
3. 在所有叶子节点之间增加了链表，且链表是有序的，以便于叶子节点的遍历。
4. 所有关键字仅在叶子节点中出现，不在非叶子节点中出现。

这些特性使得 B+ 树在范围查询和顺序访问时效率更高。

2.2 B* 树

B* 树是 B+ 树的变形，在 B+ 树的非根和非叶子节点再增加指向兄弟节点的指针。

2.3 总结

• B- 树：多路搜索树，每个节点存储 M/2 到 M 个关键字，非叶子节点存储指向关键字范围的子节点，所有关键字在整个树中出现，仅出现一次，非叶子节点可以省；
• B+ 树：在 B- 树基础上，为叶子节点增加链表指针，所有关键字都在叶子节点中出现，非叶子节点作为叶子节点的索引；B+树总是到达叶子节点才命中；
• B* 树：在 B+ 树基础上，为非叶子节点也增加链表指针，将节点的最低利用率从 1/2 提高到 2/3。