瑞_数据结构与算法_B树

1 什么是b树

1.1 b树的背景

  b树（b-tree）结构是一种高效存储和查询数据的方法，它的历史可以追溯到1970年代早期。b树的发明人rudolf bayer和edward m. mccreight分别发表了一篇论文介绍了b树。这篇论文是1972年发表于《acm transactions on database systems》中的，题目为"organization and maintenance of large ordered indexes"。

  这篇论文提出了一种能够高效地维护大型有序索引的方法，这种方法的主要思想是将每个节点扩展成多个子节点，以减少查找所需的次数。b树结构非常适合应用于磁盘等大型存储器的高效操作，被广泛应用于关系数据库和文件系统中。

  b树结构有很多变种和升级版，例如b+树，b*树和sb树等。这些变种和升级版本都基于b树的核心思想，通过调整b树的参数和结构，提高了b树在不同场景下的性能表现。

  总的来说，b树结构是一个非常重要的数据结构，为高效存储和查询大量数据提供了可靠的方法。它的历史可以追溯到上个世纪70年代，而且在今天仍然被广泛应用于各种场景。

1.2 b 的含义

  b-树的名称是由其发明者rudolf bayer提出的。bayer和mccreight从未解释b代表什么，人们提出了许多可能的解释，比如boeing、balanced、between、broad、bushy和bayer等。但mccreight表示，越是思考b-trees中的b代表什么，就越能更好地理解b-trees

1.3 b-树的度和阶

• 度（degree）：指树中节点孩子数
• 阶（order）：指所有节点孩子数最大值

  如上图：度：节点4、2都是有两个孩子，所以度数为2；节点1、3、5、7、9 10都是没有孩子，所以度数为0；节点6 8有3个孩子，所以度数为3。而阶是指上图中树的所有节点中孩子最多的那个值，就是节点6 8有3个孩子，所以上图中树的阶数为3。

1.4 b-树的特性

一颗m叉的btree特性如下 ：

1. 树中每个节点最多包含 m 个孩子，其中 m 称为b-树的阶。
2. 除根节点与叶子节点外，其它每个节点至少有 ceil(m/2) 个孩子。
3. 若根节点不是叶子节点，则至少有两个孩子。
4. 所有的叶子节点都在同一层。
5. 每个非叶子节点由 n 个关键字 key 与 n+1 个指针组成，其中 ceil(m/2)-1 <= n <= m-1 。
6. 关键字按非降序排列，即节点中的第 i 个关键字大于等于第 i-1 个关键字。
7. 指针 p[ i ] 指向关键字值位于第 i 个关键字和第 i+1 哥关键字之间的子树。

一棵 b-树具有以下性质：

  特性1️⃣：每个节点 x 具有

    1️⃣➖1️⃣ 属性 n，表示节点 x 中 key 的个数
    1️⃣➖2️⃣ 属性 leaf，表示节点是否是叶子节点
    1️⃣➖3️⃣ 节点 key 可以有多个，以升序存储

---

  特性2️⃣：每个非叶子节点中的孩子数是 n + 1、叶子节点没有孩子

---

  特性3️⃣：最小度数t（节点的孩子数称为度）和节点中键数量的关系如下：

column 1	column 2
最小度数t	键数量范围
2	1 ~ 3
3	2 ~ 5
4	3 ~ 7
…	…
n	(n-1) ~ (2n-1)

  其中，当节点中键数量达到其最大值时，即 3、5、7 … 2n-1，需要分裂

---

  特性4️⃣：叶子节点的深度都相同

  b-树与 2-3 树、2-3-4 树的关系

  它们之间的关系：

1. 2-3树是最小度数为2的b树，其中每个节点可以包含2个或3个子节点。
2. 2-3-4树是最小度数为2的b树的一种特殊情况，其中每个节点可以包含2个、3个或4个子节点。
3. b树是一种更加一般化的平衡树，可以适应不同的应用场景，其节点可以包含任意数量的键值，节点的度数取决于最小度数t的设定。

