模拟实现 B-树详解

MyBtree.java

public class MyBtree { 
    static class BTRNode { 
        public int[] keys;//关键字 
        public BTRNode[] subs;//孩子 
        public BTRNode parent;//存储当前孩子节点的父亲节点 
        public int usedSize;//记录当前节点中关键字的数量 
        public BTRNode () { 
            //说明一下：这里多给一个 是为了好进行分裂 
            this.keys = new int[M]; 
            this.subs = new BTRNode[M+1]; 
        } 
    } 
    public static final int M = 3; 
    public BTRNode root;//当前 B 树的根节点 
}

寻找插入位置

为什么返回 Pair<BTRNode,Integer>？是因为 find 函数要实现的功能是：

1. 看看 B-树中是否存在和要插入元素相等的元素，如果存在相等元素，则返回所在位置
2. 为要插入的元素找到合适的位置 如果只是返回 BTRNode，无论是上面哪种情况，结果都是非空，无法进行区分。如果只是返回 -1 和非负值，只知道 B-树是否存在和要插入元素相同的元素，并不知道要将元素插入到哪个地方。如果返回 Pair<BTRNode,Integer>，便可解决上述问题，既能知道 B-树是否存在和要插入元素相同的元素，又知道要将元素插入到哪个地方。

private Pair<BTRNode,Integer> find(int key) { 
    BTRNode cur = root; 
    BTRNode parent = null; 
    while (cur != null) { 
        int i = 0; 
        while (i < cur.usedSize) { 
            if(cur.keys[i] == key) { 
                //返回一个当前找到的节点 和 当前这个数据在节点当中的下标 
                return new Pair<>(cur,i); 
            }else if(cur.keys[i] < key) { 
                i++; 
            }else { 
                break; 
            } 
        } 
        parent = cur; 
        cur = cur.subs[i]; 
    } 
    return new Pair<>(parent,-1); 
}

插入元素

1. 首先判断 B-树根节点是否为空，如果为空，直接插入即可，并且 B-树元素个数++；
2. 如果 B-树根节点不为空，首先看看 B-树中是否存在和要插入元素相等的元素，如果存在，则插入结束，不对要插入元素进行插入
3. 如果 B-树根节点不为空，且 B-树中不存在和要插入元素相等的元素，就可以在找到的合适的插入位置进行插入，然后判断是否要对 B-树进行分裂，如果要对 B-树进行分裂，则进行分裂操作。

public boolean insert(int key) { 
    //1、如果 B 树为空的时候 
    if(root == null) { 
        root = new BTRNode(); 
        root.keys[0] = key; 
        root.usedSize++; 
        return true; 
    } 
    //2、当 B 树不为空的时候，我们需要查看当前 B 树当中 是否存在我的 Key 
    Pair<BTRNode,Integer> pair = find(key); 
    //判断 这里获取到的 val 值 是不是 -1 来确定 当前是否存在该 key 
    if(pair.getVal() != -1) { 
        return false; 
    } 
    //3、说明不存在这个 key 我们要进行插入 
    BTRNode parent = pair.getKey(); 
    int index = parent.usedSize-1; 
    for (; index >= 0;index--) { 
        if(parent.keys[index] >= key) { 
            parent.keys[index+1] = parent.keys[index]; 
        }else { 
            break; 
        } 
    } 
    parent.keys[index+1] = key; 
    parent.usedSize++; 
    //为什么不处理 孩子呢 因为你每次插入都是再叶子节点，所以叶子节点都是 null 
    if(parent.usedSize < M) { 
        //没有满 
        return true; 
    }else { 
        //满了-》分裂 
        split(parent); 
        return true; 
    } 
}

分裂节点

1. 首先把要分裂节点的父节点进行记录保存，并创建新节点
2. 然后开始挪动数据，包括关键字和孩子，需要考虑更新挪动后的孩子节点的父节点
3. 其次更新新节点的关键字个数，以及分裂节点的关键字个数
4. 然后判断分裂节点的父节点是否为空
5. 如果为空，就创建新节点，挪动数据并更新新节点的关键字个数
6. 如果不为空，继续挪动数据并更新分裂节点的父节点的关键字个数
7. 然后判断分裂节点的父节点是否需要分裂
8. 如果需要分裂，继续重复执行上述 1~7 步骤，直到不再需要分裂为止。

