常常由于索引非常庞大不能完全存放在内存中，所以数据库中的索引是一个单独的、存储在磁盘上的数据库结构，包含着对数据表里所有记录的引用指针。使用索引可以快速找出某个或多个列中有一特定值的行，所有 MySQL 列类型都可以被索引，对相关列使用索引能够显著减少查询时间，提高查询效率。

索引是在存储引擎中实现的，因此，每种存储引擎的索引都不一定完全相同，并且每种存储引擎也不一定支持所有索引类型。MySQL 中索引的存储类型有两种，即BTREE和HASH，具体和表的存储引擎相关。MyISAM和InnoDB存储引擎支持BTREE索引；MEMORY/HEAP存储引擎可以支持HASH和BTREE索引

👍 使用索引的优点主要有以下几点：

通过过创建唯一索引，可以保证数据库表中每一行数据的唯一性
可以大大加快数据的查询速度
在实现数据的参考完整性方面，可以加速表和表之间的连接
在使用分组和排序子句进行数据查询时，也可以显著减少查询中分组和排序的时间

😣 增加索引也有许多不利的方面，主要表现在如下几点：

创建索引和维护索引要耗费时间，并且随着数据量的增加所耗费的时间也会增加
索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果有大量的索引，索引文件可能比数据文件更快达到最大文件尺寸
当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

¶索引的常见模型

数据库中索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，不同的索引模型对数据库的读写效率有不同影响。当前数据库中存在三种常见的索引模型：哈希表、有序数组和搜索树

¶哈希表索引模型

哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。

假设，当前数据库系统中维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

图中， User2 和 User4 根据身份证号算出来的值都是 N，通过链地址法解决哈希冲突。

❓ 如果这时候你要查 ID_card_n2 对应的名字，处理步骤如下:
1️⃣ 首先，将 ID_card_n2 通过哈希函数算出 N；
2️⃣ 然后，按顺序遍历，找到 User2。

🎶 需要注意的是，图中四个 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

如果现在要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户，就必须将整个表全部扫描一遍。

📓 哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

¶有序数组索引模型

有序数组在等值查询和范围查询场景中的性能就都非常优秀

还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示：

假设身份证号没有重复，数组就是按照身份证号递增的顺序保存的。这时候如果如果要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 $O(log(N))$

同时很显然，这个索引结构支持范围查询。你要查身份证号在[ID_card_X, ID_card_Y]区间的 User，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），然后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，如此就能快速做到区间查询

如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，往有序数组中间插入一个记录，为了继续维持有序数组的特性就必须得挪动后面所有的记录。因此有序数组整体而言，对查询操作支持好，但是对增删操作支持较差。

:notesbook: 有序数组索引只适用于静态存储引擎，适用于为那种不会再修改的数据简历索引。

¶搜索树索引模型

二叉搜索树是一种经典的搜索树索引模型，不仅很好的继承了有序数组中的优点，而且有效的解决了有序数组对中增删操作支持较差的弊端。

还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示：

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照UserA -> UserC -> UserF -> User2这个路径得到。这个时间复杂度是 $O(log(N))$

为了维持$O(log(N))$的查询复杂度，就需要保持这棵树是平衡二叉树。为了做这个保证，更新操作的时间复杂度也将变成$O(log(N))$

树可以有二叉，也可以有多叉。多叉树就是每个节点有多个子节点，子节点之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是：索引不止存在内存中，还要写到磁盘上，因此就需要考虑二叉树结构对磁盘的读取性能

对于一棵有 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一行可能需要 20 个 10 ms 的时间，这样的查询其实非常缓慢。为了让一个查询尽量读取磁盘数量更少，就必须让查询过程访问更少的数据块。那么，搜索树模型整体结构就不应该使用二叉树，而是要使用「 N 叉树」，N 取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候就可以存储非常多的数据。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，广泛应用在数据库引擎中。

