Javajava算法
B-树原理详解与Java模拟实现
B-树原理详解与Java模拟实现 一、B-树定义与特性 定义 B-树（B-Tree）是一种平衡的多路查找树（M路，M≥2）。它可以是空树，每个节点可拥有多个子节点，从而有效降低树高，提升查找效率。 特性 根节点至少有两个子节点。 每个非根节点至少有 ⌈M/2⌉ - 1 个关键字，至多有 M - 1 个关键字，且关键字按升序排列。 每个非根节点至少有 ⌈M/2⌉ 个子节点，至多有 M 个子节点。 关…
B-树原理详解与Java模拟实现 一、B-树定义与特性 定义 B-树（B-Tree）是一种平衡的多路查找树（M路，M≥2）。它可以是空树，每个节点可拥有多个子节点，从而有效降低树高，提升查找效率。 特性 根节点至少有两个子节点。 每个非根节点至少有 ⌈M/2⌉ - 1 个关键字，至多有 M - 1 个关键字，且关键字按升序排列。 每个非根节点至少有 ⌈M/2⌉ 个子节点，至多有 M 个子节点。 关…
B-树（B-Tree）是一种平衡的多路查找树（M路，M≥2）。它可以是空树，每个节点可拥有多个子节点，从而有效降低树高，提升查找效率。
⌈M/2⌉ - 1 个关键字，至多有 M - 1 个关键字，且关键字按升序排列。⌈M/2⌉ 个子节点，至多有 M 个子节点。key[i] 和 key[i+1] 之间的子树中，所有节点的值均介于两者之间。以 M=3 为例，每个节点最多存储 2 个关键字，将区间分为 3 部分，最多有 3 个子节点。为便于实现，通常允许节点暂时插入第 3 个关键字后再触发分裂（即节点最多容纳 3 个关键字、4 个子节点）。
以下以插入序列 [53, 139, 75, 49, 145, 36, 101] 为例演示构建过程：
M。若未达到，插入完成。M），则执行分裂：
用于同时返回查找到的节点及关键字索引。
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; }
}
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;
}
返回 Pair<BTRNode, Integer> 的原因：
-1 表示应插入该节点）。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);
}
public boolean insert(int key) {
if (root == null) {
root = new BTRNode();
root.keys[0] = key;
root.usedSize++;
return true;
}
Pair<BTRNode, Integer> pair = find(key);
if (pair.getVal() != -1) {
return false; // 关键字已存在
}
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++;
// 插入均在叶子节点进行，无需处理子节点
if (parent.usedSize < M) {
return true;
} else {
split(parent);
return true;
}
}
private void split(BTRNode cur) {
BTRNode newNode = new BTRNode();
BTRNode parent = cur.parent;
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;
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;
parent.subs[endT + 2] = newNode;
parent.usedSize++;
// 递归检查父节点是否需要分裂
if (parent.usedSize >= M) {
split(parent);
}
}
private void inorder(BTRNode node) {
if (node == null) return;
for (int i = 0; i < node.usedSize; ++i) {
inorder(node.subs[i]);
System.out.println(node.keys[i]);
}
inorder(node.subs[node.usedSize]);
}
public class MyBTree {
// 包含上述所有内部类与方法
public static void main(String[] args) {
MyBTree tree = new MyBTree();
int[] array = {53, 139, 75, 49, 145, 36, 101};
for (int k : array) {
tree.insert(k);
}
tree.inorder(tree.root);
}
}
运行结果将按升序输出所有关键字。
删除操作需保证删除后节点关键字数仍满足 ≥ ⌈M/2⌉ - 1。
≥ ⌈M/2⌉ - 1，删除结束。> ⌈M/2⌉ - 1，则将父节点对应关键字下移至当前节点，兄弟节点的一个关键字上移至父节点。(注：删除过程涉及多次节点形态变化，可参考原图演示步骤 a~e)
B+树是 B-树的变种，主要区别如下：
关系型数据库索引（如 InnoDB）、文件系统目录管理、缓存系统等。
B*树是 B+树的进一步优化：
2/3（B+树为 1/2），减少分裂频率。更高的空间利用率、更好的平衡性、更少的磁盘 I/O。
B-树及其变种（B+树、B*树）通过多路平衡结构，完美契合磁盘存储特性，是现代数据库与文件系统的核心基石。理解其分裂、合并与索引机制，对系统设计与性能调优具有重要意义。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online