★ FEATURED ARTICLE B-Tree 和 BTree详解从磁盘IO开始的索引原理做了几年后端开发和数据库调优我发现很多人在面试或者实际排查慢查询时一遇到 B-Tree 和 BTree 就含糊其辞。能说出“B树叶子节点有链表”的人不少但要讲清楚“为什么 MySQL 不用 B-Tree 而用 BTree”“为什么文件系统反而喜欢 B-Tree”真正能说透的人并不多。这篇文章想把这两棵数据结构树从头到尾掰开揉碎讲清楚包括它们解决的核心问题、节点分裂合并的细节、以及落到数据库索引上的性能差异适合正在准备技术面试的开发者也适合工作中想搞懂索引原理的工程师。内容不需要你有很深的算法基础但希望你能耐心看完全文因为前后逻辑是连贯的。1. 为什么需要 B-Tree 和 BTree 这类多路搜索树1.1 二叉搜索树在磁盘场景下的天然缺陷先看一个最朴素的场景如果让你在内存里存一堆有序数据然后做快速查找你大概率会想到二叉搜索树BST或者进一步做平衡处理得到 AVL 树、红黑树。它们在内存中表现确实不错查找、插入、删除都是 O(log₂N) 的时间复杂度。但一旦数据量达到千万级别树的深度就会成为致命问题。一棵完全平衡的二叉树节点总数 N 和高度 h 的关系近似为 N ≈ 2^h。也就是说如果有一亿条数据树的高度大约是 27 层左右。内存里访问 27 次指针完全没问题每次都是纳秒级。但如果这棵树是存在磁盘上的呢每向下走一层就要做一次磁盘随机 IO29 次 IO 在机械硬盘上意味着什么一次随机 IO 大约 10 毫秒29 次就是几百毫秒这个延迟是任何人都无法接受的。这就是 B-Tree 出现的根本原因我们不是要减少比较次数而是要减少磁盘访问次数。磁盘访问的代价远远高于 CPU 比较的代价所以数据结构的设计目标从“降低树高”变成了“降低树高同时保证每个节点尽量容纳更多数据”也就是把二叉树变成多叉树。1.2 磁盘预读与局部性原理要理解多叉树为什么能降低 IO还得先理解磁盘的一个特性预读prefetch。磁盘读取数据不是读单个字节而是按页page为单位读取的机械硬盘的一次 IO 通常读取 4KB 或者更大的连续数据块即使你只需要其中的一个字节整个数据页也会被加载到内存。SSD 虽然随机 IO 快了很多但依然保持了按页读取的逻辑主存和磁盘之间的数据交换单位是页。这个特性给了我们一个巨大的优化空间既然读一个数据页需要一次 IO那不如让每个节点的大小恰好等于一个页大小这样每次向下走一层只需要一次 IO就能把这个节点里所有的关键字全部加载到内存中然后在内存里做二分查找或者线性扫描。节点越大能容纳的关键字越多树高越低IO 次数越少。这就是 B-Tree 的设计哲学用空间换 IO用节点大小对齐磁盘页大小。一个 m 阶 B-Tree每个节点最多可以有 m 个子节点、m-1 个关键字树的高度被压缩到了 log_m N 级别。m 的典型值是几百甚至上千最理想情况下一个三层的 B-Tree 就能支撑千万级别的数据量。2. B-Tree 核心机制拆解2.1 B-Tree 的定义与结构特性先给出严谨定义一棵 m 阶 B-Tree 满足以下条件每个节点最多有 m 个子节点最多 m-1 个关键字除根节点外每个非叶子节点至少有 ⌈m/2⌉ 个子节点也就是至少 ⌈m/2⌉-1 个关键字如果根节点不是叶子节点则它至少有 2 个子节点所有叶子节点出现在同一层并且节点之间没有指针连接这是和 BTree 最大的区别点之一每个节点中的关键字按非递减顺序排列并且节点内部的子树指针分隔了关键字的取值范围。要理解这个结构最好的类比是“多路文件夹收纳盒”。想象一个收纳盒里可以放多个卡片而每个卡片隔出来的区间又通向另一个收纳盒。和二叉树不同的是每个节点不再只有“左小右大”两个方向而是有多个分叉方向。每个关键字就像路标决定了查找时应该往哪个子节点走。2.2 B-Tree 的查找过程查找操作从根节点开始在节点内部用二分查找确认目标关键字落在哪个区间然后顺着对应的指针进入子节点重复这个过程直到叶子节点。如果某个节点内找到了目标就返回成功否则沿着区间指针继续向下直到叶子节点仍然没找到则失败。这里有个细节值得注意B-Tree 的每个节点都同时存储关键字和对应的数据记录指针或者完整的数据行。也就是说查找时一旦在非叶子节点命中关键字就可以直接返回数据不需要再往下走了。这个特性在内存数据库或者文件系统场景中非常有用因为数据分散存储可以减少一次甚至多次 IO。我做过一个模拟实验在一个磁盘页大小 4KB、关键字大小 16 字节的场景下4 阶 B-Tree这里阶数比较小实际中会大很多保存 100 万条记录时树高只需要 9 层左右而二叉树需要 20 层IO 次数直接减少了一半以上。实际数据库中的 B-Tree 阶数通常远高于 4效果更明显。2.3 B-Tree 的插入与节点分裂插入操作比查找复杂很多因为要时刻维持 B-Tree 的平衡性。插入了新关键字后如果某个节点中的关键字数量超过了 m-1就必须进行分裂。分裂的具体逻辑是把超过容量的节点一分为二中间位置的关键字上升到父节点左右两部分分别作为父节点的两个子节点。分裂操作会向上传播如果父节点也因此超容量继续触发分裂直到根节点。如果根节点也分裂了树的高度就增加一层这是 B-Tree 唯一增加高度的方式。这里有个容易踩坑的地方分裂时选择“中间位置的关键字”不是随便选的它必须保证左右子树的所有关键字大小关系依然成立。换句话说选出来的这个中间关键字它的左子树里全是比它小的右子树里全是比它大的。实际操作中通常选择第 ⌈m/2⌉ 个关键字作为上升关键字。举个具体例子一个 5 阶 B-Tree每个节点最多 4 个关键字假设某个节点的关键字已经存满达到 [10, 20, 30, 40, 50] 的临界状态注意这里已经超过 4 个了实际插入前是 4 个插入后变成 5 个。分裂时选择第 3 个关键字 30 上升为父节点中的关键字左边剩下 [10, 20]右边剩下 [40, 50]。整个过程只新建了一个右兄弟节点左半部分沿用原来的节点这样能减少内存分配次数。2.4 B-Tree 的删除与节点合并删除操作有两个难点一是删除非叶子节点中的关键字需要找到后继关键字来顶替二是删除后如果节点关键字数量低于下限 ⌈m/2⌉-1就需要向兄弟节点借关键字或者合并节点。向兄弟借关键字的操作是如果左兄弟有多余关键字就先借左兄弟的最大关键字上移到父节点再把父节点的对应关键字下移到当前节点右兄弟则是对称操作。这个过程中父节点和子节点的关键字数量都会发生变化需要小心维护顺序。如果两个兄弟节点都不够借就只能合并。合并时把父节点中的一个关键字也拉下来和当前节点、兄弟节点的所有关键字合并成一个新节点。如果操作了父节点后导致父节点也低于下限会继续向上处理直到根节点。如果根节点最终也被合并掉了树的高度就减少一层。3. BTreeB-Tree 的进化变体3.1 BTree 和 B-Tree 的差异到底在哪里BTree 是对 B-Tree 的一种重要变体两者的核心差异就三条记清楚了就掌握了 80%数据存储位置不同BTree 的所有数据记录或者指向实际数据行的指针都存放在叶子节点非叶子节点只存储用于索引的关键字副本和子节点指针。而 B-Tree 的每个节点都可能存数据。叶子节点之间有指针串联BTree 的叶子节点通过链表通常是双向链表按照关键字顺序连接方便范围查询和顺序遍历。这是 B-Tree 没有的。查找效率更加稳定BTree 的查询必须一路走到叶子节点才能拿到数据所有路径长度相同。B-Tree 则可能在一个高层节点就返回数据导致不同关键字的查询路径长度不一致。这三条差异看似简单实际影响深远。先说第一条非叶子节点只存关键字和指针意味着同一个磁盘页大小的节点能容纳的关键字数量更多扇出fan-out更大树自然更矮IO 次数更少。第二条让范围查询不再需要多次从根节点回溯直接顺着叶子链表线性遍历即可。第三条则让 BTree 的查询性能更可预测对于建索引来说这是很理想的特征。3.2 为什么 InnoDB 选择了 BTree聊到数据库就绕不开 MySQL 的 InnoDB 存储引擎。InnoDB 的索引结构正是 BTree主键索引的叶子节点直接存储整行数据二级索引的叶子节点存储主键值。这个设计带来的第一个直接好处就是范围查询友好。举个例子假设你的表里有 100 万条订单记录主键是自增 id你想查 id 从 100000 到 200000 的所有订单。如果用 B-Tree找到 id100000 后你要范围遍历就得反复做树的中序遍历每次从一个叶子节点跳到下一个叶子节点都要回溯父节点反向的递归成本极高。而 BTree 的叶子节点是链表连接的我先在树里找到 id100000 的叶子节点然后顺着 next 指针一路向后遍历就能拿到所有需要的数据配合预读机制性能接近顺序扫描。第二个好处是非叶子节点只存索引键内存利用效率更高。假设一个节点大小是 16KBInnoDB 的默认页大小主键是 BIGINT 类型8 字节指针约 6 字节那么一个非叶子节点大约能存 16KB / (86) ≈ 1170 个索引项。三层 BTree 能支撑的叶子节点数大约是 1170 × 1170每个叶子节点假设能容纳 10 条记录取决于行大小总记录数就能达到千万级。这意味着绝大多数业务表的三层索引树已经足够查找任何一条数据最多三次磁盘 IO。第三个好处是查询性能稳定写 SQL 的时候不会出现某个查询特别快、某个查询特别慢的情况执行计划的可预测性对于数据库调优和容量规划非常重要。3.3 BTree 的插入与分裂细节BTree 的插入逻辑和 B-Tree 类似按关键字大小定位到目标叶子节点如果叶子节点满了就分裂。但有一个关键区别分裂时中间关键字是否上升到父节点取决于 BTree 的两种分裂策略。一种是“上推中间关键字”中间关键字上升到父节点后同时保留在左叶子节点中或者右节点视实现而定另一个节点继承剩余的关键字。另一种是“复制中间关键字到父节点”中间关键字上升到父节点后在叶子节点中仍然保留一份。InnoDB 的实现属于后者这样左边节点的最大关键字会作为父节点中的分隔值确保父节点中的关键字不一定是实际叶子数据。这个细节在阅读 InnoDB 源代码或者研究页结构时非常关键。与 B-Tree 不同BTree 分裂叶子节点时创建的右兄弟节点会通过双向链表和原节点连接起来保证后续范围查询能顺畅遍历。这个链表指针在分裂后必须保持正确否则范围查询会断链这也是很多初学者手写 BTree 时经常出错的地方。4. B-Tree 与 BTree 的全面对决4.1 查询、插入、删除操作的横向对比从操作代价的角度做一个系统的对比操作类型B-Tree 行为BTree 行为实际影响单点查询可能在非叶子节点就命中路径长度不固定必须走到底层叶子节点路径长度固定BTree 查询延迟可预测范围查询需要中序遍历跨节点时需要回溯父节点叶子链表直接遍历基本是顺序 IOBTree 明显占优插入节点满则分裂中间关键字上升叶子满则分裂中间关键字上升/复制基本相当删除节点不足则借用或合并节点不足则借用或合并基本相当BTree 的叶子合并时不需要调整内部节点全表扫描需要遍历所有节点包括内部节点只需要顺序遍历叶子链表BTree 明显占优内存占用内部节点也会缓存数据浪费有限缓存内部节点只缓存索引键覆盖更多数据页BTree 对缓存更友好从这个表能看出BTree 在查询场景全面占优尤其是在数据库这种以查询为绝对主力的场景里。B-Tree 的优势主要在于它可以在非叶子节点直接返回数据对于“点查询很多、范围查询很少、节点都在内存中”的场景B-Tree 其实更高效因为省去了下探到叶子节点的开销。4.2 为什么文件系统喜欢 B-Tree 而非 BTree有人可能会问了既然 BTree 这么好为什么很多文件系统比如早期的 ext4 Htree、各种的索引结构用的却是类似 B-Tree 的结构而不是纯正的 BTree这个问题需要从文件系统的工作模式来理解。文件系统的索引通常以目录项文件名到 inode 的映射为主目录层级天然是树形结构每次访问文件的路径就是一次从根目录到目标文件的查找。文件系统更关注“通过文件名找到 inode”这种点查询而不是“找出某个目录下所有文件名在某个区间内”的范围查询实际上这种需求也有但可以通过目录项的线性扫描解决因为单个目录下文件数通常不会特别大。另一个原因是文件系统索引节点中直接保存 inode 号或者文件元数据指针可以节省一次间接寻址。如果在 BTree 中查找到叶子节点后还要再做一次指针跳转才能拿到元数据在文件系统这种对延迟极敏感的场景中并不划算。所以文件系统设计者往往倾向于使用 B-Tree 的变种比如 B*-Tree、B-link Tree把关键信息直接嵌在树的较高层级达到空间和性能的平衡。4.3 硬盘随机 IO 和顺序 IO 对选择的决定性影响再往底层看B-Tree 和 BTree 的胜负手其实在于硬件特性。传统机械硬盘的随机 IO 和顺序 IO 性能差距可以到百倍级别而 SSD 虽然大幅缩小了这个差距但随机小 IO 依然有明显损耗。BTree 的设计让范围查询、全表扫描完全退化成顺序 IO这在机械硬盘时代是压倒性优势。即使现在 NVMe SSD 普及了顺序读取和随机读取的延迟依然有几倍的差距所以 BTree 在数据库领域从来没有被真正替代过。如果你的业务场景是大量点查询、几乎没有范围查询、且数据可以完全放入内存比如内存数据库 Redis、Memcached那确实没有必须迷信 BTree 的理由甚至 hash 索引就是更好的选择。数据结构选型永远没有银弹只有适合当前场景的取舍。5. 从原理到实操索引优化中的 BTree 思维5.1 常见的索引结构误区和认知纠偏我排查慢查询时候发现很多开发对索引的依赖特别想当然几个高频误区我必须单独列出来。第一个误区是“有索引就是万能药”。实际上如果你写了一个WHERE name LIKE %关键词%这种以通配符开头的模糊查询MySQL 根本无法走 BTree 索引的有序性来加速查找只能全索引扫描。这在 BTree 的结构上很容易理解索引是按关键字有序排列的但你查询的条件没有固定前缀树根本不知道从哪个分支入手。可行的优化方案是引入全文索引或者搜索引擎而不是盲目加索引。第二个误区是“联合索引等于多个单列索引”。实际上联合索引在 BTree 中是按照多个列的顺序逐级排序的这会导致最左前缀原则如果你查询条件里没有第一个列索引就无法高效工作。比如在 (a, b) 上建了联合索引WHERE b 1就无法使用这个索引因为 BTree 的有序性是先按 a 排序再按 b 排序的跳过 a 直接找 b 等于在一个无序序列里查找。第三个误区是“索引列越短越好所以把 int 索引全部改成 tinyint”。这个想法方向是对的但忽略了主键索引特殊性。InnoDB 的二级索引叶子节点会存主键值如果你的主键是自增 bigint二级索引里就会存储这个 bigint。这决定了二级索引的大小和你每个索引项占用的空间。索引列短确实有好处的但单纯缩短而影响业务灵活性就得不偿失了尤其是当你需要做主键拆分、多租户隔离时短主键反而会带来风险。5.2 如何通过页大小和节点容量估算索引性能了解 BTree 结构之后你可以用几个简单的估算公式来判断一个表加索引是否合理。InnoDB 默认页大小是 16KB我们来计算一下单表能承载多少数据量。假设一张订单表主键是 BIGINT用户 ID 是 BIGINT订单金额是 DECIMAL加上一些 varcharchar 字段一条订单记录平均占用 512 字节一个 16KB 的页大约能存 32 条记录。两层 BTree一个根节点 一层叶子节点能支撑 1170 个叶子节点即 1170 × 32 ≈ 37440 条记录这个数据量下大多数查询只需要两次磁盘 IO一次读根节点的索引页一次读叶子节点的数据页。三层 BTree 能支撑 1170 × 1170 × 32 ≈ 4380 万条记录三次磁盘 IO 就能查到任意一行数据。这个估算过程很有价值当你发现某张表行数已经超过三层 BTree 的支撑上限一次查询可能需要四次 IO 时就要考虑分库分表、归档冷数据或者升级硬件了。实际工作中我就遇到过一张表数据量超过 3 亿行后简单主键查询从 1 毫秒涨到 15 毫秒的案例本质上就是 BTree 高度增加了一层每次查询多了一次 IO再加上缓存命中率下降延迟就上去了。5.3 覆盖索引、回表和索引下推的底层逻辑理解了 BTree 的数据分布就能真正理解覆盖索引和回表这两个概念。在 InnoDB 中二级索引的叶子节点存储的是主键值而不是整行数据。一次查询如果用到了二级索引流程是先在二级索引的 BTree 里找到主键值再拿这个主键值去主键索引聚簇索引的 BTree 里查找完整的行这就是“回表”。覆盖索引就是让你的查询条件列和查询结果列都包含在同一个联合索引里的情况。这样在二级索引的 BTree 里就能拿到所有需要的列不需要回表了省掉了一次磁盘 IO。实际优化中把高频查询的列塞进联合索引是调整慢查询性价比最高的手段之一。还有一个常被忽略的点索引下推Index Condition PushdownICP。在 MySQL 5.6 之后如果联合索引包含多个条件列存储引擎可以在索引遍历过程中直接判断这些条件是否满足减少回表次数。比如索引是 (a, b)查询是WHERE a 1 AND b 2没有 ICP 时需要把满足 a1 的所有主键都回表再判断 b2有 ICP 时直接在索引 BTree 遍历中过滤掉 b 不满足的记录只对剩余记录回表。这个优化依赖的就是 BTree 有序结构的逐列比较能力。5.4 实际排查慢查询时可以怎么分析我平时排查一条慢 SQL 时会先看执行计划中的 type 字段如果是 ALL说明做了全表扫描BTree 完全没派上用场如果是 ref 或者 range说明走了索引但可能有一些效率损耗如果是 const说明命中了主键等值查询是最理想的状态。然后看 Extra 列有没有 Using filesort、Using temporary这通常意味着 MySQL 拿到数据后还要额外排序或建临时表而这些排序操作无法利用 BTree 的有序性。解决方法通常是调整 SQL 让排序字段和索引的列顺序一致这样数据取出时已经有序省掉排序环节。最后我会用EXPLAIN ANALYZE或者SHOW PROFILE看实际耗时分布。通过实测找到瓶颈是出在磁盘 IO 还是 CPU 比较上再决定是加缓存、压缩页、扩大 buffer pool还是调整 SQL 结构。有了对 BTree 的深刻理解你在做这些优化时就不会只是盲目地“加个索引试试”而是能精准判断索引到底会不会生效以及为什么生效或者不生效。6. 常见问题与面试难点速查6.1 面试高频问题与回答思路B-Tree 高度怎么计算假设节点容量为 m查找 N 个键时树高不超过 log_m N 量级。计算时要区分内部节点和叶子节点实际能存的键数量。BTree 和 B-Tree 最大区别是什么数据全部放在叶子节点 叶子节点链表串联 非叶子节点只存索引键。e为什么大多数数据库选择 BTree范围查询友好、内部节点扇出更高、查询性能稳定、对磁盘预读更友好。BTree 和 LSM-Tree 怎么选这是一个扩展问题。BTree 读快写慢适合读多写少的在线交易系统LSM-Tree 写快读慢适合日志写入、时序数据这种写多读少的场景实际写入时 LSM-Tree 还会通过 compaction 来优化读性能。BTree 的高度为什么显得这么小因为节点容量大通常一个页能容纳几百上千个索引项树形会变得非常宽矮。这是“多路”的直接收益。6.2 实践中容易踩的坑第一个坑是把内存散列表和 BTree 混为一谈。很多人在内存量足够时把所有热点数据放到 Redis 里结果发现某些查询反而变慢了这是因为 Redis 的哈希表是无序的范围查询需要全量扫描。实际上有范围查询需求时正确做法是使用支持有序集合的数据结构比如 Redis 的 ZSET 或者直接在数据库里走 BTree 索引而不是无脑缓存。第二个坑是忽略索引的有序性约束。比如你在 (status, created_at) 上建了联合索引但你的查询是WHERE created_at 某个时间点 AND status 1由于 created_at 在最左侧MySQL 没办法高效利用这个索引的顺序可能只能全表扫描。解决办法是调整联合索引的列顺序让等值条件列在前、范围条件列在后这也是最左前缀原则的实际应用。第三个坑是不做数据规模预估就决定索引策略。一个只有几千行的配置表加不加索引对性能影响几乎为零但如果你在几十行的小表上建了特别宽的索引除了浪费空间还可能拖慢写入。IO 优化要在数据量达到一定规模比如百万行以上才有意义。第四个坑是只关心索引创建不关心碎片与页合并。BTree 在频繁随机删除插入的过程中页内部会产生碎片导致页利用率降低最终表现为索引变大、查询变慢。实践中可以通过OPTIMIZE TABLE来重建表空间和索引页但这个过程会锁表需要安排在低峰期进行。6.3 一个可复现的理解实验如果你手头有空闲机器可以做一个简单的实验来加深理解在本地创建一个包含 1000 万行数据的测试表分别用 int 主键和 varchar 主键测量同一查询的耗时再用SHOW TABLE STATUS查看索引的大小。你会发现 varchar 主键因为占用空间更大导致 BTree 的扇出更小、树更高、IO 次数更多性能明显下降。另一个实验是用INFORMATION_SCHEMA.INNODB_METRICS观察索引页的读取次数然后对比覆盖索引和回表查询之间的差异。这两个实验都能让 BTree 的底层原理“看得见摸得着”比单纯背面试题有效得多。7. 写在最后的一点经验我自己在实际项目中用过 B-Tree 思想的地方反而不仅是数据库还有一个很偏门的场景设计一个离线批量导入系统的内存索引。当时要在一秒内完成几十万条记录的去重和匹配我直接按 BTree 的思路实现了一个简化版的多路有序数组结构把数据分桶排序后从叶子层向上构建索引实测性能比用红黑树快了一个数量级。那个项目让我深刻体会到B-Tree 和 BTree 从来不只是数据库的专属内容它本质上是一种处理“海量数据 有限内存 慢速存储”的通用思想。如果你是个刚接触这块的开发者我的建议是别急着背那一堆阶数定义和分裂规则先理解“一次磁盘 IO 能读取多少数据”这个前提然后自己动手画几遍 BTree 的插入分裂图和叶子链表串联图再回到真实数据库里用 EXPLAIN 观察 SQL 的执行路径。这个过程比任何教程都管用。走完这一遍B-Tree 和 BTree 就不再是两个陌生拗口的名词而会成为你分析性能问题的得力工具。
阅读完成 · 觉得有帮助？