不管是哈希还是有序数组，或者 N 叉树，它们都是不断迭代、不断优化的产物或者解决方案。数据库技术发展到今天，跳表、LSM 树等数据结构也被用于引擎设设计。

¶InnDB 的索引模型

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称索引组织表。具体实现中，InnoDB 使用了 B+ 树索引模型，最终数据都是存储在 B+ 树中，每一个索引在 InnoDB 里面对应一颗 B+ 树。

假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。这个表的建表语句是：

mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k)
)engine=InnoDB;

表中 R1~R5 的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下。

从上图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）
非主键索引的叶子节点存的是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）

❓ 基于主键索引和普通索引的查询有什么区别？

如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树
如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

也就是说，非主键索引的查询需要多扫描一颗索引树

¶索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。
更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。

除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。与分裂对应的就是合并操作，当相邻两个页由于删除了数据，会将数据页做合并。

基于上面的索引维护过程，下面讨论一个案例：

在一些建表规范里面有这样的要求：要求建表语句里一定要有自增主键.事无绝对，那么到底哪些场景下应该使用自增主键，而哪些场景下不应该使用自增主键？

自增主键是指自增列上定义的主键，在键表语句中一般是这么定义的：NOT NULL PRIMARY KEY AUTO_INCREMENT。对具有自增主键的表中插入数据时，可以不指定 ID 对值，系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值。

也就是说，自增主键的插入数据模式，正符合了前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂；而如果业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。

除了考虑性能外，我们还可以从存储空间的角度来看。假设表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？

由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节.显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。

❓ 有没有什么场景适合用业务字段直接做主键的呢？

答案是有的，比如，有些业务的场景需求是这样的：只有一个索引并且该索引必须是唯一索引。也就是典型的 KV 场景适合使用业务字段作为主键，由于没有其他索引，所以不用考虑其他索引的叶子节点大小的问题。

这时候我们就要优先考虑上一段提到的「尽量使用主键查询」原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

❓ 对于上面例子中的 InnoDB 表 T，如果你要重建索引 k，你的两个 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 的做法是合理的，可以达到省空间的目的。但是，重建主键的过程不合理。不论是删除主键还是创建主键，都会将整个表重建。所以连着执行这两个语句的话，第一个语句就白做了。可以用这个语句代替： alter table T engine=InnoDB

¶索引种类

了解了索引模型后，在 MySQL 中的索引可以分为以下几类：

普通索引和唯一索引
单列索引和组合索引
全文索引
空间索引

¶覆盖索引

某表 T 的创建语句如下，试问select * from T where k between 3 and 5,需要执行几次树的搜索操作，会扫描多少行？

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

⛵ 这条 SQL 查询语句的执行流程如下：

在 k 索引树上找到 k=3 的记录，取得 ID = 300
再到 ID 索引树查到 ID=300 对应的 R3;
在 k 索引树取下一个值 k=5，取得 ID=500；
再回到 ID 索引树查到 ID=500 对应的 R4；
在 k 索引树取下一个值 k=6，不满足条件，循环结束

在这个过程中，回到主键索引树搜索的过程，称之为回表。可以看到，这个查询过程读了 k 索引树的 3 条记录（步骤 1、3 和 5），回表了两次（步骤 2 和 4）

❓ 回表操作必然是耗时的，那么是否可以经过索引优化，避免回表过程尼？

如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经「覆盖了」我们的查询需求，我们称为覆盖索引

🎶 需要注意的是，在引擎内部使用覆盖索引在索引 k 上其实读了三个记录，R3~R5（对应的索引 k 上的记录项），但是对于 MySQL 的 Server 层来说，它就是找引擎拿到了两条记录，因此 MySQL 认为扫描行数是 2。

❓ 在一个市民信息表上，是否有必要将身份证号和名字建立联合索引？

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

身份证号是市民的唯一标识。也就是说，如果有根据身份证号查询市民信息的需求，我们只要在身份证号字段上建立索引就够了。而再建立一个（身份证号、姓名）的联合索引，就会造成浪费空间.

