> For the complete documentation index, see [llms.txt](https://yunzhao.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yunzhao.gitbook.io/notes/database/mysql/indexing.md).

# Indexing

## 前言

索引的目的是为了提高数据的查询效率。

但是索引不是一定能提升效率，比如

* 数据量较小，如果有回表操作，那么用索引的效率可能更低。
* 字段的可选值很少，且分布较均匀，比如性别。注意可选值少还不够，还需要分布较均匀，比如有个字段只有 1，0 取值，1 有 一千万条，0 有十条，那么当这个字段建了索引，查询 0 的时候也会比较快。

索引从功能上看主要有四种：

* **普通索引**，没有任何约束，主要用于提高查询效率。
* **唯一索引**，在普通索引基础上增加了唯一性约束，一张表可以有多个。
* **主键索引**，在唯一索引的基础上增加了非空约束，一张表只能有一个。
* **全文索引**，用的不多，MySQL 自带的全文索引仅支持英文。

{% hint style="info" %}
**普通索引和唯一索引的效率问题。**\
原理上，唯一索引由于增加了唯一性约束，找到了关键字会停止检索。而普通索引还会往下继续检索，效率在理论上会第一点。\
但是这点差别可以忽略不计，原因是，根据[数据库存储方式](/notes/database/mysql/storage.md)，InnoDB 会把整个数据页加载到内存中，一个页中可能存在上千条记录，普通所以仅仅是在内存中多几次判断下一条记录，这点时间可以忽略不计。
{% endhint %}

从物理实现上有两种：

* **聚集索引**，按照主键的顺序存储数据，一张表只能一个，叶子节点存储了数据记录。
* **非聚集索引**，也叫二级索引，一张表可以有多个，叶子节点存储的是数据位置。

按照字段个数，可以分为**单一索引**和**联合索引**，联合索引注意字段顺序，有**最左匹配原则**。

## 常见索引数据结构

* [Hash 表](/notes/computer-science/algorithm/hash-table.md)：本质是**数组+链表**的数据结构。
  * **缺点**：做区间查询速度很慢。
  * **适用场景**：只有等值查询的情况。比如 Memcached 、Lucene 等。
* 有序数组：等值查询和范围查询都很快。等值查询用用二分查找，时间复杂度`O(log(N))`。范围查询先用等值查询找到第一个，然后往后遍历。
  * **缺点**：插入数据效率很低。
  * **适用场景**：静态数据，比如 2015年上海市的人口信息。
* [平衡二叉查找树](/notes/computer-science/algorithm/tree.md#ping-heng-er-cha-cha-zhao-shu)
* [B 数](/notes/computer-science/algorithm/tree.md#b-shu)
* [B+ 树](/notes/computer-science/algorithm/tree.md#b-shu-1)
* [跳表](/notes/computer-science/algorithm/skip-list.md)
* LSM 树

MySQL 中的 Memory 存储引擎支持 Hash 存储；另外 MySQL 的 InnoDB 有一个自适应 Hash 索引，当某个索引使用非常频繁时，会在 B+ 树的基础上再创建一个 Hash 索引。不过 Hash 索引相对于 B+ 树有一些缺点：

* 不支持范围查询。
* 不支持联合索引的最左匹配原则，因为 hash 函数对于输入的一点微小变化都很敏感。
* 不支持 ORDER BY 排序。
* 不支持 LIKE 'XX%'。

## 最佳实践

### 什么时候创建索引

* 字段数值有唯一限制，唯一索引和主键索引都能起到唯一性的约束。
* 作为 WHERE 查询条件的字段，尤其表较大时，包括 SELECT、UPDATE、DELETE、JOIN。
* 频繁作为 GROUP BY 和 ORDER BY 的字段。
* DISTINCT 字段。
* 多表 JOIN 时，用于连接的字段。不过，连接表尽量不要超过 3 张。

对于同时存在 GOURP BY 和 ORDER BY 的语句，如：`GROUP BY a ORDER BY b`

* 若对 a，b 分别创建单列索引，则只有一个会生效。
* 创建（b, a）联合索引没有（a, b）联合索引效率高，因为先进行 GROUP BY。

### 什么时候不创建索引

* 非查询条件的字段，查询条件指的是 WHERE、GROUP BY、ORDER BY、DISTINCT。
* 数据量较小。
* 字段中有大量重复数据，且分布较均匀。
* 频繁更新的字段，因为更新时也会更新索引。

### 什么时候索引失效

* 索引进行了表达式计算：`WHERE id + 1 = 9001` => `WHERE id = 9000`
* 索引进行了函数计算：`WHERE SUBSTRING(a, 1, 3) = 'abc'` => `WHERE a LIKE 'abc%'`
* OR 条件中有一个列没有索引，那么其他索引列也会失效。如 WHERE a = 1 OR b = 2，a 有索引，b 没有，那么 a 的索引会失效。
* LIKE 不能以 \`%\` 开头。
* 索引列与 NULL 或 NOT NULL 判断时。

## MySQL 索引

### 自增主键

自增主键指插入记录时，若不指定主键值，则会获取当前主键值并加 1 作为下一条主键的值。通过 `NOT NULL PRIMARY KEY AUTO_INCREMENT`定义

**优点**：插入数据是递增的，主键索引不会发生页分裂。且整型占用空间少，二级索引占用的空间也少。

### 索引重建

索引可能因为删除、页分裂等情况，导致数据空洞，重建索引会把数据按照顺序插入，页面利用率就高。

若需要重建索引，下面方法是否可行？

```sql
alter table T drop index k;
alter table T add index(k);

alter table T drop primary key;
alter table T add primary key(id);
```

重建索引 k 是合理的。但是重建主键索引不合理，删除、创建主键都会重建整个表，所以前面的重建 k 就白做了。可以使用`alter table T engine=InnoDB`替代。

### 索引覆盖

若查询需要的结果已经包含在二级索引里面，不需要回表，称为索引覆盖。是一个常用的性能优化手段。

### 最左匹配

最左匹配可以是联合索引的最左边的 N 个字段，也可以是字符串索引的最左 M 个字符。

联合索引的顺序考虑：

* 如果能够通过调整顺序，减少一个索引，那么应该使用这个顺序。比如已经有 (a,b) 索引，就不需要单独的 a 索引了。
* 空间原则，比如 name 和 age 两个字段，name 长度大于 age，那么应该创建 (name,age) 和 (age)，而不是 (age,name) 和 (name)。

### 索引下推

MySQL 5.6 引入索引下推优化（index condition pushdown），可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录。比如下面语句：

```sql
mysql> select * from tuser where name like '张 %' and age=10 and ismale=1;
```

在 5.6 之前需要回表四次：

![](/files/-LeGjCqHZ0TvdbEEFFjJ)

在 5.6 仅需回表两次：

![](/files/-LeGjLkpxTdVtYLa3Bh7)