MySQL（七）索引

索引的数据结构

1 为什么使用索引

索引概述

索引(Index)是帮助MySQL高效获取数据的数据结构。是“排好序的快速查找结构”，满足特定的查找算法
索引是在存储引擎中实现的，每种存储引擎的索引不一定完全相同，每种存储引擎也不一定支持所有的索引
存储引擎可以定义每个表的最大索引数和最大索引长度
所有存储引擎支持每个表最少16个索引，总索引长度最少为256字节

使用索引的优点

提高索引的效率，降低数据库IO成本，是创建索引的主要原因
通过创建唯一索引，能够保证数据库表中每一行的唯一性
可以加速表和表之间的连接，即：对于有依赖关系的子表和父表进行联合查询的时候，可以提高查询速度
对于分组和排序查询，可以显著降低分组和排序的时间（因为索引是排好序的）

使用索引的缺点

创建和维护索引需要消耗时间，并且随着数据量的增加，消耗量也会增加
对表中的数据进行增删改的时候，索引也需要动态地维护，这样就降低了数据的维护速度
索引需要占据磁盘空间，当存在大量索引时，索引可能比数据文件更快达到最大文件尺寸

2 InnoDB中索引的推演

索引之前的查找

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

1 在一个页中的查找

假设目前表中的数据较少，所有记录都存放在一个页中，在查找记录可以按照搜索条件的不同分为两种情况：

以主键为搜索条件

可以在页目录中按照二分法快速定位到对应的槽，然后遍历槽对应分组中的记录即可快速找到指定的记录。
以普通列为搜索条件

因为在数据页中没有对普通列建立所谓的页目录，所以无法使用二分法快速查找到对应的槽，只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件，这种查找效率十分低下。

2 在很多页中查找

当数据变多，需要很多页来存储的时候，在很多页中的查找就分为下面两个步骤：

定位到记录所在的页
从所在的页中查找相应的记录

需要注意的是，页与页之间是使用的逻辑上相邻而物理上不相邻的双向链表，因此无法使用二分法快速定位，也是只能依次遍历所有的页，然后在每一个页中按照上面的方法去查找指定的记录，这显然是不现实的，因此索引应运而生。

设计一种简单的索引

CREATE TABLE index_demo (
	c1 INT,
    c2 INT,
    c3 INT,
    PRIMARY KEY(c1)
) ROW_FORMAT = Compact

上面创建的表的行格式如下：

record_type：记录类型，0为普通记录、2为最小记录、3为最大记录、1为目录记录
next_record：下一项记录相对于本条记录的偏移量
其他信息：一些隐藏列和记录的额外信息

在页中的记录就表示为：

在上面的很多页中查找的时候，因为页中的记录没有规律，因此需要遍历全部的记录，这时候可以建立一个目录，以快速定位记录所在的数据页。这个目录要求：

下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值

新分配的数据页编号可能不是连续的，可以看到页10的最大主键值是5，页28的最大主键值是4，这是不符合要求的，因此插入页28数据的同时会伴随着一次记录移动，也就是把主键为4的记录移到页10，把主键值为5的记录移动到页28。

在记录的增删改的过程中，必须通过诸如记录移动的操作保证下一个页的主键值大于上一个页的主键值，这个过程被称作页的分裂

16kb的数据页的编号和在物理磁盘上可能是不连续的，所以想从这么多页中快速定位记录所在的页，可以为这些也建立一个目录，每一个页对应一个目录项，每个目录项包括两部分：

页中用户记录的最小主键值，记作key
页号，记作page_no

索引的迭代方案

上面的数据页目录存在的几个问题：

总是需要一段连续的物理空间，不方便
在删除某一个数据页的时候，也需要删除目录中对应的目录项，需要移动后面覆盖前面

因此也将目录作为一个页，即目录页存放数据页的目录信息，在页头信息中的record_type为1表示这个页为目录页。

假设此时查找c1为20的记录，首先在目录页中查找页号为9的数据页，然后在9数据页中查找到c1为20的记录，整个过程只加载了一张目录页和一张数据页，即产生了两次磁盘IO。

使用目录页的目录是离散的空间，但是也维护了一个连续的目录，可以使用二分法加快定位数据所在的页

迭代两次：多个目录项记录的页

B+树结构

不管是存放用户记录的数据页，还是存放目录记录的数据页，都放到了B+树的数据结构里面，其中，底层的叶子节点存放了真实的用户记录，这些叶子节点内部的记录通过单向链表的数据结构连接，节点之间使用双向链表；其余用来存放目录记录的节点成为内节点或者非叶子节点。

