前边我们详细说了 InnoDB 数据页的 7 个组成部分，
知道了各个数据页可以组成一个双向链表，
而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，
每个数据页都会为存储在它里面的记录生成一个页目录，
在通过主键查找某条记录时可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
页和记录的关系示意图如下：

这些页可以不在物理结构上相连，只要通过双向链表相关联即可。

没有索引的查找

我们下边先只说搜索条件为对某个列精确匹配的情况，所谓精确匹配，就是搜索条件中用 = 连接起的表达式，比如这样：select [列名列表] from 表名 where 列名 = xxx;
在一个页中的查找
假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：

• 以主键作为搜索条件，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
• 以其他列作为搜索条件，对非主键列的查找的过程不那么简单，因为在数据页中并没有对非主键列建立页目录，所以我们无法通过二分法快速定位相应的槽。

这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是否符合搜索条件

在很多页中的查找
大部分情况下我们表中存放的记录是非常多的，需要很多数据页来存储这些记录。
在很多页中查找记录可以分为两个步骤：

1. 定位到记录所在的页。
2. 从所在的页内中查找相应的记录。

在没有索引的情况下，不论是根据主键列还是其他列的值进行查找，
由于并不能快速定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据刚才说过的查找方式去查找指定的记录。
因为要遍历所有的数据页，所以这种方式非常耗时。

InnoDB 的索引方案

设计 InnoDB 的人复用了之前存储用户记录的数据页来存储目录，目录项中的两个列是主键和页号。
为了和用户记录区分，我们把这些用来表示目录项的记录称为目录项记录。
InnoDB 通过记录头信息里的 record_type 属性区分记录是普通的用户记录还是目录项记录，它的各个取值说明如下：

• 0：普通的用户记录
• 1：目录项记录
• 2：最小记录
• 3：最大记录

把目录项放到数据页中后如图所示：

从图中可以看出，我们新分配了一个编号为 30 的页来专门存储目录项记录。
目录项记录和普通的用户记录的不同点：

• 目录项记录的 record_type 值是 1，而普通用户记录的 record_type 值是 0
• 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，另外还有隐藏列
• 记录头信息中的 min_rec_mask 属性：只有在存储目录项记录的页中的主键值最小的目录项记录的 min_rec_mask 值为 1，其他记录的 min_rec_mask 值都是 0

除了上述几点外，这两者就没什么差别了，
它们用的是一样的数据页，页面类型都是索引页 (0x45BF)，这个属性在 File Header 中。
页的组成结构也是一样的，就是前边介绍过的 7 个部分。
都会为主键值生成 Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。
现在以查找主键为 20 的记录为例，根据某个主键值去查找记录的步骤大致拆分成两步：

1. 先到存储目录项记录的页，也就是页 30 中通过二分法快速定位到对应目录项，因为12 < 20 < 209，所以定位到对应的记录所在的页就是页9
2. 再到存储用户记录的页 9 中根据二分法快速定位到主键值为 20 的用户记录。

虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，
但是不论怎么说，一个页只有 16KB 大小，能存放的目录项记录也是有限的，
如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，就需要多个存储目录项记录的页。
为了更好的理解新分配一个目录项记录页的过程，这里假设一个存储目录项记录的页最多只能存放 4 条目录项记录（请注意是假设，真实情况下可以存放很多）。
所以如果此时我们再向上图中插入一条主键值为 320 的用户记录的话，那就需要分配一个新的存储目录项记录的页：

从图中可以看出，我们插入了一条主键值为 320 的用户记录之后需要两个新的数据页：

• 为存储该用户记录而新生成了页 31
• 因为原先存储目录项记录的页 30 的容量已满（我们假设一个页只能存储 4 条目录项记录），所以需要一个新的页 32 来存放页 31 对应的目录项。

现在因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要3个步骤，以查找主键值为 20 的记录为例：

1. 确定目录项记录页。我们现在的存储目录项记录的页有两个，即页 30 和页 32，又因为页 30 表示的目录项的主键值的范围是 [1, 320)，页 32 表示的目录项的主键值不小于 320，所以主键值为 20 的记录对应的目录项记录在页 30 中。
2. 通过目录项记录页确定用户记录真实所在的页。过程上面说过了，不再赘述
3. 在真实存储用户记录的页中定位到具体的记录。过程上面说过了，不再赘述

