先还原一个线上常见的分页现象。后台的订单列表按主键倒序展示,SQL 写的是 SELECT ... ORDER BY id DESC LIMIT 10 OFFSET 100000。前几页很快,翻到五位数页码之后,接口从几十毫秒涨到好几秒,而且页码越大越慢。把 OFFSET 改回 0,速度立刻恢复,说明数据量、网络和渲染都不是主因,问题出在「跳过前面十万行」这件事本身。

这里没有真实的数据库环境,SQL 的实际执行计划和耗时未在本机实测。文中的扇出、树高、页数和扫描行数,是按公开的页结构公式在本机用 Node.js 24 算出来的,代码与输出都能复现。索引内部长什么样,按常见存储引擎的公开实现描述,不同数据库会有细节差异。

这篇要回答三个具体问题:一次按主键的点查到底读了几页;按普通字段查为什么要「回表」,回表又贵在哪;为什么范围查询、排序和分页最终都落到 B+ 树的叶子上。把这些数量关系算清楚,看到执行计划里的扫描行数才不会一头雾水。

现场:翻到第十万行,为什么要先读十万行

OFFSET 的语义经常被误解成「直接跳到第 N 行」。实际执行时,存储引擎必须按索引顺序从头开始,把前面 N 行一条条读出来、判断、然后丢掉,再取接下来的 10 行。它没有「按序号直接定位」的能力,因为 B+ 树的叶子只按 key 排序,不记录「第几行」这种位置。

所以 LIMIT 10 OFFSET 100000 至少要看 100010 行:前面 100000 行是白读的,后面 10 行才是结果。翻页越深,白读的比例越高。第一页只需要读 10 行,第十万页要读十万行,耗时自然随页码线性增长。这就是「越翻越慢」的真实原因,不是数据库在针对深分页做惩罚。

把行数换算成页数会更直观。假设一行数据加行头平均占 100 字节左右,一页 16KB 能放一百多行;为了便于演示,这里取每页 100 行。用本机 Node.js 按「扫描行数等于 OFFSET 加 LIMIT」计算,四个典型偏移量的结果如下。

for (const off of [0, 1000, 10000, 100000]) {
  const rows = off + 10;
  console.log(`OFFSET ${off}:至少扫 ${rows} 行,约 ${Math.ceil(rows / 100)} 页`);
}

本机实际输出是:OFFSET 0 至少扫 10 行,约 1 页;OFFSET 1000 至少扫 1010 行,约 11 页;OFFSET 10000 至少扫 10010 行,约 101 页;OFFSET 100000 至少扫 100010 行,约 1001 页。页数从 1 涨到 1001,正好是偏移量放大的倍数。

这还只是「读索引叶子」的成本。如果查询的列不在索引里,每一行还要回到主键索引取完整数据,代价会再乘一次。深分页慢,往往是「扫很多行」和「回很多次表」两件事叠在一起。要理解后半段,得先看清楚数据到底存在哪棵树上。

聚簇索引与二级索引:数据到底存在哪

聚簇索引(clustered index)是把完整数据行直接存在 B+ 树叶子里的索引。一张表的聚簇索引通常就是主键索引:叶子节点存的是整行记录,内部节点只存主键用来指路。因为数据本身按主键顺序摆放,主键查一行只需要从根走到叶子,拿到叶子就拿到了整行,不需要再查别的地方。

二级索引(secondary index)是另外建的索引,叶子节点存的是「索引列的值加主键值」,不存完整行。它像一本书后面的索引页:查到关键词,得到的是页码(这里是主键),还要按页码翻回正文。这个「拿主键回聚簇索引取完整行」的动作,就叫回表(lookup back to table)。

二级索引叶子存索引列的值,加上这一行的主键值。它知道自己指向哪一行,但不存整行。
主键值回表的钥匙。二级索引命中后,先拿到主键,再去聚簇索引里找这一行。
聚簇索引叶子存完整数据行。按主键找到叶子,才能真正读出查询要的列。

