MySQL索引

1.索引含义

1.1 索引图解

​ 数据库索引是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询，更新数据库表中数据。

​ 数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。如果没有索引的话，我们要从500万行数据里面检索一条数据，只能一次遍历这张表的全部数据，直到找到这条数据。但是有了索引后，只需要在索引中去检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址，就可以拿到数据了。

1.2 索引类型

​ 打开navicat工具，右键设计表，在索引的这个选项卡里面，可以创建索引。

​ 在InnoDB中，索引类型有三种：普通索引，唯一索引（主键索引是特殊的唯一索引），全文索引。

​ 普通（Normal）：也叫非唯一索引，是最普通的索引，没有任何限制。

​ 唯一（Unique）：唯一索引要求键值不能重复，另外注意的是，主键索引是一种特殊的唯一索引，它还多了一个限制条件是键值不能为空。主键索引引用primary key创建。

​ 全文（Fulltext）：针对比较大的数据，比如我们存放的是消息内容，一篇文章，有几KB的数据的这种情况，如果要解决like查询在全文匹配时效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如char，varchar，text。

create table 'fulltext_test' (
	'content' varchar(50) default null,
    FULLTEXT KEY 'content'('content')
)

select * from fulltext_test where match(content) against('咕泡学院'IN NATURAL LANGUAGE MODE)

​ MyISAM和InnoDB支持全文索引。

2. 索引存储模型推演

2.1 二分查找（折半查找）

​ 每一次查找，都把候选数据缩小了一半，如果数据排过序的话，这种效率更高。所以第一个，我们可以考虑用有序数组作为索引的数据结构。有序数组的等值查询和比较查询效率非常高，但是更新数据时会出现一个问题，可能要挪动大量的数据（改变index），所以只适合存储静态的数据。为了支持频繁的修改，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。所以为了解决这个问题出现二叉查找树BST（Binary Search Tree）出现了。

2.2 二叉查找树

​ 二叉查找树的特点：左子树节点都小于父节点，右子树节点都大于父节点。投影到平面就是一个有序的线性表。

​ 二叉查找树既能够实现快速查找，又能实现快速插入，但是它有个问题：它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成O(n)。还是刚才这一批数字，如果插入的数据刚好是有序的，它就会变成链表（斜树），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

2.3 平衡二叉树(AVL Tree)(左旋右旋)

​ 平衡二叉树解决了二叉树平衡的问题。索引必须要存你建立的字段的值，叫做键值，比如id的值。还要存完整记录在磁盘上的地址。由于AVL是二叉树，所以还要额外的存储左右子树的指针。

如图：

第一个是索引的键值，比如我们在id上面创建了一个索引，我在用where id = 1的条件查询时就会找到索引里面的id的这个键值。

第二个是数据的磁盘地址，因为索引的作用就是去查找数据存放的地址。

第三个，因为是二叉树，它必须还要有左右子节点的引用，这样我们能才能找到下个子节点。

​ 当用树的结构了存储索引时，访问一个节点就要和磁盘间发生一次io操作。InnoDB操作磁盘的最小单位是一页（或者叫一个数据块，大小是16K）。那么，一个树的结点必须设计成16K的大小，不然就会出现读不完或者读不够的情况。如果一个节点只存一个键值+数据+引用，可能只用了十几个或者几十个字节，远远达不到16K的容量。我们基于索引查找数据时，肯定是希望一次从磁盘中加载很多的数据到内存中，如果一个节点只存1个这样的单元，就需要读更多的节点，发生更多的IO。

怎么解决这个问题？第一， 让每个节点存储更多的数据。第二， 节点上的关键字的数量越多，我们的指针数也越多，也就是有更多的分叉（路数），因为分叉越多，树的深度就会减少（根节点是0）。这样树的样子就从高瘦变成矮胖了。这时，时就变成多叉（多路）。

2.4 多路平衡查找树(B Tree)(分裂合并)

​ Balance Tree，跟AVL树一样，B树在节点上存储键值，数据地址，节点引用。它有一个特点：分叉数（路数）永远比关键字数多1，比如下面这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。

