B树（B-Tree）是一种自平衡的多路查找树，广泛用于数据库和文件系统等存储系统中。B树的每个节点可以有多个子节点，并且每个节点可以存储多个键值，从而减少树的高度，减少磁盘I/O操作，提高搜索效率。B树是对二叉搜索树（BST）的推广，使其适用于更大规模的数据存储和查找。
B树的设计目标是：
减少树的高度：通过允许每个节点存储多个键值，降低树的高度，从而减少访问节点的次数，特别适合外存（磁盘）场景。提高磁盘访问效率：B树节点的大小通常与磁盘块的大小相匹配，使得每次访问都能加载一个完整的节点，减少不必要的磁盘I/O操作。1. B树的定义与性质
B树是满足以下性质的多路平衡树：
每个节点可以有多个子节点。假设B树的阶数为 m，则：
每个节点最多可以有 m 个子节点。每个非根节点至少有 ⌈m/2⌉ 个子节点。每个节点可以存储多个键值。假设阶数为 m，则：
每个节点最多可以存储 m−1 个键值。每个非根节点至少存储 ⌈m/2⌉−1 个键值。所有叶子节点处于同一层。B树始终保持平衡，树的所有叶子节点位于同一层，保证了查找操作的时间复杂度为 O(logn)。节点中的键值按照递增顺序排列。对于每个节点 xxx，设其键值为 k1,k2,...,kt−1，且节点有 t个子节点，满足：
左子节点的所有键值小于 k1。介于两个键值 ki和 ki+1 之间的子节点，其键值介于 ki 和 ki+1 之间。右子节点的所有键值大于 kt−1。2. B树的操作
B树中的查找、插入和删除操作与二叉搜索树相似，但由于B树的节点可以有多个子节点和多个键值，操作会稍微复杂一些。
2.1 查找操作
查找操作在B树中与二叉搜索树类似，都是基于比较键值的大小进行的。由于每个节点包含多个键值，查找时需要在节点内进行线性或二分查找，然后根据键值的大小决定是向左子树、右子树，还是当前节点中继续查找。
步骤：
从根节点开始，比较查找键值 k 与当前节点的键值集合。如果 k 在当前节点中，则查找成功。如果 k 小于某个键值，进入该键值对应的左子树。重复上述过程，直到找到键值或到达叶子节点。查找操作的时间复杂度为 O(logn)，其中 n 是树中的总元素数量。
2.2 插入操作
B树的插入操作类似于二叉搜索树，但需要处理节点分裂的情况。插入新元素可能会导致某个节点的键值超过其最大容量（即存储超过 m−1 个键值），这时候需要将该节点分裂，并将中间的键值上移到父节点。若父节点也满了，则继续向上分裂，直到根节点。如果根节点也分裂，则树的高度增加。
步骤：
查找插入位置：首先按照查找操作找到适当的叶子节点插入键值。插入键值：如果叶子节点未满，则直接插入键值到该节点，保持键值的排序。节点分裂：如果节点满了，则将该节点分为两个节点，并将中间的键值上移到父节点。若父节点也满了，重复分裂操作，直到不再需要分裂或处理到根节点。插入操作的最坏时间复杂度为 O(logn)，因为分裂操作最多向上递归到根节点。
2.3 删除操作
B树的删除操作比插入操作更复杂，删除一个键值可能导致某个节点的键值数量小于其最小容量（即少于 ⌈m/2⌉−1 个键值），此时需要进行合并或借位操作来保持B树的平衡。
步骤：
查找删除位置：首先按照查找操作找到要删除的键值。删除键值：如果删除的是叶子节点中的键值，直接删除。如果删除的是内部节点的键值，则需要找到前驱或后继键值，并替换该键值，然后删除前驱或后继节点中的键值。节点合并或借位：
如果删除后节点的键值数量小于最小容量，则需要从兄弟节点借一个键值（借位操作），或将当前节点与兄弟节点合并（合并操作）。若父节点的键值数量也小于最小容量，则向上递归进行合并或借位操作。删除操作的最坏时间复杂度同样为 O(logn)，因为合并或借位操作最多向上递归到根节点。
3. B树的优势与应用
优势
高效的磁盘I/O：B树节点通常较大，能够一次性读取大量数据，减少磁盘访问次数，特别适合大规模数据存储。自平衡：B树始终保持平衡，确保查找、插入和删除操作的时间复杂度为 O(logn)。更少的树高度：与二叉搜索树相比，B树通过允许每个节点存储多个键值，大大减少了树的高度，从而减少了查找路径。应用
B树广泛应用于需要大量数据存储和查找的场景，特别是涉及外存的场景：
数据库索引：大多数现代数据库系统使用B树或B+树作为索引结构，以支持高效的数据查找。文件系统：许多文件系统（如NTFS、FAT）使用B树来管理磁盘上的文件和目录。键值存储：一些键值存储系统使用B树来组织和查找数据，以支持快速的数据存取。4. B树的Java实现
以下是一个简单的B树的Java实现，展示了插入操作和查找操作的基本逻辑。
import java.util.ArrayList;
import java.util.Collections;
class BTreeNode {
int t; // B树的最小度数（阶数的半数）
ArrayList
ArrayList
boolean isLeaf; // 是否是叶子节点
public BTreeNode(int t, boolean isLeaf) {
this.t = t;
this.isLeaf = isLeaf;
this.keys = new ArrayList<>();
this.children = new ArrayList<>();
}
// 插入非满节点
public void insertNonFull(int key) {
int i = keys.size() - 1;
if (isLeaf) {
// 如果是叶子节点，直接插入
keys.add(0); // 占位
while (i >= 0 && keys.get(i) > key) {
keys.set(i + 1, keys.get(i));
i--;
}
keys.set(i + 1, key); // 插入新键值
} else {
// 如果不是叶子节点，找到合适的子节点递归插入
while (i >= 0 && keys.get(i) > key) {
i--;
}
i++;
if (children.get(i).keys.size() == 2 * t - 1) {
// 如果子节点已满，需要分裂
splitChild(i, children.get(i));
if (keys.get(i) < key) {
i++;
}
}
children.get(i).insertNonFull(key);
}
}
// 分裂子节点
public void splitChild(int i, BTreeNode y) {
BTreeNode z = new BTreeNode(y.t, y.isLeaf);
for (int j = 0; j < t - 1; j++) {
z.keys.add(y.keys.remove(t));
}
if (!y.isLeaf) {
for (int j = 0; j < t; j++) {
z.children.add(y.children.remove(t));
}
}
children.add(i + 1, z);
keys.add(i, y.keys.remove(t - 1));
}
// 查找键值
public boolean search(int key) {
int i = 0;
while (i < keys.size() && key > keys.get(i)) {
i++;
}
if (i < keys.size() && key == keys.get(i)) {
return true;
}
if (isLeaf) {
return false;
}
return children.get(i).search(key);
}
}
class BTree {
BTreeNode root;
int t;
public BTree(int t) {
this.t = t;
root = new BTreeNode(t, true);
}
public void insert(int key) {
BTreeNode r = root;
if (r.keys.size() == 2 * t - 1) {
BTreeNode s = new BTreeNode(t, false);
s.children.add(r);
s.splitChild(0, r);
root = s;
}
root.insertNonFull(key);
}
public boolean search(int key) {
return root.search(key);
}
}
public class Main {
public static void main(String[] args) {
BTree btree = new BTree(3);
int[] keys = {10, 20, 5, 6, 12, 30, 7, 17};
for (int key : keys) {
btree.insert(key);
}
System.out.println("查找键值 12: " + btree.search(12));
System.out.println("查找键值 25: " + btree.search(25));
}
}
5. 总结
B树是一种自平衡、多路查找树，特别适合大规模数据的存储和查找。B树的查找、插入和删除操作具有 O(logn)的时间复杂度。B树在数据库和文件系统中得到了广泛应用，特别是在涉及外存存储的场景中。