private void split(BTRNode cur) { 
    BTRNode newNode = new BTRNode(); 
    //1. 先存储当前需要分裂节点的父节点 
    BTRNode parent = cur.parent; 
    //2. 开始挪数据 
    int mid = cur.usedSize >> 1; 
    int i = mid+1; 
    int j = 0; 
    for( ; i < cur.usedSize;i++) { 
        newNode.keys[j] = cur.keys[i]; 
        newNode.subs[j] = cur.subs[i]; 
        //处理刚刚拷贝过来的孩子节点的父亲节点 为新分裂的节点 
        if(newNode.subs[j]!=null) { 
            newNode.subs[j].parent = newNode; 
        } 
        j++; 
    } 
    //多拷贝一次孩子 
    newNode.subs[j] = cur.subs[i]; 
    if(newNode.subs[j]!=null) { 
        newNode.subs[j].parent = newNode; 
    } 
    //更新当前新节点的有效数据 
    newNode.usedSize = j; 
    //这里的 -1 指的是 将来要提到父亲节点的 key 
    cur.usedSize = cur.usedSize - j - 1; 
    //特殊：处理根节点的情况 
    if(cur == root) { 
        root = new BTRNode(); 
        root.keys[0] = cur.keys[mid]; 
        root.subs[0] = cur; 
        root.subs[1] = newNode; 
        root.usedSize = 1; 
        cur.parent = root; 
        newNode.parent = root; 
        return; 
    } 
    //更新当前新的节点的父亲节点 
    newNode.parent = parent; 
    //开始移动父亲节点 
    int endT = parent.usedSize-1; 
    int midVal = cur.keys[mid]; 
    for (; endT >= 0 ; endT--) { 
        if(parent.keys[endT] >= midVal) { 
            parent.keys[endT+1] = parent.keys[endT]; 
            parent.subs[endT+2] = parent.subs[endT+1]; 
        }else { 
            break; 
        } 
    } 
    parent.keys[endT+1] = midVal; 
    //将当前父节点的孩子节点 新增为 newNode 
    parent.subs[endT+2] = newNode; 
    parent.usedSize++; 
    if(parent.usedSize >= M) { 
        split(parent); 
    } 
}

中序遍历

private void inorder(BTRNode root){ 
    if(root == null) return; 
    for(int i = 0; i < root.usedSize; ++i){ 
        inorder(root.subs[i]); 
        System.out.println(root.keys[i]); 
    } 
    inorder(root.subs[root.usedSize]); 
}

完整代码

Pair.java

public class Pair <K,V>{ 
    private K key; 
    private V val; 
    public Pair(K key, V val) { 
        this.key = key; 
        this.val = val; 
    } 
    public K getKey() { return key; } 
    public void setKey(K key) { this.key = key; } 
    public V getVal() { return val; } 
    public void setVal(V val) { this.val = val; } 
}

MyBtree.java

