聊到 MySQL 的索引十次有九次绕不开同一个问题为什么 MySQL 默认用 B 树而不选结构更“经典”的二叉搜索树、红黑树也不选查询最快的哈希索引我最初背面试题时答案翻来覆去就是“磁盘 I/O 少、树高矮、叶子节点有链表”其实没真正理解设计者到底在权衡什么。后来在真正处理慢查询、看执行计划、甚至去看 InnoDB 在磁盘上怎么组织页之后才慢慢体会到 B 树这棵“树”本质上是为了解决磁盘模型、范围查询和读写均衡这三件事的综合方案。这篇文章没有高深数学我会把为什么选 B 树这个问题从存储介质开始拆一路拆到 InnoDB 的实际落地过程中会带扇出计算、页分裂、聚簇索引这些面试高频点也会聊一些生产环境里被常被误解的地方。适合正在准备 MySQL 面试的开发者也适合已经写了不少 SQL、但一直没搞懂索引底层逻辑的同学。1. 在解释“为什么选 B 树”之前先看清数据库的底层约束1.1 磁盘和内存的读写模型完全不同很多人把“B 树矮、所以读取快”当成一句口号这没有错但为什么矮就一定快根源在存储介质。内存是随机访问友好的CPU 去读某个地址无论顺序读还是跳跃读时间差只在纳秒级别。但数据库的数据基本都存在磁盘上磁盘是机械结构读写需要寻道、旋转、传输一旦发生随机访问主要时间都花在“把磁头移动到正确的磁道”上。这个物理动作的代价比顺序读高几个数量级。哪怕你的机器用的是 SSD随机读的延迟也比顺序读高只是差距没有机械硬盘那么夸张罢了。所以数据库设计者考虑问题的第一原则不是“比较次数少”而是“尽量把随机 I/O 变成顺序 I/O并且让每次 I/O 都尽量多拿一些有效数据”。这是一切索引结构选择的出发点。B 树的存在不是为了比赛谁比较得快而是为了在磁盘环境下用尽量少的次数读取到尽量多的目标数据。那“尽量少读几次”怎么量化看树的高度。树越高定位某个值就得从根节点一层层往下走每一层都可能对应一次磁盘读取。树越矮访问路径越短。所以问题变成如何把一棵能够存储千万行数据的树压到三四层以内。1.2 索引本质上是“目录”但目录不能乱写如果把数据库表想象成一本书索引就是书末的目录。没有目录时查找某个词只能逐页翻这叫全表扫描。有目录时你先查目录再按页码定位内容。但目录本身也有存放成本。一个索引文件不可能无限大它也得按固定的“块”来组织。数据库里这个块叫“页Page”InnoDB 默认是 16KB。所有读写的底层单位都是页而不是单条记录。既然一页只能存有限内容那么决定一个索引结构优劣的核心就变成同样一页 16KB能装下多少个“分叉点”分叉点越多同样的数据量下树就越矮树越矮查询时走的路就越短。这就把比较范围缩小到了具体结构哪种树能在单个节点上塞进更多分叉如果你用二叉搜索树一个节点只有两个分叉那么哪怕是 100 万条数据树高也要在 20 层左右。虽然内存里 20 次比较不算什么但如果在磁盘上对应 20 次随机读取生产环境就压不住了。红黑树本质上还是二叉同样的层高问题依旧存在。所以“树高”和“单节点分叉数量”是第一道筛选条件多叉树天然就是磁盘场景下更合理的形态。2. B 树相比 B 树、哈希、跳表到底赢在哪里2.1 关键词非叶子节点只存索引不存数据不少初学者会把 B 树和 B 树当成同一个东西但真正让 MySQL 选择 B 树的恰恰是这一字之差。B 树里一个节点既可以存索引键也可以存对应的数据行或行指针。这带来的问题是数据本身占空间而且行大小往往不是固定值。假设一行数据是 1KB那么一页 16KB 除去页头、页目录等开销也就放十几条记录。如果叶子和非叶子节点都放数据那么非叶子节点的分叉数量被数据撑到极小树必须长很高。更麻烦的是数据搬移会导致索引频繁调整写路径的开销很难控制。B 树做了一个很“极端”的决策非叶子节点只保存“键”和“指向子节点的指针”真正数据全部集中在叶子节点。这样做的好处立刻显现单页能放的分叉数量大幅增加。主键如果是 BIGINT占 8 字节指针按 InnoDB 典型格式约 6 字节加起来 14 字节。一页 16KB 粗略能放 1170 个分叉这个数字一上来树高就被压得很低。我们可以做一个直观的估算。第二层如果有 1170 个分叉每个分叉往下继续分那么第三层叶子理论上能覆盖 1170 × 1170 136 万个叶子页。假设每个叶子页能放 16 条约 1KB 左右的数据那这棵树就能覆盖超过 2000 万行。三层结构基本就是千万级数据量的承载上限。这个“三层读完两三千万行索引”的说法就是这么来的。2.2 叶子节点用链表串起来范围查询如鱼得水如果只做单点查找哈希表理论上比 B 树更快O(1) 定位。但数据库根本不是只做等值查询。WHERE age 18、WHERE create_time BETWEEN ...、ORDER BY id LIMIT 10这些场景比等值查询更常见。B 树把每一层的叶子节点从左到右用指针连成一个有序链表。一旦你定位到了范围起点接下来只需要沿着链表顺序往后读不需要再回到根节点重新走一遍。这个特性让范围查询、排序查询、分组统计都变成了接近顺序读的操作。对应地B 树虽然也可以在叶子层做范围遍历但它的叶子节点之间并不天然通过双向链表关联遍历时往往需要回溯父节点随机 I/O 又回来了。我在生产里见过最典型的例子订单表按create_time建了二级索引业务经常查“最近 10 分钟产生的订单”。执行计划走这个索引时InnoDB 先定位到时间起点对应的叶子页然后顺着叶子链表向后扫整个过程 I/O 路径非常短。这就是 B 树叶子链表的实际价值。2.3 几种常见结构放在一起对比一眼看明白取舍用一张表把常见的索引结构拉通对比会更直观结构单点等值查询范围查询插入/更新代价磁盘 I/O 次数MySQL 使用场景哈希索引极快不支持低但难以有序遍历1 次左右Memory 引擎、InnoDB 自适应哈希索引二叉/红黑树快内存友好快但不优中树高约 20 层磁盘随机读多较少用于磁盘表索引B 树快弱于 B 树中高节点存储数据扇出小、树偏高部分 NoSQL、文件系统B 树快极快中扇出大、树高稳定在 3~4 层InnoDB/MyISAM 默认索引跳表快快中多层指针内存结构Redis 的有序集合从这张表能看到B 树并不是所有维度上的单项冠军但它是单点查询、范围查询、排序、磁盘 I/O 这几个关键维度综合得分最高的方案。数据库要服务的是混合读写负载而不是只看某一个指标。3. InnoDB 里 B 树是怎么真正落地的3.1 页、页目录和预读为什么 16KB 是核心单位前面反复提到页现在说清楚它到底怎么和 B 树结合。InnoDB 的最小存储单位不是行而是页。页的默认大小是 16KB这个值可以用innodb_page_size参数调整但不建议随便改因为和索引结构、刷盘机制深度耦合。每次你想读某一行InnoDB 不会只读取这一行而是把它所在的那一页整页读入内存缓冲池。这是什么意思呢它天然做了一个“预读”逻辑既然反正要读一页页里相邻的数据大概率后续也会用到。而对于 B 树来说叶子节点上物理相邻的数据逻辑上也往往是相邻的这正好把“磁盘顺序读”和“B 树有序性”结合了起来。页内部还有一个叫“页目录”的结构相当于在页内再分层把页里的槽位按主键顺序组织起来做二分定位。所以查询路径实际是先通过 B 树定位到某个叶子页再在页目录里用二分法找到具体记录。这两层配合才做到“千万行数据也只需 3~4 次页访问”。页分裂也是一个不得不提的概念。当插入顺序打乱时比如主键是随机 UUID新记录找不到合适的空闲位置InnoDB 会把一个写满的页拆成两个重新分配记录再把新页指针挂到父节点上。这个动作本身是 B 树维持有序性的正常机制但开销不小。随机主键的高频插入会让页分裂频繁发生甚至引发页的“空洞”。这也是为什么强烈建议 InnoDB 表的主键尽量用自增 ID——顺序插入能让新记录基本落在页尾部页分裂的概率降到最低。3.2 聚簇索引和二级索引数据到底是怎么挂到树上的InnoDB 里的 B 树不是一个抽象概念它有非常明确的两种形态聚簇索引和二级索引。聚簇索引也叫主键索引它的叶子节点直接存整行数据。也就是说这张表本身的数据内容就是主键 B 树的叶子页。所以 InnoDB 表不能没有主键如果你不主动建主键它会隐式生成一个不可见的 rowid 来做聚簇索引的键。聚簇索引最大的特点是按主键范围扫数据时读取到的行物理上也是连续的。这个特性让ORDER BY 主键和主键范围查询非常舒服因为顺序读多、随机读少。二级索引也叫辅助索引/普通索引则是另一棵独立的 B 树它的叶子节点不存整行数据只存两样东西索引键和对应主键的值。比如你在name字段上建索引这棵 B 树的叶子存的是name和id。当你通过name查数据InnoDB 先从这棵二级索引树里找到主键再回到聚簇索引里根据主键查一整行这个“回到聚簇索引查原行”的动作就叫回表。这里涉及一个非常重要的业务优化思路如果查询需要的字段正好都包含在二级索引里那就完全不需要回表。比如索引是(name, status)而查询只取name, status, id三个字段都在索引树里能找到执行计划会显示Using index这就是“覆盖索引”。覆盖索引让查询只扫描一棵二级索引树不碰聚簇索引的数据页性能提升非常明显。我调慢查询时最先看的就是这里——能不能加一个覆盖索引来干掉回表。3.3 自适应哈希索引B 树并没有排斥哈希有人会问既然哈希单点查询更快InnoDB 为什么不直接用哈希做所有索引答案是 InnoDB 没有完全拒绝哈希而是做了一个“自适应”处理。当某个二级索引被反复等值查询并且访问模式非常稳定时InnoDB 会在内存里自动为它构建一张哈希索引用于加速这些热点查询。这就是自适应哈希索引Adaptive Hash Index。需要注意这个哈希只是 B 树之上的“跳板”本身不持久化。它解决的是“热点数据反复等值查询”这个特定问题范围查询仍然要交给 B 树。这个设计也说明了一个更底层的观点索引结构之间不是非此即彼的真实系统往往会给核心结构加各种辅助层来弥补短板。所以平时回答“为什么用 B 树而不是哈希”最准确的解释是“InnoDB 的默认主结构是 B 树因为它能满足等值、范围和排序需求在等值访问的热点路径里还有自适应哈希索引在内存中兜底加速。” 这个答案比只说“哈希不支持范围查询”要完整得多。4. 面试里最常见的追问以及实战中容易踩的坑4.1 追问一为什么不用红黑树或跳表面试官经常加一个问题“内存里不就够快了吗为什么不用红黑树”关键在数据规模。红黑树是二叉树适合在内存里动态维护有序集合但它的每个节点只有两个子节点存储 2000 万数据时树高在 25 层左右。在纯内存场景下25 次比较在几十纳秒里完成完全不是问题。问题是磁盘场景。如果树的节点对应磁盘页25 层的随机读取就意味着可能 25 次随机的磁盘 I/O这在机械硬盘时代是灾难在 SSD 时代也远不算便宜。跳表相比之下更适合内存或较低延迟的有序结构Redis 用它做有序集合。但跳表的指针维护成本高每个节点多层指针磁盘利用率并不突出而且本质上也不是为“以大页为单位持久化”而设计的结构。所以面试题的标准答法是三步第一红黑树/二叉树的单个节点分叉少磁盘索引要求的“高扇出”满足不了第二跳表等结构更适合内存场景磁盘持久化的页组织天然和 B 树契合第三B 树用“非叶子只存索引、叶子串成链表”换来了矮树高和范围扫描两个核心收益。4.2 追问二写放大那么厉害为什么不用 LSM-Tree一提到写优化就绕不开 LSM-Tree。LevelDB、RocksDB 这类存储引擎都用了 LSM用批量写和后台合并来换取极高的写吞吐。那 MySQL 为什么不用LSM 的核心是先把随机写转化为内存里的有序追加再在后台不断合并落盘。这种机制让写路径非常顺但读路径可能变复杂尤其是要查一个刚写入却还没合并的数据时可能需要查内存表、多个层次的文件还需要用布隆过滤器等辅助结构来加速。压缩Compaction过程还会带来明显的写放大和读放大。MySQL 的设计目标更偏向传统 OLTP 的均衡负载读多写多事务性要求高ACID 语义要强。B 树的写路径虽然要维护页分裂和页合并但读性能稳定事务锁管理也更成熟。所以不能说 LSM 比 B 树强只能说它们是不同负载下的不同取舍。如果生产环境是写入密集型日志场景你可以考虑把归档库放在 ClickHouse 或 RocksDB 这类引擎里但核心业务库保持 InnoDB很可能正是因为 B 树读路径的可预期性更重要。4.3 实战经验别让“大索引”变成新的“大表”聊完理论说点生产里实际碰到过的坑。有一次排查一个分页查询SQL 大概长这样SELECT * FROM operation_log WHERE status 1 AND user_id 10086 ORDER BY create_time DESC LIMIT 10;这 SQL 看起来没毛病字段也都建了索引但执行计划给出的type是range且rows非常离谱十几万条日志被扫了。问题出在哪建的是(user_id, status)单列索引排序字段create_time没有进入索引。InnoDB 拿到满足user_id和status的记录后发现无法在索引树里直接得到有序的create_time于是只能把这些记录全部找出来再用临时文件排序最后取 10 条。优化方案很简单把索引改成(user_id, status, create_time)。这样二级索引树的叶子节点已经按这三个键的有序性排列排序列直接走索引执行计划里Extra字段会出现Using index不会再出现 filesort。这个改动看着不大但日志量上来之后查询时间从秒级降到毫秒级。这个例子想说的是B 树的有序性不是自动就能被用上的只有让查询的过滤列、排序列、返回列尽量都“卷”进同一棵索引树时收益才会真正兑现。看执行计划时重点检查type至少到range/ref、key_len判断索引到底用了哪几列、rows扫描行数、Extra有没有Using filesort、Using temporary、Using index。最后分享一个我自己的习惯每次定位慢 SQL不急着加索引先拿EXPLAIN看当前 B 树有没有被正确使用。很多性能问题不是索引不存在而是索引顺序不合适多一个字段或少一个字段走不走索引的差别是数量级的。理解了 MySQL 为什么选 B 树之后再回头看执行计划你会发现自己终于知道它每一列到底在说什么了。
