MySQL / 系统课时

理解 B+Tree 搜索与回表

理解 B+Tree 搜索与回表

索引命中并不意味着一次查找就结束。本课从 InnoDB 的 B+Tree 定位过程出发,跟踪等值查询、范围查询以及二级索引命中后的数据读取路径,并据此判断一次查询是否需要回表。

学习目标

  • 说明等值查找与范围查找如何沿 B+Tree 定位叶子记录
  • 区分聚簇索引与二级索引叶子节点保存的内容
  • 根据查询列判断是否发生回表,以及覆盖索引何时能够避免回表

从 B+Tree 定位叶子记录

InnoDB 的索引使用 B+Tree 组织有序键值。查找从根页开始,根据目标键落入的区间选择子页,经过若干内部页后到达叶子页。树高通常较低,因此定位单个键通常只需要访问少量索引页。

等值查询到达目标叶子页后即可确定匹配记录;范围查询则先定位范围下界,再沿有序叶子页继续扫描,直到遇到超过上界的键。因此范围越宽,需要检查的叶子记录通常越多。

B+Tree 搜索、二级索引与回表路径

二级索引为什么还要回表

InnoDB 表的主键索引同时是聚簇索引,它的叶子记录保存完整行。普通二级索引的叶子记录保存二级索引键,并携带对应行的主键值,而不会再复制整行数据。

访问对象 叶子记录主要保存内容 能否直接取得完整行
主键聚簇索引 主键与完整行 可以
二级索引 二级索引键与主键值 通常不可以

下面建立一个最小示例,强制使用 idx_city,观察同一个过滤条件在查询不同列时的区别。

sql
DROP TABLE IF EXISTS demo_users;

CREATE TABLE demo_users (
    id BIGINT PRIMARY KEY,
    email VARCHAR(128) NOT NULL,
    city VARCHAR(32) NOT NULL,
    display_name VARCHAR(64) NOT NULL,
    KEY idx_city (city)
) ENGINE = InnoDB;

INSERT INTO demo_users (id, email, city, display_name) VALUES
    (1, 'a@example.com', 'Shanghai', 'Alice'),
    (2, 'b@example.com', 'Shanghai', 'Bob'),
    (3, 'c@example.com', 'Beijing', 'Carol'),
    (4, 'd@example.com', 'Shenzhen', 'David');

-- 非覆盖查询:display_name 不在二级索引中,需要继续访问聚簇索引
EXPLAIN
SELECT id, display_name
FROM demo_users FORCE INDEX (idx_city)
WHERE city = 'Shanghai';

-- 覆盖查询:city 与二级索引叶子中的主键 id 都可直接取得
EXPLAIN
SELECT id, city
FROM demo_users FORCE INDEX (idx_city)
WHERE city = 'Shanghai';

预期结果

text
第一条 EXPLAIN:key 为 idx_city。二级索引能够找到 city 和主键 id,但 display_name 不在该索引中,因此执行阶段还需要按 id 读取聚簇索引记录。
第二条 EXPLAIN:key 为 idx_city,Extra 中可看到 Using index。查询只需要 city 和隐含保存于二级索引叶子中的主键 id,可以直接由索引返回。

EXPLAIN 中的行数估计可能随统计信息变化,但两条查询是否覆盖索引的差异不会因此改变。

回表次数为什么会影响成本

如果二级索引只匹配一两行,额外读取聚簇索引的代价通常很小。问题出现在低选择性条件或较宽范围上:二级索引扫描得到大量主键后,还要继续读取大量聚簇索引记录,随机访问和页面读取成本都会累积。

例如查询 city = 'Shanghai' 时,如果表中大部分记录都属于 Shanghai,即使存在 idx_city,通过二级索引找到大量主键再逐行回表,也可能比顺序扫描更贵。优化器因此不会因为 WHERE 条件存在索引就必然选择该索引。

范围查询同样如此。对于 city >= 'Beijing' AND city < 'Shenzhen',执行器先在 idx_city 中定位下界,再连续扫描范围内的索引记录;如果还要读取 display_name,每个满足条件的主键都可能产生后续的聚簇索引访问。

用覆盖索引消除必要的回表

所谓覆盖索引,不是一种独立索引类型,而是当前查询需要的列恰好都能从某个索引中取得。前面的 SELECT id, city 就已经被 idx_city 覆盖,因为 InnoDB 二级索引叶子中同时保存了主键 id。

如果高频查询固定为按城市取得名称,可以考虑把名称加入索引,例如 (city, display_name)。这样能够减少回表,但索引本身会变宽,写入、页分裂、缓存占用和维护成本也会增加,因此不能为了消除所有回表而无限扩展索引列。

判断一次查询的访问成本时,应同时问三个问题:索引能够把候选记录缩小到多少行、每个候选记录是否需要回表、最终返回的列是否值得通过覆盖索引优化。少量回表通常无需处理,大量扫描再大量回表才是更值得关注的信号。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

理解 B+Tree 搜索与回表

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通