B树与B+树：从磁盘到内存的索引艺术
说实话，我第一次接触B树的时候，心里想的是：这不就是二叉搜索树的变种吗？有什么了不起的。直到我在一个嵌入式数据库项目中，发现用二叉搜索树做索引，查询速度慢得让人抓狂——磁盘I/O成了瓶颈。嗯，那时候我才真正理解B树的价值。
今天咱们就来聊聊B树和B+树。这两个结构，说白了就是为磁盘而生的大块头索引。你想想看，内存里跑红黑树很快，但数据一多，放磁盘上，每次读一个节点就要一次I/O，那二叉树的深度就成灾难了。B树的核心思想就是：一个节点多存几个键，把树压扁，减少I/O次数。
B树的定义与阶
B树是一棵多路平衡搜索树。它的核心参数是阶（order），记作m。我习惯把阶理解为“一个节点最多能有多少个孩子”。
具体规则是这样的：
- 每个节点最多有m个孩子
- 每个节点（除根外）至少有⌈m/2⌉个孩子
- 根节点至少有两个孩子（除非它是叶子）
- 所有叶子节点在同一层
- 节点内的键值有序排列
举个例子，一棵5阶B树：
- 每个节点最多4个键，5个孩子
- 非根节点至少2个键（⌈5/2⌉ - 1 = 2）
- 树的高度比二叉搜索树矮得多
关键点：B树的阶决定了树的宽度和高度。阶越大，树越矮，但每个节点占用的空间也越大。我在项目中一般选m=100到500之间，具体看磁盘块大小。
B树的查找与插入
查找其实很简单。从根开始，在节点内做二分查找，找到就返回；没找到就沿着对应的孩子指针往下走。直到叶子节点。
插入就有点意思了。我刚开始写B树插入时，踩过一个坑——忘记处理节点分裂。你想想看，一个节点满了（有m-1个键），再插入一个键怎么办？
答案是：分裂。
- 把节点从中间劈开，中间键上提到父节点
- 左右两部分变成两个新节点
- 如果父节点也满了，继续往上分裂
- 最坏情况一直裂到根，树就长高一层
// 伪代码：B树插入核心逻辑
void btree_insert(Node* root, int key) {
if (root->key_count == MAX_KEYS) {
// 根节点满了，先分裂根
Node* new_root = create_node();
new_root->is_leaf = 0;
new_root->children[0] = root;
split_child(new_root, 0, root);
insert_nonfull(new_root, key);
return new_root;
} else {
insert_nonfull(root, key);
}
}避坑指南：我曾经在实现分裂时，忘记更新父节点的孩子指针数组，导致查找时直接越界。调试了整整一个下午。记住：分裂后，父节点的孩子数+1，键数+1，所有后续的孩子指针都要后移一位。
B+树的结构特点
B+树是B树的变种。说实话，实际工程中用B+树比B树多得多。为什么？因为B+树把数据全放在叶子节点，内部节点只存索引键。
结构特点：
- 内部节点只存键值，不存数据指针
- 所有数据记录都在叶子节点
- 叶子节点之间用链表连接
- 内部节点的键是“路由”作用，告诉你去哪个子树找
你想想看，这意味着什么？内部节点可以存更多的键，树更矮。而且叶子节点连成链表，范围查询就变得极其高效——找到起点后，顺着链表往后扫就行。
注意：B+树的插入和删除比B树稍微复杂一点，因为要维护叶子节点的链表。我建议你先实现B树，再改造成B+树，这样思路更清晰。
B树与B+树在数据库索引中的应用
数据库索引，说白了就是加速查询的数据结构。MySQL的InnoDB引擎用的就是B+树。为什么选B+树而不是B树？
| 特性 | B树 | B+树 |
|---|---|---|
| 内部节点存储 | 键+数据指针 | 仅键 |
| 叶子节点 | 分散存储 | 链表连接 |
| 范围查询 | 需要多次回溯 | 一次定位+顺序扫描 |
| 磁盘I/O次数 | 较多（节点含数据） | 较少（节点更紧凑） |
| 适用场景 | 点查询为主 | 范围查询+点查询 |
我在做嵌入式数据库时，遇到过一个问题：用B树做索引，每次查询都要从磁盘读一个完整的节点。如果节点里存了数据，那节点就大，一次I/O读的数据就少。换成B+树后，内部节点只存键，一个磁盘块能装几百个键，树的高度从4层降到了2层。查询速度提升了将近一倍。
嗯，这里有个细节：数据库的页大小通常是16KB。B+树的节点大小就按16KB来设计，保证一次I/O刚好读一个节点。这就是为什么B+树在数据库领域这么流行——它和磁盘的物理特性配合得天衣无缝。
总结一下我的经验：
- 如果应用场景是点查询（比如根据ID查一条记录），B树和B+树差别不大
- 如果涉及范围查询（比如查某段时间的所有记录），B+树完胜
- 如果内存足够大，B树的缓存命中率可能更高，但磁盘场景下B+树更优
- 实际工程中，90%的数据库索引都选B+树
最后说一句：B树和B+树的实现代码量不小，我建议你从B树开始写，理解分裂和合并的逻辑后，再改造成B+树。别一上来就搞B+树，容易把自己绕晕。