1.5 b-树演变过程示例

  以5叉btree为例（度为5）为例，演示b树的演变过程

  key的数量：可以根据公式推导ceil(m/2)-1<=n<=m-1。因为m为5，所以得2<=n<=4，即当n>4时，中间节点分裂到父节点，两边节点分裂。

  演变过程如下：

  进入网页后，选择max. degree = 5选项。本例模拟的是度数为5的情况下插入cngahekqmfwltzdprxys数据，后续网址和下半部分的配置不会再进行截取（均不会更改）

  1️⃣ 依次插入前4个字母cnga后，b树演变为下图，此时b树为 4 个关键字 key（acgn） 与 n+1 = 5 个指针组成

  2️⃣ 插入h，此时 n>4，中间元素g字母向上分裂到新的节点，分裂动图如下所示（后续分裂均是同理，过程可以到网站内自己感受，后续不再放置动图）

  此时b树各个key和指针的关系如下图所示（每一个节点指针比key的数量多1，后续不再展示带指针图）

  3️⃣ 插入e、k、q不需要分裂

  4️⃣ 插入m，中间元素m字母向上分裂到父节点g

  5️⃣ 插入f、w、l、t不需要分裂

  6️⃣ 插入z，中间元素t向上分裂到父节点中

  7️⃣ 插入d，中间元素d向上分裂到父节点中，然后插入p、r、x、y不需要分裂

  8️⃣ 最后插入s，npqr节点n>5，中间节点q向上分裂，但分裂后父节点dgmt的n>5，中间节点m向上分裂

  最终如下b树演化结果如下：

---

2 b-树的java实现

1️⃣➖1️⃣ 内部节点类node中含有属性：

• 关键字
• 孩子们
• 有效关键字个数
• 是否是叶子节点
• 最小度数 (最小孩子数)

1️⃣➖2️⃣ 内部节点类node中含有方法：

• 多路查找get(int key)
• 向指定索引处插入key，insertkey(int key, int index)
• 向指定索引处插入child，insertchild(node child, int index)

1️⃣➖3️⃣ 内部节点类node中含有内部工具方法：

• 移除指定index处的关键字removekey(int index)
• 移除最左边的关键字removeleftmostkey()
• 移除最右边的关键字removerightmostkey()
• 移除指定index处的孩子removechild(int index)
• 移除最左边的孩子removeleftmostchild()
• 移除最右边的孩子removerightmostchild()
• 获取index孩子处左边的兄弟childleftsibling(int index)
• 获取index孩子处右边的兄弟childrightsibling(int index)
• 复制当前节点的所有key和child到目标节点movetotarget(node target)

2️⃣➖1️⃣ b数类btree中含有属性：

• 根节点（node）
• 树中节点最小度数
• 最小key数目
• 最大key数目

2️⃣➖2️⃣ b数类btree中含有方法：

• 是否存在某索引contains(int key)
• 新增put(int key)
• 分裂split(node left, node parent, int index)
• 删除remove(int key)
• 平衡balance(node parent, node x, int i)

2.1 b树节点类node

  实际 keys 应当改为 entries 以便同时保存 key 和 value，本文主要是为了学习b树的思想，所以做简化实现

    static class node {
        /**
         * 关键字
         */ 
        int[] keys;
        /**
         * 孩子们
         */
        node[] children;
        /**
         * 有效关键字个数（keys 中有效 key 数目）
         */
        int keynumber;
        /**
         * 是否是叶子节点
         */
        boolean leaf = true;
        /**
         * 最小度数 (最小孩子数)，它决定了节点中key 的最小、最大数目，分别是 t-1 和 2t-1
         */
        int t;

        /**
         * 构造方法（给最小度数赋值
         *
         * @param t 最小度数（t>=2）
         */
        public node(int t) {
            this.t = t;
            // 最小度数*2就是最多孩子数
            this.children = new node[2 * t];
            this.keys = new int[2 * t - 1];
        }

        public node(int[] keys) {
            this.keys = keys;
        }

        /**
         * 打印有效key，为了方便调试和测试，非必须
         */
        @override
        public string tostring() {
            return arrays.tostring(arrays.copyofrange(keys, 0, keynumber));
        }
        
        // 多路查找
        node get(int key) {
            int i = 0;
            while (i < keynumber) {
                if (keys[i] == key) {
                    return this;
                }
                if (keys[i] > key) {
                    break;
                }
                i++;
            }
            // 执行到此时 keys[i]>key 或 i== keynumber
            if (leaf) {
                return null;
            }
            // 非叶子情况
            return children[i].get(key);
        }

        // 向 keys 指定索引处插入 key
        void insertkey(int key, int index) {
            system.arraycopy(keys, index, keys, index + 1, keynumber - index);
            keys[index] = key;
            keynumber++;
        }

        // 向 children 指定索引处插入 child
        void insertchild(node child, int index) {
            system.arraycopy(children, index, children, index + 1, keynumber - index);
            children[index] = child;
        }
  }

