很多人第一次被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 一次磁盘随机读有多贵用数字说话把数字摊开看会更直观。大致量级是这样的数据访问位置典型延迟L1 缓存约 1 纳秒内存约 100 纳秒SSD 随机读约 20 到 100 微秒机械硬盘随机读约 5 到 10 毫秒机械硬盘的随机读和内存比差距是几万倍。就算换成 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 段。所有叶子节点都在同一层树是绝对平衡的。注意m3 时每节点最多 2 个键看起来很像二叉树但它每个节点可能装两个键并不是普通 BST而且最多 2 个键只是特例。真正工程里的节点不会只有三五个键而是按磁盘页大小来定一个节点容纳几百上千个键很常见。2.2 m5 的插入过程分裂发生在最坏时机我用 5 阶B树m5演示插入序列 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 一张表看清差异对比项B树B树B*树数据存放位置每个节点都可能携带数据只有叶子节点携带数据同B树非叶子节点能装多少键受限于数据大小只存键能装更多同B树但填充率更高叶子节点链表没有有支持顺序访问一般没有查找路径长度可能中途命中总是走到叶子可能中途命中范围查询中序遍历会在层间回溯定位后沿链表顺序读同B树空间利用率约 50%约 50%约 66.7%典型场景文件系统目录、MongoDB早期存储关系型数据库索引教学示例、早期内存索引选型时最实用的判断方式是如果你遇到的是按 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 BBinary的误解和中序遍历有序的真相B 姓B的来源常见说法是发明者之一 Bayer 的首字母也有说代表 balance但肯定不是 binary。B树是多路搜索树孩子数量可以远大于 2没必要跟二叉树绑死。还有一个很多人没深想的知识点B树和B树的中序遍历结果都是升序。因为每个节点的键是按顺序排列的键和键之间夹着的子树正好落在两个键的值域中间。所以整棵树中序遍历有序这条性质是所有形式的平衡搜索树共享的不是只有二叉树才有。理解这一点你就能看懂为什么数据库索引可以直接按顺序输出记录而不需要额外排序。6.3 怎么证明你实现的B树确实是平衡的最后分享一个我写B树练习时沉淀下来的验证方法。手画分裂图只能覆盖少数情况随机操作后跑一次完整的一致性检查能抓住大部分隐性 bug。检查项按优先级排列从根递归返回每个节点到叶子的深度断言所有叶子的深度完全相同。这是绝对平衡的核心条件。检查每个节点的键数量在上下限之间根节点按特殊规则放宽下限。检查节点内键严格递增每个子树的所有键都落在对应值域范围内这能发现旋转借位时把键放错位置的经典错误。把整棵树中序遍历输出成序列与一个标准有序 list 对比验证中序有序。我当年写的第二个B树版本就是在借兄弟键后更新父节点分隔键这一步写错了导致某些路径上键序正确但范围越界普通测试用例根本试不出来。随机插入删除几千次后跑一致性检查立刻现出原形。后来所有同类数据结构的实现我都默认把这段 check 函数保留着每次跑完随机操作都过一遍。这个习惯帮我省了大量调式时间也比任何纸上推演都更让人放心。
