三、索引的理解

3.1 观察主键索引现象

创建一个用户表，表中包含用户id、年龄和姓名，并将用户的id设置成主键

创建表完毕后向表中插入一些数据，并且插入数据时没有按照主键的大小顺序插入

但最终查看表中的数据时，却发现显示出来的数据是按照主键进行有序排列的

创建表时设置了主键，即便向表中插入数据时是乱序插入的，MySQL底层也会自动按照主键对插入的数据进行排序

3.2 推导主键索引结构的构建

单个Page

MySQL中要管理很多数据文件，在运行期间一定有大量的Page被换入换出，因此MySQL要将内存中大量的Page管理起来

MySQL将内存中的每一个Page都用一个结构体进行描述，然后再将各个结构体以双链表的形式组织，因此一个Page结构体内部既包含数据字段，也包含属性字段

为了方便后续数据的插入和删除，每个Page结构体内部存储的数据记录会以单链表的形式组织，并且各个记录间按照主键进行排序

页内部存放数据的模块，是一个链表的结构，链表的特点是增删快，查询修改慢，所以优化查询的效率是必须的。正是因为有序，在查找的时候，从头到后都是有效查找，没有任何一个查找是浪费的，而且，可能可以提前结束查找过程

单个Page内创建页内目录

Page结构体内部存储的数据记录是以单链表的形式组织起来的，当页内部的数据量增多时，本质在页内部进行的还是线性遍历，效率低下

可在Page结构体内部引入页内目录，将Page结构体内部存储的数据记录按照主键划分为若干区域，页内目录中就存储着这若干区域的最小键值

在Page结构体内部引入页内目录后，在页内部查询数据时就可以先通过页内目录找到目标数据所在区域的起始记录，然后再从该记录开始向后遍历找到目标记录

在每个Page结构体内部引入页内目录，目的是为了加速在单个Page内部数据查询的效率。由于这个页内目录也是保存在Page内部的，而单个Page的大小是固定的，因此添加页内目录后Page内部能够保存的数据记录变少了，所以在Page内部引入页内目录本质是空间换时间，就像给书添加目录需花费更多的纸张一样

每个Page结构体内部的数据会按照主键进行排序，其实就是为了引入页内目录，因为只有数据按照主键排序后引入页内目录才有意义，就像书中每一页都是按照页码进行排序的一样，若一本书的页码是乱序的，那么其目录就没有意义

多个Page

随着数据量不断增大，单个Page中无法存下所有数据，这时就需要用多个Page来存储数据

在查询数据时就需先遍历Page双链表，确定目标数据在哪一个Page，然后再在该Page内部找到目标数据

Page之上创建页目录

虽然在单个Page内部能够通过页内目录来快速定位数据，但在遍历Page双链表寻找目标Page时本质还是线性遍历

可以给各个Page结构体也建立页目录，页目录中的每个目录项都指向一个Page，而目录项存放的是其指向的Page中存放的最小数据的键值

各个Page结构体建立页目录后，在查询数据时就可先通过遍历页目录找到目标数据所在的Page，然后再在该Page内部找到目标数据

这里的页目录与之前的页内目录的区别在于，页目录管理的是一个个的Page，而页内目录管理的是一条条的记录。页内目录与其管理的多条记录是保存在同一个Page中，而页目录是重新申请的一个Page结构体来保存

随着数据量不断增大，Page变得越来越多，这时一个页目录无法管理所有的Page，这时就需要更多个的页目录。这些页目录也是一个个的Page结构体，只不过这些Page结构体中存放的不是数据记录，而是各个Page的目录信息。但是在MySQL看来，无论Page中存储的是什么数据，都应该被管理起来，因此这些Page页目录也需用双链表连接起来

页目录之上再创建页目录

就算给各个Page结构体也建立了页目录，但随着数据量不断增大，页目录的数量也会越来越多，这时在遍历页目录寻找目标Page时本质进行的还是线性遍历

类似的，可以不断在页目录之上再创建页目录，最终就一定能够得到一个入口页目录，这时在查询数据时就可以从入口页目录开始不断查询页目录，最终找到目标数据所在的Page，然后再在该Page内部找到目标数据

注意：

最终构建出来的实际就是一棵B+树，这棵B+树就是InnoDB的索引结构（非叶子结点的页目录不需使用双链表链接），其中每一层Page的作用就是加速其下一层的查找效率

若创建表时设置了主键，那么MySQL在底层就会自动将这张表中的的数据以B+树的形式组织起来，保存在Buffer Pool中，查询数据时就可通过查询这棵B+树来提高查询效率

MySQL中可能同时有大量的表正在被处理，因此Buffer Pool中可能会存在多个索引结构，即同时存在多个B+树结构，当查询表时访问的就是这张表对应的B+树结构

B+树中的Page结点不需要全量加入到Buffer Pool中

当对MySQL中的某张表进行增删查改操作时，不需将其对应B+树的所有结点全量加入到Buffer Pool中，甚至在刚开始时只需要将B+树的根结点加入到Buffer Pool中

当后续访问表中的数据时，再将该数据对应路径上的结点加入到Buffer Pool中即可，对于其他不需要的结点根本不用加入到Buffer Pool中，这一点和操作系统中的页表是很像的

在刷新数据时也不需将B+树中所有的结点都进行刷新，在Page结构体中有一个标记位用来标记当前Page是否被修改过，若被修改过则说明这是一个脏数据，在刷新数据时只有脏数据才需被刷新到磁盘上

由于B+树中的结点都是16KB大小的Page，因此无论是刷新数据到磁盘函数从磁盘加载数据到Buffer Pool，都是以Page为单位进行的，这也就是所谓的MySQL与磁盘交互的基本单位是Page

