本文参考了极客时间里林晓斌老师的【MySQL实战45讲】

索引

索引在MySQL中也叫键(Key)

目的:为了提高数据查询的效率,就像书的目录一样,可以快速定位内容位置

优势:降低IO成本,提高效率

劣势:会生成索引文件,占用磁盘空间

三种常见索引数据结构

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

哈希表

哈希表是一种以键-值(key-value)存储数据的结构,只要输入待查找的值即key,就可以找到其对应的值即Value,时间复杂度为O(1),但是容易发生哈希冲突,当发生冲突时,常用开放地址法、拉链法、再散列法解决

因为Value不是有序存储的,所以哈希索引做区间查询的速度是很慢的,范围查找时只能通过扫描全表的方式,所以哈希表这种结构适用于只有等值查询的场景,而不适用于范围查询

有序数组

有序数组在等值查询和范围查询场景中的性能都非常优秀,等值查询的时候可以用二分查找,时间复杂度为O(log(N));范围查询时可以先用二分查找找到第一个值,然后向右遍历。如果仅仅看查询效率,有序数组是最好的数据结构,但是要更新数据时就必须挪动后面所有的数据,成本太高。所以有序数组索引只适用于查询的情况

搜索树
  1. 二叉查找树

  2. 平衡二叉树

  3. N叉树

    实际上大多数的数据库存储并不使用二叉树。原因是,索引不止存在内存中,还要写到磁盘上。为了让一个查询尽量少地读磁盘,就必须让查询过程访问尽量少的数据块。那么,我们就不应该使用二叉树,而是要使用“N叉”树,N叉树由于在读写上的性能优点,以及适配磁盘的访问模式,已经被广泛应用在数据库引擎中了。这里,“N叉”树中的“N”取决于数据块的大小,以InnoDB的一个整数字段索引为例,这个N差不多是1200,这棵树高是4的时候,就可以存1200的3次方个值,这已经17亿了

  4. B+树

    B+树属于N叉树,MysQL中,InnoDB引擎使用了B+树索引模型,所有数据都是存储在B+树中的,每一个索引在InnoDB里面对应一棵B+树

    建立在B+树上的索引

    B+树的索引从根结点开始搜索,不需要进行全表扫描,而且B+树对索引列是顺序组织存储的,很适合范围查找,

主键索引和非主键索引

现在假设一个主键为ID的表,有字段k和name,且k上有索引

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),两棵树的示例示意图如下

左图为主键索引,右图为非主键索引

根据叶子节点的内容,索引类型分为主键索引和非主键索引

  1. 主键索引的叶子节点存的是整行数据。在InnoDB里,主键索引也被称为聚簇索引(clustered index),如果语句是 select * from T where ID=500,即主键查询方式,则只需要搜索ID这棵B+树;

  2. 非主键索引的叶子节点内容是主键的值。在InnoDB里,非主键索引也被称为二级索引(secondary index),二级索引叶子结点保存的不是指向行的物理位置的指针,而是行的主键值。如果语句是 select * from T where k=5,即普通索引查询方式,则需要先搜索k索引树,得到ID的值为500,再到ID索引树搜索一次,这个过程称为回表。也就是说,基于非主键索引的查询需要多扫描一棵索引树,因此,在应用中应该尽量使用主键查询

自增主键

B+树为了维护索引有序性,在插入新值的时候需要做必要的维护。根据B+树的算法,当一个数据页插满后会申请一个新的数据页,然后挪动部分数据过去,称为页分裂,自然的会影响性能,而且整体空间利用率会降低50%。当删除部分页数据后,页的利用率会降低,会做页合并操作,即页分裂的逆过程

解决办法:自增主键

自增主键是自增列上定义的主键,在建表语句中是这么定义的:NOT NULL PRIMARY KEY AUTO_INCREMENT

插入新记录的时候可以不指定ID的值,系统会获取当前ID最大值加1作为下一条记录的ID值,符合了我们前面提到的递增插入的场景。每次插入一条新记录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂,而有业务逻辑的字段做主键,则往往不容易保证有序插入,这样写数据成本相对较高

同时,主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小,所以,从性能和存储空间方面考量,自增主键往往是更合理的选择

适用业务字段直接做主键的场景:只有一个索引,该索引必须是唯一索引

覆盖索引

B+树索引结构

语句select * from T where k between 3 and 5的执行流程:

  1. 在k索引树上找到k=3的记录,取得ID=300
  2. 再到ID索引树查到ID=300对应的R3(第一次回表)
  3. 在k索引树取下一个值k=5,取得ID=500
  4. 再回到ID索引树查到ID=500对应的R4(第二次回表)
  5. 在k索引树取下一个值k=6,不满足条件,循环结束。

可见,回表了两次。而通过覆盖索引可以避免回表过程

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

最左前缀原则

创建一个三列的联合索引包含(col1, col2, col3),索引会生效于(col1),(col1, col2)以及(col1, col2, col3)

比如以下示例:

SELECT * FROM tbl_name WHERE col1=val1;
SELECT * FROM tbl_name WHERE col1=val1 AND col2=val2;
SELECT * FROM tbl_name WHERE col2=val2 AND col1=val1;