这个分工解释了一个常见困惑:为什么按主键查很快,按普通字段查就慢一截。按主键查是直接走聚簇索引,一次定位到整行;按普通字段查要先走二级索引拿到主键,再回聚簇索引取行,路径多了一倍,而且第二次查找是随机的。返回的行越多,回表的随机读越多。

回表不是「多一次函数调用」这么轻。每一次回表都是一次新的树查找,要从聚簇索引的根一路走到叶子。如果这些主键在聚簇索引里分布得很散,每次都要读不同的页,缓存帮不上忙,代价就接近一次独立的点查。二级索引范围扫描返回一万行,就可能触发一万次这样的点查。

一次点查读几页:扇出 1168 的算法

先把一页能放多少条目算清楚。常见页大小是 16KB,页头、页尾、校验信息等元数据先扣掉 32 字节。假设主键是 8 字节的整数,指向孩子的页号是 6 字节,那么内部节点里一个「key 加孩子指针」占 14 字节。用本机 Node.js 按这个公式计算,一页能放 1168 个条目,也就是扇出约为 1168。

const page = 16384, header = 32, keySize = 8, ptrSize = 6;
const fanout = Math.floor((page - header) / (keySize + ptrSize));
console.log('扇出', fanout);
console.log('两层叶子', fanout ** 2);
console.log('三层叶子', fanout ** 3);
console.log('一千万行树高', 10000000 <= fanout ** 2 ? 2 : 3);

本机实际输出是:扇出 1168,两层叶子 1364224,三层叶子 1593413632,一千万行树高 3。三层叶子约 15.9 亿条,两层叶子约 136 万条。一千万行超过 136 万、远小于 15.9 亿,所以需要三层内部节点。这里的树高指内部节点的层数,最下面还有一层叶子。

把树高换成读页数:一次按主键的点查,从根开始往下走,每层读一页。三层内部节点加一个叶子页,冷缓存下大约读 4 页。实际运行时根节点几乎总在内存里,第二层也大概率被缓存,真正落到磁盘的往往只有一到两页。所以「一次点查读 4 页」是冷启动的上界,不是每次都付 4 次磁盘寻道。

这个数字也解释了索引的威力。一千万行如果逐行扫,最坏要读十万页量级;走 B+ 树只要沿着一条路径读三四页,差距是几个数量级。树高能压到 3,靠的是扇出 1168 这个大数字。如果换成二叉搜索树,一千万行树高约 24 层,一次点查就要读二十多页,磁盘上根本没法和多叉树比。

扇出会随 key 变长而下降。主键如果是 36 字节的字符串,一个条目占 42 字节,扇出降到 389 左右,同样一千万行可能要多一层。索引列越短,一页装的 key 越多,树越矮,这是「主键要短」的一个具体理由。

回表与覆盖索引:同样十行,读 40 页还是读 1 页

继续用十行结果举例。如果查询的列不在二级索引里,十行就要回表十次。按冷缓存、每次点查约 4 页估算,最坏是 40 页;如果这十行的主键恰好相邻,页可能被复用,实际会少很多。但如果按状态、按时间查,命中的十行主键往往分散,回表的页也很难复用。

覆盖索引(covering index)是让查询要用的列全部落在索引里,从而完全跳过回表。比如查询只要主键和状态,而索引正好是「状态加主键」,那么二级索引叶子已经包含全部所需数据,读一遍索引就能返回,不用再去聚簇索引。代价是索引变宽,写入要多维护一列。

普通二级索引

叶子只有索引列和主键。命中后要回表取其他列,返回行越多,随机读越多。适合结果集小、或者本来就要读整行的查询。

覆盖索引

叶子包含查询需要的全部列,不用回表。适合固定几种查询、列不多、能接受索引变宽和写入变慢的场景。