若将这棵B+树逆时针旋转90度，就会发现这其实就是操作系统中的页表结构，本质操作系统中的页表也是B+树结构

以32位平台为例，页表将一个虚拟地址转换成物理地址的过程如下：

选择虚拟地址的前10个bit位在页目录当中进行查找，找到对应的页表

再继续选择虚拟地址后续的10个bit位在对应的页表当中进行查找，找到物理内存中对应页框的起始地址

最后选择虚拟地址中剩下的12个bit位作为偏移量，从对应页框的起始地址处向后进行偏移，最终得到的就是转换后的物理地址

说明：

12个bit位有种取值，而字节对应就是4KB，所以物理内存中一个页框的大小就是4KB，这也就是为什么操作系统与磁盘交互的基本单位是4KB的原因

页表中的各个B+树结点也不需全量加入到内存中，而只需加入访问到的结点即可，所以页表占用的内存大小实际是可控的，这也就是为什么二级页表可行的原因

3.3 索引结构可以采用哪些数据结构

除了InnoDB存储引擎所采用的B+树结构，索引结构还可以采用哪些数据结构呢？

链表：查找时是线性遍历，效率低

普通二叉搜索树：可能退化成线性结构，此时查找还是线性遍历

AVL树和红黑树：虽然保证了二叉树是绝对或近似平衡的，不会退化成线性结构，但AVL树和红黑树都是二叉树结构，也意味着树的层高会比较高，而查询数据时都是从根结点开始向下进行查找的，这也意味着在查询过程中需遍历更多结点，若这些结点还没有被加载到Buffer Pool中，这时就需进行更多次的IO操作，所以最终没有选择其作为索引结构

哈希表：官方的索引实现方式中MySQL是支持HASH的，只不过InnoDB和MyISAM存储引擎并不支持。哈希表的优点就是其时间复杂度是O(1)，但哈希表也有一个缺点就是不利于进行数据的范围查找

注意：图中BTREE即B+树

B树 VS B+树

B+树是B树的一种变形结构，那为什么没有采用B树作为索引结构呢？

首先，普通B树中的所有结点中都同时包括索引信息和数据信息，由于一个Page的大小是固定的，因此非叶子结点中若包含了数据信息，那么这些结点中能够存储的索引信息就会变少，这棵树形结构就会变得更高更瘦，当查询数据时就可能需与磁盘进行更多次的IO操作

其次，普通B树中的各个叶子结点之间没有连接起来，这将不利于进行数据的范围查找，而B+树的各个叶子结点之间是连接起来的，当进行范围查找时，直接先找到第一个数据然后继续向后遍历找到之后的数据即可，因此将各个叶子结点连接起来更有利于进行数据的范围查找

3.4 聚簇索引 VS 非聚簇索引

MyISAM存储引擎 - 主键索引结构

博客上述推导的主键索引结构是InnoDB存储引擎的主键索引结构，而MyISAM存储引擎同样采用B+树作为索引的基本数据结构

与InnoDB存储引擎的B+树不同的是，MyISAM存储引擎的B+树的叶子结点存放的不是数据记录，而是数据记录对应的地址

当一张表存在多个索引时，就会有多个B+树结构，叶子结点存储数据记录的地址即可

下图为MyISAM存储引擎的主键索引结构，其中Col1为主键：

InnoDB存储引擎 - 普通索引结构

InnoDB存储引擎的普通索引采用的也是B+树结构，但普通索引的B+树中的键值可以重复，并且B+树的叶子结点中存储的不是数据记录，而是对应数据记录的主键值

当根据普通索引查询数据时，会先查找普通索引对应的B+树找到目标记录的主键值，然后再查找主键索引对应的B+树找到目标记录，这个过程被称为回表查询

下图为InnoDB存储引擎的普通索引结构，其中Col3为索引列:

注意：

InnoDB的普通索引的B+树叶子结点中没有保存整条数据记录，是为了节省空间，因为同一张表可能会创建多个普通索引，每个普通索引的B+树中都保存一份数据会造成数据冗余，所以通过回表查询主键索引对应的B+来获取整个数据记录，该做法本质上是以时间换空间

当根据普通索引查询数据时，其实也不一定需要进行回表查询，因为有可能要查询的就是这条记录对应的主键值，因此查询完普通索引对应B+树后即可完成查询

采用InnoDB存储引擎建立的每张表都会有一个主键，就算用户没有设置，InnoDB也会自动创建一个不可见的主键，因为完整数据记录只会存储在主键索引对应的B+树中的，因此采用InnoDB存储引擎建立的表必须有主键

聚簇索引 VS 非聚簇索引

聚簇索引： 像InnoDB存储引擎这种，将数据记录与索引结构放在一起的索引方案，叫做聚簇索引

非聚簇索引： 像MyISAM存储引擎这种，将数据记录与索引结构分离的索引方案，叫做非聚簇索引

当采用InnoDB存储引擎创建表时，在数据库对应的目录下会新增两个文件

当采用MyISAM存储引擎创建表时，在数据库对应的目录下会新增三个文件

注意：

采用InnoDB和MyISAM存储引擎创建表时都会生成xxx.frm文件，该文件中存储的是表结构相关的信息

采用InnoDB存储引擎创建表时会生成一个xxx.ibd文件，该文件中存储的是索引和数据相关的信息，即聚簇索引，索引和数据存储在同一个文件中

采用MyISAM存储引擎创建表时会生成一个xxx.MYD文件和一个xxx.MYI文件，其中xxx.MYD文件中存储的是数据相关的信息，而xxx.MYI文件中存储的是索引相关的信息，即非聚簇索引，索引和数据是分开存储的