我最早意识到“二叉树不够用”是在做内存缓存时。排序双层树查两侧能够应对百万级数据但一旦数据跑到千万级树的高度就迅速涨起来区间的每一次点查变成 20 余次节点跳转。那时在 Java 里跑递归遍历又频繁爆栈后来到了数据库项目里看 InnoDB才真正把“多叉平衡树”这个概念刻进脑子里——B树、B树不光是教科书典故更是今天索引底部的路基石。这篇聊的就是这个进化过程二叉搜索树为什么会被多叉树替代、B树怎么保证平衡、B树又为什么能在数据库里常年占据索引首选位置。适合正在学数据结构、准备面试或者刚接触数据库索引却想弄明白底层原理的朋友。1. 先搞清来龙去脉为什么数据库索引需要一棵多叉树1.1 二分搜索树的美丽与脆弱二叉搜索树的美好之处是每个节点都维持一个“左小右大”的体系把根节点当作切分点比根小的往左比根大的往右。一次查找过程中只要每层的方向选择正确理论上能把复杂度降到 O(log2 n)。二层的 n100 万时log2 大约 20n10 亿时log2 约 30。这组数字很美但它建立在“树足够矮胖”这个前提下。二叉树的问题恰恰出在平衡性上。如果按递增顺序插入数据普通二叉搜索树会退化成一条链表根节点 1右子是 2右子的右子是 3……这时查询和插入都变成线性扫描树高等于节点数100 万条数据就是 100 万层。于是有了 AVL 树每个节点的左右子树高度差不能超过 1旋转是它维持平衡的手段。红黑树又把约束放宽了一些用颜色规则保证最长路径不超过最短路径的两倍从而把树高控制在 2log2 n 的级别。但这里有个隐藏比较二叉平衡系再怎么优化高度仍然是对数级而且每个节点只保存一个数据块。只有当数据量小到可以完全放进内存、随机访问内存又快得离谱时二叉树才能优雅发挥。一旦数据需要放在磁盘上情况就完全变了。磁盘随机读写一次的时间在毫秒量级而内存随机访问是纳秒量级差了好几万倍。如果一次查询需要跳 20 层意味着可能要读 20 个不同的磁盘页查询速度就是灾难。1.2 磁盘 I/O 的脾气决定了树的形态数据库里最基本的数据单位是页InnoDB 默认页大小是 16KB。磁盘按页读写跟按字节读写相比少了一次是一次它并不擅长“内存里那种随点随到”的访问模式。任何索引结构想在数据库里活得好都得尽量让每次查询只读少数几页而且这几页最好连续。B树就是在这种思路下被提出来的放弃“每个节点只能有两个孩子”改成让一个节点里塞进大量关键字对应有大量孩子指针从而让树从“瘦高”变成“矮胖”。矮胖树的高度压缩直接断掉了一个根到叶子之间的路径长度。假设一个节点可以容纳 1000 个关键字那么 100 万条记录只需要三层树结构第一层 1 个节点第二层 1000 个节点第三层 100 万个叶子节点。百万数据查询可能只需读三次磁盘页。这就是“多叉”的价值。这个思路不是某个人硬造出来的而是被磁盘的物理特性逼出来的。内存项目可能继续玩红黑树范围扫描都不设边界。1.3 从“二叉”到“多叉”是一条自然进化把节点变宽树的高度降低这是整体趋势。二叉树的一个节点是“1 个键 2 个指针”B树只是把它推广成“m-1 个键 m 个指针”。二叉平衡树的旋转规则在多叉树身上变成了节点的分裂与合并。比如节点塞满了就拆成两个兄弟并把中间键上交到父节点删除导致节点太稀疏就找左边或右边的兄弟借键借不到就合并。这些操作看着陌生但本质和旋转维护的平衡是一回事所有叶子节点保持同一层树高恒定。数据库中最常见的 B树比 B树更进一步。它把“数据记录”全部收进叶子节点内部节点只做路标。于是同样高度的树能容纳的关键字更多查询路径也更稳定。下面两章分别拆开看它们的结构、操作和边界弄清楚这两个主体之后第四章再面对 InnoDB 时会踏实得多。2. B树设计全景节点、关键字、分裂与合并2.1 阶数、节点结构和“半满”约束B树的参数叫“阶”m。一个 m 阶 B树每个节点最多有 m 个子节点最多存 m-1 个关键字除非根节点外每个非根节点至少有 ceil(m/2) 个子节点也就是说至少有 ceil(m/2)-1 个关键字。注意这个“至少一半”的约束正是它控制空间的机制。如果允许一个节点只有 1 个键和 2 个孩子那它就在退化成二叉树如果允许空节点树的高度就无法保证。每个节点内部关键字按升序排列子指针夹在关键字之间。结构可以写成struct BTreeNode { int keyCount; Key keys[m]; BTreeNode* children[m]; bool isLeaf; }其中孩子们的长度是 m键的长度是 m-1但为了方便插入临时溢出很多实现会把 children 和 keys 都留出一位缓冲。节点里真正的规则是对于任意索引 i孩子指针 children[i] 指向的子树中所有键都小于 keys[i]而 children[i1] 指向的子树中所有键都大于 keys[i]。七个关键排序、八个孩子这句描述可以概括 B树节点的逻辑。设计者为什么设置“至少半满”从直觉看如果删操作频繁发生且允许节点越来越空树的页数量就会无意义膨胀磁盘空间浪费掉不说树也容易越变越深。反之强制半满后即便发生合并树依然保持稳定体积。搜索一颗 100 万节点的树高度不会超过一个上界这个上界跟阶数的对数值相关。2.2 查找、插入与节点分裂的完整过程B树的查找类似于二维搜索从根开始在当前节点的键序列里顺序或二分查找目标。如果命中返回如果找到合适的位置但没命中就顺着相应的孩子指针下走一层直到叶子节点为止。区别在于B树可以在非叶子层命中并直接返回不必一路到底。这给等值查询带来了随机性也成了 B树在数据库中被替换的潜在原因之一。插入的算法更有意思。刚开始插入会一直走到对应的叶子节点把键按序塞进叶子。如果塞完后键的个数没有超过 m-1万事大吉。如果超过这个叶子就要分裂把排序后的键从中间切成两半左半边留在原节点右半边放进一个新节点中间那个键则“上升”到父节点同时把新节点指针插到父节点的对应孩子位置。父节点多了一个键和一个孩子后也可能超载于是继续向上分裂。这个过程一路走到根如果根节点也超载就分裂根并新建一个根节点整个树高度因此增加一层。我这里用一个插满的例子来说明分裂的具体表现。假设这是一棵 5 阶 B树最多存 4 个键。某个叶子节点原本有“10, 20, 30, 40”这时要插 25。插入后节点内容是“10, 20, 25, 30, 40”已经超过 4 个。分裂点在中间键 25 上左节点留“10, 20”右节点留“30, 40”键 25 上交给父节点。父节点原来可能有“12, 18, 2435”插入 25 后同样是 5 个键继续按同样规则向上提中间键。通过这种连环上升B树保证所有叶子在同一层因为每一层都是从下往上逐级长高的。这里有一个不少初学者踩过的坑分裂时忘了给新节点分配孩子数组的内存或者没有把原节点第 k 个孩子之后的孩子指针搬到新节点。键搬过去了孩子没搬过去再查询时在子树中随机指针乱转最终的回报往往是段错误或空指针。插入流程看起来只是在一个节点里做局部变动但它牵动了父节点的排序结构孩子指针的数量永远比键多 1变动时最容易漏掉的就是“多出来的那个指针”。2.3 删除、合并与向相邻兄弟借位删除是 B树所有操作里最麻烦的因为要维持“至少半满”的约束。最忌粗暴地删掉一个键后就结束那会让叶子节点变得太空。删除分两种情况如果要删除的键在内部节点需要找到它的后继键在后继子树的最左边叶子中用后继键顶替被删除的位置然后向下递归处理后继键的删除如果要删的真实位置是叶子则直接删删完检查是否违反下限。如果叶子在删除后键数低于下限先看左右相邻兄弟节点。如果某兄弟键数高于下限就“借”一个键过来同时父亲节点的相应键也要旋转一下以保证排序正确。借键时你借走的其实是兄弟靠边界位置的键而父节点下降一个键补到自己的节点兄弟把边界键顶上父节点。在这个过程中节点各自保持有序数量都没低于下限。如果兄弟也太少合并就是必然选择。合并的典型步骤是把父节点中夹在两个节点之间的一个键拉下来跟左节点的全部键、右节点的全部键以及右节点的全部孩子拼成一个新节点。父节点因此少了一个键和一个孩子。然后父节点继续检查是否低于下限如果不满足就继续对父节点做同样操作一路借位或合并直到根节点。如果根节点最后只剩一个键且没有孩子就可以删掉这一层让整个树的高度减一。删除操作里最经典的坑是只关注了键的数量没有同步更新父节点中的分隔键。比如向右兄弟借一个键时父亲节点里原先那个比两者都大的分隔键经过旋转后必须变成兄弟借出去那个键的新值很多手写代码在这里漏一个赋值导致后续查询经过父节点时分隔键错位明明存在的数据却查不到。调试这类错位问题时我通常会在纸上画出三个节点和父节点的父子关系把分隔键标出来一分多钟就能发现到底哪里没对齐。3. B树把“能不能查到”优化成“查得有多快”3.1 B树的结构约定与 B树的核心差异B树里的孩子指针和键的排列方式与 B树基本一致最根本的差别是“语义边界”所有实际数据只存放在叶子节点里而内部节点里的键只是路标不是记录。因此任何一个内部节点的键都会在所有叶子节点的键中重复出现一次。比如内部节点里有键 20它不代表 20 这条记录存在那里只是告诉查询方“大于等于 20 的记录在右边某棵子树”。叶子节点之间还通过一个双向链表或者单向链表串起来。这个设计在 B树里没有强制要求但 B树必须要有因为范围查询的核心就是顺序遍历。查找一个小于 10 等于 20 的等值记录也都要从根一路走到叶子每次中奖与否都是在叶子里判断。这样做的后果是等值查询的代价变得稳定不会像 B树那样在中间层可以碰巧命中就直接返回。有人会觉得这是“变慢了”但实际上稳定的代价对数据库非常重要预判执行时间是优化器设计的基础。内部节点只需要存键和子指针不存具体行数据所以每个内部节点能容纳的关键字远比 B树要多。一个 16KB 页如果索引键是 8 字节指针是 8 字节一个内部节点理论上能放下上千个键作为一个页的节点。大量扇出进一步压缩树的高度。三层的 B树可以轻松容纳上亿条索引记录这在 B树体系里也是类似结构但由于内部节点不存数据相同高度下容纳量要比 B树更高。3.2 两者的量化对比表单对比维度B树B树数据存放位置内部节点和叶子节点都可能存数据只有叶子节点存数据内部节点职责既是索引也可能是数据所在只做路由不存记录叶子节点是否链表连接不保证一般没有用链表串起来支持顺序扫描等值查找路径可能在内部节点提前命中一定走到叶子节点路径稳定范围查询效率中序遍历相邻块跳跃次数多找到下界后沿链表顺序走空间利用率内部节点被数据占掉一部分内部节点更小扇出更大更适合什么场景单次点查、需要快速返回的系统磁盘数据库、范围查询频繁的场景从这张表可以看出B树并非一无是处。在内存文件系统或某些单点查询场景里如果数据量不大B树提前命中可能反而快。但到了数据库这种高并发、大范围数据、范围查询频繁的领域B树在“可预测性能”和“顺序扫描”上的优势几乎碾压 B树。3.3 一次范围查询的完整路径以“SELECT * FROM user WHERE age 25 AND age 40”为例。在 B树索引中数据库先从根节点开始根据孩子指针找到一个“包含 25 的最左叶子节点”。因为叶子节点是按顺序排列并且通过链表连在一起的接下来只要沿着叶子链表的 next 指针向后扫把 age 小于 40 的记录都取出来就可以终止。这一步里真正随机访问的只有从根到那个叶子的几页随后的取值完全顺序读磁盘会非常欢喜。如果换成 B树做同样的范围查询需要中序遍历整棵树。虽然也能遍历但每个节点内部都有数据去重和排序都会让人头疼。而且遍历路径在不同子树之间来回跳页访问的局部性差很多。实际工程中这一差距就会表现为同一个区间B树的范围查询耗时可能只是 B树的零头。B树把“查找”和“遍历”彻底分离了查找只在树的路径上做遍历只在叶子链上做互不干扰。因为叶子链的存在B树也允许删除操作相对简单一些。内部节点删除键时不需要像纯 B树那样处理数据记录只需保证路由信息仍然正确真正的数据页面直接删除即可。数据库里频繁的插入删除会让叶节点碎片增多但那是页面合并回收的问题不影响搜索正确性。这一层分开之后系统设计更清晰底层的存储引擎也更好管理缓存和预读。4. 数据库索引的落地InnoDB 为什么独宠 B 树4.1 聚簇索引与辅助索引同一棵 B树的不同角色InnoDB 里表本身就是一棵 B树这句话我刚接触时一直很意外。主键索引的叶子节点直接存整行数据这种索引叫聚簇索引。数据行不是单独放在一张无序表里再让索引指向它而是行记录就待在 B树的叶子页里。表组织的方式其实就是一棵以主键为序的 B树。没有定义主键时InnoDB 会选一个非空的唯一索引作为聚簇索引都没有它就生成一个隐藏的 rowid 当做聚簇索引的键。辅助索引则不同。比如给 name 字段建了普通索引这棵辅助索引 B树的叶子节点并不是整行数据而是“索引键 主键值”。查询时如果走 name 索引先在辅助索引里找到 name 对应叶子拿到主键值再用主键值回聚簇索引查一遍完整行这个回访动作叫回表。回表的行为听起来多了一次查找但它让行数据只保留一份避免维护多份复制带来的写放大。这也解释了为什么辅助索引要求主键尽量短主键越长每个辅助索引叶子里的冗余值越大扇出越低树就越高。4.2 页大小和扇出为什么 16KB 能撑出低树高InnoDB 一个页默认 16KB磁盘一次最少读写一个页。这个数值不是拍脑袋选的它要平衡扇出和单次 I/O 的载荷。内部节点不存记录的情况下即便每条索引记录取约 16 字节键 8 字节、指针 4 字节、其他开销一页也能放大约 1000 个键。于是三层 B树内部看起来是这样的第一层 1 个页面第二层会有 1000 个页面第三层按照每个叶子页平均放 100 条记录算能支持 1000 × 100 10 万其实算错了第三层是 1000 × 叶子页数量第二层每个指针指向一个叶子页而叶子页数量可以是 1000 × 1000即 100 万条关键在于扇出层次。更准确地说假设每个节点保留 1000 个指针那么两层内部节点可以指向 100万个叶子页若每个叶子页放 100 行记录总记录数就是 1 亿。也就是说三层 B树就能撑住亿级行。生活中常用的是“三层”和“四层”树叶高度决定了命中一条记录最多读多少页这对磁盘性能来说极端关键。如果改用二叉树高度按 log2 算1 亿记录需要 27 次跳跃也就是几十次磁盘页读取而 B树三层最多读三个页差距是数量级上的。这也带来一个调优原则只要看到执行计划里“rows”数量大而对应索引高度只有 3说明这张表的索引设计大体是健康的。相反如果发现索引高度涨到了 5就要检查主键是不是选得太长太宽或者表里碎页太多。大量随机删除再插入会让叶子页有效载荷下降数据没增长多少树高先涨这也是需要优化周期整理表空间的原因。4.3 联合索引、最左前缀与覆盖索引背后的同一棵树联合索引比如 (a, b, c)看起来像一个神秘规则其实它就是一棵 B树叶子节点上的键按 a、然后 b、然后 c 的顺序排序。因为排序规则决定了每个叶子页里的数据顺序所以所有基于“最左前缀”的查询都能高效利用这棵树比如只查 a或者查 a 和 b 的组合而直接用 b 作为查询条件就没法走这棵树的前缀因为整棵树其实没有按 b 单独组织。理解这个就能理解为什么覆盖索引能避免回表。当 SELECT 的字段恰好都包含在索引键里查询可以在辅助索引的叶子页直接拿到所需数据不需要再用主键回聚簇索引。比如有联合索引 (name, age)查询“SELECT age FROM user WHERE name 张三”辅助索引叶子已经存了 age直接返回就行。覆盖索引可以显著降低随机 I/O这也是我们在压慢查询时最喜欢优先加的优化手段。但别迷信覆盖索引索引字段越多写操作时维护成本越高叶子页里的冗余也越多。加索引前先做查询集分析收益明显再动。4.4 与 LSM-Tree、红黑树等方案的取舍你可能听过 RocksDB、LevelDB 用的是 LSM-TreeMemSQL 用 lock-free skiplist那为什么 MySQL InnoDB 还要用 B树核心原因在于读写均衡。B树是一棵就地更新的树插入时不断做分裂合并保持读写都在对数级别保证范围查询的天然连续性缺点是因为磁盘随机写需要不断修改节点所在页容易出现随机写放大。而 LSM-Tree 把写请求先缓存在内存层按事件顺序落盘成有序的 SSTable读时需要合并多个层的文件整体读放大更显著。红黑树则完全不同。它是一棵内存中的二叉平衡树维护平衡的方式靠旋转和变色每个节点只有两个子节点没有页和磁盘批量读写这样的概念。把几千万数据放红黑树里也能跑但一旦数据大到要落盘每访问一层都对应一次随机 I/O基本就不适合了。之前有人问“B树是红黑树吗”这就是混淆了“平衡二叉树”和“平衡多叉树”。如果从 B树视角看莫伦的定理说红黑树可以被视作一种将节点合并后的 B树但就常见工程形态而言红黑树是二叉的B树是多叉批节点的应用场景完全不同。两者之间的关系不是同一数据结构换了个名字。还有一点常被忽略数据库需要支持大并发而 B树会让读路径非常短同时叶子页有“写锁”粒度的控制。一个节点里的多个键可以共享一次锁范围如果像红黑树那样频繁旋转旋转本身也改成写路径锁粒度和 CPU 缓存命中率都会难受。这就是工程系统没有选择“更好看”的二叉树或红黑树的原因。5. 动手理解和排错常见错误、排查与心法5.1 为什么写二叉树程序时总报运行时错误网上搜“写二叉树程序时为什么总是报运行时错误”一大部分是空指针导致的。典型的代码长这样int find(TreeNode* root, int target) { if (root-val target) return 1; if (root-val target) return find(root-right, target); else return find(root-left, target); }如果调用时 root 为 NULL第一行就已经在解引用空指针程序直接崩掉。正确写法是先在函数开头检查 root 是否为空返回 -1然后再比较值。很多初学者以为“先把值算出来再判断子节点不为空”是安全的但 root 本身都可能为空第一步就出错了。这几乎是我见过最多的二叉树运行时错误来源。还有第二类运行时错误是递归死循环。比如插入节点时忘记让新节点的左右孩子初始化为 NULL之后遍历就无法结束因为某个“叶子节点”的 left 或 right 是一个未定义值顺着它越走越远最终直接炸掉。树这种递归结构特别依赖“边界节点必须用 NULL 终止”的约定。写过几次之后我的习惯是在写任何树节点结构时立刻初始化所有指针成员甚至在调试时用一个小工具把整棵树打印出来验证叶子边界比单纯盯着递归调用栈省时得多。5.2 递归深度与内存占用问题树相关的代码尤其递归遍历最容易踩第二个工程坑深度过大造成调用栈溢出。当树退化为链表递归深度等于节点数几十万个节点一递归JVM 或 C 的进程栈就直接 Segment Fault。面试题里大家都背过“二叉树的最大深度”递归解法但没有意识到在真实场景里这种递归写法在树不平衡时会杀进程。更稳健的做法是改成显式栈做迭代遍历或者在递归中加一个最大深度保护。此外还有内存占用问题。B树和 B树每个节点都是一个页页里可能只放了少量有效键但分配时整页都要保留页碎片大了会浪费存储。O记碎片、页内部碎片不同很多数据库会在后台做页面“合并游离页”的操作。如果突然发现某棵索引“体积”明显大于估算值可能是删除操作留下了大量半空页。用 OPTIMIZE TABLE 或 ALTER TABLE 重建表后经常看到磁盘占用大幅下降就是这个原因。5.3 B树是红黑树吗如何跟别人解释这个热词很有代表性。答案很直接B树不是红黑树两者完全不是同一种东西。红黑树是二叉平衡树每个节点只有两个子节点内存中用得多B树是平衡多叉树一个节点能存很多键和很多子指针磁盘数据库用得多。有关系吗有源自 1970 年代对 B树与 2-3-4 树的研究红黑树可以看成一种将 2-3-4 树编码成二叉树的方式但你不会拿红黑树直接替代数据库索引。跟别人解释时我常用一个半比喻红黑树像一排双人小房间住两人调整时必须频繁换房间B树像一个能住几百人的大厅能直接容纳很多东西。条目越多门厅数量越少进出次数自然更少。而叶子节点之间的链表就像每层房间外有一条走廊直接把范围查询变成“从第一个入口进去沿走廊挨个敲门”。这个画面感比单纯背节点规则好记。5.4 一张速查表加几条能记住的实操心法现象大概率原因排查方向树形递归程序运行时崩溃空指针解引用或 NULL 终止条件缺失检查 root 是否判空、叶子指针是否初始化为 NULL查询特别慢索引高度偏高主键过长、页碎片太多、索引冗余严重分析主键长度、重建表、减少辅助索引冗余字段插入大量数据后树高暴涨分裂逻辑缺失或扇出设计过低确认阶数上限、检查每个节点的键数维持半满B树范围查询依然卡没有用到覆盖索引、叶子页碎片化用覆盖索引优化、检查优化器是否真的走索引对一个联合索引只用第二字段查询不符合最左前缀索引失效调整索引顺序或新建针对第二字段的索引实操心法一写 B树或 B树代码先做小规模测试。一次把 m 设成 3插入 1 到 20把每一层的叶子键都打印出来看是不是一直保持有序且半满。这一步通过再测 1 万条随机数据用程序自动验证所有叶子在同一层、所有非根节点的键数合法。没有自动化验证手写树结构想靠肉眼找出合并借位的 bug太痛苦了。实操心法二调索引问题时先看树的高度和页大小而不是急着调 sql。可以用 InnoDB 的统计数据或者SHOW INDEX FROM table看 Cardinality用ANALYZE TABLE刷新统计信息。很多“慢查询”并非 SQL 写得烂而是统计信息过期优化器选错了索引。重建统计信息后执行计划立刻变了。实操心法三如果一定要在内存里模拟 B树不要自己从头造轮子。用成熟的现成库学习原理比如 Java 里的 TreeMap 更适合红黑树场景看 MySQL 源码或 LevelDB 的 SkipList 实现能学到很多工程化的内存管理和页回收技巧。手写一版用于教学是完全必要的但要上线直接用成熟方案更稳。数据结构是工具不是用来炫技的牌面。最后再分享一个小技巧调试树结构别只盯着逻辑而不用数据验证。每次插入删除后打印整棵树的层级结构最下面把所有叶子节点的键序列拉出来直接对比预期顺序。我第一次调 B树删除合并时就是靠这种“打印法”发现仓库边界键没有同步更新半天时间省下来了。这套方法的本质是把抽象的递归结构变成可以人工校验的序列输出它适用于所有树形数据结构的调试。