public class MyBtree { 
    static class BTRNode { 
        public int[] keys;//关键字 
        public BTRNode[] subs;//孩子 
        public BTRNode parent;//存储当前孩子节点的父亲节点 
        public int usedSize;//记录当前节点中关键字的数量 
        public BTRNode () { 
            //说明一下：这里多给一个 是为了好进行分裂 
            this.keys = new int[M]; 
            this.subs = new BTRNode[M+1]; 
        } 
    } 
    public static final int M = 3; 
    public BTRNode root;//当前 B 树的根节点 
    public boolean insert(int key) { 
        //1、如果 B 树为空的时候 
        if(root == null) { 
            root = new BTRNode(); 
            root.keys[0] = key; 
            root.usedSize++; 
            return true; 
        } 
        //2、当 B 树不为空的时候，我们需要查看当前 B 树当中 是否存在我的 Key 
        Pair<BTRNode,Integer> pair = find(key); 
        //判断 这里获取到的 val 值 是不是 -1 来确定 当前是否存在该 key 
        if(pair.getVal() != -1) { 
            return false; 
        } 
        //3、说明不存在这个 key 我们要进行插入 
        BTRNode parent = pair.getKey(); 
        int index = parent.usedSize-1; 
        for (; index >= 0;index--) { 
            if(parent.keys[index] >= key) { 
                parent.keys[index+1] = parent.keys[index]; 
            }else { 
                break; 
            } 
        } 
        parent.keys[index+1] = key; 
        parent.usedSize++; 
        //为什么不处理 孩子呢 因为你每次插入都是再叶子节点，所以叶子节点都是 null 
        if(parent.usedSize < M) { 
            //没有满 
            return true; 
        }else { 
            //满了-》分裂 
            split(parent); 
            return true; 
        } 
    } 
    private void split(BTRNode cur) { 
        BTRNode newNode = new BTRNode(); 
        //1. 先存储当前需要分裂节点的父节点 
        BTRNode parent = cur.parent; 
        //2. 开始挪数据 
        int mid = cur.usedSize >> 1; 
        int i = mid+1; 
        int j = 0; 
        for( ; i < cur.usedSize;i++) { 
            newNode.keys[j] = cur.keys[i]; 
            newNode.subs[j] = cur.subs[i]; 
            //处理刚刚拷贝过来的孩子节点的父亲节点 为新分裂的节点 
            if(newNode.subs[j]!=null) { 
                newNode.subs[j].parent = newNode; 
            } 
            j++; 
        } 
        //多拷贝一次孩子 
        newNode.subs[j] = cur.subs[i]; 
        if(newNode.subs[j]!=null) { 
            newNode.subs[j].parent = newNode; 
        } 
        //更新当前新节点的有效数据 
        newNode.usedSize = j; 
        //这里的 -1 指的是 将来要提到父亲节点的 key 
        cur.usedSize = cur.usedSize - j - 1; 
        //特殊：处理根节点的情况 
        if(cur == root) { 
            root = new BTRNode(); 
            root.keys[0] = cur.keys[mid]; 
            root.subs[0] = cur; 
            root.subs[1] = newNode; 
            root.usedSize = 1; 
            cur.parent = root; 
            newNode.parent = root; 
            return; 
        } 
        //更新当前新的节点的父亲节点 
        newNode.parent = parent; 
        //开始移动父亲节点 
        int endT = parent.usedSize-1; 
        int midVal = cur.keys[mid]; 
        for (; endT >= 0 ; endT--) { 
            if(parent.keys[endT] >= midVal) { 
                parent.keys[endT+1] = parent.keys[endT]; 
                parent.subs[endT+2] = parent.subs[endT+1]; 
            }else { 
                break; 
            } 
        } 
        parent.keys[endT+1] = midVal; 
        //将当前父节点的孩子节点 新增为 newNode 
        parent.subs[endT+2] = newNode; 
        parent.usedSize++; 
        if(parent.usedSize >= M) { 
            split(parent); 
        } 
    } 
    private Pair<BTRNode,Integer> find(int key) { 
        BTRNode cur = root; 
        BTRNode parent = null; 
        while (cur != null) { 
            int i = 0; 
            while (i < cur.usedSize) { 
                if(cur.keys[i] == key) { 
                    //返回一个当前找到的节点 和 当前这个数据在节点当中的下标 
                    return new Pair<>(cur,i); 
                }else if(cur.keys[i] < key) { 
                    i++; 
                }else { 
                    break; 
                } 
            } 
            parent = cur; 
            cur = cur.subs[i]; 
        } 
        return new Pair<>(parent,-1); 
    } 
    private void inorder(BTRNode root){ 
        if(root == null) return; 
        for(int i = 0; i < root.usedSize; ++i){ 
            inorder(root.subs[i]); 
            System.out.println(root.keys[i]); 
        } 
        inorder(root.subs[root.usedSize]); 
    } 
}

代码测试

