为什么需要索引
- 减少扫描量：存储引擎直接定位到目标行，不再全表扫描
- 避免临时表排序：B+ 树天然有序，ORDER BY 可直接走索引
- 随机 I/O 转顺序 I/O：范围查询时顺着叶子节点链表扫描
可用做索引的数据结构演进
线性查找 / 二分查找
- 数组 / 链表：O(n)，数据量大时不可用
- 二分查找：O(log n)，但要求有序数组，插入删除代价大
二叉搜索树 / AVL
- 解决了”二分查找要求静态有序”的问题
- 极端情况下退化为链表（如按序插入 1,2,3,4,5），需要 AVL 等平衡树来保持高度
B 树
- 每个节点存多条数据 + 多个指针（解决”磁盘块利用率低”的问题）
- 磁盘按块读写（一般 SSD 4K），多数据节点能减少 I/O 次数
- 缺点：范围查询需要不断回到上层找下一个范围，B 树所有节点都存数据，导致叶子节点的数据是分散的
B+ 树（InnoDB 实际采用）
B+ 树对 B 树的关键改进：
- 只叶子节点存数据，非叶节点只存索引——同样大小的页能装更多索引项，树更矮
- 叶子节点之间用链表串联——范围查询只需在叶子节点顺序扫描
- 数据集中在叶子节点——磁盘预读（read-ahead）命中率更高
InnoDB 一般使用 2~4 层 B+ 树，根节点常驻内存，3 次磁盘 I/O 即可命中任何数据。
Hash
- 优点：等值查询一次定位，O(1)
- 缺点：
- 不能范围查询（Hash 无序）
- 不能利用联合索引的部分列（整列一起算 Hash）
- 极端情况 Hash 冲突严重时退化
聚簇索引 vs 非聚簇索引
| 维度 | InnoDB（聚簇） | MyISAM（非聚簇） |
|---|---|---|
| 主键索引叶子节点 | 存完整数据行 | 存数据行地址 |
| 辅助索引叶子节点 | 存主键值 | 存数据行地址 |
| 数据文件 | 与主键索引合一 | 独立存储 |
| 辅助索引查询 | 二次查找（回表） | 一次定位地址 |
| 聚簇索引数量 | 只能 1 个 | 无此概念 |
InnoDB 必须有聚簇索引，规则：
- 有主键 → 主键就是聚簇索引
- 没有主键 → 第一个声明的唯一非空索引
- 都不满足 → InnoDB 内部生成 6 字节的 ROW_ID 隐藏主键
“回表”是什么？ 当你用辅助索引（比如 idx_name）查询时，InnoDB 先在辅助索引树上找到主键值，再回到聚簇索引树上按主键查完整数据——这就是”两次 B+ 树查找”，也叫回表。
💡 优化回表：
SELECT id, name FROM user WHERE name = 'a'这种查询，如果辅助索引已经”覆盖”了需要的所有列（id 是主键，name 是索引列），不需要回表——这就是覆盖索引（Covering Index）的精髓。
Btree 索引的 4 大使用限制
- 不从最左前缀开始查询，无法使用索引
WHERE name = 'a' AND age = 10命中联合索引(name, age)WHERE age = 10不命中（跳过了 name）
- 不能跳过索引中的列
WHERE name = 'a' AND addr = '北京'只用到了 name，addr 走全表扫描
- NOT IN /
<>操作无法使用索引 - 范围查询（
>、<、BETWEEN）右边的列无法使用索引WHERE name = 'a' AND age > 10 AND addr = '北京'只用到 name + age 范围
下一篇会讲 InnoDB 并发的核心：锁机制（全局锁/表级锁/MDL/行级锁）+ MVCC + 间隙锁与幻读的解决。