一、B树基础：从磁盘I/O到多路平衡查找

说起B树，我得先坦白一件事。刚入行那会儿，我总觉得二叉树就够用了，搞什么B树？直到有一次做数据库索引优化，一张千万级的表，用AVL树做索引，查询慢得让人抓狂。后来一分析，问题出在磁盘I/O上——树太高了，每次查找都要读好几次磁盘。嗯，B树就是为解决这个问题而生的。

1.1 什么是B树？为什么需要它？

B树是一种多路平衡查找树。说白了，它允许一个节点存多个关键字，也有多个子节点。你想想看，二叉树每个节点最多俩孩子，B树可以有一堆孩子。这样树的高度就大大降低了。

举个例子：

• 一棵200万节点的二叉树，高度大约21层
• 一棵200万节点的B树（阶数m=100），高度只有3-4层

磁盘I/O是内存操作的几万倍慢，每多一层就多一次磁盘读取。B树矮胖的结构，正是为了减少磁盘访问次数。我在项目中遇到过，把索引从二叉树换成B树后，查询耗时从秒级降到了毫秒级。

1.2 B树的定义与阶

先给个正式定义。一棵m阶B树（m≥3），满足以下条件：

1. 每个节点最多有m个子节点（m-1个关键字）
2. 除根节点外，每个节点至少有⌈m/2⌉个子节点（⌈m/2⌉-1个关键字）
3. 根节点至少有两个子节点（除非它也是叶子）
4. 所有叶子节点在同一层——这是平衡的关键
5. 节点内关键字有序排列，左子树的关键字都小于当前关键字，右子树都大于

来看一个3阶B树的例子（3阶也叫2-3树）：

        [30, 70]
       /    |    \
   [10,20] [40,50] [80,90]

每个节点最多3个子节点，最少⌈3/2⌉=2个子节点（根节点除外）。

1.3 B树的查找

B树的查找和二叉查找树很像，只不过每个节点里多了几个关键字。流程是这样的：

1. 从根节点开始
2. 在当前节点内顺序查找（或二分查找）关键字
3. 如果找到，返回
4. 如果没找到，根据关键字大小，进入对应的子树继续查找
5. 直到叶子节点还没找到，说明不存在

我建议你记住：B树查找的时间复杂度是O(logₘn)，其中m是阶数。因为树高大约是logₘn，每个节点内查找是O(log m)（如果用二分查找的话）。

1.4 B树的插入——节点分裂

插入操作是B树最核心也最复杂的部分。核心思想就一句话：先插进去，满了就分裂。

具体步骤：

1. 先查找，找到要插入的叶子节点位置
2. 如果叶子节点没满（关键字数 < m-1），直接插入
3. 如果叶子节点满了（关键字数 = m-1），就要分裂

分裂过程：

• 把当前节点的关键字分成三部分：左半、中间关键字、右半
• 中间关键字上提到父节点
• 左半和右半分别成为两个新节点
• 如果父节点也满了，继续向上分裂，直到根节点
• 如果根节点也分裂了，树的高度增加1

来看一个5阶B树插入的例子（m=5，每个节点最多4个关键字）：

初始状态（根节点已满）：
[10, 20, 30, 40]

插入25：
1. 找到根节点，发现满了
2. 分裂根节点：
   中间关键字20上提为新根
   左：[10]  右：[30, 40]
3. 将25插入到右子节点
   右子节点变为：[25, 30, 40]

最终结果：
      [20]
     /    \
  [10]   [25, 30, 40]

1.5 核心知识图谱

下面这张图帮你理清B树的核心脉络：

1.6 为什么B树这么重要？

说白了，B树就是为磁盘存储量身定做的数据结构。它的设计哲学是：用一次磁盘读取，获取尽可能多的信息。

对比一下：

特性	二叉查找树	B树
树高	O(log₂n)	O(logₘn)，m通常很大
磁盘I/O次数	≈树高	≈树高，但树高小得多
节点内查找	O(1)（比较一次）	O(log m) 或 O(m)
适用场景	内存数据	磁盘/数据库索引

你想想看，数据库里几亿条记录，用二叉树要查30多次磁盘，用B树可能3-4次就够了。这就是为什么MySQL的InnoDB引擎用B+树（B树的变种）做索引。

好了，B树的基础就讲到这里。记住三个核心：阶决定了扇出、查找就是多路二分、插入满了就分裂。下一节我们会深入B树的删除操作，那个比插入还要麻烦一点。

---

公众号:蓝海资料掘金营，微信deep3321