企业官网建设流程全解析

很多人第一次被B树系列难住，是在准备面试或者啃数据库原理的时候。那会儿脑子的印象就是"B树好像家谱一样，一个节点能放好几个键"，但一旦问到B+树为什么成了 InnoDB 的默认索引结构、B树到底比B+树强在哪，又说不清了。这次我把 B-树（也就是常说的B树）、B+树、B树放在一起捋一遍。它们不是一个东西的三个名字，而是在同一个出发点——减少磁盘访问——下演化了三个版本。看完这篇，你至少能回答三件事：它们各自解决了什么问题、插入删除时内部发生了什么、以及为什么你八成时间都在跟B+树打交道。

1. 为什么要为磁盘设计一棵树：B树出现前的问题

1.1 内存里的二叉树藏不住的危险

先回到最基础的问题：为什么我们不在内存里用二叉搜索树，然后直接抱着一棵红黑树去数据库建索引？

二叉搜索树在数据量不大的时候确实够用，插入、查找都是 O(log n)。就算数据顺序不理想导致退化成链表，也还有 AVL、红黑树这类平衡二叉搜索树把高度压住。问题不在这些树本身，而在它们为"内存访问成本近乎一致"这个前提设计的。

磁盘不一样。磁盘上的一次随机读，和内存里的一次随机访问，中间隔着几个数量级的时间差。数据库索引如果做成一棵二叉树，哪怕树高只有 20 层，一次查询最坏要访问 20 个节点；假设每次都落到磁盘上、每次 5 到 10 毫秒，一次查询跑出 100 毫秒以上是很正常的。这在 OLTP 场景下几乎不可接受。

所以 B 树系的核心思路非常简单：让每个节点尽可能多装键，树自然就矮了，查找时跨过的节点数就少了。树从"高瘦"变成"矮胖"，磁盘访问次数从几十次降到三五次。这个方向上的第一版成品，就是B树。

1.2 一次磁盘随机读有多贵（用数字说话）

把数字摊开看会更直观。大致量级是这样的：

机械硬盘的随机读和内存比，差距是几万倍。就算换成 SSD，随机读也比内存慢两三个数量级。所以磁盘索引的核心优化目标从来不是"CPU 少算几次"，而是"少跨几个节点、少读几个页"。B树用多路结构把节点数密度提升上去，同样 1 亿条数据，二叉搜索树要 27 层左右，而一颗 3 到 4 层的 B+树就能装完。这就是差距的来源。

1.3 多路树的直觉：用"宽度"换"高度"

B树和二叉树最直观的区别，是节点从"一个键两个子树"变成"多个键多个子树"。比如一棵 5 阶B树，每个节点最多能放 4 个键、分出 5 个孩子。树的高度下来了，宽度上去了，代价是每个节点的插入、删除、查找都不再是简单的局部操作，而是要维护一套"满了就分裂、少了就合并"的规则。

这套规则才是B树真正有含金量的部分。下面我用一个具体例子把插入和删除完整走一遍。

2. 把B树拆开看：定义、插入分裂、删除合并

2.1 五条规则把B树框得死死的

先给一个规范的 m 阶B树定义，后面所有操作都围绕它：

• 每个节点最多有 m 个孩子，最多 m-1 个键。
• 除根节点外，每个非叶节点至少有 ceil(m/2) 个孩子，也就是至少 ceil(m/2)-1 个键。
• 如果根节点不是叶子节点，它至少要有 2 个孩子。
• 有 k 个孩子的非叶节点，恰好包含 k-1 个键，这些键把孩子的键值范围切分成 k 段。
• 所有叶子节点都在同一层，树是绝对平衡的。

注意，m=3 时每节点最多 2 个键，看起来很像二叉树，但它每个节点可能装两个键，并不是普通 BST；而且"最多 2 个键"只是特例。真正工程里的节点不会只有三五个键，而是按磁盘页大小来定，一个节点容纳几百上千个键很常见。

2.2 m=5 的插入过程：分裂发生在最坏时机

