MySQL 索引实现结构详解

覆盖 B+Tree · Hash · Full-Text · R-Tree · 物理结构 · 使用策略 · 最左前缀 · 执行计划

总览 B+Tree Hash 全文索引 R-Tree InnoDB页结构 聚簇/非聚簇 索引类型 联合索引 横向对比 执行计划 使用策略
1
MySQL 索引全景总览
按数据结构 / 存储引擎 / 逻辑功能三维分类
MySQL 索引体系
🏗️ 按底层数据结构
B+ Tree（最主流）
InnoDB 主键
InnoDB 辅助索引
MyISAM 索引
Hash（Memory引擎）
Hash 索引
自适应 Hash
Inverted Index（全文）
Full-Text 倒排索引
R-Tree（空间）
Spatial 空间索引
🎯 按逻辑功能
类型关键字特点
主键索引PRIMARY KEY唯一+非空，InnoDB聚簇
唯一索引UNIQUE值唯一，允许NULL
普通索引INDEX / KEY无约束，最常用
联合索引INDEX(a,b,c)多列，最左前缀原则
全文索引FULLTEXT文本搜索，倒排表
空间索引SPATIAL地理空间，R-Tree
🗄️ 按存储方式
类型引擎说明
聚簇索引 InnoDB 数据与索引在同一 B+Tree，叶节点存完整行
非聚簇索引 MyISAM 索引文件(.MYI)与数据文件(.MYD)分离，叶节点存地址
辅助索引 InnoDB 叶节点存主键值，回表查询完整行
覆盖索引 均支持 查询列全在索引中，无需回表
2
B+ Tree 索引 —— 最核心结构
InnoDB / MyISAM 默认索引底层实现，支持范围查询与排序
📐 B+ Tree 核心特征
  • 🔹 多路平衡 — 每个节点可存 N 个键，减少树高，磁盘 IO 少
  • 🔹 所有数据在叶节点 — 内部节点只存键，不存数据
  • 🔹 叶节点双向链表 — 相邻叶节点互链，范围扫描无需回溯
  • 🔹 高扇出（Fan-out） — InnoDB 页 16KB，单节点约存 1000+ 键
  • 🔹 树高极低 — 千万行表，树高仅 3~4 层
  • 🔹 稳定 O(log n) — 查找/插入/删除均为对数复杂度
