上一篇我们讲清楚了 B树和 B树之间的区别B树的所有节点都可能存储数据B树的非叶子节点主要负责导航数据集中存放在叶子节点叶子节点按照索引顺序组织适合连续扫描。但这里很容易产生一个新的疑问红黑树的查询效率也很高Java 中的 TreeMap、Linux 中的一些数据结构也会使用红黑树为什么 MySQL 索引不使用红黑树而要使用看起来更加复杂的 B树这个问题的关键不在于红黑树查得快不快。而在于红黑树更适合内存查找B树更适合以磁盘页为单位存储和读取的大规模数据。本文就从这个区别开始把背后的原因一步步讲清楚。一、先明确讨论范围MySQL 不只有一种索引结构严格来说不能简单地说“MySQL 的所有索引都是 B树”。MySQL 支持多种存储引擎不同索引类型也可能采用不同的数据结构。例如MEMORY 存储引擎既支持 HASH 索引也支持 BTREE 索引空间索引还可能使用 R-tree。本文讨论的是最常见的场景InnoDB 普通索引和聚簇索引为什么采用 B-tree 系列结构而不是红黑树。MySQL 官方文档通常统一称其为 B-tree 索引在数据库原理的讲解中由于其数据集中于叶子层、支持有序范围扫描等特点通常会按照 B树的思路进行理解。MySQL 官方文档也明确说明B-tree 索引能够支持等值查询、范围查询、BETWEEN、IN等操作。二、红黑树是什么在理解为什么不用红黑树之前先简单认识一下红黑树。红黑树本质上是一种自动保持平衡的二叉搜索树。“二叉”的意思是每个节点最多只有两个子节点左子树 当前节点 右子树例如50 / \ 20 80 / \ / \ 10 30 60 90查找 60 时50 ↓ 80 ↓ 60只需要比较几次就能找到。红黑树还会通过旋转、变色等操作让整棵树不会严重倾斜从而把查询、插入和删除的时间复杂度保持在较好的范围内。所以红黑树本身并不慢。如果数据全部放在内存中红黑树是一种非常优秀的数据结构。问题在于MySQL 的大量数据不能全部常驻内存最终需要存储在磁盘或固态硬盘中。这时问题就发生了变化。三、内存查找和磁盘查找不是同一个问题在内存中访问一个节点速度很快。但数据库中的数据量可能非常大100 万行 1000 万行 1 亿行这些数据不可能永远全部放在内存里。当内存中没有需要的数据时数据库需要从磁盘读取。而磁盘读取的成本远远高于在内存中进行一次大小比较。因此数据库索引真正关心的并不是一共比较了多少次而是为了找到数据需要读取多少个磁盘页这就是理解红黑树与 B树差异的核心。四、数据库不是一个节点一个节点地读取数据数据库从磁盘读取数据时通常不是只读取几个字节。它会按照“页”读取。你可以把页理解为数据库与磁盘之间一次读取和写入的基本单位。索引节点、索引记录和数据记录会被组织到一个个页中。MySQL 官方文档说明InnoDB 的数据和索引存储在 B-tree 结构中并以索引页的形式组织。所以数据库设计索引结构时要考虑一个页能放多少索引项 一次读取一个页后能排除多少数据 整棵树需要读取多少层这正是红黑树不占优势的地方。五、红黑树的第一个问题一个节点只有两个分支红黑树属于二叉树。每个节点最多只能分出两个方向左边 右边假设当前节点是 50小于 50往左 大于 50往右这意味着每经过一层最多只能把搜索范围大致缩小一半。如果数据量不断增加树的层数也会不断增加。即使红黑树能够保持平衡它仍然是一棵二叉树。例如一棵拥有大量数据的红黑树可能需要经过很多层才能定位目标节点根节点 ↓ 第2层 ↓ 第3层 ↓ 第4层 ↓ …… ↓ 目标节点如果这些节点分布在不同的磁盘页中那么每向下一层都可能需要读取一个新的页。所以红黑树的问题不是查找复杂度差而是分支太少树容易变高树越高可能产生的页面访问就越多。六、B树的第一个优势一个节点可以有很多分支B树不是二叉树而是多路平衡查找树。一个节点中可以存放多个索引键和多个子节点指针。例如[20 | 40 | 60 | 80] / | | | \ 20 20~40 40~60 60~80 80同样访问一层红黑树只能判断“往左还是往右”B树可以直接判断目标属于多个区间中的哪一个。如果一个节点能够管理几百个甚至更多子节点那么一层就可以排除绝大部分数据。因此B树即使存储非常多的数据树的高度通常仍然比较低。它的核心思路不是减少 CPU 比较次数而是用更多分支降低树高从而减少页读取次数。七、为什么 B树一个节点能放更多索引键B树的非叶子节点主要负责导航。可以简化理解为索引键 子节点指针非叶子节点不需要存放完整的数据行。因此在一个固定大小的页中可以容纳更多索引键和子节点指针。容纳的索引键越多分支越多 ↓ 一层管理的数据越多 ↓ 树的高度越低 ↓ 查询需要访问的页越少这就是 B树设计中非常重要的“高扇出”特点。这里的“扇出”就是一个节点能够拥有的子节点数量。红黑树的扇出最多是 2。B树的扇出可以非常大。这才是数据库选择 B树而不是红黑树的核心原因之一。八、用一个简化例子理解树高差异假设有 100 万条数据。为了方便理解暂时忽略页大小、键长度、填充率等真实因素。红黑树因为它是二叉树每个节点最多两个分支。即使完全平衡也需要很多层才能容纳 100 万个节点。大致可以理解为2^20 ≈ 100 万也就是说理想平衡的二叉树都可能需要接近 20 层。红黑树不是严格意义上的完全平衡树实际路径还可能更长。B树假设一个非叶子节点能够分出 1000个分支。那么第一层管理 1000 个方向 第二层管理 1000 × 1000 个方向两层分支理论上就已经可以覆盖约 100 万个范围。真实数据库结构当然没有这么简单还要考虑页容量、记录大小、填充率等因素但这个例子足以说明多叉树通过提高每个节点的分支数量可以显著降低树的高度。所以不能只看两种树的时间复杂度。更应该看在磁盘页模型下需要访问多少层。九、红黑树的第二个问题不能充分发挥“整页读取”的价值红黑树的一个节点通常只包含一个 key 左子节点指针 右子节点指针 其他平衡信息如果把这种结构直接映射到磁盘存储中一个节点能够提供的信息比较有限。即使数据库一次从磁盘读取了一个完整页面也很难像 B树那样在一个页中放入大量有序索引键并一次性判断出目标属于哪个范围。而 B树天然适合页面结构一个页面 ├── 多个有序 key ├── 多个子节点指针 └── 页面管理信息读取一个 B树非叶子页相当于一次拿到了一大批导航信息。所以 B树更能够利用数据库“一次读取一页”的特点。十、B树的第二个优势天然支持范围查询数据库不只会执行等值查询SELECT * FROM user WHERE id 100;还会执行大量范围查询SELECT * FROM user WHERE id BETWEEN 100 AND 1000;或者SELECT * FROM orders WHERE create_time 2026-01-01 ORDER BY create_time;MySQL 官方文档明确说明B-tree 索引能够高效支持特定值、值集合和范围值的查询。B树的数据集中存放在叶子层并按照索引键有序组织。可以简化成[1, 2, 3] → [4, 5, 6] → [7, 8, 9]查询 3 到 8 时先通过树定位到 3从 3 开始顺序向后扫描扫描到 8 时结束。这非常符合数据库范围查询的执行方式。十一、红黑树做范围查询会怎样红黑树本身也能保存有序数据。通过中序遍历也可以按照顺序读取数据。所以不能说红黑树完全不能做范围查询。但问题在于它的逻辑结构类似50 / \ 20 80 / \ / \ 10 30 60 90完成范围遍历时需要不断处理左子树当前节点右子树父子节点之间的跳转。这种结构更适合内存中的指针访问。而 B树把有序数据集中组织在叶子层通过连续叶子页扫描完成范围读取更符合数据库页和顺序扫描的需求。因此真正的区别不是红黑树不能范围查询 B树能范围查询而是两者都能维护顺序但 B树的叶子层结构更适合数据库批量、连续地读取范围数据。十二、B树的第三个优势等值、范围、排序能够统一处理数据库索引不仅要支持WHERE id 100还要支持WHERE id 100 WHERE id BETWEEN 100 AND 200 ORDER BY idB树中的索引键有序排列因此可以同时服务于等值查询范围查询有序扫描部分排序和分组场景最左前缀匹配。MySQL 官方文档也将 B-tree 索引用于、、、BETWEEN、IN等条件。红黑树也能维护顺序但综合磁盘页访问、树高和连续扫描来看B树更适合作为通用数据库索引结构。十三、那为什么 Java 的 TreeMap 可以使用红黑树看到这里可能又会产生一个疑问既然 B树这么好为什么 Java 的 TreeMap 不用 B树因为它们解决的问题不同。TreeMap 的典型场景TreeMap 中的数据通常位于内存。访问一个节点本质上是内存中的对象引用跳转。它主要关心查询效率插入效率删除效率保持键有序动态平衡。红黑树在这些场景下非常合适。MySQL 索引的典型场景MySQL 索引要管理的数据量可能远远超过内存容量。它主要关心如何减少磁盘页访问如何让一层容纳更多索引项如何降低整棵树的高度如何高效进行范围扫描如何把数据组织进固定大小的页。因此内存有序容器红黑树很合适 磁盘数据库索引B树更合适不是谁绝对更高级而是应用场景不同。十四、为什么不是普通 B树而是 B树讲到这里还可以再向前追问一步既然 B树也是多路平衡查找树为什么还要改造成 B树原因主要在于B树的非叶子节点也可能存储真实数据。这会带来两个影响。第一非叶子节点能够容纳的索引键减少一个页中如果还要存放真实数据那么留给索引键和子节点指针的空间就会减少。索引键减少分支数量就可能减少。分支减少树可能变高。第二数据分布在不同层级B树中的数据可能出现在根节点、中间节点或叶子节点。而 B树把数据统一组织到叶子层非叶子节点专门负责导航。这让 B树更适合提高非叶子节点的扇出降低树高在叶子层进行连续范围扫描。所以数据库索引真正看重的不是“能不能提前在中间节点找到数据”而是能不能让整个索引结构更矮并让大量查询以更少、更连续的页面访问完成。十五、B树也不是没有代价B树并不是在所有场景下都优于红黑树。它也有自己的成本。例如插入新记录时可能需要进行页面分裂删除数据后可能出现页面利用率下降随机插入可能导致索引页碎片维护多棵索引会增加存储和写入成本。MySQL 官方文档也指出随机插入和删除二级索引记录可能造成索引碎片。因此B树不是“没有缺点的数据结构”。而是在磁盘页、范围查询、大数据量和通用数据库索引这些约束下综合表现更合适。十六、把整个选择过程串起来现在可以把 MySQL 选择 B树的逻辑串成一条完整路线数据库数据量很大 ↓ 数据不能全部常驻内存 ↓ 查询可能需要读取磁盘页 ↓ 磁盘页访问成本很高 ↓ 需要尽量减少树的层数 ↓ 红黑树每个节点最多两个分支树相对较高 ↓ B树一个节点可以拥有大量分支 ↓ B树树高更低页面访问次数更少 ↓ 数据集中在有序叶子层 ↓ 范围查询可以连续扫描 ↓ 所以 InnoDB 更适合使用 B树类型的索引结构十七、面试怎么回答如果面试官问MySQL 为什么不用红黑树而使用 B树可以这样回答红黑树是一种平衡二叉搜索树每个节点最多只有两个子节点。即使它能够保持平衡在数据量很大时树的高度仍然会比较高。MySQL InnoDB 的数据和索引主要按照页进行存储和读取查询时真正昂贵的是页面访问而不是在内存中进行几次 key 比较。B树属于多路平衡查找树一个非叶子节点可以存放多个索引键和子节点指针因此分支更多、树高更低能够减少查询过程中需要访问的页面数量。同时B树的数据集中在叶子层叶子记录按照索引键有序组织非常适合范围查询和顺序扫描。所以红黑树更适合内存中的有序数据结构而 B树更适合大规模磁盘数据库索引。十八、一个容易被忽略的纠正很多资料在解释 B树时会强调B树所有查询都走到叶子节点所以查询更加稳定。这句话不能算错但它不是 MySQL 选择 B树的最核心原因。真正关键的原因应该按照这个优先级理解高扇出 ↓ 树高低 ↓ 页面访问少 ↓ 叶子层有序 ↓ 范围扫描方便至于“查询路径稳定”只能算结构上的一个特点不应该当成决定性原因。另外也不能简单地说红黑树范围查询不行。红黑树同样可以维护有序数据也能通过遍历完成范围查询。更加准确的说法是红黑树更适合内存中的节点跳转B树的叶子页结构更适合数据库按照页进行连续范围扫描。十九、这一篇真正需要记住什么只需要记住四句话。第一红黑树是二叉树一个节点最多只有两个分支。第二B树是多叉树一个节点可以拥有大量分支因此树更矮。第三数据库真正昂贵的是磁盘页访问树越矮通常需要访问的页越少。第四B树的叶子层有序组织更适合范围查询和顺序扫描。最终一句话总结红黑树解决的是内存中的有序查找问题而 B树解决的是大规模数据在磁盘页中的高效定位和范围扫描问题。二十、结尾学习数据库索引时不能只背MySQL 使用 B树因为 B树查询快。因为红黑树查询也很快。真正需要理解的是不同数据结构的“快”是在不同存储模型下定义的。在内存模型中我们更关注算法复杂度和指针访问。在数据库磁盘模型中我们更关注树有多高 需要读取多少页 每个页能提供多少导航信息 范围数据能不能连续读取理解这一层以后就不会再把红黑树、B树和 B树简单地理解成“谁的时间复杂度更低”。下一篇我们继续进入《MySQL 索引原理系列三MySQL 主键索引到底是什么》下一篇将正式讲清楚主键是什么主键索引是什么聚簇索引是什么为什么 InnoDB 聚簇索引中存放行数据没有主键时InnoDB 会怎么组织数据。MySQL 官方文档说明每张 InnoDB 表都会有一个用于存放行数据的聚簇索引通常主键会被用作聚簇索引。如果没有主键InnoDB 会依次寻找满足条件的唯一非空索引或者生成隐藏的聚簇索引。