2.1.1 实现多路查找方法get(int key)

        // 多路查找
        node get(int key) {
            int i = 0;
            while (i < keynumber) {
                if (keys[i] == key) {
                    return this;
                }
                if (keys[i] > key) {
                    break;
                }
                i++;
            }
            // 执行到此时 keys[i]>key 或 i== keynumber
            if (leaf) {
                return null;
            }
            // 非叶子情况
            return children[i].get(key);
        }

2.1.2 实现插入key方法insertkey(int key, int index)

        // 向 keys 指定索引处插入 key
        void insertkey(int key, int index) {
            system.arraycopy(keys, index, keys, index + 1, keynumber - index);
            keys[index] = key;
            keynumber++;
        }

2.1.3 实现插入child方法insertchild(node child, int index)

        // 向 children 指定索引处插入 child
        void insertchild(node child, int index) {
            system.arraycopy(children, index, children, index + 1, keynumber - index);
            children[index] = child;
        }

2.1.4 实现节点类内部工具方法

		// 移除指定 index 处的 key
        int removekey(int index) {
            int t = keys[index];
            system.arraycopy(keys, index + 1, keys, index, --keynumber - index);
            return t;
        }

        // 移除最左边的 key
        int removeleftmostkey() {
            return removekey(0);
        }

        // 移除最右边的 key
        int removerightmostkey() {
            return removekey(keynumber - 1);
        }

        // 移除指定 index 处的 child
        node removechild(int index) {
            node t = children[index];
            system.arraycopy(children, index + 1, children, index, keynumber - index);
            children[keynumber] = null; // help gc
            return t;
        }

        // 移除最左边的 child
        node removeleftmostchild() {
            return removechild(0);
        }

        // 移除最右边的 child
        node removerightmostchild() {
            return removechild(keynumber);
        }

        // index 孩子处左边的兄弟
        node childleftsibling(int index) {
            return index > 0 ? children[index - 1] : null;
        }

        // index 孩子处右边的兄弟
        node childrightsibling(int index) {
            return index == keynumber ? null : children[index + 1];
        }

        // 复制当前节点的所有 key 和 child 到 target
        void movetotarget(node target) {
            int start = target.keynumber;
            if (!leaf) {
                for (int i = 0; i <= keynumber; i++) {
                    target.children[start + i] = children[i];
                }
            }
            for (int i = 0; i < keynumber; i++) {
                target.keys[target.keynumber++] = keys[i];
            }
        }

2.2 b树类btree

public class btree {
    final int t; // 树中节点最小度数
    final int min_key_number; // 最小key数目
    final int max_key_number; // 最大key数目
    node root; // 根节点

    public btree() {
        this(2);
    }

    public btree(int t) {
        this.t = t;
        min_key_number = t - 1;
        max_key_number = 2 * t - 1;
        root = new node(t);
    }
}

2.2.1 实现是否存在某索引方法contains(int key)

    // 1. 是否存在
    public boolean contains(int key) {
        return root.get(key) != null;
    }

2.2.2 实现新增方法put(int key)

  思路：

• 首先查找本节点中的插入位置 i，如果没有空位（key 被找到），应该走更新的逻辑，目前什么没做
• 接下来分两种情况
  • 如果节点是叶子节点，可以直接插入了
  • 如果节点是非叶子节点，需要继续在 children[i] 处继续递归插入
• 无论哪种情况，插入完成后都可能超过节点 keys 数目限制，此时应当执行节点分裂
  • 参数中的 parent 和 index 都是给分裂方法用的，代表当前节点父节点，和分裂节点是第几个孩子

  判断依据为：