B Tree的查找规则是什么样的？

比如要找15：因为15<17，走左边；15>12，走右边，在磁盘7里找到了15，只用了3次IO。

B Tree是怎样保持平衡的，和AVL有什么区别？

当路数为3时，我们插入3的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字，意味着有4个指针，子节点就会变成4格，所以这个时候就需要分裂。把中间数据2提上去，把1和3变成2的子节点。如果删除节点，会有相反的合并的操作（注意这里的合并和分裂跟AVL中的左右旋是不一样的）。从这里可以看到，在更新索引时会有大量的索引结构的调整，所以解释我们不要在频繁更新的列上加索引，或者不要更新主键。

节点的分裂和合并，其实就是InnoDB页的分裂和合并。如果索引键值有序，写满一页接着开辟一个新的页，如果索引值无序，存储过程中造成大量的磁盘碎片，带来频繁的page分裂和合并。

2.5 B+树(加强版多平衡查找树)

B+树的存储结构。

B+树的特点：

1.它的关键字的数量和路数时相等的

2.B+树的根节点和枝节点都不会存储数据，只有叶子节点才存储数据，搜索到关键字不会直接返回，会到最后一层的叶子节点才会返回数据。

3.B+树的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表，方便范围查询。

总结一下，InnoDB的B+tree特性带来的优势：

1. 它是B Tree的变种，B Tree能解决的问题，它都能解决（每个节点存储更多的关键字；路数更多），

2. 扫库，扫表能力强（如果我们要对全表进行扫描，只需要遍历叶子节点就可以了，不需要便利整课B+树拿数据）。

3. B+树的磁盘读写能力比B树更强（根节点不保存数据，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）。

4. 排序能力更强（因为叶子节点有下一个数据区的指针，数据形成了链表）

5. 效率更加稳定（B+tree永远只在叶子节点拿数据，所以IO次数时稳定的）。

2.6 为什么不用红黑树？

红黑树也是BST树，但是不是严格平衡的，通过变色和旋转来保持平衡，必须满足5个约束：

1. 节点为红色或者黑色

2. 根节点必须是黑色的

3. 叶子节点都是黑色的null节点

4. 红色节点的两个子节点都是黑色（不允许两个相邻的红色节点）。

5. 从任意节点出发，到每个叶子节点的路径中包含相同数量的黑色节点。

基于以上节点，可以推导出：从根节点到叶子节点的最长路径（红黑相同的路径）不大于最短路径（全部是黑色节点）的2倍。

为什么不用红黑树？1，只有两路。2，不够平衡。红黑树一般在内存里运用。

2.7 Hash索引

HASH：以KV的形式检索数据，也就是说，它会根据字段生成哈希码和指针，指针指向数据。

Hash索引的特点：

1. 它的时间复杂度是O(1)，查询速度比较快。因为哈希索引里面的数据不是按顺序存放的，所以不能用于排序。

2. 我们在查询数据时要根据键值计算哈希码，所以它只能支持等值查询，不支持范围查询。

3. 如果字段重复值很多的时候，会出现大量的哈希冲突（采用拉链法解决）效率会降低。

​ 在InnoDB中，不能显示的创建一个哈希索引（所谓的支持哈希索引指的是AHI,自适应哈希，它是InnoDB自动为buffer pool中的热点页创建的索引）。Memory存储引擎中可以使用Hash索引。

3 B+Tree的落地形式

​ MySQL的数据都是文件形式存放在磁盘的，可以找到这个目录。

show variables like 'datadir';

​ 每个数据库都有一个目录，主要关注一下最长用的两个存储引擎，MyISAM和InnoDB的索引的实现。InnoDB的表有两个文件（.frm和.ibd），MyISAM的表有三个文件（.frm，.MYD, .MYI）。其中.frm是Mysql数据库中定义表结构的文件，每一种存储引擎都有。

3.1 MyISAM

在MyISAM中有另外两个文件，数据和索引是两个独立的文件：