问：
在查询步骤的第 1 步中，我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，
如果我们表中的数据非常多，则会产生很多存储目录项记录的页，怎么根据主键值快速定位一个存储目录项记录的页呢？
答：
为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页如图所示：

我们生成了一个存储更高级目录项的页 33，这个页中的两条记录分别代表页 30 和页 32，如果用户记录的主键值在 [1, 320) 之间，则到页 30 中查找更详细的目录项记录，如果主键值不小于 320 的话，就到页 32中查找更详细的目录项记录。
随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么可以用下图来描述它：

这就是 B+ 树。
不论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到 B+ 树这个数据结构中了，所以我们也称这些数据页为节点。
从图中可以看出，我们的实际用户记录都存放在 B+ 树的叶子节点，目录项记录存放在 B+ 树的非叶子节点或者称内节点，其中 B+ 树最上边的那个节点也称为根节点。
一个 B+ 树的节点可以分成好多层，设计 InnoDB 的人为了讨论方便，规定存放用户记录的那层为第 0 层，之后依次往上加。
真实环境中一个页可以存放的记录数量是非常大的，这里假设所有存放用户记录的数据页可以存放 100 条用户记录，所有存放目录项记录的数据页可以存放 1000 条目录项记录，那么：

• 如果 B+ 树有 1 层，也就是只有 1 个用于存放用户记录的节点，最多能存放 100 条记录
• 如果 B+ 树有 2 层，最多能存放 1000 × 100 = 100000 条记录
• 如果 B+ 树有 3 层，最多能存放 1000 × 1000 × 100 = 100000000 条记录
• 如果 B+ 树有 4 层，最多能存放 1000 × 1000 × 1000×100=100000000000 条记录

所以一般情况下，我们用到的 B+ 树都不会超过 4 层，那我们通过主键值去查找某条记录最多只需要做 4 个页面内的查找（查找 3 个目录项页和 1 个用户记录页），又因为在每个页面内有 Page Directory（页目录），所以在页面内可以通过二分法实现快速定位记录。

InnoDB 的不同索引

聚簇索引

B+ 树本身就是一个目录，或者说本身就是一个索引。
它有以下两个特点：

1. 使用记录的主键值的大小进行记录和页的排序，这包括三个方面的含义：
   • 页内的记录是按照主键的大小顺序排成一个单向链表
   • 各个存放用户记录的页也是根据页中用户记录的主键的大小顺序排成一个双向链表
   • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键的大小顺序排成一个双向链表
2. B+ 树的叶子节点存储的是完整的用户记录。所谓完整的用户记录是指：这个记录中存储了所有列的值（包括隐藏列）

我们把具有这两种特性的 B+ 树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点。
这种聚簇索引并不需要我们在 MySQL 语句中显式的使用 index 语句去创建，InnoDB 会自动的创建聚簇索引。
在 InnoDB 中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

二级索引

聚簇索引只能在搜索条件是主键值时才能发挥作用，因为 B+ 树中的数据都是按照主键进行排序的。
如果想以别的列作为搜索条件，可以多建几棵 B+ 树，不同 B+ 树中的数据采用不同的排序规则。
比如：我们用 c2 列的大小作为数据页、页中记录的排序规则，再建一棵 B+ 树，效果如图所示：

这个 B+ 树与聚簇索引有以下几处不同：

• 使用记录的 c2 列的大小进行记录和页的排序，这包括三个方面的含义：
  • 页内的记录是按照 c2 列的大小顺序排成一个单向链表
  • 各个存放用户记录的页也是根据页中记录的 c2 列的大小顺序排成一个双向链表
  • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的 c2 列的大小顺序排成一个双向链表
• B+ 树的叶子节点存储的并不是完整的用户记录，只是 c2 列 + 主键这两个列的值
• 目录项记录中不再是主键 + 页号的搭配，变成了 c2 列 + 页号的搭配

所以如果现在想通过 c2 列的值查找某些记录的话，就可以使用这个 B+ 树了。
以查找 c2 列的值为 4 的记录为例，查找过程如下：

1. 确定目录项记录页根页面，也就是页 44，可以快速定位到目录项记录所在的页为页 42
2. 通过目录项记录页确定用户记录真实所在的页。在页 42 中可以快速定位到实际存储用户记录的页，但是由于 c2 列没有唯一性约束，所以 c2 列值为 4 的记录可能分布在多个数据页中，确定实际存储用户记录的页在页 34 和页 35 中
3. 在真实存储用户记录的页中定位到具体的记录。到页 34 和页 35 中定位到具体的记录。
4. 这个 B+ 树的叶子节点中的记录只存储了 c2 和主键两个列，所以必须再根据主键值去聚簇索引中查找完整的用户记录。

