前言

在数据库中，随着数据量增长，查询效率会急剧下降。
例如：

SELECT * FROM user WHERE id = 1;

如果没有索引，数据库只能进行全表扫描（Full Table Scan），逐行匹配数据，当数据达到百万级甚至千万级时，查询性能会显著下降。因此，数据库引入了索引机制。

索引的本质：

帮助数据库快速定位数据的数据结构。

1. 为什么需要索引

索引在数据库中扮演着“目录“的角色。想象一本没有目录的厚书，你要找某个知识点只能一页页翻，而有了目录，直接定位到章节即可。

具体来说，索引带来的好处有：

• 大幅提升查询速度：对于 WHERE、JOIN、ORDER BY、GROUP BY 等操作，索引能减少扫描的数据量，从全表 O(n) 降到 O(log n) 甚至更低。
• 减少磁盘 I/O：数据库数据存储在磁盘上，没有索引时可能产生大量随机 I/O；索引结构（如 B+ 树）能将随机 I/O 转为顺序 I/O，或大幅减少 I/O 次数。
• 唯一性约束：唯一索引可以保证表中某列（或列组合）的值不重复。
• 辅助排序与分组：索引本身已经有序，可以避免额外的 filesort 操作。

当然，索引也有代价：

• 占用额外的存储空间。
• 增、删、改数据时需要同步维护索引，降低写入性能。
• 不合理的索引可能被优化器忽略，甚至拖慢查询。
  因此，索引需要根据查询模式合理设计，并非越多越好。

2. 索引底层数据结构演化

2.1 二叉搜索数（BST）

BST的特点：

• 每个节点的左子树中，所有节点的值都小于该节点
• 每个节点的右子树中，所有节点的值都大于该节点
• 左右子树本身也是 BST
  这一规则保证了"左小右大"，使得每次比较都能排除一半的候选范围，所以BST的效率非常高。
  

但BST存在一个致命问题：
如果插入顺序是1、2、3、4、5，树就会变为：

这时查找数据只能全部遍历，复杂度变为O(n)，性能崩了。

2.2 平衡二叉树（AVL）

AVL 是第一种字平衡二叉搜索树，它规定任意节点左右子树高度差(平衡因子)不能超过1，从而实现树的平衡。在每次插入或删除操作后，会从受影响的节点向上回溯，检查平衡因子（左高 - 右高）。若平衡因子绝对值大于 1，则通过旋转操作恢复平衡：左旋、右旋、左右双旋、右左双旋。

AVL 的特点：

• 查询效率稳定：严格平衡使得树高保持在 O(log n)，查找、插入、删除均为 O(log n)。
• 适合读多写少的场景：因为维持平衡的旋转成本较高，频繁插入删除会导致多次旋转。
• 每个节点存储一个高度值或平衡因子，额外占用少量空间。

插入顺序：2/5/6/3/1/4

AVL虽然解决了 BST 的退化问题，但仍然是二叉树。当数据量巨大（千万级）时，树高约为 log₂(10⁷) ≈ 24 层，查询一个数据可能需要 24 次磁盘 I/O，每次 I/O 都很慢。数据库索引需要更“矮胖”的结构，以减少 I/O 次数。因此 AVL 并未被主流数据库采用为索引结构。

2.3 红黑树

红黑树也是一种自平衡二叉搜索树，但它不追求 AVL 那样的“绝对平衡”，而是保证从根到叶子的最长路径不超过最短路径的 2 倍，从而近似平衡。在每次- 插入或删除后，通过变色和旋转（左旋/右旋）来恢复规则。

红黑树的五条规则：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL 空节点）是黑色。
4. 红色节点的两个子节点必须是黑色（即不能有连续的两个红色节点）。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高一致）。

插入顺序：2/5/6/3/1/4

红黑树 vs AVL：