public static void main(String[] args) { 
    MyBtree myBtree = new MyBtree(); 
    int[] array = {53, 139, 75, 49, 145, 36,101}; 
    for (int i = 0; i < array.length; i++) { 
        myBtree.insert(array[i]); 
    } 
    myBtree.inorder(myBtree.root); 
}

运行结果：程序输出有序序列。

B-树的删除

删除操作是指，根据 key 删除记录，如果 B 树中的记录中不存对应 key 的记录，则删除失败。

1. 如果当前需要删除的 key 位于非叶子结点上，则用后继 key（这里的后继 key 均指后继记录的意思）覆盖要删除的 key，然后在后继 key 所在的子支中删除该后继 key。此时后继 key 一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第 2 步
2. 该结点 key 个数大于等于 Math.ceil(m/2)-1，结束删除操作，否则执行第 3 步。
3. 如果兄弟结点 key 个数大于 Math.ceil(m/2)-1，则父结点中的 key 下移到该结点，兄弟结点中的一个 key 上移，删除操作结束。 否则，将父结点中的 key 下移与当前结点及它的兄弟结点中的 key 合并，形成一个新的结点。原父结点中的 key 的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第 2 步。 有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

下面以 5 阶 B 树为例，介绍 B 树的删除操作，5 阶 B 树中，结点最多有 4 个 key，最少有 2 个 key。 a）原始状态 b）在上面的 B 树中删除 21，删除后结点中的关键字个数仍然大于等 2，所以删除结束。 c）在上述情况下接着删除 27。从上图可知 27 位于非叶子结点中，所以用 27 的后继替换它。从图中可以看出，27 的后继为 28，我们用 28 替换 27，然后在 28（原 27）的右孩子结点中删除 28。删除后的结果如下图所示。 删除后发现，当前叶子结点的记录的个数小于 2，而它的兄弟结点中有 3 个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后 B 树的形态会不一样而已），我们可以从兄弟结点中借取一个 key。所以父结点中的 28 下移，兄弟结点中的 26 上移，删除结束。结果如下图所示。 d）在上述情况下接着 32，结果如下图。 当删除后，当前结点中只 key，而兄弟结点中也仅有 2 个 key。所以只能让父结点中的 30 下移和这个两个孩子结点中的 key 合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。 当前结点 key 的个数满足条件，故删除结束。 e）上述情况下，我们接着删除 key 为 40 的记录，删除后结果如下图所示。 同理，当前结点的记录数小于 2，兄弟结点中没有多余 key，所以父结点中的 key 下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。 同理，对于当前结点而言只能继续合并了，最后结果如下所示。 合并后结点当前结点满足条件，删除结束。

B-树的优点

1. 减少磁盘 I/O 操作：B-树的设计目标是减少磁盘 I/O 操作，提高存取速度。由于磁盘访问速度远慢于 CPU 处理速度，因此减少磁盘访问次数可以显著提高性能。
2. 自平衡性：B-树在插入和删除操作时会自动进行节点的分裂和合并，以保持树的平衡性。这种自平衡性确保了 B-树在查找、插入和删除操作中的高效性。
3. 支持大量数据：B-树能够很好地处理大规模数据，因为它通过增加节点的子节点数量来降低树的高度，从而减少了查找过程中需要遍历的节点数。

B-树的应用场景

1. 数据库索引：B-树常被用作数据库系统的索引结构，以加快数据的读取速度。例如，MySQL、PostgreSQL 等数据库系统都基于 B-树或其变种实现数据索引。
2. 文件系统：B-树可以在文件系统中用于管理目录和文件，如 Unix 文件系统中的索引节点（Inode）就是以 B-树为基础结构实现的。
3. GIS（地理信息系统）：GIS 数据需要用到空间索引算法查询与分析空间数据，B-树作为为空间数据设计的一种索引结构，可用于 GIS 数据库中的数据索引。
4. 路由表：B-树可用于构建路由表，快速定位目标路由器地址。

B+ 树

B+ 树是 B-树的变形，也是一种多路搜索树：