我用 5 阶B树（m=5）演示插入序列 1 到 8，看叶子节点怎么一步步生长和分裂。

空树插入 1、2、3、4 时很简单，根节点逐个放进去，变成 [1,2,3,4]。插入 5 的时候，根节点已经满了，四键变五键，必须取中间的第 3 个键 3 提升为新根，左右各剩两个键：左边 [1,2]，右边 [4,5]。树从一层变成两层。

继续插入 6、7，都进右子树：插入 6 后右子树 [4,5,6]，插入 7 后 [4,5,6,7]，还没满。插入 8 时，右子树变成 [4,5,6,7,8] 五个键，必须分裂：中间键 6 上移到父节点，原节点变成 [4,5]，新生成节点 [7,8]。父节点从 [3] 变成 [3,6]，三个孩子分别是 [1,2]、[4,5]、[7,8]。

到这里能看出分裂的规律：当一个节点插入后键数达到 m，就把中间的键上交给父节点，左右各 m/2 个键形成两个新节点。如果父节点也满了，分裂会继续向上传播；如果一路传到根节点，根就分裂成两个节点，新的根带着这两个孩子往上顶，树高加 1。这是B树唯一的长高方式。

2.3 删除时的借钱与合并：谨慎处理下溢

删除比插入麻烦，因为要让节点在减少一个键之后仍然满足"键数不低于下限"的要求。以刚才那棵三层树 [3,6] 根、孩子 [1,2]、[4,5]、[7,8] 为例，删除 8：

第一步，8 在叶子节点 [7,8] 里，删掉后变成 [7]，只有 1 个键，低于 5 阶B树的叶子下限 2，下溢了。于是看左兄弟 [4,5]，它正好也是下限 2，借不了。既然左右都借不出，就做合并：把父节点的分隔键 6 拉下来，和左兄弟 [4,5] 以及当前节点 [7] 合并成 [4,5,6,7]，父节点少一个孩子，变成 [3]，合法。

如果合并导致父节点也下溢，就继续向上合并，甚至一路合并到根。最极端的情况是根节点失去唯一一个键，那根就空出来了，直接把它的唯一孩子提为新根，树高减 1。

如果删除时兄弟节点有富余键，就不用合并，而是做一次"旋转借位"：比如左兄弟有 3 个键，当前节点缺 1 个，就把父节点里的分隔键移到当前节点，再把左兄弟的最大键移到父节点位置。这样两边都合法，父节点键不变，树高不变。删除内部节点时还有个常用技巧：找左子树的最大键或右子树的最小键替换它，把问题从"删内部键"转化成"删叶子键"，然后按上面流程处理。

3. B+树凭什么成为数据库默认方案

3.1 非叶子节点彻底卸下"数据包袱"

B树已经能让查找次数少很多，但数据库最终选了B+树，核心原因是它进一步压缩了非叶子节点的"开销"。B+树的结构调整就两条：非叶子节点只存键、不存数据，所有数据都放在叶子节点；叶子节点之间用链表串起来。

这两条改动看着简单，实际效果很大。第一，非叶子节点不再背负数据指针、行记录甚至整行数据，单个节点能放下的路由键数量大幅增加。InnoDB 默认 16KB 一个页，如果键是 8 字节、指针是 6 字节，非叶子节点一页轻松放下上千个路由项；对比B树节点要同时存数据，同样一页能放下的键数少得多。键数多，树就矮；树矮，跨层 IO 就少。这是B+树成为默认方案的第一张王牌。

第二，关于"B-树"这个写法顺手提一句：B-树就是B树，中间的横线只是中文资料里为了和B+、B*对齐加上去的，它并不是"B减树"。网上看到"B减树"的说法可以无视。

3.2 叶子链表是怎么让范围查询飞起来的

B树做范围查询很尴尬。你想查 key 从 10 到 20 的所有数据，B树虽然中序遍历能得到有序序列，但查找过程中要在叶子节点和非叶子节点之间反复横跳，数据分散在不同层和不同分支。一旦范围跨多个叶子节点，你很难确定下一个比当前节点大的值到底在哪个子树，只能一层层回溯。