特性	AVL	红黑树
平衡性	严格（高度差 ≤1）	松散（最长路径≤2倍最短路径）
查询性能	更快（更矮）	稍慢（略高）
插入/删除性能	多次旋转，较慢	变色+少量旋转，较快
适用场景	读多写少	读写相当，如 Java HashMap、Linux CFS

为什么数据库不用红黑树？
红黑树仍然是二叉树，树高较高，I/O 次数多。此外，红黑树不擅长范围查询——需要中序遍历回溯，效率低。因此它只适用于内存中的数据结构（如 TreeMap、TreeSet），不适合磁盘索引。

2.4 Hash 表

Hash 表（散列表）是另一种常见的数据结构，通过哈希函数将键映射到数组中的某个位置，实现 O(1) 的等值查询。

Hash 索引的特点：

• 查询极快：只需一次哈希计算 + 一次定位，等值查询复杂度 O(1)。
• 不支持范围查询：哈希映射是随机的，数据在物理上无序，无法进行 < > BETWEEN 等操作。
• 哈希冲突：不同键计算出相同哈希值，需要通过拉链法、开放寻址法等解决，冲突多了性能下降。
• 不支持排序：无法利用索引做 ORDER BY。
• 无法利用前缀查找：对 LIKE 'abc%' 无效，因为哈希是对完整键值计算的。
  

2.5 B树

B 树也称 B- 树，全称为 多路平衡查找树，B+ 树是 B 树的一种变体。B 树和 B+ 树中的 B 是 Balanced（平衡）的意思。
目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构

B-树的特点：

• 每个节点既存索引键，也存完整数据
• 节点内键值有序排列
• 所有叶子节点在同一层，保持绝对平衡
• 一个节点可以有多个子节点，M阶B树，最多M个子节点
• 非叶子节点的键值将子树分隔开，遵循左小右大
  

查找过程：从根节点开始，每层做二分查找，一旦命中就立刻返回，不需要走到叶子节点。

2.6 B+ 数（❗Mysql使用）

MySQL 与 B+ 树没有直接关系，和 B+ 树有直接关系的是MySQL的默认存储引擎InnoDB，而 InnoDB 默认使用B+ Tree。除 InnoDB 外MySQL还支持其他存储引擎，如MyISAM。

B+ 树的特点：

• 所有数据存储在叶子结点，非叶子节点只存键值
• 叶子节点通过双向链表连接，范围查询效率极高
• 非叶子节点的键会在叶子节点中重复出现
• 树高通常只有3~4层，I/O 次数极少

查询过程：从根节点出发，递归向下经过内部节点，到达叶子节点完成查找。

B树与B+树的对比：

对比维度	B树	B+树
数据存储位置	所有节点存储数据	只有叶子节点存数据
非叶子节点	存键 + 数据	只存键，占用空间小
叶子节点链表	没有	双向链表连接
查找路径	命中即返回，路径不固定	必须到叶子节点，路径固定
范围查询	需要中序遍历，效率低	直接走链表，效率极高
等值查询	最好情况根节点命中，更快	固定走到叶子，稍慢
树的高度	相对较高	相对较矮
IO 次数	较多	较少
稳定性	不稳定，层数不同	稳定，都到叶子

为什么 InnoDB 选择 B+ 树？

1. 磁盘 I/O 更少：非叶子节点不存数据，一个磁盘块可存储大量键，分叉因子极大，树高通常 3~4 层，千万数据也只需 3~4 次 I/O。
2. 范围查询高效：叶子链表使得 BETWEEN、>、<、ORDER BY 等只需遍历叶子节点，无需回溯。
3. 全表扫描更友好：直接遍历叶子链表即可，相当于顺序读磁盘。
4. 数据存储稳定：所有数据都在叶子，查询任何记录的 I/O 次数相同，性能可预测。

3. InnoDB索引机制

前面介绍了 B+Tree 以及索引的数据结构，那么在 MySQL 中，索引到底是如何存储的？

