本文承接 Mysql系列（三）InnoDB存储结构之行结构和页结构 一文继续介绍Innodb引擎相关的内容。本节将介绍Innodb的索引结构。

数据库可能存在千万级的数据，必须将这些行数据以一定的结构组织起来做到高效的增删改查。下面将分别探索innodb和myisam两种引擎的索引方案。

一、InnoDB的索引方案

1、假设表初始没有记录，只有一个空页，所有记录按照主键顺序放到页中。随着记录的增长，一个页放不下所有记录，因此会分裂成多个页，每个页用双向指针链接，页与页之间形成一条双向链表。

这些页我们称为用户记录页，页内记录的字段是用户定义的字段内容。如下图所示，这是一个以 (id, key1, key2) 组成的联合索引，页10的第1条记录表示(id=1, key1=4, key2='u')。

如果Innodb表数据是按这种结构存储，那么我们只能做到“页间遍历，页内二分搜索的方式查找”。也就是说当我要查找一条id=30的数据，需要先对页10进行二分查找，没找到再从页28进行二分查找，没找到再从页9进行二分查找直到找到，效率很低。为了提高查找效率，可以为这些 用户记录页 建立 目录页。

2、目录页在页结构上 和 用户记录页 一样，目录页的行记录也是以堆的形式存储，我们称目录页的行记录为目录项，每条记录只有两个列（没有其他的隐藏列），分别是下层页中最小记录的主键 和 用户记录页的页号。根据主键值（或者索引值）查找数据时，会从最顶层的目录页开始检索，找到目录页中符合的记录后，再根据记录中的最小记录的主键 和 用户记录页的页号这两个信息，找到其对应的用户页的最小记录在磁盘中的位置。

记录头信息的record_type = 0 表示该记录是用户记录，record_type = 1 是目录项记录。

需要注意：

目录页的页内查找也是通过上节中介绍的页目录（Page Directory）进行二分查找进行检索的。

目录页内的行记录过多，一个页放不下的时候，目录页也会发生页分裂，而且目录页之间也有双向链接。

如下图所示

3、如果目录页也有多个，那么查目录也要遵循目录页间遍历查找，目录页内二分查找，为了避免目录页间的横向遍历，可以建立多层目录，顶层目录只有一个目录页。所有目录页和用户记录页形成一棵B+树：

这么一来，就可以把 页间查找 的次数压缩为树的层数，这意味着磁盘IO的次数被压缩到树的层数。一般而言，MySQL中一棵B+树不会超过4层。

Innodb规定，无论是目录页还是用户记录页，一个页至少容纳2条记录，这样做是为了控制树的高度，不让B+树的性能优势丧失。

主键索引（聚簇索引）和普通索引的区别

对于主键索引B+树而言，页内记录是按照主键大小排序的，同一层的双向链表目录页也是按照主键索引排序的。

对于二级索引B+树而言，假设该B+树是以c2字段为索引。那么

二级索引的叶子节点页的记录只有两个列：c2列 和 主键值，不含其它列和隐藏列。（重点来了）而二级索引的非叶子节点页内的记录有3个列：c2列 、 下层页号 和 主键值。

页内记录是按照 c2列和主键值 （先按c2列排序后按主键列排序）的大小排序的，页目录（Page Directory）每个槽（Slot）也是分组中拥有最大c2列值的记录的地址，目录页之间也是按照c2列和主键大小排序的。

为什么二级索引的目录页和叶子页的记录需要保存主键索引并且在二级索引值相同的情况下按主键索引排序呢？考虑一个问题，如下图所示：c1是主键，c2是普通索引。

此时 c2 字段索引的B+树如下：

此时，如果我想插入一个 c1：9、c2：1、c3：'c' 的记录，在目录页3没有存储主键值的情况下，由于目录页3的c2全都是1，所以页3无法决定该记录应该插在页4还是页5。

但如果目录页加上主键字段就可以解决这个问题：

所以，为 c2 列建立普通索引 相当于为 c2 和 主键列建 立了一个联合索引。

对于唯一二级索引来说，也可能会出现 多条记录键值相同的情况(例如NULL，以及MVCC)，所以唯一二级索引的目录项记录也会包含记录的主键值。

我们结合下面这个例子，看看innodb是如何在使用索引找到对应记录的，其中key1是普通索引。

SELECT * FROM single_table WHERE key1 = ' a ' AND id > 9000 ;

这个sql的行为如下：

1、在从key1字段的B+树最顶层目录页的记录查找，找到符合 key1 = 'a' 的记录后，根据下层页号找到下一层目录页，依此类推，最终找到符合 key1 = 'a'的叶子节点的第一条记录；

