观察B树如何在插入和删除时保持平衡
B树是一种自平衡的多路搜索树，广泛应用于数据库和文件系统。每个节点可以有多个键和子节点，保持树的高度较低以实现高效的磁盘I/O操作。
| 操作 | 平均 | 最坏 |
|---|---|---|
| 查找 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) |
空间复杂度：O(n)
树高：O(log_m n)，其中 m 是阶数
MySQL InnoDB 使用 B+ 树作为主索引和辅助索引
NTFS、HFS+、ext4 使用 B 树变体进行目录索引
LevelDB、RocksDB 使用基于 B 树原理的 LSM 树
class BTreeNode:
def __init__(self, leaf=True):
self.keys = []
self.children = []
self.leaf = leaf
class BTree:
def __init__(self, order=4):
self.root = BTreeNode()
self.order = order # Maximum children
self.min_keys = (order + 1) // 2 - 1
def search(self, key, node=None):
"""Search for a key in the B-Tree"""
if node is None:
node = self.root
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return (node, i)
elif node.leaf:
return None
else:
return self.search(key, node.children[i])
def insert(self, key):
"""Insert a key into the B-Tree"""
root = self.root
if len(root.keys) == self.order - 1:
# Root is full, need to split
new_root = BTreeNode(leaf=False)
new_root.children.append(self.root)
self._split_child(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key)
def _split_child(self, parent, index):
"""Split a full child node"""
order = self.order
child = parent.children[index]
mid = (order - 1) // 2
# Create new node with right half
new_node = BTreeNode(leaf=child.leaf)
new_node.keys = child.keys[mid + 1:]
if not child.leaf:
new_node.children = child.children[mid + 1:]
# Promote middle key
parent.keys.insert(index, child.keys[mid])
parent.children.insert(index + 1, new_node)
# Truncate original child
child.keys = child.keys[:mid]
if not child.leaf:
child.children = child.children[:mid + 1]
# Usage
btree = BTree(order=4)
for val in [10, 20, 5, 15, 25, 30]:
btree.insert(val)
print(btree.search(15)) # Found
import java.util.ArrayList;
import java.util.List;
public class BTree {
private BTreeNode root;
private int order;
public BTree(int order) {
this.order = order;
this.root = new BTreeNode(true);
}
public boolean search(int key) {
return searchNode(root, key) != null;
}
private BTreeNode searchNode(BTreeNode node, int key) {
int i = 0;
while (i < node.keys.size() && key > node.keys.get(i)) {
i++;
}
if (i < node.keys.size() && key == node.keys.get(i)) {
return node;
}
if (node.leaf) {
return null;
}
return searchNode(node.children.get(i), key);
}
public void insert(int key) {
BTreeNode r = root;
if (r.keys.size() == order - 1) {
BTreeNode newRoot = new BTreeNode(false);
newRoot.children.add(root);
splitChild(newRoot, 0);
root = newRoot;
}
insertNonFull(root, key);
}
private void splitChild(BTreeNode parent, int index) {
BTreeNode child = parent.children.get(index);
int mid = (order - 1) / 2;
BTreeNode newNode = new BTreeNode(child.leaf);
for (int j = mid + 1; j < child.keys.size(); j++) {
newNode.keys.add(child.keys.get(j));
}
if (!child.leaf) {
for (int j = mid + 1; j <= child.children.size() - 1; j++) {
newNode.children.add(child.children.get(j));
}
}
parent.keys.add(index, child.keys.get(mid));
parent.children.add(index + 1, newNode);
// Truncate child
while (child.keys.size() > mid) {
child.keys.remove(child.keys.size() - 1);
}
}
public static void main(String[] args) {
BTree tree = new BTree(4);
int[] values = {10, 20, 5, 15, 25, 30};
for (int v : values) tree.insert(v);
System.out.println(tree.search(15)); // true
}
}
class BTreeNode {
List<Integer> keys = new ArrayList<>();
List<BTreeNode> children = new ArrayList<>();
boolean leaf;
BTreeNode(boolean leaf) {
this.leaf = leaf;
}
}