SELECT * FROM tbl_name WHERE col2=val2;
SELECT * FROM tbl_name WHERE col2=val2 AND col3=val3;

SELECT * FROM tbl_name WHERE col1=val1 AND col3=val3;
  1. 第一条和第二条和第三条查询语句用到了索引,第二条和第三条效果是一样的,即与where语句中字段出现的顺序无关

  2. 第四条和第五条查询虽然包含索引的列,,但是不会用索引去执行查询,因为(col2)和(col2, col3) 不是(col1, col2, col3)的最左前缀

  3. 第六条查询只会执行(col1)的索引查询

对于索引的第一个字段,用like时左边必须是固定值,通配符只能出现在右边,select * from AAA where a like '张%'会用到索引;而select * from AAA where a like '%三'不会用到索引

区分各种索引类型

创建索引语句差异

alter table `test` add primary key (`id`);															#创建主键索引
alter table `test` add unique (`title`); #创建唯一索引
alter table `test` add index `title`(`title`); #创建普通索引

各索引区别

主键索引:它 是一种特殊的唯一索引,不允许有空值

唯一索引:与”普通索引”类似,不同的是索引列的值必须唯一,不允许包含重复的值,但允许有空值

普通索引:最基本的索引,没有任何限制

change buffer

查询过程

在保证不会写入重复的情况下,从性能的角度考虑,应该用唯一索引还是普通索引呢?假设字段k的值都不重复

InnoDB的索引组织结构

假设执行的语句是select Id from T where k=5

  1. 对于普通索引查找到第一个满足条件的(5, 500)后,还需要再查找下一个记录,直到碰到第一个不满足k=5条件的记录,因为普通索引的索引列值是不要求唯一的,所以还要再多判断一次
  2. 对于唯一索引,因为它的索引列的值必须唯一,所以找到(5, 500)后会直接停止检索

这个不同带来的性能差距会有多少呢?微乎其微

更新过程

为了说明普通索引和唯一索引对更新语句性能的影响这个问题,需要先了解change buffer

当需要更新一个数据页时,如果数据页在内存中就直接更新,如果没有在内存中,在不影响数据一致性的前提下,InooDB会将这些更新操作缓存在change buffer中,这样就不需要从磁盘中读入这个数据页。在下次查询需要访问这个数据页的时候,将数据页读入内存,然后执行change buffer中与这个页有关的操作。通过这种方式就能保证这个数据逻辑的正确性。虽然名字叫作change buffer,实际上它是可以持久化的数据。也就是说,change buffer在内存中有拷贝,也会被写入到磁盘上

将change buffer中的操作应用到原数据页,得到最新结果的过程称为merge。除了访问这个数据页会触发merge外,系统有后台线程会定期merge。在数据库正常关闭(shutdown)的过程中,也会执行merge操作。显然,如果能够将更新操作先记录在change buffer,减少读磁盘,语句的执行速度会得到明显的提升。而且,数据读入内存是需要占用buffer pool的,所以这种方式还能够避免占用内存,提高内存利用率

使用change buffer的条件
  1. 对于唯一索引,所有的更新操作都要先判断是否违反唯一性约束。比如,要插入(4,400)这个记录,就要先判断现在表中是否已经存在k=4的记录,而这必须要将数据页读入内存才能判断。如果都已经读入到内存了,那直接更新内存会更快,就没必要使用change buffer了
  2. 对于普通索引,不用像唯一索引一样先访问内存,所以可以直接使用change buffer,change buffer因为减少了随机磁盘访问,所以对更新性能的提升是会很明显的
change buffer的使用场景

普通索引的所有场景,使用change buffer都可以起到加速作用吗?

不是的。前面讲到真正进行数据更新的时候会触发merge操作,所以merge之前,change buffer里面记录的操作越多,收益就越大。同时change buffer更适用于写多读少的场景,因为读的时候要访问数据页,会触发merge,即会触发磁盘IO操作,不利于提升性能

综合前面所说,唯一索引和普通索引在查询能力上的差别不明显,主要考虑的是更新时的性能差别,其中涉及到了change buffer

区分change buffer与redo log

因为change buffer与redo log功能相似,所以容易混淆其概念,这里举例子来辨析二者区别

假设要在表上执行下面这个插入语句

insert into T(ID, k) values(id1, k1), (id2, k2);

假设k1的数据页已经在内存(InnoDB buffer pool)中,k2的数据页不在内存中

带=change buffer的更新过程

这条更新语句做了如下操作:

  1. Page1已经在内存,插入(id1, k1)操作直接就在内存执行
  2. Page2没有在内存,所以先在内存的change buffer区域记录“往Page2插入(id2, k2)”的信息
  3. 将1,2步的操作记录在redo log

可以看到这条插入语句写了两处内存,写了一次磁盘(两次操作合并在一起写了一次磁盘),而且还是通过redo log实现顺序写

假设现在要执行如下查询语句

select * from t where k in (k1, k2);

如果查询语句发生在插入语句后不久,内存中的数据都还在,此时和ibdata1,redo log(ib_log_fileX)就无关了,下图中没有画出这部分

带change buffer的读过程