根据这个以 c2 列大小排序的 B+ 树只能确定我们要查找记录的主键值，所以如果我们想根据 c2 列的值查找完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程也被称为回表。
因为这种按照非主键列建立的 B+ 树需要一次回表操作才可以定位到完整的用户记录，所以这种 B+ 树也被称为二级索引 (secondary index)，或者称辅助索引。
由于我们使用的是 c2 列的大小作为 B+ 树的排序规则，所以也称这个 B+ 树为 c2 列建立的索引。

联合索引
可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，
比如：我们想让 B+ 树按照 c2 和 c3 列的大小进行排序，这个包含两层含义：

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

为 c2 和 c3 列建的索引如图所示：

我们需要注意以下几点：

• 每条目录项记录都由 c2、c3 和页号这三个部分组成，各条记录先按照 c2 列的值进行排序，如果记录的 c2 列相同，则按照 c3 列的值进行排序

• B+ 树叶子节点处的用户记录由 c2、c3 和主键 c1 列组成

  InnoDB 的B+树索引的注意事项

  根页面万年不动窝

  前边介绍 B+树索引的时候，为了方便理解，
  先把存储用户记录的叶子节点都画出来，然后接着画存储目录项记录的内节点，
  实际上 B+树的形成过程是这样的：

• 每当为某个表创建一个 B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。

最开始表中没有数据的时候，B+树索引对应的根节点中既没有用户记录，也没有目录项目录。

• 随后向表中插入用户记录时，先把用户记录存储到这个根节点页面中。
• 当根节点页面中的可用空间用完后继续插入用户记录，此时会将根节点页面中的所有记录复制到一个新分配的页 a 中，然后对这个新页进行页分裂的操作，得到另一个新页 b。

这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就
会被分配到页 a 或者页 b 中，而根节点便升级为存储目录项记录的页。
这个过程需要特别注意的是：
一个 B+树索引的根节点自诞生起，便不会再移动。
这样只要对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，
然后凡是 InnoDB 需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。

小贴士：
这个存储某个索引的根节点在哪个页面中的信息是数据字典中的一项信息 关于数据字典的内容，后边会详细介绍。

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

我们知道 B+树索引的内节点中目录项记录的内容是索引列 + 页号的搭配，
但是这个搭配对于二级索引来说有点儿不严谨。
假设 index_demo 表中的数据如下：

如果二级索引中目录项记录的内容只是索引列 + 页号搭配的话，
那么为 c2 列建立索引后的 B+树应该长这样：

如果想新插入一行记录，其中c1、c2、c3的值分别是：9、1、’c’，那么在修改这个为 c2 列建立的二级索引对应的 B+树时便碰到了问题：
由于页 3 中存储的目录项记录是由 c2 列 + 页号的值构成的，
页 3 中的两条目录项记录对应的 c2 列的值都是 1，
而我们新插入的这条记录的 c2 列的值也是 1，
那这条新插入的记录到底应该放到页 4 中，还是应该放到页 5 中？

为了让新插入记录能找到自己在哪个页里，
需要保证在 B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。
所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：索引列的值、主键值、页号
这样就能保证 B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，
所以我们为 c2 列建立二级索引后的示意图实际如下：

这样再插入记录(9, 1, ‘c’)时，由于页 3 中存储的目录项记录是由 c2 列 + 主键 + 页号的值构成的，
可以先把新记录的 c2 列的值和页 3 中各目录项记录的 c2 列的值作比较，
如果 c2 列的值相同的话，可以接着比较主键值，
因为 B+树同一层中不同目录项记录的 c2 列 + 主键的值是不一样的，所以能定位唯一的一条目录项记录。

一个页面最少存储2条记录

B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。
如果一个大的目录中只存放一个子目录呢？那就是目录层级非常多，而且最后存放真实数据的目录中只能存放一条记录。
所以 InnoDB 的一个数据页至少可以存放两条记录。

MyISAM 的索引方案