​ 1.MYD文件，D代表数据，是一个数据文件。

​ 2.MYI文件，I代表index，是索引文件，存放索引

​ MyISAM的B+Tree中，叶子节点存储的是数据文件对应的磁盘地址。从索引文件中找到键值后，会到数据文件中获取相应的数据记录。

​ 在MyISAM中，其他索引也在MYI文件中，非主键索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件中找到磁盘地址，然后到数据文件中获取数据。

3.2 InnoDB

​ 在InnoDB的某个索引的叶子节点上，直接存储了我们的数据。所以，为什么说在InnoDB中索引即数据，数据即索引，就是这个原因。

​ 但是有一个问题，一张InnoDB表可能有很多索引，数据肯定只有一份，那数据是在哪个索引的叶子节点上呢？

​ 这里要介绍一个叫做聚集索引（聚簇索引）的概念，就是索引键值的逻辑顺序和表数据行的物理存储顺序是一致的。

​ InnoDB组织数据的方式就是（聚集）索引组织表（clustered index organize table）。如果说一张表创建了主键索引，那么这个主键索引就是聚集索引，决定数据行的物理存储顺序。

​ 问题来了，那聚集索引之外的索引，会不会也把完整记录在叶子节点放一份呢？并不会，因为这回带来额外的存储空间浪费和计算损耗。那他们的叶子节点上没有数据怎么检索完整的数据呢？比如我们在name字段上建立的普通索引。

​ InnoDB中，主键索引和辅助索引是由一个主次之分的，如果有主键索引，那么主键索引就是聚集索引，其他的索引统称为“二级索引”（secondary index）。二级索引存储的是二级索引的键值，而叶子节点存的是这条记录对应的主键的值，所以，二级索引检索数据的流程是这样的：

​ 当我们用name索引查询一条记录，它会在二级索引的叶子节点找到name=qingshan，拿到主键值，也就是id=1，然后再到主键索引的叶子节点拿到数据。

​ 为什么不存地址而是存键值？因为地址会变化。从这个角度来说，因为主键索引比二级索引少扫描了一棵B+Tree（避免了回表），所以它的速度相对快一些。

​ 但是，如果一张表没有主键怎么办？那完整的记录放在哪个索引的叶子节点？或者这张表根本没有索引呢？数据放在哪里？

​ 1.如果我们定义了主键（primary key），那么InnoDB会选择主键作为聚集索引。

​ 2.如果没有显示定义主键，则InnoDB会选择第一个不包含有null值得唯一索引作为主键索引。

​ 3.如果也没有这样得一个唯一索引，InnoDB会选择内置6字节长得ROWID作为隐藏得聚集索引，它会随着行记录得写入而主键递增。

4 索引使用原则

4.1 列的离散度

​ 列的离散度，定义公式：count(distinct(column_name)):count(*)，列的全部不同值和所有数据行的比例，数据行相同的情况下，分子越大，列的离散度越高。简单来说，如果列的重复值越多，离散度度劫越低，重复值越多，离散度就越高。我们不建议在离散度低的字段上，如果B+Tree中的重复值太多，MySQL的优化器发现走索引跟使用全表扫描差不多，就算建立了索引，也不一定会走索引。

4.2 联合索引最左匹配原则

​ 前面都是针对单列创建的索引，但有时我们的多条件查询的时候，也会建立联合索引。单列索引也可以看作是特殊的联合索引。如果我们创建三个字段的联合索引index(a, b, c)，相当于创建了三个索引：index(a), index(a, b), index(a, b, c)；

4.3 覆盖索引

​ 回表：非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引中没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表。在二级索引中，不管单列索引还是联合索引，如果select的数据列只用从索引中就能取得，不必从数据区中读取，这时使用的索引叫做覆盖索引，这样避免了回表。很明显，因为覆盖索引减少了IO次数，减少了数据的访问量，可以大大提高查询效率。

4.4 索引条件下推（ICP）