在 MySQL 的 InnoDB 存储引擎中，索引并不是独立存在的，而是以 B+Tree 的形式组织数据，并且根据存储内容的不同，分为：

• 聚簇索引（Clustered Index）
• 二级索引（Secondary Index）

理解这两者的区别，是掌握 MySQL 索引底层原理的关键。

3.1 聚簇索引（主键索引）

聚簇索引是指数据和索引存储在一起，在InnoDB中，主键索引就是聚簇索引，它的叶子节点保存的不是地址，而是完整的数据行。

例如，创建如下表结构：

CREATE TABLE user(
	id INT PRIMARY KEY,
	name VARCHAR(50),
	age INT
);

假设user表中的数据有：

id	name	age
1	Tom	18
3	Jack	22
5	Alice	20
聚簇索引的B+ Tree结构就是：

聚簇索引具有以下特点：

1. 主键有序存储：
   因为B+ Tree 天然有序，所以执行语句

   SELECT *
   FROM user
   ORDER BY id;
   

   执行效率较高。

2. 查询速度快：
   执行参训语句：

   SELECT *
   FROM user
   WHERE id = 3;
   

   只需要一次 B+Tree 查找即可定位完整数据。
   时间复杂度为O(logN)。

注意：主键不能太大

因为二级索引叶子节点保存的是主键值，如果主键越大，不仅索引占用的空间越大，还会导致io越多，从而查询性能下降。

推荐采用自增长主键：BIGINT AUTO_INCREMENT，不推荐UUID。因为UUID 长度较大且无序，容易导致 B+Tree 页分裂，影响插入性能与索引效率。

3.2 二级索引（辅助索引）

除了主键外创建的索引都叫二级索引。

例如：在 user 表的 name 字段上，创建一个名为 idx_name 的 B+ 树索引。
sql语句如下：

CREATE INDEX idx_name
ON user(name);

此时idx_name的结构为：

此时，叶子节点保存的是(name, id)，而非(name, age)，因为真正的数据在聚簇索引中，二级索引只是记录主键值。如何获取数据？答案是回表查询。

3.3 回表查询

既然二级索引只保存主键值，那么查询完整数据时，还需要再查一次聚簇索引。这个过程就叫回表。

例如：

SELECT *
FROM user
WHERE name = 'Jack';

它背后的执行流程是：

• 第一步：先走二级索引，name = Jack，获取主键 id = 3
• 第二步：再走聚簇索引，id = 3，找完整数据。

这就是回表查询，比之主键索引查询，二级索引查询多查了一次B+ Tree ，所以二级索引查询通常比主键索引慢。

主键索引 VS 二级索引

对比项	主键索引（聚簇索引）	二级索引（辅助索引）
创建方式	定义 PRIMARY KEY 时自动创建	必须手动 CREATE INDEX
树结构	1 棵 B+ 树	每建一个索引，就多 1 棵独立 B+ 树
叶子节点存储	整行完整数据	(索引列值，主键 ID)
查询完整数据	直接读取，无需回表	需要回表查主键索引
一个表有多少个	只能有 1 个	可以有多个
增删改效率	只维护一棵树，相对快	每多一个索引，写入就更慢
占用空间	存储所有真实数据	只存索引列 + 主键，空间较小
适用场景	按主键查询、获取完整数据	按非主键字段（name/age/phone）查询

3.4 覆盖索引

有没有办法不回表？
如果查询字段都存在与索引中，那么就不需要回表。这就是覆盖索引。

假设已经建立了索引INDEX(name)，执行：

SELECT name
FROM user
WHERE name = 'Jack';

因为二级索引叶子节点本身存(name, id)，查询的字段name已经包含在索引中，所以不需要回表。
而执行：

SELECT name, age
FROM user
WHERE name = 'Jack';

由于age不在索引中，所以必须回表。
如果想减少io提升性能，那么建立联合索引INDEX(name, age)，也可以直接走覆盖索引，无需回表。