2、沿着叶子节点页的向后指针找到所有满足 key1 = 'a'  的记录，在这个过程中同时一条条的比对 id > 9000 这个条件，得到满足条件的叶子节点记录。

也就是说，id > 9000 的比较是在二级索引发生的，而不是在主键索引发生的，这样就可以减少多次回表带来的磁盘IO。

3、根据满足条件的叶子节点记录中的主键值，到主键索引B+树中查找，查找方式和前两个步骤一致。最终找到主键B+树叶子节点对应的目标记录。

主键索引和二级索引不同的一点在于，主键索引的叶子页的记录包含用户定义的所有字段，而二级索引的叶子页的记录只包含二级索引值和主键值。

联合索引的页

对于联合索引B+树（假设联合索引的字段是 c3,c4)，叶子节点页的记录会包含 c3、c4 和 主键 这3个列。

二、MyISAM的索引方案

在介绍MyISAM的索引结构之前，需要先介绍MyISAM的行格式，分为3种：定长记录（static）、变长记录（Dynamic）和压缩格式（compressed）。

MyISAM的索引和表记录是分成两个文件存储的（MYD 和 MYI）。InnoDB 和 MyISAM 都是用B+树作为索引结构。不同点在于：

1、InnoDB的表记录（包含用户定义的所有字段）是保存在主键的叶子页并通过一系列页内的数据结构维护（例如以数组为结构的页目录）。

而MyISAM的表记录是按照记录的插入顺序（而不是主键顺序）紧密的存储在MYD文件中，并没有将它们分成多个页。

如下图所示

图中是定长格式（static）的记录在 MYD 的存储方式，每一行拥有一个虚拟的逻辑行号。

2、MyISAM的B+树的叶子节点只存储索引字段的值 和 行号，InnoDB的B+树叶子节点存的是行的所有字段值。

MyISAM下，若要根据一个索引值查找一条或多条记录，需要先在MYI文件的B+数中，根据索引值找到行号，再根据行号到MYD文件找记录。

所以MyISAM的主键索引比InnoDB多了一次回表。

MyISAM的主键索引是一个二级索引而不是聚集索引。MyISAM的二级索引比InnoDB的二级索引快，因为前者直接根据行的地址到MYD文件回表，后者是根据主键值回表，这意味着要根据主键值逐层查到用户记录页的地址和行的页内地址。

在聚集索引页不在缓冲区的情况下InnoDB比MyISAM多了2~3次磁盘IO才能获得行内容。

另外，如果MyISAM使用变长格式的记录，那么MyISAM的叶子节点存储 索引字段值 和 行所在MYD的地址。

三、索引的代价

空间上，每建立一个索引就会创建一个B+树，一个索引页就是16K；

时间上，增删改需要对所有B+树操作，由于新数据添加时发生在叶子节点，因此要从根节点找到叶子节点，会涉及多次磁盘IO，B+树越多，IO次数越多。

此外DML操作可能引起页分裂、页回收，InnoDB需要额外的时间完成这些操作以维护节点和记录的排序。

最后，如果一条查询语句涉及多个索引，生成执行计划需要计算使用不同索引执行查询的成本，并选择成本最低的哪个索引执行（因为一般情况下一个查询语句最多使用一个二级索引）。建立太多索引会导致成本分析时间过长。

四、索引条件下推

所谓的索引条件下推是指在二级索引中就尽可能根据sql条件减少在二级索引匹配到的记录数，这是一种用二级索引进行范围搜索的优化，可以有效减少回表的次数。

举个例子：

有一个联合索引 key (a, b, c)，有一个sql语句：

SELECT * from t WHERE a = ' a'  AND c = 'c';

假设 满足 a = 'a' 的记录有 10 条，满足 a = 'a' and c = 'c' 的记录有5条，聚集索引 M 和联合二级索引 N 都只有3层，不考虑页缓存，请问回表次数和磁盘IO次数是多少？

查找过程如下：

1、从索引N的根节点（根目录页）开始，找到 a < 'a' 且离 a = 'a' 最近的目录项，进入下一层目录页；

2、同上操作，进入到第三层页，即叶子节点页。

3、在第三层叶子节点页页内找到 a < 'a' 且离 a = 'a'最近的记录，顺着指针在页内往下遍历；在页外顺着页间指针遍历；（如果 所有a='a' 的记录都在二级索引N的一个用户记录页，则第3步需要进行1次IO，如果是分布在2个用户记录页，则第3步需要2次IO，不会分布超过2个用户记录页的，因为满足 a='a' 的记录只有10条）。

第3步得到了 满足 a="a" 的10个主键id；

4、对着10个主键id进行回表，需要回表10次；

5、每次回表查到了完整的表记录，查看 c字段是否满足 c = 'c'；

总回表次数为10，总IO次数为（10*3 + 3~4 = 33~34）。