但是，如果现在有一个高频请求，要根据市民的身份证号查询他的姓名，这个联合索引就有意义了。它可以在这个高频请求上用到覆盖索引，不再需要回表查整行记录，减少语句的执行时间。

¶最左前缀匹配原则

如果为每一种查询都设计一个索引，索引是不是太多了。如果我现在要按照市民的身份证号去查他的家庭地址呢？虽然这个查询需求在业务中出现的概率不高，但总不能让它走全表扫描吧？反过来说，单独为一个不频繁的请求创建一个（身份证号，地址）的索引又感觉有点浪费。应该怎么做呢？

B+ 树这种索引结构，可以利用索引的「最左前缀」，来定位记录，具体使用情况可以查看例子：

可以使用(name,age)联合索引进行分析，上图中，索引项是按照索引定义里面出现的字段顺序排序的

当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果，如果你要查的是所有名字第一个字是张的人，你的 SQL 语句的条件是where name like ‘张%’。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

既然能够通过最左前缀索引进行查询优化，那么必然存在这样一个问题：在建立联合索引的时候，如何安排索引内的字段顺序

评估标准是：索引的复用能力。因为可以支持最左前缀，所以当已经有了(a,b)这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的

那么，如果既有联合查询，又有基于 a、b 各自的查询呢？查询条件里面只有 b 的语句，是无法使用(a,b)这个联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护(a,b)、(b) 这两个索引。

这时候，要考虑的原则就是索引占用的空间。比如上面这个市民表的情况，name 字段是比 age 字段大，建议创建一个（name,age)的联合索引和一个(age)的单字段索引。

¶索引下推

最左前缀可以用于在索引中定位记录，如果这时候，哪些不符合最左前缀的部分，会怎么样？

以市民表的联合索引（name, age）为例。如果现在有一个需求：检索出表中名字第一个字是张，而且年龄是10岁的所有男孩。那么，SQL 语句是这么写的：

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

通过最左前缀匹配能够找到第一个满足条件的记录，这样总比全表扫描要好，但是接下来如何判断其他条件是否满足？

在 MySQL 5.6 之前，只能从 ID3 开始一个个回表。到主键索引上找出数据行，再对比字段值,而 MySQL 5.6 引入的索引下推优化(index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。下面左图就是没有索引下推的流程，需要许多额外的回表操作，右图是有索引下推的操作，在回表之前就可以做到条件的判断，图中的每一个虚线表示回表一次

有这么一个表，表结构定义类似这样：

CREATE TABLE `geek` (
  `a` int(11) NOT NULL,
  `b` int(11) NOT NULL,
  `c` int(11) NOT NULL,
  `d` int(11) NOT NULL,
  PRIMARY KEY (`a`,`b`),
  KEY `c` (`c`),
  KEY `ca` (`c`,`a`),
  KEY `cb` (`c`,`b`)
) ENGINE=InnoDB;

这个表需要 a、b 做联合主键,既然主键包含了 a、b 这两个字段，那意味着单独在字段 c 上创建一个索引，就已经包含了三个字段了，是因为有如下的业务需求，所以额外创建了ca,cb这两个索引

1 2	select * from geek where c=N order by a limit 1; select * from geek where c=N order by b limit 1;

❓ 但是，真的有必要为了这两个查询模式，创建这两个额外的索引吗？

¶面试题目

本小节主要记录在面试中对索引考察比较频繁的知识点

¶哪些情况下可以考虑建立非聚集索引？

¶N 叉树中的 N 值在 MySQL 中是可以人工调整的吗？

可以按照调整 key 的大小的思路来说，5.6 以后可以通过 page 大小来简洁控制

¶MySQL 为什么用 B+ 树，而不用 B 树？

¶附录

牛客 Java 面试宝典
 Mysql 索引查询失效的情况
 MySQL 为什么用 B+树，而不用 B 树？

MySQL(七) 数据库索引

目录

¶概述