Mysql索引

索引

一、为什么要有索引

索引最主要的目的就是提高查询的效率（更快地查到想要的数据）。

在Mysql中，索引是在存储引擎层实现的。

索引的优势：

1. 可以提高数据检索的效率，降低数据库的IO成本，类似于书的目录。
2. 通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗。
3. 被索引的列会自动进行排序，包括【单列索引】和【组合索引】，只是组合索引的排序要复杂一些。
4. 如果按照索引列的顺序进行排序，对应order by语句来说，效率就会提高很多。

索引的劣势：

1. 索引会占据磁盘空间
2. 索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件。

二、常见的索引模型

比较常见的索引模型有：

• 哈希表
• 有序数组
• 搜索树

2.1.哈希表

哈希表就是key-value的形式，给定一个key，查询到对应的value。多个key经过hash之后，可能会得到同一个值，这时候用一个链表即可。

例如user2和user4都hash到同一个结果，使用链表串起来。查询的时候，先找到该链表，然后按顺序遍历查找。

Hash表只适用于等值查询，即根据对应的key，查value。 如果要让Hash表查询m到n区间的数据，因为不是有序的，所以需要全表扫一遍，效率低。

2.2.有序数组

有序数组就是将数据按顺序存放在数组里面。

很明显，因为需要保证有序，所以如果插入一个中间位置的数据，需要将后面的数据全部往后挪动，成本是很高的。因此，如果使用有序数组，索引最好是递增的。

有序数据适用于等值查询和范围查询，范围查询时使用二分查询，时间复杂度时O(log(N))。

有序数据主要用在静态存储引擎，例如xx年城市的人口信息，这类不会再修改的数据。

2.3.搜索树

例如二叉搜索树，查询和更新的时间复杂度都是O(log(N))。

为了减少树高带来的磁盘读延时（例如树高为10，那么查到最下面的叶子节点，就得访问磁盘10次），一般会使用N叉树而不会直接用二叉树。

InnoDB的一个整树字段索引，N差不多为1200。当树高为4时，就可以存储1200^3个值（越17亿）。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

三、InnoDB的索引模型

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

3.1.聚簇索引和二级索引

现有如下表：id为主键，k字段设置了一个索引：

create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;
1
2
3
4
5

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

索引的类型分为主键索引和非主键索引

• ID字段的索引是主键索引，其叶子节点存放的是整行数据，在 InnoDB 里，也称为聚簇索引（Clustered Index）。
• k字段的索引是非主键索引，其叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（Secondary Index）。

因此，当我们要查询某条数据的时候，根据主键索引去查，只要查一次。而根据非主键索引去查，就要先查到对应的主键值，然后再查主键的B+树到对应的数据。这个过程称为 回表。

所以我们最好优先用主键索引去查数据。

ps：如果没有主键的表，有一个普通索引，InnoDB会默认创建一个RowID做主键

3.2.B+树索引维护

B+树需要维护索引的有序性。

假设现在插入一个ID值为700的新数据，可以直接在R5的记录后面插入。但是如果插入ID值为400，那么就需要逻辑上将后面的数据挪动，空出位置。

这么看自增的整数类型主键是最合适的（有序，空间占用比字符串小）

但是整数类型的主键也有一些问题，以数据库自增为例，单点无法水平切分，并且可能会把关键的信息暴露（通过主键的增长情况），等等。 当然，如果是小项目，直接用这个是最方便的。

如果使用UUID作为主键，优点是关键信息不会暴露，并且可以分库。但是UUID生成的时间比较久，并且是字符串类型，存储空间大。

现在比较常用的就是用雪花算法生成主键了。有序、可使用整形、可以分库，对分布式友好，生成速度也比UUID快一些。但是缺点是依赖时钟，如果时间回拨会造成错乱。

四、重建索引

重建索引k

alter table T drop index k;
alter table T add index(k);
1
2

重建主键索引

alter table T drop primary key;
alter table T add primary key(id);
1
2

• 仅重建索引k，仅仅影响该索引，是合理的，重建后可以省空间。
• 删除主键索引，会导致其他索引失效。上面的语句如果连着执行，前两条语句相当于白执行了。

ps：OPTIMIZE TABLE也会对索引进行重建

为什么删除索引能省空间？

1. 对于InnoDB引擎，即使把表的数据给删除了，其索引内容还在，会占用空间
2. 索引可能因为删除，或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
3. 重建索引前，应当先分析表

五、覆盖查询

现有一个表

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


// DML
insert into T values(100,1, 'aa'),(200,2,'bb'), \
				(300,3,'cc'),(500,5,'ee'), \
				(600,6,'ff'),(700,7,'gg');
1
2
3
4
5
6
7
8
9
10
11
12
13

接下来执行

select * from T where k between 3 and 5
1

该语句的查询过程如下：

1. 在k树上找到 k=3 的记录（ID=300）
2. 在ID树找到ID=300的记录R3
3. 在k树上找到 k=5 的记录（ID=500）
4. 在ID树找到ID=500的记录R5
5. 在k树取k=6，不满足条件，循环结束

可以看到，整个查询过程读k树3次，回表2次

假设只查询k=3～5的ID值，那么这个过程是不需要回表的

select ID from T where k between 3 and 5
1

因为索引k已经覆盖了我们的查询需求，所以这样的查询称为 覆盖查询

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

例如现在有一个表，包括某个城市的市民资料，由于身份证号具有唯一性，并且查询的频率高，因此会给身份证建一个索引。

现在需要根据身份证号查询对应的姓名，这时候就需要回表去查。

如果经常有这种身份证号查姓名的场景，那么就可以考虑给身份证号和姓名建立联合索引，这样无需回表就可以快速得到结果。