本机按同样的假设算过一笔账:十行结果、每次回表按 4 页算,最坏是 40 页;覆盖索引下十行只落在 1 个叶子页(按每页 100 行估算)。实际数据库有缓存和预读,数字不会这么整齐,但「回表次数乘上每次点查的页数」这个结构是对的。

console.log('十行回表最坏页数', 10 * 4);
console.log('覆盖索引十行约占叶子页', Math.ceil(10 / 100));

实际输出是:十行回表最坏页数 40,覆盖索引十行约占叶子页 1。这组数字不是为了证明覆盖索引一定快四十倍,而是说明成本模型:回表是按行乘上去的,覆盖索引则把「按行随机找」变成「按页顺序读」。

覆盖索引也有边界。查询一旦多要一列不在索引里的字段,覆盖就失效,优化器可能宁可直接全表扫描也不走这个索引。所以覆盖索引通常是为少数高频查询定制的,不是给所有查询都建一遍。索引列越多,页里能放的条目越少,树可能变高,写入也更贵。

页分裂:写入为什么会让树变胖

页分裂(page split)是 B+ 树在写入时绕不开的动作。叶子页装满以后,再插入一个 key,就要申请一个新页,把原来的条目大致对半分开,再把新页接进叶子链表、更新父节点的分隔 key。一次分裂会写新页、写旧页、写父页,写放大至少是原来的两三倍。

分裂还会留下空隙。对半分开意味着两个页都只填了一半左右,随机插入时页的平均填充率通常在六成到七成。填充率低,同样的数据就要占更多页;范围扫描要读的叶子页变多,缓存能装下的记录变少,查询和写入都会受影响。

插入顺序决定分裂形态。主键一直递增时,所有插入都落在最右边那个叶子页,它会被反复填满、分裂、再填满,左边的页却长期只填了一半。这样做的好处是分裂集中、页序连续;坏处是这个最右页成了写入热点,高并发下会成为锁争用的焦点。

随机主键则相反,插入分散到整棵树,分裂也分散,热点问题缓解,但页的物理顺序和主键顺序不再一致,范围扫描读到的页可能不连续。用随机字符串当主键还会让索引变大、树变高。时间有序的 UUID 是折中:既不完全随机,也不完全集中,很多系统用它来兼顾写入分散和范围扫描。

现象、原因与第一步排查

下面这些现象在「索引看起来建了,查询还是慢」的场景里出现频率很高。排查时先看执行计划里的扫描行数和实际读页,不要只看有没有索引。

现象真实原因第一步查什么
LIMIT 10 OFFSET 100000 越翻越慢OFFSET 要先扫过前十万行再丢弃,成本随偏移量线性增长执行计划扫描行数,能否改成按上一页主键续查
第一页很快,最后一页很慢偏移量不同,扫描行数不同,和 LIMIT 大小关系不大记录实际 OFFSET 与扫描行数,别只看接口耗时
按主键查一行很快,按状态查一行很慢二级索引命中后要回表,多了一次随机点查查询列是否都在索引里,回表了几次
建了索引还是走全表扫描选择率太低,或索引列被函数、模糊前缀破坏执行计划的访问方式和 key 列是否为空
范围查询比等值查询慢很多二级索引范围扫出大量主键,逐行回表造成随机读放大返回行数、回表次数、能否用覆盖索引
联合索引只用上了第一列不满足最左前缀,跳过某一列后无法继续用后面的列定位索引列顺序与查询条件是否对得上
插入越来越慢,索引文件越来越大页分裂和碎片让填充率下降,同样的数据占更多页主键是否随机、页填充率与索引实际大小
小表反而走了全表扫描优化器估算回表成本高于直接顺序扫全表统计信息是否过期,表实际行数与选择率

表里第一行和第三行最容易被误判。第一行看起来像「数据库深分页性能差」,实际是 OFFSET 的线性成本;第三行看起来像「状态字段没建索引」,实际可能是建了索引但回表太贵,优化器主动放弃。判断索引问题,先分清「扫了多少行」和「读了多少页」,再看这些页是顺序读还是随机读。