我们一般使用的B+树不会超过4层

常见的索引概述

1 聚簇索引

聚簇索引并不是一种单独的索引，而是一种数据存储方式（所有用户记录都存放在了叶子节点上），也就是所谓的索引即数据，数据即索引。

特点：

使用记录的主键值的大小进行记录和页的排序，包含三层意思
- 页内的记录按照主键值排序成一个单链表
- 各个存放用户数据的页之间按照页内最小的主键值排序成双向链表
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小排序成一个双向链表
B+树的叶子节点存储的是完整的用户记录（指的是存储了所有的列的值，包括一些隐藏列）

优点：

数据访问更快，因为将所有的索引和数据都放在同一个B+树中，因此从聚簇索引中获取数据要比从非聚簇索引获取要快
聚簇索引对于主键的排序和范围查找速度非常快
按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据是紧密相连的，数据库不需要从多个数据库获取数据，节省了大量IO操作

缺点：

插入操作严重依赖插入顺序：按照主键的顺序插入是最快的方式，否则会造成页的分裂，严重影响性能。因此一般会定义一个自增的字段作为主键
更新主键的代价很高，因为会导致被更新的行移动，一般会设置InnoDB的主键不可更新
二级索引需要两次索引查找，第一次找到主键值，第二次回表根据主键值查找行数据

限制：

只有InnoDB支持聚簇索引，MyISAM不支持
由于数据物理存储方式只能有一种，所以每个mysql表也只能有一种聚簇索引，一般情况下就是表的主键
如果没有主键，InnoDb会选择一个非空的唯一索引代替。如果不存在，InnoDB则会隐式地定义一个主键作为聚簇索引
为了充分利用聚簇索引的特性，应该尽量选择有序的顺序id作为主键

2 二级索引（辅助索引、非聚簇索引）

上面的聚簇索引只有在搜索条件为主键的时候才能发挥作用，而当搜索条件为其他列的时候该怎么办呢？解决方法是多建几棵B+树，不同的B+树使用不同的排序规则，比如以c2列的大小作为数据页、页中记录的排序规则，再建一棵B+树：

特点：

使用记录的其他非主键列的大小进行记录和页的排序，包含三层意思
- 页内的记录按照列值排序成一个单链表
- 各个存放用户数据的页之间按照页内最小的列值排序成双向链表
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的列值大小排序成一个双向链表
B+树中不存放全部的用户记录的列，只存放作为排序规则的列和主键，因此在查询完后还需要一次回表操作，即拿着主键值去聚簇索引的B+树中查询才能查到完整的表信息
目录项记录也是作为排序规则的列和页号
非聚簇索引并不会影像到聚簇索引中的组织，所以一张表中能有多张聚簇索引

因为这种按照非主键列的大小对数据页和页内记录进行排列建立的B+树，在查询的时候需要再通过一次回表操作才能定位到完整的用户记录，所以这种B+树也被称作二级索引或者辅助索引，或者该非主键列建立的索引。

为什么不在聚簇索引中也放入其他列的信息，以减少回表操作的IO消耗呢？

当列数非常多的时候，每个列建立的聚簇索引如果都存放一份全部的记录，那么数据的冗余度是非常大的

3 联合索引

联合索引的本质其实还是非聚簇索引，是使用多个列的大小作为数据页和页内记录的排序规则而建立的B+树，比如想要按照c2和c3的大小进行排序：

先把各个记录和页按照c2列进行排序
在记录的c2列相同的情况下，采用c3列进行排序

特点：

每条目录项记录由c2 c3 页号组成，按照c2的值进行排序，如果相同则按照c3的值进行排序
B+树的叶子节点的用户记录由c1 c2 c3组成

InnoDB中B+索引的注意事项

1 B+树索引创建的实际过程

在上面的讲述中，是从下而上创建的节点，即页数过多创建的目录页，目录页过多有创建的上一级目录页，而实际的过程是这样的：

每当为每个表创建一个B+树索引（聚簇索引不是人为创建，默认就有）的时候，会自动为这个索引创建一个空白页，在表中没有存入数据的时候，页中既没有用户记录也没有目录记录
当向表中添加数据的时候，就会向这个空白页中添加用户记录
当根节点中的空间用完时继续插入数据的话，会将根节点中的数据复制到一个新的页中，然后这个页执行分裂操作，得到一个新的页，这时根据键值（聚簇索引的主键值或者非聚簇索引的索引列的值）的大小决定将该条记录分配到哪一个页中，根节点则上升为存储目录项记录的页。