B+树因为所有数据都在叶子节点，并且叶子节点用链表从左到右串起来，范围查询就变成了：从根一路定位到第一个满足条件的叶子，然后顺着链表往后遍历。数据库里最常见的一个场景"SELECT * FROM table WHERE id BETWEEN 1000 AND 2000"就是这么高效的。顺序遍历对机械硬盘和 SSD 都友好，读的是连续页，不需要跳来跳去。这个特性让B+树在数据库里基本不可替代。

3.3 用InnoDB的例子算算三层能装多少行

InnoDB 的聚簇索引本身就是一棵B+树。主键索引的叶子节点直接存整行记录，二级索引的叶子节点存主键值，所以查二级索引经常还要回表。你可以按页大小粗算一下容量：

• 非叶子页假设能路由出约 1000 个孩子。
• 叶子页按每行 1KB 估算，一页大约存 15 行。
• 从根到叶子两层（root + 一层中间节点 + 叶子），约 1000 个中间节点 * 1000 个叶子页 * 15 行，约 1500 万行。
• 从根到叶子三层，约 1000 的三次方再乘以 15，就是百亿行量级。

这就是为什么多个千万行、上亿行的生产表，走主键查询依然很快——从根到叶子也就三次页读取。实际页填充率、行宽、碎片都会让数字缩水，但量级关系不会变。

InnoDB 还有一个小细节值得知道：插入时如果主键顺序随机（比如 UUID），叶子页会很早就分裂，页填充率低，产生大量碎片和随机写。生产环境里把 UUID 主键换成自增主键是我见过的最高频优化手段之一。这就是在跟 B+树的页分裂机制对着干，不如顺着它来。

4. B*树的"先借后裂"：空间利用率的最后挣扎

4.1 从单节点分裂到双节点分裂

B树最常见的定义，是"分裂前先尝试向兄弟借位"的B树变体。普通B树节点满了就立刻分裂成两个各 50% 填充的节点；B树则不一样：当节点满时，先看左右兄弟有没有多余空间，有的话就把一部分键挪给兄弟，同时更新父节点的分隔键，尽量推迟分裂。

只有当兄弟节点也满了，没办法再腾地方，才执行一次更复杂的"双节点分裂"：把当前节点、一个相邻兄弟节点、以及新插入的键全部合并到一起，重新平衡成三个节点。因为两个满节点加上一个新键大约有 2m-1 个键，分成三个节点后，每个节点大约分到 (2m-1)/3 个键，大概就是 2m/3 的填充率。这个填充率就是B*树名字的核心卖点：把节点平均利用率从 50% 附近拉高到 2/3 附近。

这里要注意，不同教材对B*树的描述侧重点不同，有的强调"所有非根节点填充至少 2/3"这个静态性质，有的强调"先转移再分裂"这个动态过程，但本质是同一件事的两面——高填充率是靠延迟分裂换来的。

4.2 2/3填充率到底省了多少节点

假设B树节点平均填充率约 50%，B树约 66.7%，同样的键数量下，B树需要的节点数是B树的 3/4 左右，也就是能少用大约 25% 的节点。节点少了，树会稍微矮一点，随机读的次数也能再少一点点。

但代价也摆在台面上：分裂逻辑从"只看自己一个节点"变成"要看自己和邻居两个节点"，插入路径上的锁范围更大，并发写入时更容易互相等待。数据库这种高并发环境里，锁粒度变大一丁点都可能引发连锁问题。所以B树更多出现在教学和文献里，现代数据库索引反而很少真正采用它。说白了，它解决的主要是空间利用率问题，而现代引擎有页压缩、页填充率可调这些手段之后，B树那点空间收益就有点鸡肋了。

5. 三兄弟同框：选型前先看这几个指标

5.1 一张表看清差异

