2.InnoDB中的索引方案
①迭代1次:目录项记录的页
上边称为一个简易的索引方案，是因为为了在根据主键值进行查找时使用二分法快速定位具体的目录项而假设所有目录项都可以在物理存储器上连续存放，但是这样做有几个问题:
InnoDB是使用页来作为管理存储空间的基本单位，最多能保证16KB的连续存储空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数且非常多的表是不现实的。
我们时常会对记录进行增删，假设把页28中的记录都删除了，那意味着目录项2也就没有存在的必要了，这就需要把目录项2后的目录项都向前移动一下。这样牵一发而动全身的操作效率很差
所以，需要一种可以灵活管理所有目录项的方式。可以发现目录项其实长得跟用户记录差不多，只不过目录项中的两个列是主键和页号而已，为了和用户记录做一下区分，把这些用来表示目录项的记录称为目录项记录。那InnoDB怎么区分一条记录是普通的用户记录还是目录项记录呢?使用记录头信息里的record_type属性，它的各个取值代表的意思如下:
0：普通的用户记录
1：目录项记录
2：最小记录
3：最大记录
现在把上面使用到的目录项放到数据页中的样子就是这样:
从图中可以看出来，新分配了一个编号为30的页来专门存储目录项记录。
再次强调目录项记录和普通的用户记录的异同
不同点：
目录项记录的record_type值是1，而普通用户记录的record_type值是0
目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含 很多列 ，另外还有InnoDB自己添加的隐藏列
了解：记录头信息里还有一个叫min_rec_mask的属性，只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1 ，其他别的记录的 min_rec_mask 值都是 0
相同点：
两者用的是一样的数据页，都会为主键值生成Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。
现在以查找主键为 20 的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：
1.先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，因为 12 < 20 <209 ，所以定位到对应的记录所在的页就是页9。
2.再到存储用户记录的页9中根据 二分法 快速定位到主键值为 20 的用户记录。
②迭代2次：多个目录项纪录的页
虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有16KB大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，如何处理呢?
这里假设一个存储目录项记录的页最多只能存储4条目录项记录，所以如果此时再向上图中插入一条主键值为320的用户记录的话，那就需要分配一个新的存储目录项记录的页:
从图中可以看出，插入一条主键值为320的用户记录之后需要两个新的数据页：
为存储该用户记录而新生成了页31 。
因为原先存储目录项记录的页30的容量已满 （前边假设只能存储4条目录项记录），所以不得不需要一个新的页32来存放页31对应的目录项
现在因为存储目录项记录的页不止一个，所以如果想根据主键值查找一条用户记录大致需要3个步骤，以查找主键值为 20 的记录为例：
1.确定目录项记录页
我们现在的存储目录项记录的页有两个，即页30和页32 ，又因为页30表示的目录项的主键值的范围是 [1, 320) ，页32表示的目录项的主键值不小于 320 ，所以主键值为 20 的记录对应的目录项记录在 页30 中。
2.通过目录项记录页 确定用户记录真实所在的页
在一个存储目录项记录的页中通过主键值定位一条目录项记录的方式说过了。
3.在真实存储用户记录的页中定位到具体的记录。
③ 迭代3次：目录项记录页的目录页
问题来了，在这个查询步骤的第1步中需要定位存储目录项记录的页，但是这些页是不连续的，如果表中的数据非常多则会产生很多存储目录项记录的页，那怎么根据主键值快速定位一个存储目录项记录的页呢?那就为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样了:
如图，生成了一个存储更高级目录项的页33 ，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在 [1, 320) 之间，则到页30中查找更详细的目录项记录，如果主键值不小于320 的话，就到页32中查找更详细的目录项记录。
随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下边这个图来描述它:
这样的数据结构，就是 B+树 。
上面的每个蓝框表示一个数据页，最下面的叶子节点中存放了真实的一条条数据，这些数据之间用单向链表连接，叶子节点之间用双向链表连接。非叶子节点是目录页。
④B+Tree
不论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到B+树这个数据结构中了，所以我们也称这些数据页为节点。从图中可以看出，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中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.3 常见索引概念
索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。也可以把非聚集索引称为二级索引或者辅助索引。
1. 聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式(所有的用户记录都存储在了叶子节点)，也就是所谓的索引即数据,数据即索引。
术语"聚簇"表示数据行和相邻的键值聚簇的存储在一起。
特点：
1.使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
页内的记录是按照主键的大小顺序排成一个单向链表 。
各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表 。
存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表 。
2.B+树的 叶子节点 存储的是完整的用户记录。
所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
把具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建,InnoDB存储引擎会自动地创建聚簇索引。
优点：
数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以 节省了大量的IO操作 。
缺点：
插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，一般都会定义一个自增的ID列为主键
更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，一般定义主键为不可更新
二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据
限制:
对于MysQL数据库目前只有InnoDB数据引擎支持聚簇索引，而MylSAM并不支持聚簇索引。
由于数据物理存储排序方式只能有一种，所以每个MySQL的表只能有一个聚簇索引。一般情况下就是该表的主键。
如果没有定义主键，InnoDB会选择非空的唯一索引代替。如果没有这样的索引,InnoDB会隐式的定义一个主键来作为聚簇索引
为了充分利用聚簇索引的银簇的特性，所以InnoDB表的主键列尽量选用有序的顺序id，而不建议用无序的id,比如UUID、MD5、HASH、字符串列作为主键无法保证数据的顺序增长
2. 二级索引（辅助索引、非聚簇索引）
上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果想以别的列作为搜索条件该怎么办呢?肯定不能是从头到尾沿着链表依次遍历记录一遍。
答案:可以 多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比方说用c2列的大小作为数据页、页中记录的排序规则，再建一棵B+树，效果如下图所示:
这个B+树与上边介绍的聚簇索引有几处不同:
使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
页内的记录是按照c2列的大小顺序排成一个单向链表
各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表
存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表
B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值
目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配
所以如果想通过c2列的值查找某些记录的话就可以使用刚刚建好的这个B+树了
以查找c2列的值为4的记录为例，查找过程如下:
1.确定 目录项记录页
根据根页面 ，也就是页44，可以快速定位到目录项记录所在的页为页42(因为2<4< 9 )
2.通过目录项记录页确定用户记录真实所在的页
在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2<4<=4，所以确定实际存储用户记录的页在页34和页35中
3.在真实存储用户记录的页中定位到具体的记录:
到页34和页35中定位到具体的记录
4.但是这个B+树的叶子节点中的记录只存储了c2和c1〔也就是主键）两个列，所以必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。
概念：回表
根据这个以c2列大小排序的B+树只能确定要查找记录的主键值，所以如果想根据c2列的值查找到完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程称为回表。也就是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树！
**问题：**为什么我们还需要一次 回表 操作呢？直接把完整的用户记录放到叶子节点不OK吗
回答:
如果把完整的用户记录放到叶子节点是可以不用回表。但是太占地方了，相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了
因为这种按照 非主键列 建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为 二级索引 (英文名secondary index )，或者辅动索引。由于使用的是c2列的大小作为B+树的排序规则，所以也称这个B+树是为c2列建立的索引
非聚簇索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个非聚簇索引
小结:聚簇索引与非聚簇索引的原理不同，在使用上也有一些区别:
1.聚簇索引的叶子节点存储的就是数据记录，非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序
2.一个表只能有一个聚簇索引，因为只能有一种排序存储的方式，但可以有多个非聚簇聚簇索引，也就是多个索引目录提供数据检索
3.使用聚簇索引的时候，数据的查询效率高(不用回表)，但如果对数据进行插入，删除，更新等操作，效率会比非聚簇索引低