boolean isfull(node node) {
    return node.keynumber == max_key_number;
}

  代码实现：

    // 2. 新增
    public void put(int key) {
        doput(root, key, null, 0);
    }

    private void doput(node node, int key, node parent, int index) {
        int i = 0;
        while (i < node.keynumber) {
            if (node.keys[i] == key) {
                return; // 更新
            }
            if (node.keys[i] > key) {
                break; // 找到了插入位置，即为此时的 i
            }
            i++;
        }
        if (node.leaf) {
            node.insertkey(key, i);
        } else {
            doput(node.children[i], key, node, i);
        }
        if (node.keynumber == max_key_number) {
            split(node, parent, index);
        }
    }

2.2.3 实现分裂方法split(node left, node parent, int index)

  分两种情况：

• 如果 parent == null 表示要分裂的是根节点，此时需要创建新根，原来的根节点作为新根的 0 孩子
• 否则
  • 创建 right 节点（分裂后大于当前 left 节点的），把 t 以后的 key 和 child 都拷贝过去
  • t-1 处的 key 插入到 parent 的 index 处，index 指 left 作为孩子时的索引
  • right 节点作为 parent 的孩子插入到 index + 1 处

    /**
     * <h3>分裂方法</h3>
     *
     * @param left   要分裂的节点
     * @param parent 分裂节点的父节点
     * @param index  分裂节点是第几个孩子
     */
    void split(node left, node parent, int index) {
        // 分裂的是根节点
        if (parent == null) {
            node newroot = new node(t);
            newroot.leaf = false;
            newroot.insertchild(left, 0); // @todo keynumber 的维护（新节点没有孩子，应该不会有问题）
            this.root = newroot;
            parent = newroot;
        }
        // 1. 创建 right 节点，把 left 中 t 之后的 key 和 child 移动过去
        node right = new node(t);
        right.leaf = left.leaf;
        system.arraycopy(left.keys, t, right.keys, 0, t - 1);
        // 分裂节点是非叶子的情况
        if (!left.leaf) {
            system.arraycopy(left.children, t, right.children, 0, t);
            for (int i = t; i <= left.keynumber; i++) {
                left.children[i] = null;
            }
        }
        right.keynumber = t - 1;
        left.keynumber = t - 1;
        // 2. 中间的 key （t-1 处）插入到父节点
        int mid = left.keys[t - 1];
        parent.insertkey(mid, index);
        // 3. right 节点作为父节点的孩子
        parent.insertchild(right, index + 1);
    }

2.2.4 实现删除方法remove(int key)

  注意本删除方法是删除b树中某个节点的某个key，不是把整个节点删了

  主要分为以下情况：

  case 1：当前节点是叶子节点，没找到，直接返回

  case 2：当前节点是叶子节点，找到，因为是叶子节点，所以直接删

  case 3：当前节点是非叶子节点，没找到，要继续到孩子节点查找

  case 4：当前节点是非叶子节点，找到，再接着找到其后继key，替换被删除节点，然后删除后继key

  case 5：删除后 key 数目 < 下限 [ t - 1 ]（不平衡），进行平衡性调整（具体见 2.2.4）

  case 6：根节点

// 3. 删除
    public void remove(int key) {
        doremove(null, root, 0, key);
    }

    private void doremove(node parent, node node, int index, int key) {
        int i = 0;
        while (i < node.keynumber) {
            if (node.keys[i] >= key) {
                break;
            }
            i++;
        }
        // i 找到：代表待删除 key 的索引
        // i 没找到： 代表到第i个孩子继续查找
        if (node.leaf) {
            if (!found(node, key, i)) { // case1
                return;
            } else { // case2
                node.removekey(i);
            }
        } else {
            if (!found(node, key, i)) { // case3
                doremove(node, node.children[i], i, key);
            } else { // case4
                // 1. 找到后继 key
                node s = node.children[i + 1];
                while (!s.leaf) {
                    s = s.children[0];
                }
                int skey = s.keys[0];
                // 2. 替换待删除 key
                node.keys[i] = skey;
                // 3. 删除后继 key
                doremove(node, node.children[i + 1], i + 1, skey);
            }
        }
        if (node.keynumber < min_key_number) {
            // 调整平衡 case 5 case 6
            balance(parent, node, index);
        }
    }

2.2.4 实现平衡方法balance(node parent, node x, int i)

  删除后平衡主要分为以下情况：

  case 5-1：左边富裕，右旋

  case 5-2：右边富裕，左旋

  case 5-3：两边都不够借，向左合并