我们知道 InnoDB 中索引即数据，也就是聚簇索引的 B+树的叶子节点中包含了所有完整的用户记录，
而 MyISAM 的索引方案虽然也使用树形结构，但是却将索引和数据分开存储。
将表中的记录按照记录的插入顺序单独存储在一个文件中，称为数据文件。
这个数据文件并没有划分为若干个数据页，所有记录都存储在这一个数据文件中。
可以通过行号快速访问到一条记录。
MyISAM 记录也需要记录头信息来存储一些额外数据，
我们以上边说过的 index_demo 表为例，这个表中的记录使用 MyISAM 存储引擎在存储空间中的表示：

由于在插入数据时没有按照主键大小排序，所以并不能在这些数据上使用二分法进行查找。
使用 MyISAM 的表会把索引信息另外存储到一个称为索引文件的另一个文件中。
MyISAM 会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。
也就是先通过索引找到对应的行号，再通过行号去找对应的记录。这一点和 InnoDB 是完全不相同的。
在 InnoDB 中，只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，
而在 MyISAM 中却需要进行一次回表操作，意味着 MyISAM 中建立的索引相当于全部是二级索引。
如果有需要的话，也可以对其它的列分别建立索引或者建立联合索引，原理和 InnoDB 中的索引差不多，不过在叶子节点处存储的是相应的列 + 行号，这些索引也全部都是二级索引。

小贴士： MyISAM 的行格式有：定长记录格式 (Static)、变长记录格式 (Dynamic)、压缩记录格式 (Compressed)。 上边用到的 index_demo 表采用定长记录格式，也就是一条记录占用存储空间的大小是固定的，这样就可以轻松算出某条记录在数据文件中的地址偏移量。 但是变长记录格式就不行了，MyISAM 会直接在索引叶子节点处存储该条记录在数据文件中的地址偏移量。 通过这个可以看出，MyISAM 的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的， 反观 InnoDB 是通过获取主键之后再去聚簇索引里面找记录，虽说也不慢，但还是比不上直接用地址去访问。

InnoDB 中的索引即数据，数据即索引，而 MyISAM 中却是索引是索引、数据是数据。

MySQL 中创建和删除索引的语句

InnoDB 和 MyISAM 会自动为主键或者声明为 unique 的列自动建立 B+ 树索引，
如果想为其他列建立索引需要显式指明。
问：
为什么不自动为每个列都建立个索引？
答：
每建立一个索引都会建立一棵 B+ 树，每插入一条记录都要维护各个记录、数据页的排序关系，这很费性能和存储空间的。
可以在创建表的时候指定需要建立索引的单个列或者建立联合索引的多个列：

create table 表名 (
    各种列的信息 ··· , 
    [key|index] 索引名 (需要被索引的单个列或多个列)
)

其中的 key 和 index 是同义词，任意选用一个就可以。
可以在修改表结构的时候添加索引：
alter table 表名 add [key|index] 索引名 (需要被索引的单个列或多个列);
也可以在修改表结构时删除索引：
alter table 表名 drop [key|index] 索引名;
比如：想在创建 index_demo 表时为 c2 和 c3 列添加联合索引，建表语句如下：

create table index_demo(
    c1 int,
    c2 int,
    c3 char(1),
    primary key(c1),
    index idx_c2_c3 (c2, c3)
);

在这个建表语句中创建的索引名是 idxc2_c3，这个名称建议以 idx为前缀，后边跟着需要建立索引的列名，多个列名之间用下划线 _分隔开。

总结

1. 对于 InnoDB 存储引擎来说，在单个页中查找某条记录分为两种情况：
   • 以主键为搜索条件，可以使用 Page Directory 通过二分法快速定位相应的用户记录。
   • 以其他列为搜索条件，需要按照记录组成的单链表依次遍历各条记录。
2. 没有索引的情况下，不论是以主键还是其他列作为搜索条件，只能沿着页的双链表从左到右依次遍历各个页。
3. InnoDB 存储引擎的索引是一棵 B+树，完整的用户记录都存储在 B+树第 0 层的叶子节点，其他层次的节点都属于内节点，内节点里存储的是目录项记录。
4. InnoDB 存储引擎的索引分为两大种：
   • 聚簇索引：以主键值的大小为页和记录的排序规则，在叶子节点处存储的记录包含了表中所有的列。
   • 二级索引：以自定义的列和主键列的大小为页和记录的排序规则，在叶子节点处存储的记录内容是列 + 主键。
5. MyISAM 存储引擎的数据和索引分开存储，这种存储引擎的索引全部都是二级索引，在叶子节点处存储的是列 + 页号。