1. 其定义基本与 B-树相同，除了：
2. 非叶子节点的子树指针与关键字个数相同
3. 非叶子节点的子树指针 p[i]，指向关键字值属于 [k[i]，k[i+1]) 的子树
4. 为所有叶子节点增加一个链指针
5. 所有关键字都在叶子节点出现

B+ 树的搜索与 B-树基本相同，区别是 B+ 树只有达到叶子节点才能命中 (B-树可以在非叶子节点中命中)，其性能也等价与在关键字全集做一次二分查找。 B+ 树的特性：

1. 所有关键字都出现在叶子节点的链表中 (稠密索引)，且链表中的节点都是有序的。
2. 不可能在非叶子节点中命中。
3. 非叶子节点相当于是叶子节点的索引 (稀疏索引)，叶子节点相当于是存储数据的数据层。
4. 更适合文件索引系统

B+ 树的优势

1. 降低磁盘 I/O 次数：由于 B+ 树的非叶子节点不保存数据，且叶子节点之间通过指针相连，这使得在查找数据时，可以一次性加载更多的关键字到内存中，从而减少磁盘 I/O 次数。
2. 提高查询效率：B+ 树的叶子节点之间通过指针相连，形成了有序链表，这使得范围查询变得非常高效。
3. 适用于大数据集：B+ 树的高度较低，对于大数据集来说，可以减少查找、插入和删除操作所需的时间复杂度。

B+ 树的应用场景

1. 数据库索引：在关系型数据库中，B+ 树被广泛用于索引数据，以提高查询效率。
2. 文件系统：在文件系统中，B+ 树用于存储和管理文件和目录，保证文件的快速查找和高效顺序访问。
3. 缓存管理：在计算机系统中，B+ 树可用于管理缓存数据，因为它能够快速索引和更新数据，同时保证数据的一致性和可靠性。

B+ 树与 B 树的区别

1. 关键字存储位置：B+ 树的所有关键字都存储在叶子节点中，且叶子节点之间通过指针相连；而 B 树的关键字则可能存储在非叶子节点中。
2. 内部节点结构：B+ 树的内部节点仅包含其子树中的最大（或最小）关键字作为索引；而 B 树的内部节点则可能包含多个关键字和相应的子树指针。
3. 查询效率：由于 B+ 树的叶子节点之间通过指针相连，形成了有序链表，这使得范围查询在 B+ 树中更加高效。

B*树

B 树是 B+ 树的一种变体，它在 B+ 树的基础上进行了优化。

特点

1. 节点结构：B 树保留了 B+ 树的基本结构，即所有关键字都存储在叶子节点中，且叶子节点之间通过指针相连形成有序链表。但 B 树在非根和非叶子节点中增加了指向兄弟的指针，这一特点使得 B*树在节点分裂和合并时更加灵活。
2. 关键字数量：B 树定义了非叶子节点关键字个数至少为 (2/3)M，即块的最低使用率为 2/3（其中 M 为节点的最大关键字数），这比 B+ 树的 1/2 更高。这意味着 B*树在分配新节点方面的概率更低，空间使用率更高。
3. 分裂与合并：当 B 树的节点满时，会分配一个新的节点，并将数据根据一定的规则进行分裂。在分裂过程中，B 树会尽量保持节点的平衡，以维持树的整体性能。同样，在删除关键字导致节点关键字数量不足时，B*树也会通过合并节点或借用兄弟节点的关键字来保持树的平衡。

B*树的优势

1. 更高的空间使用率：由于 B 树定义了更高的块最低使用率，因此在相同条件下，B 树能够存储更多的关键字，从而提高了空间使用效率。
2. 更好的平衡性：B*树通过增加指向兄弟的指针和更严格的节点分裂与合并规则，使得树在插入和删除操作时能够更好地保持平衡，减少了树的高度，提高了查询效率。
3. 更低的磁盘 I/O 次数：由于 B*树在存储结构上的优化，使得在进行大量数据的查询、插入和删除操作时，能够减少磁盘 I/O 次数，提高操作效率。

总结

B-树及其变种 B+ 树、B*树在数据存储和检索领域扮演着重要角色，特别是在需要频繁磁盘 I/O 的场景下。