高级篇 - 索引 - 《MySQL 实战读书笔记》

概述
索引结构
索引中用到的数据结构（常见模型）
索引分类
- 聚集索引&二级索引
索引语法
最左前缀法则
索引失效的情况
覆盖索引
前缀索引
单列索引与联合索引
索引设计原则

概述

索引（index）是帮助MySQL高效获取数据的数据结构(有序)。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

索引结构

MySQL的索引是在存储引擎层实现的，不同的存储引擎有不同的索引结构，主要包含以下几种：

索引结构	描述
B+Tree索引	最常见的索引类型，大部分引擎都支持 B+ 树索引
Hash索引	底层数据结构是用哈希表实现的, 只有精确匹配索引列的查询才有效, 不支持范围查询
R-tree(空间索引）	空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少
Full-text(全文索引)	是一种通过建立倒排索引,快速匹配文档的方式。类似于Lucene,Solr,ES

上述是MySQL中所支持的所有的索引结构，接下来，我们再来看看不同的存储引擎对于索引结构的支持情况。

索引	InnoDB	MyISAM	Memory
B+tree索引	支持	支持	支持
Hash 索引	不支持	不支持	支持
R-tree 索引	不支持	支持	不支持
Full-text	5.6版本之后支持	支持	不支持

索引中用到的数据结构（常见模型）

Hash

哈希索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中。

如果两个(或多个)键值，映射到一个相同的槽位上，他们就产生了hash冲突（也称为hash碰撞），可以通过链表来解决。

特点：
A. Hash索引只能用于对等比较(=，in)，不支持范围查询（between，>，< ，…）
B. 无法利用索引完成排序操作
C. 查询效率高，通常(不存在hash冲突的情况)只需要一次检索就可以了，效率通常要高于B+tree索引

有序数组

搜索树

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。
假如说MySQL的索引结构采用二叉树的数据结构，比较理想的结构如下：

如果主键是顺序插入的，则会形成一个单向链表，结构如下：

所以，如果选择二叉树作为索引结构，会存在以下缺点：

顺序插入时，会形成一个链表，查询性能大大降低。
大数据量情况下，层级较深，检索速度慢。

此时，我们可以选择红黑树，红黑树是一颗自平衡二叉树，那这样即使是顺序插入数据，最终形成的数据结构也是一颗平衡的二叉树,结构如下:

但是，即使如此，由于红黑树也是一颗二叉树，所以也会存在一个缺点：

大数据量情况下，层级较深，检索速度慢。

所以，在MySQL的索引结构中，并没有选择二叉树或者红黑树，而选择的是B+Tree，那么什么是B+Tree呢？在详解B+Tree之前，先来介绍一个B-Tree。

B树

B-Tree，B树是一种多叉路衡查找树，相对于二叉树，B树每个节点可以有多个分支，即多叉。
以一颗最大度数（max-degree）为5(5阶)的b-tree为例，那这个B树每个节点最多存储4个key，5个指针：

知识小贴士：树的度数指的是一个节点的子节点个数。

B+树

B+Tree是B-Tree的变种，我们以一颗最大度数（max-degree）为4（4阶）的b+tree为例，来看一
下其结构示意图：

我们可以看到，两部分：

绿色框框起来的部分，是索引部分，仅仅起到索引数据的作用，不存储数据。
红色框框起来的部分，是数据存储部分，在其叶子节点中要存储具体的数据。

MySQL中优化之后的B+Tree。

MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能，利于排序。

为什么实际上大多数的数据库存储却并不使用二叉树？

树可以有二叉，也可以有多叉。
多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。
二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。
其原因是，索引不止存在内存中，还要写到磁盘上。
你可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

索引分类

在MySQL数据库，将索引的具体类型主要分为以下几类：主键索引、唯一索引、常规索引、全文索引。

聚集索引&二级索引

在InnoDB存储引擎中，根据索引的存储形式，又可以分为以下两种：

聚集索引选取规则：

如果存在主键，主键索引就是聚集索引。
如果不存在主键，将使用第一个唯一（UNIQUE）索引作为聚集索引。
如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引。

聚集索引和二级索引的具体结构如下：

聚集索引的叶子节点下挂的是这一行的数据。
二级索引的叶子节点下挂的是该字段值对应的主键值。

回表查询：这种先到二级索引中查找数据，找到主键值，然后再到聚集索引中根据主键值，获取数据的方式，就称之为回表查询。

思考题：以下两条SQL语句，那个执行效率高? 为什么? A. select from user where id = 10 ; B. select from user where name = ‘Arm’ ; 备注: id为主键，name字段创建的有索引；解答： A 语句的执行性能要高于B 语句。因为A语句直接走聚集索引，直接返回数据。而B语句需要先查询name字段的二级索引，然后再查询聚集索引，也就是需要进行回表查询。

思考题： InnoDB主键索引的B+tree高度为多高呢? 假设: 一行数据大小为1k，一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间，主键即使为bigint，占用字节数为8。高度为2： n 8 + (n + 1) 6 = 161024 , 算出n约为 1170 1171 16 = 18736 也就是说，如果树的高度为2，则可以存储 18000 多条记录。高度为3： 1171 1171 16 = 21939856 也就是说，如果树的高度为3，则可以存储 2200w 左右的记录。

索引语法

创建索引

CREATE [ UNIQUE | FULLTEXT ] INDEX index_name ON table_name ( index_col_name,… ) ;
查看索引

SHOW INDEX FROM table_name ;
删除索引

DROP INDEX index_name ON table_name ;

最左前缀法则

如果索引了多列（联合索引），要遵守最左前缀法则。最左前缀法则指的是查询从索引的最左列开始，并且不跳过索引中的列。如果跳跃某一列，索引将会部分失效(后面的字段索引失效)。
注意：最左前缀法则中指的最左边的列，是指在查询时，联合索引的最左边的字段(即是
第一个字段)必须存在，与我们编写SQL时，条件编写的先后顺序无关。

索引失效的情况

范围查询

联合索引中，出现范围查询(>,<)，范围查询右侧的列索引失效。
所以，在业务允许的情况下，尽可能的使用类似于 >= 或 <= 这类的范围查询，而避免使用 > 或 <。

索引列运算

不要在索引列上进行运算操作，索引将失效。

字符串不加引号

字符串类型字段使用时，不加引号，索引将失效。
如果字符串不加单引号，对于查询结果，没什么影响，但是数据库存在隐式类型转换，索引将失效。

模糊查询

如果仅仅是尾部模糊匹配（%加在关键字之后），索引不会失效。如果是头部模糊匹配（%加在关键字之前），索引失效。
在like模糊查询中，在关键字后面加%，索引可以生效。而如果在关键字前面加了%，索引将会失效。

or连接条件

用 or 分割开的条件，如果 or 前的条件中的列有索引，而后面的列中没有索引，那么涉及的索引都不会被用到。
当 or 连接的条件，左右两侧字段都有索引时，索引才会生效。

数据分布影响

如果MySQL评估使用索引比全表更慢，则不使用索引。

select * from tb_user where phone >= '17799990005';
select * from tb_user where phone >= '17799990015';

经过测试我们发现，相同的SQL语句，只是传入的字段值不同，最终的执行计划也完全不一样，这是为什么呢？
就是因为MySQL在查询时，会评估使用索引的效率与走全表扫描的效率，如果走全表扫描更快，则放弃索引，走全表扫描。因为索引是用来索引少量数据的，如果通过索引查询返回大批量的数据，则还不如走全表扫描来的快，此时索引就会失效。
一模一样的SQL语句，先后执行了两次，结果查询计划是不一样的，为什么会出现这种现象，这是和数据库的数据分布有关系。查询时MySQL会评估，走索引快，还是全表扫描快，如果全表扫描更快，则放弃索引走全表扫描。因此，is null 、is not null是否走索引，得具体情况具体分析，并不是固定的。

覆盖索引

尽量使用覆盖索引，减少select 。那么什么是覆盖索引呢？ *覆盖索引是指查询使用了索引，并且需要返回的列，在该索引中已经全部能够找到。
接下来，我们来看一组SQL的执行计划，看看执行计划的差别，然后再来具体做一个解析。

explain select id, profession from tb_user where profession = '软件工程' and age =
31 and status = '0' ;
explain select id,profession,age, status from tb_user where profession = '软件工程'
and age = 31 and status = '0' ;
explain select id,profession,age, status, name from tb_user where profession = '软
件工程' and age = 31 and status = '0' ;
explain select * from tb_user where profession = '软件工程' and age = 31 and status
= '0';

上述这几条SQL的执行结果为:

从上述的执行计划我们可以看到，这四条 SQL 语句的执行计划前面所有的指标都是一样的，看不出来差异。但是此时，我们主要关注的是后面的 Extra，前面两条 SQL 的结果为 Using where; Using Index ; 而后面两条 SQL 的结果为: Using index condition 。

因为，在tb_user表中有一个联合索引 idx_user_pro_age_sta，该索引关联了三个字段
profession、age、status，而这个索引也是一个二级索引，所以叶子节点下面挂的是这一行的主键 id。所以当我们查询返回的数据在 id、profession、age、status 之中，则直接走二级索引直接返回数据了。如果超出这个范围，就需要拿到主键 id，再去扫描聚集索引，再获取额外的数据了，这个过程就是回表。而我们如果一直使用 select * 查询返回所有字段值，很容易就会造成回表查询（除非是根据主键查询，此时只会扫描聚集索引）。
为了大家更清楚的理解，什么是覆盖索引，什么是回表查询，我们一起再来看下面的这组SQL的执行过程。

A. 表结构及索引示意图:

id 是主键，是一个聚集索引。 name 字段建立了普通索引，是一个二级索引（辅助索引）。

B. 执行SQL : select * from tb_user where id = 2;

根据 id 查询，直接走聚集索引查询，一次索引扫描，直接返回数据，性能高。

C. 执行SQL：selet id,name from tb_user where name = ‘Arm’;

虽然是根据name字段查询，查询二级索引，但是由于查询返回在字段为 id，name，在name的二级索引中，这两个值都是可以直接获取到的，因为覆盖索引，所以不需要回表查询，性能高。

D. 执行SQL：selet id,name,gender from tb_user where name = ‘Arm’;

由于在 name 的二级索引中，不包含 gender，所以，需要两次索引扫描，也就是需要回表查询，性能相对较差一点。

思考题：一张表, 有四个字段(id, username, password, status), 由于数据量大, 需要对以下SQL语句进行优化, 该如何进行才是最优方案: select id,username,password from tb_user where username =’itcast’;

答案: 针对于 username, password建立联合索引, sql为: create index idx_user_name_pass on tb_user(username,password); 这样可以避免上述的SQL语句，在查询的过程中，出现回表查询。

前缀索引

当字段类型为字符串（varchar，text，longtext等）时，有时候需要索引很长的字符串，这会让索引变得很大，查询时，浪费大量的磁盘 IO，影响查询效率。此时可以只将字符串的一部分前缀，建立索引，这样可以大大节约索引空间，从而提高索引效率。

语法

create index idx_xxxx on table_name(column(n)) ;

示例 : 为 tb_user 表的 email 字段，建立长度为5的前缀索引。 create index idx_email_5 on tb_user(email(5));

前缀长度

可以根据索引的选择性来决定，而选择性是指不重复的索引值（基数）和数据表的记录总数的比值，索引选择性越高则查询效率越高，唯一索引的选择性是1，这是最好的索引选择性，性能也是最好的。

select count(distinct email) / count() from tb_user ; select count(distinct substring(email,1,5)) / count() from tb_user ;

前缀索引的查询流程

单列索引与联合索引

单列索引：即一个索引只包含单个列。
联合索引：即一个索引包含了多个列。

在业务场景中，如果存在多个查询条件，考虑针对于查询字段建立索引时，建议建立联合索引，而非单列索引。

如果查询使用的是联合索引，具体的结构示意图如下：

索引设计原则

针对于数据量较大，且查询比较频繁的表建立索引。
针对于常作为查询条件（where）、排序（order by）、分组（group by）操作的字段建立索引。
尽量选择区分度高的列作为索引，尽量建立唯一索引，区分度越高，使用索引的效率越高。
如果是字符串类型的字段，字段的长度较长，可以针对于字段的特点，建立前缀索引。
尽量使用联合索引，减少单列索引，查询时，联合索引很多时候可以覆盖索引，节省存储空间，避免回表，提高查询效率。
要控制索引的数量，索引并不是多多益善，索引越多，维护索引结构的代价也就越大，会影响增删改的效率。
如果索引列不能存储 NULL 值，请在创建表时使用 NOT NULL 约束它。当优化器知道每列是否包含 NULL 值时，它可以更好地确定哪个索引最有效地用于查询。