如果使用索引条件下推，那么在二级索引的叶子节点比对的时候，还会检查 c = 'c' 的条件，因为 N 的页的记录也包含c字段的值。所以检索完毕后可以在N的叶子节点层得到 5 个满足条件的主键，所以只会回表5次，发生 15 + 3~4 = 18~19次磁盘IO。

再例如这2个例子：

SELECT * from t WHERE a > ' a'  AND a like '%mbc';
SELECT * FROM t WHERE a = ' a ' AND id > 9000 ;

也同样会用到索引条件下推优化。

在 mysql 5.6以后，索引条件下推功能默认是开启的。

五、索引的功能

索引主要具有3个功能：高效查找、排序和分组；

在没有用到索引的情况下，只能将数据加载到内存，并在内存中排序和分组（如果中间结果太多还需要将中间结果存到磁盘中），这种情况叫做文件排序（filesort）。使用到文件排序会降低查找性能。

而使用了索引，由于记录插入B+树时本来就是按索引列的顺序插入，因此索引内的数据是有序的，查询时无需再在内存中排序或分组。

几种无法使用索引排序的情况：

1、ASC和DESC混用，即对某个字段升序排序，对另一个字段降序排序；

不过，Mysql 8.0 给出了 Descending Index 的新功能，允许联合索引的建立可以按某个字段升序，某个字段降序的方式插入。

2、order by 包含非同一个索引的列；

3、order by 包含多个是同一联合索引的列，但列的顺序不对（例如对字段A升序，对字段B降序）；

4、where 条件的索引列和排序的索引列不同，因为你无法保证 where a='xxx' 的情况下的记录 其排序字段 c 是有序的；

5、order by 对列使用函数；

六、回表的代价

回表的代价就是当执行对二级索引的范围查询时，如果查到的记录数太多，每条记录都需要在主键索引进行回表，回表一次就会在主键索引发生多次随机IO。

一次sql查询中，回表的记录（或者说次数）越少，二级索引的效率越高。

例如下面的sql语句：

SELECT * from single_table WHERE key1 > ' a ' AND key1< ' c ' ;

可以选择使用 key1 索引进行查询，也可以选择不使用 key1 索引而是直接全表扫描。

这是由查询优化器决定的，而决定的标准就是 区间 ('a', 'c') 的范围有多大，也就是取决于使用二级索引会发生回表的次数所带来的磁盘IO次数 和 全表臊面发生的磁盘IO次数哪个更多。

一般情况下，对于指定了 limit 子句的查询，优化器倾向于使用二级索引 + 回表的方式；

如果一个order by 使用了二级索引作为排序列，但是记录数太多，而且没有覆盖索引，那么mysql很可能使用 全表扫描 + 文件排序的方式也不用二级索引的排序，例如：

SELECT * from single_table order by key1 ;

七、如何善用索引

1、只为用于查询、排序和分组的列创建索引；

2、为基数大（即重复值少）的列建立索引（因为重复值多意味着回表次数多）；

3、索引列的类型尽量小（例如int类型，较短的varchar类型，能用int就不用bigint，能用tinyint就不用int），这决定了页内能容纳记录的个数（一次磁盘IO能将更多的目录项和记录加载到内存），也决定了树高；

这个建议尤其适用在主键上，因为所有二级索引的页都会存一份记录的主键值。

4、为列前缀建立索引，例如不要对一个varchar(100)的字段c1建立索引，而是对 c1的前10个字节建立索引；

原因有二：一是为了让页内能容纳更多的记录和目录项，二是字符串的比较，其复杂度会随字符串长度增加而增加；

另外需要注意：为列前缀建立索引，该索引只能用于查找，无法用于排序。例如：

ALTER TABLE single_table ADD INDEX idx_key1(key1(10));SELECT * from single_table ORDER BY key1 limit 10;

这个排序没有用到key1的索引，因为B+树只对key1的前10个字节排序了，没有给整个key1值排序；

5、覆盖索引（即避免使用*，而是在sql中注明要查询的列）：可以彻底避免回表，对于二级索引而言，覆盖索引会让优化器会选择使用二级索引而不会选择全表扫描。

6、让索引列以列名的形式在搜索条件中单独出现（别使用函数或对列计算）。

7、主键的插入尽可能按顺序插入：这是为了避免也分裂。对于二级索引，就没办法要求它的插入页按顺序了，这是业务需求决定的。

考虑一种情况：一个页按照id为 1、3、5、7、9、2、4、6、8、10的顺序插入，这会导致页分裂；

但是如果 1、2、3、4、5、6，我删除id=2的记录，再插入id=2的记录，是不会导致页分裂的，他会重新占用页内的已删除空间。

更多内容请关注微信公众号