MySQL 索引原理及设计

索引一直是数据库中非常重要的概念，所以了解索引相关的知识是转入后端开发中必不可少的一环。这篇文章是我从开始做后端开发之后至今学习关于索引知识的一个总结，从原先很多概念的模糊和不理解到现在大致有一个比较清楚的认知，尽量会把关于索引的一些点以及为什么需要这么做给解释明白，包括使用 InnoDB 引擎的 MySQL 索引的相关概念，以及如何针对 InnoDB 进行索引的设计和使用，以及三星索引的概念，会从我所了解到的知识去解释为什么需要这样，如果有错误的地方还请指出。

B+ Tree

在 InnoDB 中，索引使用的数据结构是 B+ Tree，这里的 B 是 Balance 的意思。B 类树的一个很鲜明的特点就是树的层数比较少，而每层的节点都非常多，树的每个叶子节点到根节点的距离都是相同的（这也是为什么叫 Balance Tree 的原因）。

另外，树的每一个节点都是一个数据页，这样每个节点只需要一次 IO 就可以全部读取。这样的结构保证了查询数据时能尽量少地进行磁盘 IO，同时保证 IO 的稳定性。

B+ Tree 和 B Tree 不同，B+ Tree 中，只能将数据存储在叶子结点中，内部节点将只包含指针，而 B Tree 可以将数据存储在内部的叶节点中。

因此 B+ Tree 的关键优势是中间节点不包含数据，因此 B+ Tree 的大小远小于 B Tree，并且可以将更多数据存储到存储器中。另外，B+ Tree 的每一个叶子节点包含了到相邻的节点的链接，这样可以快速地进行范围遍历。

主索引和辅助索引

在 InnoDB 存储引擎中，每一个索引都对应一棵 B+ Tree，InnoDB 的索引主要分为主索引和辅助索引：

1. 主索引：包含记录的文件按照某个 key 制定的顺序排序，这个 key 就是主索引，也就是主键，也被称为聚簇索引。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚集索引。在 InnoDB 中，主索引的叶子节点存的是整行数据，这也意味着 InnoDB 中的表一定要有一个主索引；

2. 辅助索引：某个 key 指定的顺序与文件记录的物理顺序不同，这个 key 就是辅助索引。InnoDB 中的辅助索引在叶子节点中并不存储实际的数据，只会包含主索引的值 。这就意味着如果使用辅助索引进行数据的查找，只能查到主索引，然后根据这个主索引再次扫描以下主索引的树，进行一次回表操作；

上面讲到，InnoDB 的表中要求必须有一个主键，那么可能有人会将身份证号这种唯一性的标识作为主索引，这样就大错特错了。刚刚说到主键也被称为聚簇索引，它是要按照顺序进行排序的，要求有聚簇性。如果将身份证号作为主键，不能保证每次插入的数据都是按照身份证号的顺序进行排列的，这就使得每次主键的插入都变得完全随机，可能导致每次插入一条数据都会引起页分裂的问题（这个话题在后面会讲到）。

所以在表结构定义的时候，应该使用一个具有聚集性的 key 作为主键，如果真的没有的话，可以使用一个 AUTO INCREMENT 代理键作为主索引，这样可以保证数据行是顺序写入的。如果你真的完全没有定义主键，InnoDB 会选择一个唯一的非空索引代替，但是如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚集索引。

正因为 InnoDB 索引的这种结构，产生了一些限制：

1. 如果不是按照索引的最左列开始查找，则无法使用索引；

2. 不能跳过联合索引中的某些列；

3. 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找；

以上几点也基本上代表常听到的“最左前缀”，我们通过几个例子来解释一下这个问题，可能有的情况举的例子不太恰当，但希望能说明白想说出的问题。假设我们有一个 employees 表，表结构如下：

Column

Type

Usage

Index

id	bigint	Primary Key	primary_index
employee_id	varchar(10)	员工编号	employee_id_index
name	varchar(20)	姓名	name_age_gender_index
age	int	年龄	name_age_gender_index
gender	int	性别	name_age_gender_index

这个表中我们有 (name, age, gender) 这个联合索引，这个索引的结构大概如下图所示：

在上面的叶子节点下，假设有多个名为 BX 和 iCell 的员工，他们的年龄都不太一样，是先按照 name 排序，再按照 age 进行排序。

查询 1:

	SELECT * FROM employees 
WHERE name='BX' AND age=19 AND gender=0;