从上面的过程中可以看出，自始至终根节点都没有发生移动，这样我们只要对表建立一个索引，根节点的页号就会存储到一个地方，之后凡是InnoDB需要用到这个索引的时候，都会从那个地方取出根节点的页号，从而来访问这个索引。

2 内节点中目录项记录的唯一性

在聚簇索引中，目录项要求是页号 + 索引列的组合，但是在二级索引中，这么做有些问题：

如上图是以c2列为索引建立的B+树，当插入记录9、1、c的时候，新插入记录的c2为1，则不能判断是加入页4还是插入页5，因此要保证B+树的同一层内节点的目录项记录除了页号这个字段以外是唯一的。所以二级索引的内节点的目录项记录是由一下几部分组成的：

索引列的值
主键值
页号

MyISAM索引方案

B树索引适用的存储引擎有：InnoDB、MyISAM、Memory

多个存储引擎支持的同一种存储引擎，但是实现原理是不同的
InnoDB和MyISAM支持的索引是B-tree索引，Memory支持的是Hash索引
MyISAM使用B+Tree作为索引结构，叶子的data域存放的是数据记录的地址

这里的B-tree就是B+tree，两者在mysql官方是一个概念

MyISAM索引的原理

InnoDB中索引即数据，也就是聚簇索引的B+树的叶子节点把数据和索引都包含了，而MyISAM的索引方案虽然也是用的树形结构，但是数据和索引是分开存放的，因此MyISAM使用的是非聚簇索引。

如图test表为MyISAM引擎的表，数据目录中的文件包含：

sdi：用于存储表的结构信息（5.7中为.frm）

MYD：用于存储数据

MYI：用于存储索引

将表中的数据按照记录插入的顺序单独存储在一个文件中，称之为数据文件(.MYD)。这个文件不会刻意划分为若干个数据页，有多少记录就会往文件追加多少；也不会按照主键大小排列记录，因此不能够使用二分法在文件中查找记录。
使用MyISAM存储引擎的表会将表的索引信息存入一个索引文件（.MYI）中，MyISAM会单独为表的主键创建一个索引，只不过创建的索引的叶子结点的记录存放的不是完整的用户记录信息，而是主键值 + 数据文件中记录地址的组合，因此也属于是非聚簇索引。

MyISAM的检索算法：首先在表的索引文件中按照B+树的搜索算法搜素，如果指定的key存在，则去取出data域，然后以data域中的记录地址去数据文件中取出查询的记录。

MyISAM和InnoDB的对比

在InnoDB中，只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中，需要找到记录的地址然后去数据文件中查找记录，即多一次回表操作，这也意味着MyISAM建立的全是二级索引
InnoDB的数据文件本身也是索引文件，而MyISAM的数据和索引是分离的，索引文件仅保存记录的地址
InnoDB的非聚簇索引的data域是主键的值，而MyISAM的索引的data域是对应记录的地址，也可以说，InnoDB的非聚簇索引引用了主键作为data域
MyISAM的回表操作是很快的，只需要拿着地址偏移量去文件里面找对应记录，而InnoDB则需要通过获取主键再去聚簇索引中获取记录
InnoDB要求表必须有主键（MyISAM可以没有），当没有显示指定的时候，会自动将一个有序且唯一的字段作为主键，如果没有这样的字段则会隐式地生成一个自增的主键

小结

1 不建议使用过长的字段作为主键

所有的聚簇索引和二级索引都会引用主键索引，因此过长的主键索引会导致索引变得过大。

2 不建议使用非单调的字段作为主键

使用非单调的字段作为主键的时候，存储引擎为了维护B+Tree的特性，即以主键大小作为数据页之间和页内记录的排序规则，而频繁地进行页的分裂调整，十分低效。

索引的代价

空间上的代价

每建立一个索引就会建立一棵b+树，每一棵B+树的每一个节点就是一个数据页，每一个数据页的大小是16kb，一棵很大的B+树由很多数据页组成，是一片很大的存储空间
时间上的代价

每次对表中数据进行增删改操作的时候，都需要去修改各个B+树的索引，增删改则会对节点或记录的排序造成破坏，所以存储引擎需要一些额外的时间进行记录移位、页面分裂、页面回收等操作来维护好节点和记录的操作。