​ 索引条件下推（index condition pushdown），5.6后完善的功能。只适用于二级索引。ICP的目标是减少访问表的完整行的读数量从而减少IO操作。这里说的下推，其实意思是把过滤的动作在存储引擎做完，而不需要到Server层过滤。来看这么一张表。在last_name和first_name上面创建联合索引。

drop table employees;
create table 'employees' (
	'emp_no' int(11) NOT NULL,
    'birth_date' date NULL,
    'first_name' varchar(14) NOT NULL,
    'last_name' varchar(16) NOT NULL,
    'gender' enum('M','f') NOT NULL,
    'hire_date' date NULL,
    primary key ('emp_no')
) engine=InnoDB default charset=latinl;

alter table employees add index idx_lastname_firstname(last_name,first_name);

insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(1,null,'689','liu','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(2,null,'431','afdu','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(3,null,'3424','fdasfng','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(4,null,'41z','fdasfg','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(5,null,'41zz','wfdasf','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(6,null,'41zz','wang','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(7,null,'41zz','wang','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(8,null,'41zzi','wang','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(9,null,'41zi','gda','F',null);
insert into 'employees'('emp_no','birth_date','first_name','last_name','gender','hire_date') values(10,null,'4i','qafd','F',null);

现在查询所有姓wang，并且最后一字是zi的员工。查询的sql：

select * from employees where last_name='wang' and last_name='%zi';

​ 正常来说，因为字符是从左往右排序的，当你把%加在前面时，是不能基于索引去比较的，所以只有last_name这个字段能够用于索引比较和过滤。所以查询过程是这样的：

​ 1）根据联合索引查出所有姓wang的二级索引数据（3个主键6，7，8）

​ 2）回表，到主键索引上查询全部符合条件的数据（3条数据）

​ 3）把这3台哦数据返回到Server层，在Server层过滤出名字以zi结尾的员工。

​ 注意，索引的比较是在存储引擎中进行的，数据记录的比较是在Server中进行的。而当first_name的条件不能用于索引过滤时，Server层不会把first_name的条件传递给存储引擎，所以读取了两条没用的记录。这时，如果满足last_name=‘wang’的记录有10万条，就会有99999条没有必要读取的记录。所以，根据first_name字段过过滤的动作，能不能再存储引擎层完成呢？这是第二种查询方法：

​ 1）根据联合索引查出所有姓wang的二级索引数据（3个主键值6，7，8）

​ 2）然后从二级索引中筛选出first_name以zi结尾的索引（1个索引）

​ 3）然后再回表，到主键索引上查询全部符合条件的数据（1条数据），返回给server层

​ 很明显，第二种方法到主键索引上查询的数据更少。 ICP时默认开启的，也就是说针对二级索引，只要能够把条件下推给存储引擎，它就会下推，不需要我们干预：

set optimizer_switch='index_condition_pushdown=on';

关闭ICP：

set optimizer_switch='index_condition_pushdown=off';

Using where代表从存储引擎返回的数据不全部满足条件，需要再server层过滤。

5 索引的创建和使用

5.1 索引的创建

1. 在用于where判断order排序和join的（on），group by的字段上创建索引

2. 索引的个数不要太多 —-浪费空间，更新变慢

3. 过长的字段，建立前缀索引

4. 区分度低的字段，例如性别，不要建立索引 —-离散度太低，导致扫描行数过多

5. 频繁更新的值，不要作为主键或者索引 ——页分裂

6. 随机无序的值，不建议建立索引，例如身份证，UUID

7. 组合索引把离散度高的值放在前面

8. 创建复合索引，而不是修改单列索引

5.2 索引失效的情况

1. 在索引列上使用函数，表达式

2. 字符串不加引号，出现隐式转换

3. Like条件中前面带%

4. 负向查询: NOT LIKE不能；！= （<>）和not in某些情况下可以

   explain select * from employees where emp_no not in(1)
   explain select * from employees where emp_no <> 1

​ 这个例子中，因为索引是有序的，只要从1之后开始顺序读取就行了。其实，用不用索引，最终都是优化器说了算。