覆盖索引的应用场景有：

1. 统计数量

SELECT COUNT(name) FROM user WHERE name = 'Jack';

2. 范围查询

SELECT name FROM user WHERE name LIKE 'J%';

不需要回表，纯索引查询，性能很高。

二级索引 VS 覆盖索引

对比项	二级索引	覆盖索引
本质	一种索引结构	一种查询效果 / 优化状态
是否独立存在	是，独立的 B+ 树	不是独立索引，是二级索引的一种理想使用场景
叶子节点存储	(索引列, 主键ID)	依然是 (索引列, 主键ID) 或联合索引多存几个字段
查询必须回表？	必须回表（拿完整数据）	完全不回表
查询速度	较快（多一次回表 I/O）	极快（少一次 I/O）
满足条件	只要创建索引就成立	查询的所有字段都在索引里才成立
例子	INDEX(name)	SELECT name FROM user WHERE name='xxx'
核心作用	加速 WHERE 条件查找	避免回表，极致提升查询性能

4. 索引分类

从业务角度来看，MySQL 中常见索引有：

• 主键索引
• 唯一索引
• 普通索引
• 联合索引

4.1 主键索引

主键索引起到了唯一标识一条数据的作用，它的特点是唯一、不允许为NULL、一张表只能有一个。

例如：

CREATE TABLE user (
    id INT PRIMARY KEY
);
# 等价于
# PRIMARY KEY(id)

在 InnoDB 中： 主键索引就是聚簇索引。

4.2 唯一索引

唯一索引要求值必须唯一，但可以为NULL。

例如要求user表邮箱表唯一：

CREATE UNIQUE INDEX idx_email
ON user(email);

4.3 普通索引

普通索引是最基础的索引，它的唯一作用就是提高查询速度。它允许值重复，允许值为NULL。
例如：

CREATE INDEX idx_name
ON user(name);

适用于高频查询字段。

4.4 联合索引

联合索引即多列共同组成一个索引，联合索引并不等于覆盖索引，但联合索引更容易形成覆盖索引，从而减少回表查询。

例如：

INDEX(name, age, city)

这条语句底层排序规则是：

• 先按照name排序。
• name相同，再按age排序。
• age相同，再按city排序。

例如：

(Alice,18,Beijing)
(Alice,20,Shanghai)
(Bob,19,Hangzhou)

所以下面SQL能命中：

WHERE name = 'Alice'

也能命中：

WHERE name='Alice'
AND age=18

但：

WHERE age=18

❗通常无法命中。

原因是MySQL遵循最左前缀原则，即必须从最左边开始匹配。
例如索引(name, age, city)，可用name、(name, age)、(name, age, city)，不能直接age city (age, city)。详细讲解将在后续第五节展开。

结语

索引的本质，是一种帮助数据库快速定位数据的数据结构。

从最开始的 BST，到解决退化问题的 AVL、红黑树，再到最终适用于磁盘存储的 B+Tree，我们可以发现：数据库索引的设计核心，始终是在 查询效率、磁盘 I/O、范围检索、写入成本 之间寻找平衡。

而在 MySQL 的 InnoDB 中，索引并不只是一个“加速器”，它本身就是数据的组织方式：

• 主键索引（聚簇索引）决定数据如何存储
• 二级索引通过主键关联数据
• 回表查询影响查询成本
• 覆盖索引能够进一步减少 I/O 开销

但真正决定索引性能的，并不仅仅是“有没有索引”，而是：

索引是否建得合理，SQL 是否真正命中了索引。

很多线上慢查询问题，本质上不是数据库性能差，而是索引设计不合理、联合索引使用错误、或者索引发生了失效。

下一篇，我们将正式进入 MySQL 索引中最容易出问题、也是面试高频考点之一：

联合索引与最左前缀原则：为什么索引建了却不生效？