选型时最实用的判断方式是：如果你遇到的是"按 key 精确查找 + 磁盘 IO 昂贵"的场景，B树和B+树都合格；如果还有大量范围查询和顺序扫描，直接选B+树；如果你极度在意空间占用、写并发不高，可以研究B*树的思路，但别指望在成熟数据库里找到现成实现。

5.2 真实数据库和文件系统里分别是谁在服役

MySQL 的 InnoDB 是B+树，这个最典型。PostgreSQL 的索引类型叫 btree，虽然名字叫 B-tree，但引擎实现里融入了很多B+树要素：非叶子节点存键和子页指针，叶子节点存键和元组定位信息，整体上还是"宽窄树"的底子。SQLite 的索引也是 B+树结构，页大小默认 4KB 可调。MongoDB 的 WiredTiger 存储引擎在数据文件里也用 B+树组织文档，按 _id 范围扫描时优势明显。

文件系统里B树同样不少见：HFS+ 的目录索引就是一颗 B 树，用于文件名查得又快又有序；NTFS 的目录索引用 B+树；Ext4 的 HTree 则是一种哈希B树变体，专门解决大目录下线性扫描文件名太慢的问题。

甚至内存场景也不是非B+树不可。Redis 的有序集合用跳跃表，是因为内存访问没有磁盘那种"跨层代价"，跳跃表实现简单、区间遍历顺手。所以别形成"B+树万能"的错觉，选型永远跟着瓶颈走。

6. 这些年常见的认知误区，以及一个验证技巧

6.1 最小度数t、阶数m、页大小，别被三套术语绕晕

《算法导论》里讲B树用的是"最小度数 t"，规则是每个节点有 t 到 2t 个孩子，即 t-1 到 2t-1 个键。国内不少教材讲"m 阶B树"，规则是每个节点最多 m 个孩子，最多 m-1 个键。两套表述可以换算，t 和 ceil(m/2) 有关，但面试时经常有人把 t 和 m 混用，导致满节点键数对不上。

我的建议是，面试时先明确问一句"你说的是算法导论的最小度数，还是 m 阶定义"，再动手推。工程上更常用的概念是"页大小加填充因子"，InnoDB 的索引页默认 16KB，决定了一个节点大概能装多少键，这才是你调参时真正关心的事。

6.2 "B=Binary"的误解和"中序遍历有序"的真相

B 姓"B"的来源常见说法是发明者之一 Bayer 的首字母，也有说代表 balance，但肯定不是 binary。B树是多路搜索树，孩子数量可以远大于 2，没必要跟二叉树绑死。

还有一个很多人没深想的知识点：B树和B+树的中序遍历结果都是升序。因为每个节点的键是按顺序排列的，键和键之间夹着的子树，正好落在两个键的值域中间。所以"整棵树中序遍历有序"这条性质，是所有形式的平衡搜索树共享的，不是只有二叉树才有。理解这一点，你就能看懂为什么数据库索引可以直接按顺序输出记录，而不需要额外排序。

6.3 怎么证明你实现的B树确实是平衡的

最后分享一个我写B树练习时沉淀下来的验证方法。手画分裂图只能覆盖少数情况，随机操作后跑一次完整的一致性检查，能抓住大部分隐性 bug。检查项按优先级排列：

• 从根递归，返回每个节点到叶子的深度，断言所有叶子的深度完全相同。这是"绝对平衡"的核心条件。
• 检查每个节点的键数量在上下限之间，根节点按特殊规则放宽下限。
• 检查节点内键严格递增，每个子树的所有键都落在对应值域范围内，这能发现旋转借位时把键放错位置的经典错误。
• 把整棵树中序遍历输出成序列，与一个标准有序 list 对比，验证"中序有序"。

我当年写的第二个B树版本，就是在"借兄弟键后更新父节点分隔键"这一步写错了，导致某些路径上键序正确但范围越界，普通测试用例根本试不出来。随机插入删除几千次后跑一致性检查，立刻现出原形。后来所有同类数据结构的实现，我都默认把这段 check 函数保留着，每次跑完随机操作都过一遍。这个习惯帮我省了大量调式时间，也比任何纸上推演都更让人放心。