一张订单表三千万行数据线上一个按主键查单的接口要求返回时间不能超过一百毫秒。这就是我前几年接手过的一个真实场景。刚开始我以为是索引没建检查后发现主键索引、普通索引都在但某些查询就是慢慢到用户开始投诉。后来把执行计划翻出来逐条看再把 InnoDB 的索引结构从底层过了一遍才真正弄明白索引不是建了就完事你还得知道那一棵 BTree 到底是怎么帮你把数据捞出来的它为什么能撑住千万级乃至上亿级的数据量以及一旦用错会付出什么代价。这篇文章我打算把 BTree 从里到外拆开讲清楚。你不需要是数据库内核专家只要写过 SQL、被慢查询折磨过就能跟着我的思路走一遍为什么千万级数据不能全表扫描BTree 相比 B-Tree 到底赢在哪一棵树是怎么在 InnoDB 里实际落地的一条 SQL 穿过这棵树时每一步在做什么最后再给你一份我踩过坑之后整理出来的索引设计避坑清单。1. 千万级数据检索的真正瓶颈为什么不能全表扫描先说一个最基础的结论数据库里最贵的操作不是 CPU 计算而是磁盘 IO。CPU 算一个数只要几纳秒但从机械硬盘读一个数据块要几毫秒SSD 虽然快一次随机读也要几十到一百微秒。这个差距意味着如果你让数据库一层一层扫下去哪怕 CPU 忙得冒烟整体速度也会被磁盘拖死。1.1 把十万次磁盘IO压缩成几次全表扫描意味着什么一张一千万行的表假设每行数据平均占 1KBInnoDB 默认一个页是 16KB那一页能放下约 16 行数据整张表大约要 62.5 万个页。全表扫描就是这 62.5 万个页全部读一遍哪怕全部命中缓冲池也要付出几十万次逻辑 IO 的成本一旦落到磁盘时间直接奔着几十秒甚至几分钟去。这个账算下来你就明白凡是上了千万级的表全表扫描基本等于事故。BTree 解决的就是这个“读太多”的问题。它在数据之上构建了一层索引结构把“大海捞针”变成“沿着树走”。你从根节点出发每一层只需要判断一次走哪个分支树的每一层对应一次磁盘读取。树的层数往往是三到四层也就是说一次主键查询只需要三五次磁盘 IO 就能定位到目标数据页。把几十万次压缩到几次这中间的差距就是千万级数据下 BTree 存在的全部意义。1.2 为什么二叉树和哈希表都“退赛”了你可能会有疑问能限制 IO 次数的结构那么多为什么偏偏是 BTree我分别说下二叉搜索树和哈希表的短板你就明白选型背后的逻辑了。二叉搜索树的问题是“矮不了”。二叉树的每个节点最多两个子节点数据量一旦到千万级树的高度就奔着二十多层去了。每一层都是一次磁盘随机读二十多次 IO虽然比全表扫描好很多但跟 BTree 的三五次比起来还是太慢了。更麻烦的是普通二叉搜索树如果插入顺序不当还会退化成链表高度直接变成一千万那跟全表扫描没什么区别。AVL 树和红黑树能解决退化问题但高度仍然维持在二十层上下磁盘 IO 次数依旧偏高。哈希表的问题是“只能精确匹配”。哈希索引在单点等值查询上确实快理论上是 O(1)可一旦碰到范围查询比如WHERE age BETWEEN 20 AND 30哈希表就彻底抓瞎了因为哈希函数打散了键值之间的顺序关系你只能把符合条件的值一个个全部试一遍。业务系统里绝大多数查询都不是单纯等值范围查询、排序、分组、前缀匹配到处都是这些恰恰是哈希的禁区。BTree 的叶子节点天然有序等值、范围、排序一把抓这才是它能成为 InnoDB 默认索引结构的根本原因。2. 从 B-Tree 到 BTree数据库为什么偏偏选它很多人第一次听说 BTree 都会带着疑问B-Tree 看起来也能做索引为什么不直接用 B-Tree这就要说到 btree 和 btree 的区别了这也是面试和实战里都绕不开的高频话题。2.1 btree和btree究竟差在哪B-Tree 是最早被提出来的一种多路平衡查找树它的设计目标就是减少磁盘 IO。每个节点能存多个键值对并且每个节点下面有多个子节点这让整棵树变得又矮又宽。但关键区别在于B-Tree 的每个节点都存储“键 数据”也就是说非叶子节点里不光有索引键还挂着对应的行数据或数据指针。BTree 则做了一个关键改动只有叶子节点存数据非叶子节点只存键和指向子节点的指针而且所有叶子节点通过双向链表串在一起。这个改动看似不大实际影响却非常深远。对比维度B-TreeBTree非叶子节点内容存储键 数据或指针只存储键和子节点指针叶子节点分散存储数据集中存储全部数据按序排列叶子节点间关系无链表连接双向链表连接一次查询的IO次数可能提前命中非叶子节点返回必须走到叶子节点次数稳定范围查询需要中序遍历链表顺序遍历页利用率键和数据混存单页能容纳的键少非叶子节点仅存键扇出大、树更矮B-Tree 看起来省事数据在非叶子节点就能取到但正因为它把数据和索引混在一起单页能容纳的键数量就变少了。同样 16KB 的页B-Tree 可能只塞得下几百个键BTree 的非叶子节点却能塞下一千多个键这就导致同一个数据量下B-Tree 的树更高磁盘 IO 次数更多范围查询还得靠中序遍历一点点往回找非常麻烦。2.2 叶子链表范围查询和排序的“作弊器”BTree 这个“只在叶子存数据”的设计还带出了一个隐藏福利所有数据按主键顺序排列在叶子页上页与页之间用链表串起来。这意味着你一旦定位到范围查询的起始位置后面就只管沿着链表顺序往后读不需要再回到树的上层判断走哪条路径。我举个例子你感受一下。执行WHERE id BETWEEN 1000 AND 2000BTree 先通过树搜索定位到 id1000 所在的叶子页然后顺着链表依次读后面的页直到遇到超过 2000 的记录才停。这个过程中树搜索只发生了两三次 IO剩下的大量数据完全是顺序读。数据库的预读机制对这种连续页访问非常友好磁盘顺序读的速度比随机读快好几个量级整段查询下来可能几毫秒就搞定了。如果用的是 B-Tree你得在中序遍历和父子节点之间反复跳跃每一步都可能触发随机 IO性能完全不在一个等级上。这也是我经常跟人强调的BTree 的高效并不仅仅是“树矮”更在于它把随机查询和顺序查询两种场景统一到了一个结构里。单点查询靠树高来限制 IO 次数范围查询靠叶子链表吃顺序读的红利这两个优势叠加起来才让 InnoDB 在千万级数据下依然游刃有余。3. 一棵 BTree 在 InnoDB 里到底长什么样前面讲的都是抽象的树结构现在落到 InnoDB 这个具体的存储引擎里看看 BTree 是怎么被“物理实现”的。理解了这一层你再去看执行计划、索引优化很多曾经觉得玄乎的地方都会变得非常直白。3.1 一切从16KB的页开始InnoDB 里最小的存储单位不是行而是页默认大小 16KB。页是磁盘和内存之间交互的基本单位你读一行数据数据库也是把整页读进缓冲池写一行数据也是把整页刷回磁盘。这个设计带来的一个直接推论就是单个索引项越小一个页能装下的索引项就越多树的分叉就越宽树高就越矮查询的 IO 次数就越少。BTree 的每个节点在物理上就是一个页。根节点是根页中间节点是内部页叶子节点是数据页。内部页里每一行装的是一个“索引键 下一页指针”的组合比如主键是 BIGINT8 字节加上 4 字节的页号再加一些页内记录头和状态信息一个索引项大约占用 13 字节。按这个来算一个 16KB 的页大约能放 16 * 1024 / 13约等于 1170 个索引项。这个数非常关键因为它直接决定了千万级数据下的树高。你现在记住 1170 这个数后面计算树高的时候会反复用到。3.2 聚簇索引和二级索引一张表的两种BTreeInnoDB 里一张表至少有两套 BTree 结构。第一套是聚簇索引它在主键上构建叶子节点直接存整行数据。这张表的全部数据实际上都存放在这棵聚簇索引的叶子节点里所以 InnoDB 表本质上就是一棵以主键为序的 BTree这句话是理解 InnoDB 一切行为的钥匙。第二套是二级索引它在用户创建的索引列上构建叶子节点存的是“索引列的值 主键值”。查询时先走二级索引查到主键再拿主键去聚簇索引里捞整行数据这个过程叫回表。回表意味着多一次按主键的树搜索速度会慢一些但它能让二级索引保持小而紧凑不至于每建一个索引就把整行数据拷贝一份。这里有一个常见的误区很多人以为索引越多查询越快实际情况是每个二级索引都是一棵独立的 BTree写入一行数据时要同时维护所有索引树。索引越多写放大越严重插入和更新会变得异常缓慢。我在生产环境见过一张表建了十几个索引结果主键查询倒是挺快写入却慢到需要几秒钟后来删掉几个低频索引才恢复正常。3.3 用真实参数算一算多少层才能装下千万行光说“BTree 很矮”不够直观我按 InnoDB 的真实参数帮你算一遍。先看非叶子节点。一个页 16KB每个索引项约 13 字节所以一个内部页大约能容纳 16 * 1024 / 13 1170 个索引项也就是 1170 个分叉。再看叶子节点。假设你表里的行平均大小是 1KB那么一个叶子数据页能放 16 行数据。接下来从下往上推算这棵树能承载多少数据树高为 1 时只有一个叶子页装 16 行。树高为 2 时根页能指向 1170 个叶子页总共 1170 * 16 18720 行大概两万行左右。树高为 3 时根页下面有 1170 个内部页每个内部页又能指向 1170 个叶子页叶子页总数是 1170 * 1170约 136.9 万个页乘以每页 16 行大约是 2190 万行。看到没有只要树高到 3 层这棵 BTree 就能支撑两千万行级别的数据量。而你从根节点出发找到任何一个叶子节点只需要经过根页、内部页、叶子页三次 IO还没算缓冲池命中的情况。如果主键用 BIGINT 这种紧凑类型索引项更小扇出更高三层装下四五千万行完全不是问题。这就回答了标题里的问题一棵 BTree 之所以能支撑千万级数据检索核心就一句话用三层高度换两千万行容量每次定位数据只需要三次磁盘访问。有人可能会问如果数据量继续涨到几亿行怎么办树高到 4 层定位也就是四次 IO依然很可控。真正需要关心的是单个叶子页能存多少行换句话说行的宽度越小同样的树高能装的行数越多。这也是为什么我建表时反复提醒同事列别乱加能用 1KB 的行别设计成 4KB因为行越宽BTree 的“容量”越低。4. 一条SQL穿过BTree的完整路径树的结构讲清楚了接下来我们把一个查询语句真正丢进去看看它是怎么一路走到底的。这部分是“看着简单、想明白不容易”的地方我会结合一次主键查询和一次范围查询分别拆解。4.1 主键查询为什么能稳定在毫秒级假设有一张订单表orders主键是order_id BIGINT查询语句是SELECT * FROM orders WHERE order_id 4987123;这条 SQL 的底层执行路径是这样的MySQL 的优化器判断这个查询命中了主键的聚簇索引于是从 BTree 的根页开始查找。根页存放在内存中大概率已经在缓冲池里里面存储着键值和子页的地址。InnoDB 会在根页里做二分查找定位到 4987123 应该走哪个指针进入下一层。这里有个细节值得注意根页里的键值是按大小排序的InnoDB 用的不是遍历而是基于数组的二分查找。页内记录数量通常几百到一千出头二分查找只需要十次左右比较速度可以忽略不计。拿到下一个页的地址后InnoDB 要看这个页是否在缓冲池中。如果在直接从内存里继续二分如果不在触发一次磁盘 IO 把页加载进来。第三层是叶子页里面存放的就是完整的行数据。InnoDB 在叶子页内继续二分查找命中目标记录把整行返回。这个过程稳定在三到四次 IO。即便没有缓冲池缓冲纯磁盘随机读每次按 10ms 算也就是 30 到 40 毫秒。加上页内二分查找的 CPU 时间一百毫秒内返回完全没问题。这就是为什么千万级表的主键查询可以很快因为它根本就不扫描表只是在树上走了三层而已。4.2 范围查询和索引扫描如何吃掉“链表红利”单点查询是 BTree 的看家本领但业务里真正的重头戏是范围查询。再看这条 SQLSELECT order_id, amount FROM orders WHERE order_id BETWEEN 1000000 AND 2000000 ORDER BY order_id;整个执行过程分成两步。第一步是定位从根页出发二分地找到第一个满足order_id 1000000的叶子页这一步和单点查询一样三到四次 IO。第二步是顺序遍历从定位到的叶子记录开始在页内顺序读取读完当前页后通过叶子节点上的双向链表直接跳到下一页继续读直到遇到第一个超过 2000000 的记录才停止。关键点在于第二步不会再触发任何树搜索完全是沿着链表往前走而相邻的叶子页在物理磁盘上大概率也是连续或相邻的数据库的预读机制会把后续页一次性加载进缓冲池。所以整个区间扫描的实际开销几乎等同于顺序读和全表扫描的成本完全不是一个概念。这也就是为什么 BTree 在有排序场景时特别能打数据天然有序范围查询和排序都吃到了链表红利省掉了一次 filesort。顺带补充一个实操经验如果你让这个范围查询走了二级索引而非主键结果大概率会变成“二级索引范围扫描 逐行回表”。当回表的行数占全表比例较高时优化器可能干脆放弃索引直接全表扫描反而更快。这个点会直接引出第五章的避坑清单。5. 千万级表上的索引设计避坑清单索引设计的最优策略不是“每个查询都建一个索引”而是让每一棵 BTree 都尽可能矮、尽可能少回表、尽可能多利用顺序读。下面这些坑全是我在真实业务里踩过或看人踩过的整理成一张表方便你对号入座。5.1 索引失效场景速查表常见问题底层原因解决建议对索引列使用函数或计算函数破坏了键值排序BTree 无法定位改写为范围条件或建函数索引部分版本支持隐式类型转换字段是 varchar 却用数字查询索引失效保证查询参数类型与字段类型完全一致前导模糊查询%abc无法从 BTree 有序键中确定起始位置改为后缀查询或利用覆盖索引缓存做兜底联合索引没用最左列索引树按第一列排序跳过第一列无法二分定位查询条件尽量覆盖最左前缀行太宽导致叶子页存行数太少单页行数下降树容量变小IO 概率上升拆大字段到子表保持行紧凑选择性太低的列做索引大量重复键让叶子链表扫描冗长优先选择区分度高的列每一条我都实际遇到过。印象最深的是有一次排查线上的慢 SQL明明字段是 varchar业务代码里却传了个 int 进去。MySQL 做了隐式转换后索引直接废掉原本几毫秒的查询变成了全表扫描跑了二十多秒。排查到最后原因就是一行代码的类型写错了。这种事在千万级数据量下不是小事一次全表扫描就可能把数据库 CPU 打满。5.2 建索引前先问自己这几个问题在决定新建索引之前我建议你先回答自己四个问题。这个索引能不能降低树的高度如果你的查询走的是主键数据量又只有百万级加普通索引的收益可能并不大因为树高本来就够低了。如果是千万级表查询又频繁这时候一个合适的二级索引才能显著减少扫描的粒度。需要建联合索引还是单列索引联合索引的排序规则是先按第一列排再按第二列排所以(a, b)和(b, a)是两棵完全不同的树。你要结合实际查询的最左前缀来判断哪列放前面而不是谁查询频率高就放谁前面。这里最常见的错误是单独为 b 列又建一个索引造成冗余。用不用考虑覆盖索引如果查询的字段都包含在索引里InnoDB 可以直接从二级索引返回结果不需要回表。这个优化往往能让查询性能翻倍。我经手的一个报表查询原本要回表三千多次改成覆盖索引后直接从一秒变成了五十毫秒。代价是多占一部分存储但对于高频查询来说这笔交易非常划算。主键到底选递增整数还是随机字符串这个问题我放在最后单独说。如果主键是 UUID 之类的随机字符串有两个后果一是值随机插入时新行落到的叶子页是不确定的频繁引起页分裂产生碎片并降低页利用率二是字符串键比 BIGINT 长索引项变大扇出变小。即便额外还有唯一键做保证你也要问自己真的要拿一个 36 位字符串当主键吗我在实际项目里见过太多“为了分布均匀”而用 UUID 做主键的到了千万级数据量后插入性能下降明显页碎片多到需要定期OPTIMIZE TABLE。后来统一改成自增 BIGINT 做主键业务侧用雪花算法生成的 ID 做唯一索引查询用唯一索引插入不再随机跳页整体稳定性提升了一大截。索引设计这件事永远没有银弹但遵循 BTree 的原理去思考很多问题是可以提前避免的。最后再分享一个我在排查慢查询时用的习惯每次看执行计划先问三个问题这条 SQL 是否命中了索引树命中的是哪一棵树走了这棵树之后还需要回表多少行这三个问题每一个都能从EXPLAIN的输出里找到答案。搞清楚它们你的 MySQL 性能调优就算真正入门了。而这一切的起点就是理解那一棵 BTree 是怎么扎根在磁盘页里用三层的高度撑起了千万级的数据检索。