2.2.4.1 右旋

  一颗平衡的b树，如下

		    4
		 /     \
	  1,2,3     5,6

  删除key 5后变为

		    4
		 /     \
	  1,2,3     6

  此时节点6的key的数目小于下限，为了让节点6平衡，需要对key的数目+1，此时左边兄弟的节点富裕，所以可以通过右旋保持平衡

  1️⃣ 先把父节点4旋转下去，如下

		    4
		 /     \
	  1,2,3     4,6

  2️⃣ 再把左边兄弟节点的3旋转上去，b树恢复平衡，如下

		    3
		 /     \
	  1,2      4,6

2.2.4.2 左旋

  一颗平衡的b树，如下

		    3
		 /     \
	  1,2      4,5,6

  删除key 1后变为

		    3
		 /     \
	   2       4,5,6

  此时节点2的key的数目小于下限，为了让节点2平衡，需要对key的数目+1，此时右边兄弟的节点富裕，所以可以通过左旋保持平衡

  1️⃣ 先把父节点3旋转下去，如下

		    3
		 /     \
	   2,3      4,5,6

  2️⃣ 再把右边兄弟节点的4旋转上去，b树恢复平衡，如下

		    4
		 /     \
	   2,3      5,6

2.2.4.3 合并

  一颗平衡的b树，如下

		    3
		 /     \
	   1,2      4,5

  删除key 4后变为

		    3
		 /     \
	   1,2       5

  此时节点5的key的数目小于下限，为了让节点5平衡，需要对key的数目+1。但此时左边或右边的兄弟节点并不富裕，不能通过旋转的方式重新平衡，所以这类情况要使用合并（向左合并）

  1️⃣ 先把父节点3合并到最右边，如下

		   null
		 /      \
	   1,2,3      5

  2️⃣ 再把右边的兄弟节点元素合并到最右边，如下

		   null
		 /      
	   1,2,3,5

  3️⃣ 最后把0号孩子替换根节点，如下

	   1,2,3,5

2.2.4.4 代码实现

// 平衡
    private void balance(node parent, node x, int i) {
        // case 6 根节点
        if (x == root) {
            if (root.keynumber == 0 && root.children[0] != null) {
                root = root.children[0];
            }
            return;
        }
        node left = parent.childleftsibling(i);
        node right = parent.childrightsibling(i);
        // case 5-1 左边富裕，右旋
        if (left != null && left.keynumber > min_key_number) {
            // a) 父节点中前驱key旋转下来
            x.insertkey(parent.keys[i - 1], 0);
            if (!left.leaf) {
                // b) left中最大的孩子换爹
                x.insertchild(left.removerightmostchild(), 0);
            }
            // c) left中最大的key旋转上去
            parent.keys[i - 1] = left.removerightmostkey();
            return;
        }
        // case 5-2 右边富裕，左旋
        if (right != null && right.keynumber > min_key_number) {
            // a) 父节点中后继key旋转下来
            x.insertkey(parent.keys[i], x.keynumber);
            // b) right中最小的孩子换爹
            if (!right.leaf) {
                x.insertchild(right.removeleftmostchild(), x.keynumber); 
            }
            // c) right中最小的key旋转上去
            parent.keys[i] = right.removeleftmostkey();
            return;
        }
        // case 5-3 两边都不够借，向左合并
        if (left != null) {
            // 向左兄弟合并
            parent.removechild(i);
            left.insertkey(parent.removekey(i - 1), left.keynumber);
            x.movetotarget(left);
        } else {
            // 向自己合并
            parent.removechild(i + 1);
            x.insertkey(parent.removekey(i), x.keynumber);
            right.movetotarget(x);
        }
    }

---

3 b树java实现代码完整版（复制粘贴用）

import java.util.arrays;

/**
 * <h3>b-树</h3>
 */
@suppresswarnings("all")
public class btree {

    static class node {
        /**
         * 关键字
         */
        int[] keys;
        /**
         * 孩子们
         */
        node[] children;
        /**
         * 有效关键字个数（keys 中有效 key 数目）
         */
        int keynumber;
        /**
         * 是否是叶子节点
         */
        boolean leaf = true;
        /**
         * 最小度数 (最小孩子数)，它决定了节点中key 的最小、最大数目，分别是 t-1 和 2t-1
         */
        int t;

