B树（B-tree）是一种自平衡的树数据结构，常被用于数据库和文件系统中，能够高效地支持插入、删除和查找操作。B树通过增加每个节点的子节点数量来降低树的高度，从而减少查找、插入和删除的时间复杂度。在B树中，每个节点可以有多个子节点，并且可以存储大量的键值对。
B树最初是设计用来解决磁盘I/O操作效率低下的问题。在传统的二叉搜索树中，由于每个节点只有两个子节点，所以需要经常进行磁盘读写操作，效率较低。而B树通过增加每个节点的子节点数量，减少了树的高度，从而减少了磁盘I/O次数，提高了数据库的性能。
度 degree 指树中节点孩子数
阶 order 指所有节点孩子数最大值
B-树的特性：
- 每个节点最多有m个孩子,其中m称为B-树的阶;
- 除根节点和叶子节点外，其他每个节点至少有ceil(m/2）个孩子（ceil向大取整）；
- 每个节点最多有最小度数的两倍子节点数。同样最多有最小度数乘2减一个关键字数。
- 若根节点不是叶子节点，则至少有两个孩子；
- 所有叶子节点都在同一层;
- 每个非叶子节点由n个关键字和n+1个指针（孩子）组成，又因为每个节点至少有ceil(m/2）个孩子，所以其中ceil(m/2）-1<=n<=m-1；
- 关键字按非降序排列，即节点中的第i个关键字大于等于第i-1个关键字；
- 指针P[i]指向关键字值位于第i个关键字和第i+1个关键字之间的子树。
基本框架
先建立基本框架
package com.dreams.BTree;
import java.util.Arrays;
/**
* B-树
*/
public class BTree {
static class Node {
}
}Node节点作为类节点
static class Node {
int[] keys; // 关键字
Node[] children; // 孩子
int keyNumber; // 有效关键字数目
boolean leaf = true; // 是否是叶子节点
int t; // 最小度数 (最小孩子数)
public Node(int t) { // t>=2
this.t = t;
this.children = new Node[2 * t];
this.keys = new int[2 * t - 1];
}
public Node(int[] keys) {
this.keys = keys;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));
}
}该类节点还需要提供方法查找key
- 开始时，将索引变量 i 初始化为 0。
- 进入一个循环，该循环将检查当前节点中的关键字，如果找到与给定关键字相等的关键字，则返回当前节点。
- 如果当前关键字大于给定关键字，则退出循环，因为B树的性质保证了关键字按升序排列，所以后面的关键字肯定也大于给定关键字，没有必要继续查找。
- 如果当前关键字小于给定关键字，则增加索引 i，继续检查下一个关键字。
- 如果循环结束时，没有找到与给定关键字相等的关键字，则根据节点的属性判断：
- 如果当前节点是叶子节点(leaf为true)，则说明给定关键字不存在于B树中，返回null。
- 如果当前节点不是叶子节点，则递归地在相应的子节点(此时的i刚好对应的子节点)上执行相同的查找操作，直到找到叶子节点为止。
// 多路查找
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);
}然后是3个添加删除方法，这里只是添加和删除的方法，是内部类Node类的方法，不需要判断，判断的逻辑在 BTree类里，添加或删除就调用Node类的方法
// 向 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;
}
同样B树类还会有自己的属性
构造函数 BTree() 和 BTree(int t) 分别用于创建一个默认度数为 2 的B树和指定度数的B树。在构造函数中，会初始化根节点，并根据度数计算最小和最大关键字数目。
package com.dreams.BTree;
import java.util.Arrays;
/**
* B-树
*/
public class BTree {
static class Node {
//......
}
Node root;
int t; // 树中节点最小度数
final int MIN_KEY_NUMBER; // 最小key数目
final int MAX_KEY_NUMBER; // 最大key数目
public BTree() {
this(2);
}
public BTree(int t) {
this.t = t;
root = new Node(t);
MAX_KEY_NUMBER = 2 * t - 1;
MIN_KEY_NUMBER = t - 1;
}
}
是否存在
调用 root.get(key) 方法，该方法是B树节点 Node 类中的一个方法，用于在当前节点及其子节点中查找给定关键字。
如果 get(key) 方法返回的结果不为 null，则说明在B树中找到了包含给定关键字的节点，返回 true，表示存在该关键字。
// 1. 是否存在
public boolean contains(int key) {
return root.get(key) != null;
}
新增
逻辑：
- put(int key) 方法是对外公开的插入方法，它调用了私有方法 doPut(Node node, int key, Node parent, int index) 来实际执行插入操作。
- doPut 方法首先在当前节点中查找给定关键字的插入位置，通过循环遍历节点的关键字数组，找到第一个大于给定关键字的位置 i，如果找到了相同的关键字，则直接返回，因为不允许重复关键字。
- 如果当前节点是叶子节点，则调用节点的 insertKey(int key, int index) 方法将关键字插入到找到的位置 i 处。
- 如果当前节点不是叶子节点，则递归地调用 doPut 方法，在相应的子节点上执行插入操作，直到找到合适的叶子节点为止。
- 在插入完成后，检查当前节点的关键字数是否超过最大允许数，如果超过了，则进行分裂操作 split(node, parent, index)。
分裂操作会在节点关键字数达到最大限制时执行，保持B树的平衡性。
// 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);
}
}
分裂操作
执行过程：
- 如果分裂的节点是根节点，则需要创建一个新的根节点，并将分裂后的节点作为其孩子。在这个过程中，新的根节点会成为树的新根。
- 创建一个新的节点 right 用于存储分裂节点 left 中的后半部分关键字和孩子节点（如果存在）。
- 如果分裂的节点是叶子节点，那么分裂后新创建的节点也是叶子节点，反之亦然，因为B树要求叶子节点在同一层。
- 将 left 节点中第 t 个关键字及其后的关键字复制到 right 节点中，并更新 right 节点的关键字数。
- 如果分裂的节点 left 不是叶子节点，则需要处理其孩子节点。将 left 节点中第 t 个孩子节点及其后的孩子节点复制到 right 节点中，并将 left 节点中第 t 个孩子节点及其后的孩子节点设置为 null。
- 更新 left 节点和 right 节点的关键字数，使其符合 B 树的定义。
- 将 left 节点中第 t-1 个关键字插入到父节点 parent 的相应位置 index 中（ index 指left作为孩子时的索引）。
- 将 right 节点作为父节点 parent 的孩子节点，插入到位置 index + 1 中。
- parent==null 表示要分裂的是根节点，此时需要创建新根，原来的根节点作为新根的索引为0的孩子，然后逻辑与前面一样，就是创建 right 节点（分裂后大于当前 left 节点的），把t以后的 kcy 和 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);
// 如果分裂的节点是叶子节点，那么分裂后新创建的节点也是叶子节点，反之亦然，因为B树要求叶子节点在同一层。
right.leaf = left.leaf;
// 这里设置t-1的意思是最多拷贝t-1个
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);
}注意：我们重写了tostring方法，只打印有效值，所以在有效值更新前，debug只显示有效值
删除方法
为了方便操作，在内部类里添加一些工具方法。
// 移除指定 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];
}
}
逻辑：
1.remove(int key): 删除给定的键值。
2.doRemove(Node parent, Node node, int index, int key): 实际执行删除操作的递归方法。它接收当前节点、父节点、父节点中当前节点的索引和待删除的键值作为参数。
3.删除操作分为四种情况（case1 – case4）：
- case1: 待删除的键值在叶子节点中不存在，直接返回。
- case2: 待删除的键值在叶子节点中存在，直接删除。
- case3: 待删除的键值在非叶子节点中不存在，递归到子节点继续查找。
- case4: 待删除的键值在非叶子节点中存在，找到后继键值替换，然后继续递归删除后继键值。
4.balance(Node parent, Node x, int i): 平衡操作。当节点的关键字数低于最小要求时（MIN_KEY_NUMBER），需要进行平衡操作。分为几种情况：
- case 5-1: 左兄弟节点富裕，进行右旋。
- case 5-2: 右兄弟节点富裕，进行左旋。
- case 5-3: 左右兄弟节点都不足以借，需要合并节点。
5.found(Node node, int key, int i): 判断键值是否在当前节点中找到。
代码：
// 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;
}整个删除操作分为几个步骤：
1.在 remove 方法中，首先调用 doRemove 方法，并传入根节点、根节点、索引 0 和待删除的键值。doRemove 方法是真正执行删除操作的方法。
2.doRemove 方法中，首先通过循环找到要删除的键值在节点中的位置 i，这里的逻辑是if (node.keys[i] >= key) { break; }: 在循环中，检查当前关键字数组中的第 i 个关键字是否大于等于目标关键字 key。如果是，说明找到了目标关键字应该插入的位置，因此跳出循环。i++就是如果当前关键字不大于等于目标关键字 key，则继续迭代下一个关键字。循环结束后，i 的值代表了目标关键字 key 应该在的位置或者下一个应该查找的子节点的索引。
3.如果当前节点是叶子节点，进入 found 方法检查是否找到了要删除的键值：
- 如果没有找到（found 方法返回 false），说明待删除键值不在当前节点中，直接返回，不用再继续执行。
- 如果找到了，从当前节点中移除这个键值。
4.如果当前节点不是叶子节点，也没有找到，表示需要继续向下查找。根据找到的索引 i（上面循环出来后下一个应该查找的子节点的索引），递归调用 doRemove 方法，传入当前节点的第 i 个子节点。
5.如果当前节点不是叶子节点且找到了待删除的关键字：找到待删除关键字的后继关键字，即当前节点中第 i + 1 个孩子节点的最左边的关键字（通过循环找到最左边的叶子节点）（case4）。将后继关键字替换到当前节点中待删除的关键字位置。递归地在后继关键字所在的孩子节点中删除后继关键
6.如果删除操作导致节点的关键字数量小于最小要求（MIN_KEY_NUMBER），需要进行平衡操作，即调用 balance 方法。
7.balance 方法中，首先处理特殊情况：如果当前节点是根节点且根节点中没有关键字了，则将根节点的第一个子节点（如果存在子节点）设置为根节点。
8.否则，找到当前节点的左兄弟节点和右兄弟节点（如果存在），然后根据它们的关键字数量进行不同的处理：
- 如果左兄弟节点关键字数量大于最小要求，从左兄弟节点中借一个关键字和相应的子节点到当前节点中。（进行右旋。）
- 如果右兄弟节点关键字数量大于最小要求，从右兄弟节点中借一个关键字和相应的子节点到当前节点中。（进行左旋。）
- 如果左右兄弟节点都不满足条件，将当前节点与左（右）兄弟节点进行合并。
右旋示意图：
右旋操作步骤如下：
- 首先，检查左兄弟节点是否存在且关键字数量大于最小要求（left != null && left.keyNumber > MIN_KEY_NUMBER）。
- 如果满足条件：将父节点中的一个键值移动到当前节点中（x.insertKey(parent.keys[i – 1], 0)）。这个键值会插入到当前节点的最左边。
- 如果左兄弟节点不是叶子节点，还需要将左兄弟节点中最大的子节点（孩子）移动到当前节点中（x.insertChild(left.removeRightmostChild(), 0)）。
- 然后，将左兄弟节点中的最大键值移动到父节点中对应位置（parent.keys[i – 1] = left.removeRightmostKey()）。这样，左兄弟节点的关键字数减少了一个。
- 右旋操作完成后，函数返回。
右旋操作的效果是从左兄弟节点向当前节点移动一个键值和（如果存在）一个子节点，从当前节点向父节点移动一个键值，从而完成平衡调整。
如果存在子节点情况：
9.合并操作中，如果合并到左兄弟节点，将父节点中的相应关键字移动到左兄弟节点中，然后将当前节点的所有关键字和子节点移动到左兄弟节点中；如果合并到右兄弟节点，将父节点中的相应关键字移动到右兄弟节点中，然后将右兄弟节点的所有关键字和子节点移动到当前节点中。
合并操作左旋操作步骤如下：
如果存在左兄弟节点（left != null）：
- 首先从父节点中移除当前节点的索引位置（parent.removeChild(i)）。
- 然后将父节点中的一个键值移动到左兄弟节点中（ left.insertKey(parent.removeKey(i – 1), left.keyNumber);），此时左兄弟节点的关键字数增加了一个。
- 最后将当前节点中的所有键值和子节点移动到左兄弟节点中（x.moveToTarget(left)）。这个方法将当前节点的所有键值和子节点移动到指定节点中，并将当前节点标记为无效。
如果不存在左兄弟节点，则向右兄弟节点合并：
- 类似地，首先从父节点中移除当前节点的索引位置（parent.removeChild(i + 1)）。
- 然后将父节点中的一个键值移动到当前节点中（x.insertKey(parent.removeKey(i), x.keyNumber);），此时当前节点的关键字数增加了一个。
- 最后将右兄弟节点中的所有键值和子节点移动到当前节点中（right.moveToTarget(x)）。
这样，无论是向左兄弟节点合并还是向右兄弟节点合并，都将使得父节点中的一个键值被删除，当前节点的关键字数增加，以及一个兄弟节点的内容被移动到另一个节点中，从而完成了平衡调整。
注意：根节点唯一不平衡的情况是没有关键字，平衡操作就是将根节点的第一个子节点（如果存在子节点）设置为根节点即可。
参考
