MySQL 索引数据结构与算法

MySQL 索引数据结构与算法

一、索引的本质

索引是帮助 MySQL 高效获取数据的排好序的数据结构，通过优化查找路径提升查询效率。类比书的目录——无需逐页翻阅即可快速定位。

二、索引数据结构对比

1. B-Tree

[20 | 40] / | \ [5|10] [25|30] [50|60]

• 所有叶节点深度相同
• 节点内索引元素不重复
• 数据从左到右递增排列
• 叶节点指针为空

2. B+Tree（MySQL 主力索引）

[20 | 40] ← 非叶子节点：仅索引，不存数据 / | \ [5|10] → [25|30] → [50|60] ← 叶子节点：存完整数据，双向链表 data data data

与 B-Tree 的核心区别：

3. Hash 表

key → hash(key) → 桶定位 → 数据

三、B+Tree 深度解析

1. 为什么 B+Tree 比二叉树更适合磁盘存储

二叉搜索树： 100 高度 = 节点数 → 磁盘 IO 次数多 / \ 50 200 / \ 30 70 每层一个节点 → 一次磁盘 IO → 效率低 B+Tree： [100 | 200 | 300] 高度 = 3~4 层，每层存几百个索引 / | | \ [叶子叶子叶子叶子叶子叶子] 一个节点 = 一个磁盘页（16KB）→ IO 次数少

核心思想：让每个节点大小等于磁盘一页（16KB），一次 IO 读入大量索引项，从而将树高度控制在 3~4 层，百万级数据仅需 2~4 次 IO。

2. 叶子节点链表的作用

[1|data] → [3|data] → [5|data] → [7|data] → [9|data] ↑ ↓ └──────────── 双向链表遍历 ←────────────────┘

• 等值查询：从根走 B+Tree 到叶子
• 范围查询：定位起点后，沿链表顺序遍历，无需回到非叶子节点 —— 这是 B+Tree 相比 B-Tree 的最大优势

四、存储引擎的索引实现

1. MyISAM（非聚集索引）

.MYI 索引文件 .MYD 数据文件 ┌──────────┐ ┌──────────┐ │ 索引 + 指针 │ ──────→ │ 完整数据行 │ └──────────┘ └──────────┘

• 索引与数据分离存储
• 叶子节点存的是数据物理地址
• 主键索引和二级索引结构相同

2. InnoDB（聚集索引）

主键索引（聚集索引） 二级索引（非主键索引） ┌─────────────────┐ ┌───────────────┐ │ 主键 + 完整数据行 │ │ 索引列 + 主键值 │ │ （数据即索引） │ │ （不存完整数据） │ └─────────────────┘ └───────┬───────┘ ↑ │ └─────── 回表查询 ←─────────────────┘

核心特点：

• 表数据文件本身就是按 B+Tree 组织的索引结构
• 聚集索引叶子节点存完整数据记录
• 二级索引叶子节点只存主键值，查到后还需回表取完整数据

两个关键问题：

Q1：为什么 InnoDB 表建议必须有主键，且推荐整型自增？

• InnoDB 用主键组织 B+Tree，无主键则自动选唯一键，都没有则生成隐藏 rowid（6 字节，无业务意义）
• 整型：比大小快，占用空间小（4/8 字节），UUID 字符串长且无序
• 自增：新数据永远追加到最右叶子，避免页分裂和索引重建，写入效率最高

Q2：为什么二级索引叶子节点存主键值而不是数据地址？

• 数据一致性：数据移动（页分裂）时，只需维护主键索引，二级索引无需更新
• 节省空间：避免每条记录在多个索引中重复存储完整数据

五、联合索引与最左前缀

联合索引结构示例（(a, b, c)联合索引）

B+Tree 按 (a, b, c) 字典序排列： (1,1,1) → (1,2,2) → (1,2,3) → (2,1,1) → (2,3,4) → (3,1,2) 先按 a 排 → a 相同时按 b 排 → b 相同时按 c 排

最左前缀原理：

本质原因：B+Tree 按联合索引从左到右排序，跳过左边就无法利用有序性定位。

总结