前阵子帮一个朋友排查慢查询SQL本身很简单就是按主键查一行数据结果执行计划里直接走了全表扫描扫了上百万行。问题出在查询条件上套了一层函数导致索引失效。排查完他顺口问了一句那MySQL的索引底层到底为什么用B树这个问题看起来是面试八股但真往深了挖它能把磁盘IO、数据页、聚簇索引、索引失效、主键设计全部串起来。如果只是背结论转头就忘如果理解了数据结构背后的取舍很多日常调优的动作都能找到依据。这篇就从“如果让你自己设计一个索引”的角度把MySQL选择B树的整个推理过程过一遍希望对刚开始看索引的后端同学以及正在准备面试的同行都有点帮助。1. 先站在磁盘的角度思考问题1.1 索引要解决的核心矛盾数据库最朴素的需求是给一个条件快速定位到数据。在没有索引的情况下MySQL只能做全表扫描也就是从头到尾把数据翻一遍。数据量小的时候问题不大几千行、几万行数据库几毫秒就能跑完可一旦到了百万、千万行级别顺序扫描的耗时就会直线上升从“毫秒级”变成“秒级”甚至更糟。这时候自然想到维护一份“目录”让我们不用从头翻直接跳到目标附近。这个目录就是索引。但目录不是白来的它要占存储空间每次插入、更新、删除时也要跟着维护。换句话说索引结构必须同时满足两个方向的要求读的时候能快速定位写的时候维护成本不能高到没法用。后面比较各种数据结构B树、B树、哈希、红黑树其实都是在拿这把尺子量。还有一个容易被忽视的点索引不只是一个查询加速工具。像UNIQUE约束、ORDER BY排序优化、范围过滤很大程度上也是依赖索引底层的有序结构才能高效完成。所以MySQL底层的索引数据结构必须是既能等值查询又能范围查询还要能支撑排序的东西这个定位从一开始就很明确。1.2 数据页和磁盘IO是真正的瓶颈InnoDB存储引擎不是按“行”来读磁盘的而是按“页”来读。默认情况下一个页的大小是16KB哪怕你只想查一行记录数据库也得先把包含这一行的那一整页加载到内存。这个设计主要是为了减少IO次数磁盘上相邻的数据一次性读进来后续访问同一页里的其他记录时就不用再碰磁盘了这就是局部性原理在存储引擎层面的应用。理解这一点之后就能明白为什么索引结构要和“页”匹配。衡量一个索引结构好不好不只是看算法时间复杂度更要看在磁盘场景下要发生多少次随机IO。机械硬盘寻道一次大概是几毫秒到十几毫秒SSD虽然快很多但一次寻址加读取的开销依然远高于内存访问。内存是纳秒级磁盘是毫秒级中间差了好几个数量级。很多时候一条SQL慢不是CPU算得慢而是磁盘访问次数太多。举个例子如果某个索引结构查询时需要向下走20层每一层都要读一个不在内存里的节点那就是20次随机IO。SSD每秒钟能处理的随机IO数量是有上限的这20次可能就要几十毫秒甚至更久。所以设计索引结构的第一原则是树要矮每次查询访问的节点数量要少。这也就是为什么MySQL最终选择了多路搜索树而不是内存里常用的二叉树。2. 从索引设计一路推导到B树2.1 从有序数组和链表说起先看最简单的两个数据结构。有序数组的等值查询可以用二分查找复杂度是O(logN)范围查询也很方便取一段连续区间就行。但问题在于插入和删除要移动元素往中间插一条数据后面所有数据都得挪位置写入是O(N)的。对于OLTP系统这种高频写入的场景完全不可接受。链表反过来插入和删除很爽只要改指针就行但查找只能从头遍历等值查询退化成O(N)范围查询更是灾难。所以这两者都只能作为局部手段不能担当索引结构的主干。二叉搜索树看起来是折中方案普通情况下等值查询、插入、删除都是O(logN)。但二叉搜索树有个老毛病当插入的数据本身就是有序的树会退化成一个链表查询直接变成O(N)。所以真实场景不能直接用裸的二叉搜索树得用平衡树比如AVL树或红黑树它们通过旋转操作保证树的高度不会失控。到这里理论上前三步都是顺的数组二分快但写入难链表写入快但查找难平衡二叉树两边兼顾。那为什么MySQL不直接用红黑树当索引结构问题出在“高度”上下一节细说。2.2 平衡树解决了退化却没解决树高红黑树和AVL树在内存里确实好用Java的TreeMap、C的std::map底层都是平衡树。但是放到磁盘数据库场景里它们有一个致命短板每个节点只存一个键和两个孩子指针。假设表里有1000万条记录用红黑树组织索引树的高度大约是24层左右。每向下走一层如果对应的节点不在内存里就需要一次磁盘IO。理想情况下可能有些上层节点已经被缓存了但极端情况下一次等值查询要发生二十几次磁盘IO这就非常致命了。前面说过机械盘一次寻道就几毫秒二十几次下来就是小半秒这还只是一条查询线上稍微热点一点的SQL直接就扛不住。二叉平衡树之所以高是因为每个节点的“分叉数”只有2也就是所谓的“路数”太少。一个节点只保存一个键节点能覆盖的数据范围就很小为了到达海量数据所在的叶子层只能一层一层往下加高度。内存里访问这些节点几乎不用考虑成本RAM的随机读取性能是线性的多走几层无所谓。但磁盘IO不一样每层都可能意味着一次昂贵的物理寻址。所以结论很直接要降低树高就得让每个节点多存一些键多带一些孩子从二叉树变成多路搜索树。这就是B树和B树的出发点。2.3 B树和B树是怎么把高度打下来的B树是平衡多路搜索树一个节点可以存放多个键也可以拥有多个子树。举个例子如果一个节点能存放1000个键那么简单算一笔账两层树的节点数量就是1000的平方能覆盖百万级别的数据三层就是十亿级别。树的高度被压到3到4层一次查询最多几次IO这在磁盘场景下完全可以接受。B树是B树的变体MySQL的InnoDB引擎最终选择的是B树而不是原始B树核心区别有三点第一B树的非叶子节点只存索引键和指向子节点的指针不存数据行。这个设计让非叶子节点在同样的16KB页大小里能塞进更多的键进一步压低树高。第二B树的所有数据都存放在叶子节点并且叶子节点之间通过链表按顺序连接。在InnoDB里这个链表是双向的。不管是范围查询还是排序都只要找到起点顺着链表往后扫就行不需要来回回溯父节点。第三上层节点里的键是从子节点中提升出来的“冗余键”。比如父节点里有个键是40那它右子树上所有键都大于等于40左子树都小于40这个键本身并不直接对应某条完整数据只是用来在搜索时判断走向。冗余看起来浪费了一点空间但换来了更简单的搜索路径和更友好的磁盘IO。简单的说B树通过“非叶子节点只存索引、叶子节点存全部数据并串成链表”这两个改动把B树在多路平衡的基础上又往前推了一步让查询路径更稳定也让范围查询和排序变成了顺序扫描这块放到下一节对比详谈。3. 为什么B树能在对比中胜出3.1 B树和B树的正面对比B树和B树都支持多路搜索树高都不高那为什么InnoDB选B树不选B树放在真实查询场景里就能看出差别。先看单点查询。B树在内部节点也可能存储数据所以在查找过程中如果在内层节点就命中了目标键可以直接返回不一定走到叶子。听起来好像B树更快但其实这也意味着B树的查询耗时是不稳定的运气好中间命中运气不好一直走到叶子。对于数据库来说稳定性很重要因为查询计划优化器需要相对稳定的成本估算。B树的数据全在叶子节点任何查询都要走完整条从根到叶子的路径IO次数固定估算起来更靠谱。再看范围查询这是B树最明显的优势。B树的叶子节点之间没有链表数据分散在各个节点范围查询时需要中序遍历从一个节点跳到相邻节点中途可能还要回到父节点再折下来这中间涉及到大量的回溯和跳转磁盘访问随机性很强。而B树的叶子节点已经按顺序用链表串起来了找到范围起点后直接沿着链表顺序往后读磁盘预读也能发挥作用扫描性能高出一大截。还有一个隐性优势B树的内节点不存数据所以每个内节点体积小在同样的缓冲池里可以缓存更多内节点。实际运行时B树的上层节点往往都能常驻内存一个查询真正发生磁盘IO的次数往往只有最后读取叶子节点那一次或者连叶子页也在内存里那就根本不碰磁盘。B树因为内节点可能携带数据整体体积大内存缓存的效果就差一些。我把两者的关键差异整理成一张表方便对比对比项B树B树内节点是否存数据可以存只存索引键单点查询路径可能内层命中路径不稳定固定走到叶子路径稳定范围查询方式中序遍历跨节点回溯叶子链表顺序扫描磁盘预读友好度数据分散预读效果弱叶子有序连续预读效果好内节点缓存效率体积大缓存条目少体积小缓存更多索引项3.2 哈希索引等值查询快范围查询直接废哈希索引是另一个经常被提到的方案。用哈希函数把索引键映射到槽位等值查询理论上能做到O(1)比B树的O(logN)还快。那MySQL为什么不把哈希当作默认索引结构主要原因是哈希完全放弃了顺序性。哈希索引只能做等值匹配WHERE id 100没问题但一旦出现WHERE id 100 AND id 200这类范围查询哈希就无能为力了因为散列之后的数据在物理上完全没有顺序关系。ORDER BY、GROUP BY、前缀模糊匹配LIKE abc%这些依赖有序结构的操作在哈希索引上全部无法使用。另外哈希还有冲突问题极端情况下冲突变多性能会退化。InnoDB其实也内置了自适应哈希索引但它只是B树索引的一种加速辅助结构用来加速某些热点等值查询并不能替代B树成为通用索引结构。所以哈希索引在MySQL里的定位非常清晰锦上添花可以挑大梁不行。3.3 红黑树与跳表内存场景的优等生红黑树和跳表都是内存数据结构的常客。红黑树在C的std::map、Java的TreeMap里很常见跳表是Redis有序集合的底层实现之一。它们在内存里表现很好为什么一放到磁盘数据库就水土不服红黑树的问题前面已经分析过节点存储信息量太少树太高磁盘随机IO次数过多。跳表的特点是每个节点有多个指针查找时要沿着指针跳转访问路径在内存中是连续跨度不大的随机访问内存吃这套但放到磁盘上每跳一次都可能落在不同的磁盘页随机IO次数比B树多得多而且跳表没有利用“页”的概念做批量预读局部性不如B树。还有一个经常被拿出来对比的LSM-Tree它面向的是写多读少的场景通过顺序写和后台合并来优化写入吞吐但代价是读放大读取时可能要查多层文件还要做归并检查。MySQL作为通用关系型数据库面对的查询模式是读多写多、范围查询高频出现B树这种“读写平衡、顺序扫描友好”的结构就是综合最优解。数据结构没有绝对的好坏只有场景适配度的问题。4. InnoDB里的B树长什么样4.1 聚簇索引和二级索引的分工在InnoDB里B树不只是索引它直接决定了表数据的物理组织形式。主键索引是聚簇索引也就是说整张表的行数据本身就被组织成了一棵以主键为序的B树每个叶子节点里存的不是索引项而是完整的一行数据。这和MyISAM不同MyISAM的索引文件和表数据文件是分离的索引叶子节点里存的是指向数据的指针或行号。二级索引则完全不一样。InnoDB里除了主键索引外其他索引都是二级索引它们的B树叶子节点里存的不是行数据而是该行对应的主键值。当我们通过二级索引查到目标主键后还要拿着这个主键再去主键B树里查一次这个过程叫回表。所以SELECT * FROM t WHERE name xxx和SELECT id FROM t WHERE name xxx看着差不多实际执行路径差别很大。如果查询所需的列全部包含在二级索引里就不用回表这叫覆盖索引。理解了二级索引叶子节点存主键这个细节就很容易明白为什么联合索引设计、覆盖索引设计能带来明显的性能提升也能理解为什么主键应该尽量短——因为每个二级索引的叶子节点都在冗余主键值主键越长二级索引越臃肿占用的空间和IO都更多。4.2 三层B树到底能存多少行很多人对“B树三层就能存千万行”没概念这里算一笔账。InnoDB默认页大小是16KB也就是16384字节。先算非叶子节点。假设主键是BIGINT占8字节指针大概6字节一个索引项约14字节。16384除以14大约等于1170。也就是说一个非叶子节点大概能放1170个索引键也就是最多分出1170个子节点。再算叶子节点。假设表里一行数据平均大小为1KB那么一个16KB的叶子页大约可以存放16行数据。那么两层B树能覆盖1170乘以16大约18720行。三层B树就是1170乘以1170再乘以16大约2190万行。这个数字很能说明问题。千万级数据的表按主键等值查询最多只需要访问三个节点根节点、中间层节点、叶子节点。而且在实际运行中根节点和大部分中间层节点早就被缓冲池缓存了真实发生的磁盘IO往往只有读取叶子页那一次或者一次都没有。如果主键是INT索引项占用空间更小一个非叶子页能放的索引项更多树会更矮容量会进一步增大。当然这是非常理想化的估算真实情况里会有页填充率、行大小波动、主键类型差异数据量级会浮动但结论方向不变B树用极低的高度撑起了关系型数据库的海量数据访问需求。4.3 页内结构、页分裂和主键的顺序问题B树在InnoDB里的基本组成单位是页。一个叶子页内部记录按照主键顺序在逻辑上串联为了加速页内查找InnoDB还维护了一个类似稀疏索引的Page Directory结构可以先用二分法定位到大概的槽位再在槽里做小范围线性查找。页与页之间通过链表串联这就保证了范围扫描时能从起点一路向后。页分裂是B树写入时最重要的机制。当一个叶子页写满了再插入新记录时如果这个页已经装不下InnoDB就会申请一个新的页把一部分记录挪过去再更新父节点里的索引键这个过程叫页分裂。页分裂本身会产生额外的写IO而且分裂后可能留下碎片空间导致页面填充率下降。这就引出了一个实际经验主键设计要尽量有序。自增主键插入时新记录总是在B树最右侧的叶子页上顺序追加大多数情况下已有的叶子页已经留有余量或者直接在末尾插入页分裂频率非常低。反过来如果主键是UUID这种随机字符串每次插入的落点分散在整棵树的各个位置容易导致大量页分裂和页移动写入放大明显还会产生碎片时间长了整个表的更新和查询都会劣化。可以类比图书馆的书架编号新书如果按编号顺序送过来管理员往最后一格放就行如果编号完全随机那就得频繁腾挪、重新排架效率自然低。所以很多业务主键用自增ID或者雪花算法生成的有序分布式ID本质上都是在配合B树的物理结构。5. 从B树原理推导出来的调优与面试技巧5.1 两分钟把这个问题讲清楚如果面试中被问到“MySQL为什么用B树”我建议按下面这个逻辑展开而不是直接背诵B树的定义。先讲约束MySQL数据在磁盘上InnoDB按16KB的页读取数据磁盘随机IO是最大瓶颈所以索引结构必须尽量降低查询时的磁盘访问次数。再讲候选二叉树和红黑树每个节点只能存一个键数据量大时树高在磁盘上查询会触发高额随机IO不可行。哈希索引虽然等值查询快但范围查询和排序天然不能支持。B树和B树通过多路设计把树高压到3到4层其中B树内节点不存数据、叶子节点串成链表让范围查询和排序变成顺序扫描还能充分利用页预读和缓冲池缓存。最后落到InnoDB实现主键聚簇索引就是B树二级索引叶子存主键值所以主键要短、要有序。这个逻辑链条每一步都有因果而不是零散的知识点。面试官想看的其实不是你会不会背“B树有三层”而是你能不能把存储模型、IO成本和数据结构设计串起来讲清楚。5.2 理解B树之后建索引和写SQL会有变化很多索引使用规则如果从B树结构出发是能直接推出来的不需要死记硬背。最左前缀法则。联合索引的B树内部记录先按第一列排序第一列相同的再按第二列排序。查询条件如果不包含第一列就像查字典不知道部首只能从头翻索引起不到定位作用。所以联合索引要尽量把最常出现在查询条件里的列放前面。范围查询后面的索引列会失效。比如联合索引是(a,b)查询WHERE a1 AND b2B树可以通过a定位到a1的区段在区段内通过b过滤但如果再有一个c列就没法继续通过索引精确定位了因为b的范围让后续的c无法保持有序。覆盖索引可以避免回表。既然二级索引叶子里存的是主键值如果查询的列全部在索引里InnoDB就不需要回表再去主键树翻一次。这也是为什么SELECT id,name比SELECT *有时候快很多的原因之一不光是传输数据量小。排序可以利用索引有序。B树叶子节点本身按索引键有序如果ORDER BY字段和索引顺序一致优化器能直接顺序读叶子节点避免filesort。反过来如果排序顺序和索引顺序冲突就会重新排序。这些规则都可以用一个EXPLAIN验证EXPLAIN SELECT id, name FROM t WHERE name zhangsan;看key字段是否命中索引key_len用了索引的哪几个字段rows估算扫描多少行。实测几次之后对B树和查询优化器的配合会理解得更具体。5.3 几个容易误解的索引问题第一B树读快写慢是不是写密集场景就该避开MySQL这句话只说对了一半。B树的写路径和读路径高度一致都会经历从根节点到叶子节点的定位任何插入更新都要先走一遍索引查找。但页分裂等写放大问题并非不可控选择有序主键就能大幅减少分裂。对比红黑树和哈希B树在通用读写混合场景下依然是平衡得很好的方案。第二页越大树越矮是不是把InnoDB页调大就更好不一定。页变大单个页能容纳的记录和索引项变多树确实可能变矮但页分裂的代价也变大缓冲池能缓存的页数量变少高频小查询浪费的内存IO反而增加。16KB是InnoDB在不同负载、不同硬件环境下权衡出的默认值虽然也支持修改页大小选项但日常使用不建议随便动。第三索引越多越好每个索引本质上都是一棵独立的B树插入一条记录要同时维护这棵树更新主键更是要牵连所有二级索引。索引越多写入路径越长还占磁盘空间。建索引之前要想清楚业务查询模式是不是真的需要它联合索引能不能覆盖更多查询而不是每看到一个查询条件就加一个索引。最后再分享一点个人体会我理解B树感受最深的一次是调一张用UUID做主键的表。表到了千万级之后插入越来越慢磁盘IO经常被打满。一开始怀疑硬件瓶颈后来看监控发现写入时页分裂频繁页碎片率一路走高才真正意识到是主键随机性在踩B树的软肋。把新表改成自增主键、旧表通过回填方式重建后同样量级的数据写入耗时降了一个数量级查询也因为碎片减少变得稳定。从那以后我做表结构设计时会习惯性多问一句主键有序吗查询真的需要这个索引吗联合索引能不能覆盖更多如果你也想验证这篇文章里的结论可以自己建两张结构相同的表一张自增主键、一张UUID主键分别灌几百万行数据再对比插入耗时、SHOW TABLE STATUS里的数据长度和碎片信息会比看十篇分析文章都直观。B树不是什么玄学它就是一个在磁盘约束下做了大量取舍的结构理解了它MySQL里很多看似玄乎的调优规则都能找到根因。