        /**
         * 构造方法（给最小度数赋值
         *
         * @param t 最小度数（t>=2）
         */
        public node(int t) {
            this.t = t;
            // 最小度数*2就是最多孩子数
            this.children = new node[2 * t];
            this.keys = new int[2 * t - 1];
        }


        public node(int[] keys) {
            this.keys = keys;
        }

        /**
         * 打印有效key，为了方便调试和测试，非必须
         */
        @override
        public string tostring() {
            return arrays.tostring(arrays.copyofrange(keys, 0, keynumber));
        }

        // 多路查找
        node get(int key) {
            int i = 0;
            while (i < keynumber) {
                if (keys[i] == key) {
                    return this;
                }
                if (keys[i] > key) {
                    break;
                }
                i++;
            }
            // 执行到此时 keys[i]>key 或 i== keynumber
            if (leaf) {
                return null;
            }
            // 非叶子情况
            return children[i].get(key);
        }

        // 向 keys 指定索引处插入 key
        void insertkey(int key, int index) {
            system.arraycopy(keys, index, keys, index + 1, keynumber - index);
            keys[index] = key;
            keynumber++;
        }

        // 向 children 指定索引处插入 child
        void insertchild(node child, int index) {
            system.arraycopy(children, index, children, index + 1, keynumber - index);
            children[index] = child;
        }

        // 移除指定 index 处的 key
        int removekey(int index) {
            int t = keys[index];
            system.arraycopy(keys, index + 1, keys, index, --keynumber - index);
            return t;
        }

        // 移除最左边的 key
        int removeleftmostkey() {
            return removekey(0);
        }

        // 移除最右边的 key
        int removerightmostkey() {
            return removekey(keynumber - 1);
        }

        // 移除指定 index 处的 child
        node removechild(int index) {
            node t = children[index];
            system.arraycopy(children, index + 1, children, index, keynumber - index);
            children[keynumber] = null; // help gc
            return t;
        }

        // 移除最左边的 child
        node removeleftmostchild() {
            return removechild(0);
        }

        // 移除最右边的 child
        node removerightmostchild() {
            return removechild(keynumber);
        }

        // index 孩子处左边的兄弟
        node childleftsibling(int index) {
            return index > 0 ? children[index - 1] : null;
        }

        // index 孩子处右边的兄弟
        node childrightsibling(int index) {
            return index == keynumber ? null : children[index + 1];
        }

        // 复制当前节点的所有 key 和 child 到 target
        void movetotarget(node target) {
            int start = target.keynumber;
            if (!leaf) {
                for (int i = 0; i <= keynumber; i++) {
                    target.children[start + i] = children[i];
                }
            }
            for (int i = 0; i < keynumber; i++) {
                target.keys[target.keynumber++] = keys[i];
            }
        }
    }


    final int t; // 树中节点最小度数
    final int min_key_number; // 最小key数目
    final int max_key_number; // 最大key数目
    node root; // 根节点


    public btree() {
        // 最小度数默认是2
        this(2);
    }

    public btree(int t) {
        this.t = t;
        root = new node(t);
        max_key_number = 2 * t - 1;
        min_key_number = t - 1;
    }

    // 1. 是否存在
    public boolean contains(int key) {
        return root.get(key) != null;
    }

    // 2. 新增
    public void put(int key) {
        doput(root, key, null, 0);
    }

    private void doput(node node, int key, node parent, int index) {
        int i = 0;
        while (i < node.keynumber) {
            if (node.keys[i] == key) {
                return; // 更新
            }
            if (node.keys[i] > key) {
                break; // 找到了插入位置，即为此时的 i
            }
            i++;
        }
        if (node.leaf) {
            node.insertkey(key, i);
        } else {
            doput(node.children[i], key, node, i);
        }
        if (node.keynumber == max_key_number) {
            split(node, parent, index);
        }
    }