边界与代价:B+ 树索引不是万能的

第一个边界是选择率。选择率指查询条件能筛掉多少行。如果一千万行里要返回三百万行,走二级索引就要回表三百万次,优化器算完账通常直接全表扫描。索引适合「少量定位」,不适合「大部分都要」。反过来,如果条件命中的行极少,索引的收益最大。

第二个边界是表达式。索引是按列值有序存放的,一旦在列上套了函数,或者用前置通配符匹配,有序性就用不上了,只能逐行计算再比较。把函数移到常量一侧、把前缀匹配改写成范围条件,往往能让索引重新生效。这类改写不改变业务语义,只改变查询的形状。

第三个边界是写入成本。每个索引都是一棵额外的 B+ 树,插入要更新所有索引,删除要处理页合并,更新索引列等于删一条再插一条。索引越多,写入越慢,占用的空间越大,页分裂带来的碎片也越多。索引不是「多建几个总没坏处」,每一棵都要用真实的查询去换。

第四个边界是分页方式本身。深分页的正解通常不是加索引,而是改成游标分页:记住上一页最后一条的主键,下一页用「主键小于上一页最后一条」继续查。这样每页都从树里定位到起点,只读当前页需要的行,不再扫前面十万行。代价是不能随意跳到任意页码,产品上要做取舍。

最后一个边界是结构选型。B+ 树适合范围查询、排序和前缀匹配,因为叶子有序且连成链表。如果只有等值查询、完全不需要顺序,哈希索引的点查可以做到一次定位,但它不支持范围扫描和排序。下一篇讲哈希表时会看到,桶、冲突和扩容决定了它的强项和短板。

当天能做的练习

  1. 用本文的公式算扇出、两层叶子容量、三层叶子容量,再把页大小改成 8KB 重算一次,记录树高会不会从 3 变成 4,并解释原因。
  2. 按「每页 100 行」算 OFFSET 为 0、1000、10000、100000 时的扫描行数和页数,列成一张小表,再算 OFFSET 为 500000 时大约要读多少页。
  3. 假设十行结果每行都要回表,每次点查 4 页,算出最坏页数;再假设这十行的主键连续、能共用缓存,估算实际页数会降到多少,说明两种情况的差别。
  4. 写出三条查询:按主键查一行、按状态查十行、按状态查一万行。分别判断该不该走索引、要不要覆盖索引,并说明优化器可能怎样选。
  5. 把 LIMIT 10 OFFSET 100000 改写成基于上一页主键的续查写法,写出两条 SQL 并对比扫描行数。没有数据库就只做纸面推演,标注未实测。
环境说明:扇出、容量、树高、OFFSET 扫描行数与页数、回表页数估算,都是本机用 Node.js 24 按公式实际计算的结果,输出与文中一致。SQL 的执行计划与耗时未在本机实测,不同数据库的页大小、缓存策略、优化器规则会让实际页数不同。文中的「每页 100 行」只是为了演示取的整数,不是任何数据库的真实行宽。

小结与下一篇

三句话收一下:一次点查从根走到叶子,一千万行树高 3,冷缓存下约读 4 页;二级索引只存索引列和主键,取其他列要回表,回表按行乘成本,覆盖索引把这部分省掉;OFFSET 深分页慢在「先扫再丢」,改成按上一页主键续查才能把成本拉回常数级。

下一篇讲哈希表。B+ 树靠有序换来范围查询和排序,哈希表则放弃顺序,用桶和哈希函数把 key 直接映射到位置,等值查询可以做到平均常数时间。但冲突怎么处理、负载因子(已用桶数占总桶数的比例)到了多少要扩容、扩容时为什么所有元素都要重新分布,这些问题会决定哈希表在真实系统里的表现。今天先把「读几页」的成本感建立起来,下一篇会看到另一种完全不同的取舍。