上述这种查询，根据 (name, age, gender) 这个索引树来查找，找到 id 为 2 的索引数据符合条件，然后通过相邻的节点链接继续查找，发现下一个数据不符合条件，最终命中索引的就是 id 为 2 的这一条数据，因为是要查找行的所有数据，所以再根据 id 为 2 去主键索引树中继续回表查找，得到结果数据。

查询 2:

	SELECT * FROM employees WHERE name='iCell';

根据 (name, age, gender) 这个索引树来查找，找到 id 为 3 的索引数据符合条件，然后通过相邻的节点链接继续查找，发现下一个数据也符合条件，继续根据节点链接查找，直到发现数据已经不符合条件了，于是命中索引的就是 id 为 3，4，5 的几条数据，然后继续根据这几个 id 值进行回表操作，得到结果数据。

查询 3:

	SELECT * FROM employees WHERE age=17;

根据“最左前缀”原则，并不存在 age 为前缀的索引，所以这个查询无法使用 (name, age, gender) 这个索引树进行数据查找，得去主索引中进行全表扫描，这无非是非常慢的。所以如果想让这个查询命中索引，得单独为 age 添加索引或者添加 age 为前缀的联合索引。或者，这类情况还有一种方法，就是给跳过的索引列使用 IN 的查询方式让其发生“最左前缀”匹配，但是在这里 name 这个字段不适合用 IN 这种查询方法。

查询 4:

	SELECT * FROM employees 
WHERE name like 'B%' AND age=17;
SELECT * FROM employees 
WHERE name='iCell' AND age > 18 AND gender=1;

由于 B+ Tree 的限制，当查询中出现有某个列的范围查询，则这个范围查询后面的列都无法使用索引。上面的查询中，like B%和 age > 18都是范围查询，所以后面的查询不能通过索引树来直接查找。

对于此种情况，MySQL 5.6 版本增加了 Index Condition Pushdown 技术，如果查询中 where 语句可以使用索引中已有的字段（比如这里就是 name，age， gender），在遍历索引时对这些字段先做判断直接过滤掉不满足条件的值，减少引擎层访问表的次数和 MySQL Server 层访问存储引擎的次数。但是这种技术跟“最左前缀”并无冲突，只是做了数据过滤的优化。

查询 5:

	SELECT * FROM employees WHERE employee_id=11;

注意看之前的数据表定义，employee_id 是 varchar 类型，但这个查询语句中将其与数字类型做比较，这时候会触发 MySQL 的隐式类型转换，将字符串转换成数字进行比较，也就是说上述的语句相当于：

	SELECT * FROM employees 
WHERE CAST(employee_id AS int)=11;

也就是说，在这个查询中对索引字段做了函数操作，而这样的话会破坏索引值的有序性，于是不会命中索引，转而进行全表扫描。

查询 6:

	SELECT age, gender FROM employees WHERE name='iCell';

这种情况类似于查询 2 中所举的例子，但是这个查询的结果要求只返回 age 和 gender，而 age 和 gender 的值是包含在索引中的，这样就可以直接返回而不用再进行回表查询了。如果一个索引包含所有需要查询的字段的值，则为覆盖索引，使用覆盖索引不需要进行回表操作，能增加数据查询效率

ORDER BY 如何使用索引

要说 ORDER BY 如何利用索引进行排序，得先弄清楚 ORDER BY 本身是如何进行排序的。在 MySQL 中，会给每个线程分配一块内存空间 buffer 用于排序，还有一个参数叫做 max_length_for_sort_data，这个参数作用是用来规定排序返回行的字段长度，默认值是 1024，最小值为 4，如果排序返回行的字段长度没有超过这个参数的值，就会使用一次访问排序，否则使用二次访问排序。

现在我们还是通过上面这张 employees 表来说明问题，有以下语句：

	SELECT name, age, employee_id FROM employees 
WHERE name='iCell' ORDER BY employee_id;

现在我要查的排序的返回字段只包括 name, age 和 employee_id，在默认情况下肯定不会超过 1024，所以会使用一次访问排序，流程如下：

1. 初始化 buffer

2. 根据最左匹配原则命中 name 为 'iCell' 的值，根据辅助索引找出主键 id；

3. 根据主键 id 取出整行的值，然后将 name, age 和 employee_id 这三个返回列的的值存入到 buffer 中；

4. 重复以上 2 和 3 的步骤，直到不再满足查询条件为止；

5. 对 buffer 中的数据根据 employee_id 进行排序；

6. 将排序结果返回；

那么假设我现在的 max_length_for_sort_data 的值很小，要查询的返回子段长度超过了这个值，那就会使用二次访问排序，流程如下：

1.初始化 buffer

2.根据最左匹配原则命中 name 为 'iCell' 的值，根据辅助索引找出主键 id；

