第四章 索引
1. 索引概述
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现高级查找算法。
1.1 优点
（1）提高数据检索的效率，降低数据库的IO成本，创建索引的主要原因。
（2）通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
（3）在实现数据的参考完整性方面，可以加速表和表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
（4）在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，降低了CPU的消耗。
1.2 缺点
（1）创建索引和维护索引要耗费时间，并且随着数据量的增加，所耗费的时间也会增加。
（2）索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
（3）虽然索引大大提高了查询速度，同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
2. B+ 树索引设计推演
2.1 无索引的查找
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
在一个页中的查找
假设目前表中的记录比较少，所有的记录都可以被存放在一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：
- 以主键为搜索条件
可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。- 以其他列作为搜索条件
因为在数据页中并没有对非主键建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
在很多页中查找
大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：
- 定位到记录所在的页。
- 从所在的页内查找相应的记录。
总结：在没有索引时，不论是根据主键列或者其他列的值进行查找，只能
从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的。
2.2 设计索引
mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;
这个表使用Compact行格式来实际存储记录的。这里简化index_demo表的行格式示意图：
record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、1表示目录项记录、2表示最小记录、3表示最大记录。next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁。各个列的值：这里只记录在index_demo表中的三个列，分别是c1、c2和c3。其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。
将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：
把一些记录放到页里的示意图就是：
2.2.1. 一个简单的索引设计方案
因为各个页中的记录并没有规律，我所以不得不依次遍历所有的数据页。所以如果我们
想快速的定位到需要查找的记录在哪些数据页中该咋办？我们可以为快速定位记录所在的数据页而建立一个目录，建这个目录必须完成下边这些事：
- 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
- 给所有的页建立一个目录项。
以
页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键值为20的记录，具体查找过程分两步：
- 先根据
二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 209 ），它对应的页是页9。- 再根据前边说的在页中查找记录的方式去
页9中定位具体的记录。
至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为索引。
2.2.2. 迭代1次：1个目录项组成的页
2.2.3. 迭代2次：多个目录项组成的页
2.2.4. 迭代3次：目录项记录页的目录页
这个数据结构，它的名称是 B+树 。
一个B+树的节点其实可以分成好多层，规定最下边的那层（第
0层），用来存放用户记录，之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页最多存放3条记录，存放目录项记录的页最多存放4条记录。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录，那么：
- 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放
100条记录。- 如果B+树有2层，最多能存放
1000×100=10,0000条记录。- 如果B+树有3层，最多能存放
1000×1000×100=1,0000,0000条记录。- 如果B+树有4层，最多能存放
1000×1000×1000×100=1000,0000,0000条记录。相当多的记录！！！
你的表里能存放100000000000条记录吗？所以一般情况下，我们用到的B+树都不会超过4层，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的Page Directory（页目录），所以在页面内也可以通过二分法实现快速定位记录。
3. 常见索引及其概念
索引按照物理实现方式，索引可以分为 2 种：
聚簇索引和非聚簇索引。
非聚集索引也称为二级索引或者辅助索引。
3.1 聚簇索引
特点：
- 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
页内的记录是按照主键的大小顺序排成一个单向链表。- 各个存放
用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。- 存放
目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
- B+树的
叶子节点存储的是完整的用户记录。
所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
优点：
数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快- 聚簇索引对于主键的
排序查找和范围查找速度非常快- 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以
节省了大量的io操作。
缺点：
插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增ID列为主键更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据
3.2 二级索引（辅助索引、非聚簇索引）
二级索引：以非主键列创建的索引。也会生成一棵B+树，但此棵树只存储主键值，不存储其他列数据，若需找到其他列数据，还需再到聚簇索引B+树寻找一遍所需要的值。
回表：再到聚簇索引B+树寻找一遍所需要的值的过程就是回表。
3.3 联合索引
同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照
c2和c3列的大小进行排序，这个包含两层含义：
- 先把各个记录和页按照c2列进行排序。
- 在记录的c2列相同的情况下，采用c3列进行排序
注意：联合索引，本质上也是一个二级索引。只不过是以多列的值先后排序的二级索引