    /**
     * <h3>分裂方法</h3>
     *
     * @param left   要分裂的节点
     * @param parent 分裂节点的父节点
     * @param index  分裂节点是第几个孩子
     */
    void split(node left, node parent, int index) {
        // 分裂的是根节点
        if (parent == null) {
            node newroot = new node(t);
            newroot.leaf = false;
            newroot.insertchild(left, 0); // @todo keynumber 的维护（新节点没有孩子，应该不会有问题）
            this.root = newroot;
            parent = newroot;
        }
        // 1. 创建 right 节点，把 left 中 t 之后的 key 和 child 移动过去
        node right = new node(t);
        right.leaf = left.leaf;
        system.arraycopy(left.keys, t, right.keys, 0, t - 1);
        // 分裂节点是非叶子的情况
        if (!left.leaf) {
            system.arraycopy(left.children, t, right.children, 0, t);
            for (int i = t; i <= left.keynumber; i++) {
                left.children[i] = null;
            }
        }
        right.keynumber = t - 1;
        left.keynumber = t - 1;
        // 2. 中间的 key （t-1 处）插入到父节点
        int mid = left.keys[t - 1];
        parent.insertkey(mid, index);
        // 3. right 节点作为父节点的孩子
        parent.insertchild(right, index + 1);
    }

    // 3. 删除
    public void remove(int key) {
        doremove(null, root, 0, key);
    }

    private void doremove(node parent, node node, int index, int key) {
        int i = 0;
        while (i < node.keynumber) {
            if (node.keys[i] >= key) {
                break;
            }
            i++;
        }
        // i 找到：代表待删除 key 的索引
        // i 没找到： 代表到第i个孩子继续查找
        if (node.leaf) {
            if (!found(node, key, i)) { // case1
                return;
            } else { // case2
                node.removekey(i);
            }
        } else {
            if (!found(node, key, i)) { // case3
                doremove(node, node.children[i], i, key);
            } else { // case4
                // 1. 找到后继 key
                node s = node.children[i + 1];
                while (!s.leaf) {
                    s = s.children[0];
                }
                int skey = s.keys[0];
                // 2. 替换待删除 key
                node.keys[i] = skey;
                // 3. 删除后继 key
                doremove(node, node.children[i + 1], i + 1, skey);
            }
        }
        if (node.keynumber < min_key_number) {
            // 调整平衡 case 5 case 6
            balance(parent, node, index);
        }
    }

    // 平衡
    private void balance(node parent, node x, int i) {
        // case 6 根节点
        if (x == root) {
            if (root.keynumber == 0 && root.children[0] != null) {
                root = root.children[0];
            }
            return;
        }
        node left = parent.childleftsibling(i);
        node right = parent.childrightsibling(i);
        // case 5-1 左边富裕，右旋
        if (left != null && left.keynumber > min_key_number) {
            // a) 父节点中前驱key旋转下来
            x.insertkey(parent.keys[i - 1], 0);
            if (!left.leaf) {
                // b) left中最大的孩子换爹
                x.insertchild(left.removerightmostchild(), 0);
            }
            // c) left中最大的key旋转上去
            parent.keys[i - 1] = left.removerightmostkey();
            return;
        }
        // case 5-2 右边富裕，左旋
        if (right != null && right.keynumber > min_key_number) {
            // a) 父节点中后继key旋转下来
            x.insertkey(parent.keys[i], x.keynumber);
            // b) right中最小的孩子换爹
            if (!right.leaf) {
                x.insertchild(right.removeleftmostchild(), x.keynumber);
            }
            // c) right中最小的key旋转上去
            parent.keys[i] = right.removeleftmostkey();
            return;
        }
        // case 5-3 两边都不够借，向左合并
        if (left != null) {
            // 向左兄弟合并
            parent.removechild(i);
            left.insertkey(parent.removekey(i - 1), left.keynumber);
            x.movetotarget(left);
        } else {
            // 向自己合并
            parent.removechild(i + 1);
            x.insertkey(parent.removekey(i), x.keynumber);
            right.movetotarget(x);
        }
    }

    private boolean found(node node, int key, int i) {
        return i < node.keynumber && node.keys[i] == key;
    }

    // 遍历树结构并打印节点的键值
    public void travel() {
        dotravel(root);
    }

    public void dotravel(node node) {
        if (node == null) {
            return;
        }
        int i = 0;
        for (; i < node.keynumber; i++) {
            dotravel(node.children[i]);
            system.out.println(node.keys[i]);
        }
        dotravel(node.children[i]);
    }
}

---

本文是博主的粗浅理解，可能存在一些错误或不完善之处，如有遗漏或错误欢迎各位补充，谢谢

  如果觉得这篇文章对您有所帮助的话，请动动小手点波关注💗，你的点赞👍收藏⭐️转发🔗评论📝都是对博主最好的支持~