3.根据主键 id 取出整行的值，然后将排序行 employee_id 以及 primary key 的值存入到 buffer 中；

4.重复以上 2 和 3 的步骤，直到不再满足查询条件为止；

5.对 buffer 中的数据根据 employee_id 进行排序；

6.根据排序结果中的 primary key，就会回表操作，并将最终结果返回；

以上两种排序，无非是 MySQL 认为内存够不够用，够用的话就多利用内存而避免过多的回表操作从而增加磁盘访问。那如果排序申请的内存空间不过用了怎么办？参数 sort_buffer_size 就是控制排序内存空间大小的，如果内存不够用，就会使用磁盘临时文件做外部归并排序。

知道了以上排序操作，再结合之前覆盖索引以及 B+ Tree 索引的逻辑，是不能就有办法去优化 ORDER BY 的流程了。首先，不管是一次访问排序还是二次访问排序，都要在 buffer 对数据做排序操作，而 B+ Tree 本身的叶子结点就是有序排列的，所以只要能做到排序行也能按照最左匹配原则匹配到索引，就可以避免内存排序的步骤了。另外，上述的排序步骤中还需要进行回表操作，那么只要查询的语句能命中覆盖索引，是不是就能够避免回表操作了。进一步，如何可以使用同一个索引既满足排序又用于查找行那就相当不错了。

三星索引

在《高性能 MySQL》书中提到了一本书叫《Relational Database index design and the optimizers》，书中有一个概念是“三星索引”，它是这样定义的：

1. 满足第一颗星：取出 WHERE 语句后的相关的列，将这些列作为索引最开始的列，这样可以利用索引来尽可能的过滤不必要的数据，减少数据处理的规模；

2. 满足第二颗星：将 ORDER BY 列加入到索引中，不改变这些列的顺序，不考虑第一颗星已经出现的列，利用索引进行排序；

3. 满足第三颗星：将查询语句中剩余的列加到索引中去，达到覆盖索引的效果。

但是三星索引往往是理想中的情况，现实状况下往往会同时有范围查询和排序的需求出现，这样就很难同时满足第一颗星和第二颗星，比如下列语句：

	SELECT name, age FROM employees 
WHERE age BETWEEN 15 AND 30 
AND gender=1 ORDER BY name;

根据以上 SQL 建立索引，会出现两种情况：

第一种情况的索引为 (age, gender, name)：

1. 满足第一颗星：将 age 和 gender 放入索引中，这样满足 WHERE 后有一个索引列和一个过滤列；

2. 无法满足第二颗星：age 是范围查询，此时的 gender 并不是有序的；

3. 满足第三颗星：将查询列 name 放入索引中；

第二种情况的索引为 (gender, name, age):

1. 不满足第一颗星：只能匹配到 gender 索引列；

2. 满足第二颗星：gender 相等的前提下，name 是有序排列的；

3. 满足第三颗星：将查询列 age 放入索引中；

关于三星索引的概念这里只是简单地举例子说明，之后会对 “Relational Database index design and the optimizers” 书中提到的一些索引优化的例子做更多的说明。

页分裂

前面说到，InnoDB 中数据是存储在数据页中的，而数据是按照索引的顺序插入到数据页中的，所以数据是紧凑排序的，但如果随机对数据进行插入，就有可能导致数据页分裂的问题。

假设一个数据页只能存储 3 条数据，且已经有 3 条数据（100， 200， 300）了，这时候想插入一条 150 的数据，就会再申请一个新的数据页，100，150 两条数据存放在原来的数据页中，200 和 300 存放在新的数据页中，这样可能会存在数据页利用率不高的问题。

不仅仅是插入数据会导致上述问题，删除数据也会。这里要注意，如果删除掉了一个数据页中的某条数据，这条数据所留下的位置并不会缩小而是等待复用，如果是一整个页的数据被删除了，那这个页也是出于被复用状态。如果相邻的两个数据页的利用率很小，系统会把这两个页的数据合到其中一个页上，另一个页就处于可被复用的状态。所以通过 delete 删除数据并不会回收表空间。

为了解决频繁删除数据导致的没有回收表空间的问题，可以通过重建表来解决，比如以下命令：

	alter table table_name engin=InnoDB;

这个命令的流程基本上是：

1. 新建一个临时表，结果同原表相同；

2. 按照主键 id 递增的顺序将数据从原表读出插入到新表中；

3. 用新的表替换旧表，删除旧表；

所以我们使用 AUTO INCREMENT 主键的插入数据模式，正符合了递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。

原文链接:http://www.phpxs.com/post/6316/
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有