📊 B Tree vs B+ Tree 对比
特性B TreeB+ Tree
数据位置所有节点仅叶节点
叶节点链表❌✅ 双向链表
范围查询需中序遍历链表顺序扫
内节点空间存数据，占空间只存键，更紧凑
查询稳定性不稳定稳定（必到叶）
MySQL使用❌✅ 全面使用
🌳 B+ Tree 结构可视化（3层，order=4）
根节点（Root Node）— 内部节点，只存索引键
P₀
20
P₁
50
P₂
80
P₃
↙
↓
↓
↘
内部节点（Internal Node）— 引导查询方向
P
5
P
10
P
P
30
P
40
P
P
60
P
70
P
P
90
P
95
P
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
叶节点（Leaf Node）— 存储完整数据行（聚簇索引）或主键值（辅助索引），双向链表连接
1
3
5
→
7
9
10
→
20
25
28
→
30
35
40
→
50
55
60
→
65
70
75
→
80
85
88
→
90
95
99
∅
💡 叶节点双向链表：叶节点之间通过 prev/next 指针相连，执行范围查询（BETWEEN、>、<）时，找到起始叶节点后，直接顺着链表扫描，无需再回到根节点，极大提升范围扫描效率。
📄 InnoDB 数据页（16KB）内部布局
File Header (38B)
页号、LSN、页类型、校验和
Page Header (56B)
槽数量、最大事务ID、层级...
Infimum Record
本页最小虚拟记录（哨兵）
Supremum Record
本页最大虚拟记录（哨兵）
User Records（主体）
行记录按主键有序排列单向链表串联每行包含：变长字段长度列表 + NULL位图 + 记录头(5B) + 真实数据
Free Space
未使用空间，向下增长
Page Directory
稀疏槽（Slot），每个槽指向一组记录的最后一条，二分查找用
File Trailer (8B)
校验和，页完整性验证
📌 页目录（Page Directory）
每 4~8 条记录设一个「槽」，槽中存该组最后一条记录的偏移量。查找时先二分槽定位分组，再线性扫描组内记录，将 O(n) 降为 O(log n + 常数)。
📌 记录头（Record Header, 5字节）
包含：delete_mask（标记删除）、min_rec_mask（B+Tree最小记录标记）、n_owned（本槽拥有记录数）、heap_no（堆位置）、record_type（0普通/1非叶/2最小/3最大）、next_record（下条记录偏移）
📌 隐藏列（Implicit Columns）
InnoDB 自动追加：row_id（无主键时）、trx_id（事务ID，MVCC用）、roll_pointer（回滚指针，指向 undo log）
3
聚簇索引 vs 非聚簇索引
InnoDB聚簇索引 / InnoDB辅助索引回表 / MyISAM非聚簇索引 深度对比
🌀 InnoDB 聚簇索引（Clustered Index）
核心：数据即索引，索引即数据。 叶节点存储完整行记录，主键 B+Tree 的物理存储顺序 = 数据行的物理顺序。
根/内部节点 — 存主键键值
P
id=5
P
id=10
P
↓↓↓
叶节点 — 存完整行数据（所有列）
id=1
name: Alice
age: 25
addr: Beijing
trx_id | roll_ptr
id=3
name: Bob
age: 30
addr: Shanghai
trx_id | roll_ptr
🟢 优点：主键查询极快，范围查询连续IO
🔴 缺点：主键无序插入引发页分裂；辅助索引需回表
🔄 InnoDB 辅助索引（Secondary Index）+ 回表
辅助索引叶节点 只存索引列值 + 主键值，不存完整行。查询时先查辅助索引树找到主键，再用主键去聚簇索引查完整行（称为"回表"）。
① 用户查询 SELECT * FROM t WHERE name='Bob'
↓
② 在 name 辅助索引 B+Tree 中查找
叶节点找到：name='Bob' → id=3
↓ 回表（Back to Clustered Index）
③ 用 id=3 去聚簇索引 B+Tree 中再查一次
取到完整行数据
💡 覆盖索引（Covering Index）：若查询列全部在辅助索引中，则无需回表。
例：SELECT id, name FROM t WHERE name='Bob' — name索引含id，直接返回，EXPLAIN中 Extra 显示 Using index
🗂️ MyISAM 非聚簇索引（Non-Clustered Index）
MyISAM 的索引与数据完全分离存储：
· .MYD（MYData）— 存实际行数据
· .MYI（MYIndex）— 存 B+Tree 索引结构
主键索引与辅助索引的叶节点都存的是 数据行的物理地址（row pointer），而非主键值。
🟢 优点：无回表之分，主键/辅助索引查询路径相同
🔴 缺点：不支持事务/行锁，全表锁，无MVCC
MyISAM B+Tree 叶节点
id=1
ptr → 0x00F01A
(.MYD文件偏移量)
id=3
ptr → 0x00F08C
(.MYD文件偏移量)
↓ 通过地址直接访问 .MYD
数据文件 .MYD：完整行数据
4
Hash 索引
Memory 引擎默认 / InnoDB 自适应 Hash Index
⚡ Hash 索引结构
哈希桶（Hash Bucket）
bucket[0]NULL
bucket[1]→ 链
bucket[2]→ 链
bucket[3]空
bucket[4]→ 链
bucket[5]空
→
哈希冲突链（拉链法）
hash("Bob") → 0x4A2F → row_ptr
hash("Bobby") → 0x4A2F → row_ptr
↑ 哈希碰撞，链表挂载
查找过程：key → hash(key) → 取桶 → 遍历链表比较 → 返回 row_ptr
🔄 Hash vs B+Tree 关键差异
维度Hash 索引B+Tree 索引
等值查询O(1)O(log n)
范围查询不支持✅ 高效
排序不支持✅ 有序
前缀查询不支持✅ 支持
联合索引不支持部分列✅ 最左前缀
适用引擎MemoryInnoDB/MyISAM
⚠️ 自适应哈希索引（Adaptive Hash Index, AHI）
InnoDB 特有，由引擎自动管理，无法手动创建。当某些 B+Tree 索引页被频繁访问时，InnoDB 会在内存中为其建立 Hash 映射，使热点等值查询从 O(log n) 降为 O(1)。关闭：innodb_adaptive_hash_index=OFF
5
全文索引（Full-Text Index）— 倒排索引
MySQL 5.6+ InnoDB 支持，解决 LIKE '%xxx%' 全表扫描问题
📚 倒排索引（Inverted Index）结构
核心思想：词 → 文档列表（而非文档 → 词）。分词后建立词项到包含该词的文档行ID集合的映射。
词典（Dictionary）→ 倒排列表（Posting List）
MySQL
→
doc[1, 3, 7, 12, 45]
索引
→
doc[1, 2, 7, 9, 23, 45]
优化
→
doc[2, 3, 11, 23]
查询
→
doc[5, 7, 18, 45]
性能
→
doc[1, 4, 8, 23, 45]
🏗️ InnoDB 全文索引底层表
InnoDB 全文索引由 6张隐藏辅助表（FTS_DOC_ID 字段做 doc ID）组成：
FTS_INDEX_TABLE
词典+倒排列表（分片存储）
FTS_DOC_ID
文档ID映射（bigint）
FTS_DELETED
标记删除的doc IDs
FTS_BEING_DELETED
正在删除的doc IDs
FTS_CONFIG
索引配置信息
使用方式：
MATCH(col) AGAINST('keyword' IN BOOLEAN MODE)
支持 NATURAL LANGUAGE MODE（自然语言）和 BOOLEAN MODE（布尔操作 +/-/*）
6
R-Tree 空间索引（Spatial Index）
用于 GIS 地理信息查询，基于最小外包矩形（MBR）递归分割
🗺️ R-Tree 空间分割可视化
R1（根MBR）
R2（根MBR）
A
B
C
D
E
F
每个父节点是子节点的最小外包矩形（MBR），查询时剪枝不相交的矩形分支
📐 R-Tree 核心概念
概念说明
MBRMinimum Bounding Rectangle 最小外包矩形，每个节点存储其子节点的MBR
插入选择MBR面积增量最小的分支插入，必要时分裂
查询从根节点递归检查MBR是否与查询区域相交，剪枝不相交分支
分裂节点溢出时，使用二次分裂（Quadratic）或线性分裂算法
SQL示例：
CREATE SPATIAL INDEX idx_loc ON shops(location);
SELECT * FROM shops WHERE ST_Contains(region, location);
要求列类型为 GEOMETRY / POINT / POLYGON 等空间类型
7
按逻辑功能的索引类型详解
主键·唯一·普通·联合·前缀·全文·空间 全类型覆盖
🔑 主键索引（PRIMARY KEY）
• InnoDB：即聚簇索引，数据随主键排序
• 唯一 + 非空（NOT NULL）
• 每表只能有一个
• 无主键时：取第一个非空唯一索引；再无则自动生成 6B rowid
CREATE TABLE t (
  id INT PRIMARY KEY,
  name VARCHAR(50)
);
🔒 唯一索引（UNIQUE）
• 索引列值唯一（NULL 除外，多个NULL允许）
• 可多列组合唯一
• INSERT/UPDATE 时引擎强制校验唯一性
• B+Tree 结构，支持范围查询
CREATE UNIQUE INDEX
  idx_email
  ON users(email);
📋 普通索引（INDEX / KEY）
• 无唯一性约束，允许重复值
• 最常用，加速 WHERE / JOIN / ORDER BY
• B+Tree 结构
• 可针对高频查询列建立
CREATE INDEX idx_age
  ON users(age);

-- 或建表时
KEY idx_age (age)
✂️ 前缀索引（Prefix Index）
对 VARCHAR/TEXT/BLOB 等长文本列，只取前 N 个字符建索引，节省空间。
代价：无法用于覆盖索引，因为只存了前缀。 
CREATE INDEX idx_name
  ON users(name(10));
-- 只索引 name 的前10字符
最优前缀长度选择方式：
计算不同前缀长度的选择性（Selectivity = 唯一值数/总行数）： 
SELECT
  COUNT(DISTINCT LEFT(name, 5)) / COUNT(*),
  COUNT(DISTINCT LEFT(name, 8)) / COUNT(*),
  COUNT(DISTINCT LEFT(name, 10)) / COUNT(*)
FROM users;
-- 选择性接近完整列时即可
8
联合索引（Composite Index）与最左前缀原则
多列索引的存储结构、使用规则与索引跳跃扫描
🔗 联合索引 INDEX(a, b, c) 的 B+Tree 排序规则
联合索引先按 a 排序，a 相同再按 b 排序，b 相同再按 c 排序。叶节点存储 (a, b, c, 主键)。
联合索引 idx(a,b,c) 叶节点排列示例
行1
a=1, b=1, c=1
行2
a=1, b=1, c=3
行3
a=1, b=2, c=2
行4
a=2, b=1, c=5
行5
a=2, b=3, c=1
行6
a=3, b=1, c=4
📏 最左前缀原则（Leftmost Prefix）使用规则
查询条件是否使用索引使用的索引列说明
WHERE a=1✅ 全用a前缀匹配
WHERE a=1 AND b=2✅ 全用a, b连续前缀
WHERE a=1 AND b=2 AND c=3✅ 全用a, b, c全列匹配
WHERE a=1 AND c=3⚠️ 部分仅 ab断了，c无法使用
WHERE b=2❌ 不用无跳过最左列a
WHERE b=2 AND c=3❌ 不用无缺少最左列
WHERE a>1 AND b=2⚠️ 部分仅 aa范围查询后b失效
WHERE a=1 AND b>2 AND c=3⚠️ 部分a, bb范围查询后c失效
ORDER BY a, b✅ 可排序a, b无需filesort
WHERE a=1 ORDER BY b✅ 可排序a, ba等值+b排序
💡 索引跳跃扫描（Index Skip Scan，MySQL 8.0+）：当跳过最左列时，优化器可以枚举最左列的所有唯一值，分别进行索引扫描，在最左列基数（Cardinality）较低时有效。EXPLAIN 中体现为 Using index for skip scan。
9
各索引结构横向对比
性能特性、适用场景、局限性全面对比
特性 B+Tree Hash Full-Text R-Tree
底层结构 多路平衡树 哈希表+链表 倒排索引 矩形树
等值查询 O(log n) O(1) 不适用 不适用
范围查询 ✅ 高效 ❌ 不支持 ❌ 不支持 ❌ 不支持
排序/ORDER BY ✅ 天然有序 ❌ ❌ ❌
模糊搜索 仅前缀 LIKE 'x%' ❌ ✅ 全文分词 ❌
空间查询 ❌ ❌ ❌ ✅ MBR相交
联合索引 ✅ 最左前缀 整体hash ❌ ❌
覆盖索引 ✅ ❌ ❌ ❌
支持引擎 InnoDB/MyISAM Memory/InnoDB(AHI) InnoDB/MyISAM InnoDB/MyISAM
存储开销 中等 低 大 中等
📊 查询场景性能对比
等值查询速度（相对值）
Hash
95%
B+Tree
75%
Full-Text
不适用
R-Tree
不适用
范围查询速度（相对值）
B+Tree
90%
Hash
不支持
Full-Text
不支持
10
EXPLAIN 执行计划解读
判断索引是否被使用及使用质量的核心工具
📋 EXPLAIN 关键字段详解
字段含义重点关注值
type 访问类型（最重要） system→const→eq_ref→ref→range→index→ALL（全表扫）
从左到右性能递减，至少达到 range 级别
key 实际使用的索引名 NULL 表示未使用索引
key_len 使用的索引字节数 越大代表使用了更多索引列
rows 预估扫描行数 越小越好
Extra 附加信息 Using index 覆盖索引
Using where 回表过滤
Using filesort 内存排序（需优化）
Using temporary 临时表（需优化）
Using index condition ICP下推
possible_keys 可能使用的索引 与 key 不同时，说明优化器放弃了某些索引
🏎️ type 访问类型详解（性能从高到低）
system
表只有1行，系统表，最快
const
主键/唯一索引等值查询，最多1行，如 WHERE id=1
eq_ref
联接时，右表用主键/唯一索引，每次联接只读一行
ref
非唯一索引等值查询，可能返回多行
fulltext
使用 FULLTEXT 全文索引
ref_or_null
类似 ref，但多查一次NULL值
range
索引范围扫描，BETWEEN / > / < / IN 等
index
全索引扫描（非数据扫），比ALL快，但仍较慢
ALL
全表扫描，最差，表示无有效索引可用
11
索引失效场景 & 使用策略
哪些写法会导致索引失效，以及高效索引的设计原则
⚠️ 索引失效场景（必须规避）
失效原因示例
列上做函数运算WHERE YEAR(create_time)=2024
列上做隐式类型转换WHERE phone=13800138000（phone是字符串）
LIKE 前缀通配符WHERE name LIKE '%abc'
OR 有非索引列WHERE id=1 OR addr='北京'（addr无索引）
NOT IN / NOT EXISTS全表扫描替代
联合索引跳过最左列WHERE b=1 AND c=2（缺a）
范围查询后的列WHERE a>1 AND b=2（b失效）
NULL 值判断WHERE col IS NULL（有时可用，看情况）
使用 != / <>全表扫更快
✅ 高效索引设计原则
1. 选择性高的列优先建索引
选择性 = 唯一值数/总行数，越接近1越好。性别、状态等低基数列不适合单独建索引。
2. 覆盖索引优于回表
查询所需列尽量全放入索引，SELECT id, name WHERE name=? 优于 SELECT *，Extra 显示 Using index。
3. 联合索引列顺序：等值查询列靠前，范围列靠后
INDEX(status, age, create_time) 适合 WHERE status=1 AND age>18
4. 主键用自增整型（AUTO_INCREMENT）
避免随机UUID造成页分裂，保持 B+Tree 叶节点的顺序插入。
5. 控制索引数量
每个索引都会增加写入开销（INSERT/UPDATE/DELETE 都需维护索引），建议单表不超过 5~6 个索引。
🚀 索引条件下推（Index Condition Pushdown, ICP）— MySQL 5.6+
Without ICP（旧版本）：
引擎层根据索引找到主键 → 回表取完整行 → 交给 Server 层过滤条件
问题：很多回表是无效的
Storage Engine：索引扫描 → 取主键
↓ 每条都回表
Storage Engine：回表取完整行
↓ 大量IO
Server Layer：再过滤 WHERE 其他条件
With ICP（5.6+）：
引擎层在索引中就能判断 WHERE 的其他条件 → 不满足的不回表 → 减少回表次数
EXPLAIN Extra 显示 Using index condition
Storage Engine：索引扫描 + 在引擎层过滤其他索引列条件
↓ 只对通过条件的行回表
Storage Engine：回表（行数大幅减少）
↓ IO显著降低
Server Layer：最终结果集
🔀 MRR（Multi-Range Read Optimization）— 减少随机IO
原理：回表时不按索引顺序一条一条取，而是先把主键收集起来并按主键排序，再按顺序访问聚簇索引页，把随机IO变为顺序IO。
EXPLAIN Extra 显示 Using MRR 
-- 启用/禁用 MRR
SET optimizer_switch =
  'mrr=on,mrr_cost_based=off';

-- read_rnd_buffer_size 控制排序缓冲区
SET read_rnd_buffer_size = 262144;
MySQL 索引实现结构详解 · 涵盖 B+Tree / Hash / Full-Text / R-Tree / 聚簇索引 / 联合索引 / EXPLAIN / ICP / MRR