B 树与 B+ 树：面向磁盘与数据库索引的结构
前面我们已经学过 BST、AVL、红黑树，它们都在解决一个核心问题：如何在内存中保持有序查找结构，并尽量让树高不要失控。但如果场景从“内存里的几万几百万条数据”，切换到“磁盘上的海量数据索引”，问题重点就会立刻变化。此时真正昂贵的，往往不再是一次内存比较，而是一次磁盘 I/O。
也就是说，到了数据库和文件系统这类场景里，决定性能的关键通常不是“旋转几次”“比较多少次”，而是：
我为了找到目标记录，需要访问多少个磁盘块？
这就是 B 树和 B+ 树出现的背景。它们可以理解成是“面向外存 I/O 的平衡查找树”。和前面的二叉平衡树相比，它们不再执着于一层只放一个关键字，而是让每个节点容纳更多关键字和更多孩子，从而极大降低树高。这一变化看似简单，实际上正是数据库索引结构最关键的一步。
一、为什么二叉搜索树不适合直接做磁盘索引
BST、AVL、红黑树在内存里很好用，但如果直接拿去做磁盘索引，会有一个明显问题：
- 每个节点通常只保存一个关键字；
- 树的分叉度较小；
- 当数据量非常大时，树高仍然可能不低；
- 每下一层都可能意味着一次新的磁盘块访问。
而磁盘 I/O 的代价远比内存访问高得多，所以：
- 即使查找路径只有十几层；
- 只要每层都要做磁盘访问；
- 性能也会明显吃不消。
所以外存索引真正要优化的是：
尽量让树变矮，让每次查找少做几次 I/O。
二、B 树的核心思想是什么
B 树的核心思想可以概括成一句话：
一个节点里不要只放一个关键字，而是放多个关键字和多个孩子指针，让每一层尽可能“装更多东西”。
这样一来：
- 每个节点的分支数大幅增加；
- 树高显著降低；
- 查找时经过的层数变少；
- 磁盘块利用率更高。
也就是说，B 树不是简单的“更复杂 BST”，而是为了适应磁盘块组织方式而重新设计的多路平衡搜索树。
三、什么是 B 树
B 树是一种多路平衡查找树。和二叉树不同，一个 B 树节点中通常包含：
- 多个关键字；
- 多个孩子指针；
- 并且关键字在节点内部有序。
对于一个节点来说：
- 它的关键字把值域划分成多个区间；
- 不同孩子指针分别指向不同区间的数据范围。
于是查找时就变成：
- 先在当前节点内部查找应该落在哪个区间；
- 再沿着对应孩子指针往下走。
所以 B 树仍然保留了搜索树的本质，只是把“二叉分叉”升级成了“多路分叉”。
四、B 树为什么树高很低
因为每个节点都能容纳很多关键字和很多孩子。
假设一个节点最多能有上百个孩子，那么：
- 第一层就能覆盖上百个区间；
- 第二层就能覆盖上万级别；
- 第三层可能就已经覆盖百万甚至更大规模数据。
于是即使数据量很大，树高也仍然很低，常常只有 2 到 4 层左右。这对磁盘索引来说意义巨大，因为：
- 查找一次，只需要少量块访问；
- I/O 次数被显著压缩。
五、B 树如何保持平衡
和 AVL、红黑树一样，B 树也必须保证查找路径稳定，不能任由某些分支特别深。
B 树保持平衡的关键规则通常是：
- 所有叶子节点在同一层；
- 每个节点关键字个数和孩子个数都受到上下界约束；
- 节点太满时要分裂；
- 节点太空时可能要借位或合并。
于是 B 树不会像普通 BST 那样轻易退化，而是始终保持一棵高度较低、比较均匀的多路平衡树。
六、B 树插入时为什么要分裂节点
插入新关键字时，通常先找到叶子位置。如果该叶子还有空间，直接插入即可；但如果节点已经满了，就必须处理“装不下”的问题。
典型做法是：
- 把中间关键字提升到父节点；
- 左右关键字分成两个新节点；
- 原节点被一分为二。
这就叫分裂。
分裂的意义是：
- 保持单个节点容量约束；
- 同时维护整体有序结构；
- 必要时还可能向上传播，甚至让根节点分裂，树高增加 1。
七、B 树删除时为什么会借位和合并
删除关键字后，如果某个节点变得太空，就可能违反最小容量约束。这时通常有两种修复方式：
1. 借位
如果相邻兄弟节点比较“富”，可以从兄弟节点借一个关键字，并通过父节点调整分隔关键字。
2. 合并
如果兄弟节点也不富裕，就可能把两个节点和父节点中的一个分隔关键字合并成一个更大的节点。
所以 B 树插入和删除虽然看起来比 BST 复杂，但本质仍然是在维护：
- 节点内部有序；
- 节点容量合法；
- 所有叶子同层。
八、什么是 B+ 树
B+ 树可以看作是 B 树的一种重要改进形式，也是数据库索引里更常见的版本。
它和 B 树最核心的区别通常有两点：
1. 所有实际记录或数据指针通常都放在叶子节点
内部节点主要保存索引关键字，用于导航。
2. 叶子节点通常会按顺序链接起来
形成一个有序链表，方便顺序扫描和范围查询。
可以简单理解成：
- B 树：内部节点和叶子节点都可能承载数据；
- B+ 树：内部节点更像“目录”，真正数据集中在叶子层。
九、为什么数据库更喜欢 B+ 树
这是非常关键的一点。
B+ 树之所以在数据库索引里更常见，通常有几个重要原因：
1. 内部节点更轻，更适合放更多索引项
因为不存真实数据，内部节点可以容纳更多关键字，于是树更矮。
2. 所有查询最终都会到叶子层，查询路径更稳定
无论命中与否，过程更统一。
3. 范围查询特别高效
因为叶子节点顺序链接，找到起点后可以沿叶子链表直接顺扫。
而数据库里：
- 范围查询；
- 排序扫描；
- 区间检索；
都非常常见，所以 B+ 树天然更适合这类需求。
十、B 树和 B+ 树最核心的区别怎么抓
可以先记住这样一个简化理解：
1. B 树
- 每层都可能命中数据；
- 内部节点和叶子节点都可能存实际记录。
2. B+ 树
- 内部节点主要做索引导航；
- 实际数据集中在叶子；
- 叶子之间顺序相连。
所以如果你的重点是：
- 单点查找；
- 范围扫描；
- 外存块利用率；
B+ 树通常更有工程优势。
十一、B+ 树和红黑树的应用边界有什么不同
这是非常常见、也非常重要的对比。
1. 红黑树
- 更适合内存结构；
- 节点小，局部调整灵活；
- 适合通用有序映射。
2. B+ 树
- 更适合磁盘页或外存块；
- 分叉高，树高低；
- 特别适合数据库索引和范围扫描。
所以不是说 B+ 树“更高级”，而是它更适合 I/O 敏感场景。
十二、为什么说 B+ 树是数据库索引的核心入门知识
因为只要谈到数据库索引，最终几乎都会碰到这些问题：
- 为什么索引树层数不高；
- 为什么查主键通常很快；
- 为什么范围查询可以顺着叶子扫；
- 为什么页分裂、页合并会影响性能；
- 为什么随机插入可能导致页分裂和碎片化。
而这些问题，背后几乎都和 B+ 树的结构设计直接相关。
所以学 B+ 树不只是为了应付面试，而是为了真正理解数据库索引底层为什么这么设计。
十三、学习 B 树 / B+ 树时最容易踩的坑
1. 只会背定义，不知道它们是为磁盘 I/O 优化的
这是最常见的问题。如果脱离外存背景，很多设计动机就看不懂。
2. 把 B 树和 B+ 树混成一回事
二者思想接近，但数据放在哪里、范围查询特性并不相同。
3. 以为它们只是“多叉版 BST”
它们更关键的价值，是面向块访问与低树高，而不只是多几个孩子。
4. 忽略叶子链表的重要性
这恰恰是 B+ 树支持高效范围扫描的核心优势之一。
总结
B 树和 B+ 树的重要性，不只是因为它们出现在数据库课程里，而是因为它们第一次让你真正从“内存数据结构”切换到“外存索引结构”的视角。真正值得先建立起来的，是这些核心认识：
- 外存场景里，真正昂贵的通常是磁盘 I/O，而不是单次比较；
- B 树通过让单个节点容纳多个关键字和孩子，显著降低树高；
- 节点分裂、借位、合并，是维护多路平衡查找树的核心机制；
- B+ 树把内部节点更多用于索引导航，把实际数据集中到叶子节点；
- 叶子有序链表让 B+ 树特别适合范围查询和顺序扫描；
- 真正学会 B 树与 B+ 树，不是会背定义，而是理解“为什么数据库索引不选红黑树，而更偏向 B+ 树”。
把这一篇理解透之后，后面再去看 Trie、跳表、哈希索引甚至数据库执行计划时，你会更容易把“索引结构设计”放到真实系统性能视角下去理解，而不是只停留在课本定义上。
参考资源：