一、索引基本知识

1.1 索引的优点

1. 大大减少了服务器需要扫描的数据量，加快数据库的检索速度
2. 帮助服务器避免排序和临时表
3. 将随机io变成顺序io

1.2 索引的用处

1. 速查找匹配WHERE子句的行
2. 从consideration中消除行,如果可以在多个索引之间进行选择，mysql通常会使用找到最少行的索引
3. 如果表具有多列索引，则优化器可以使用索引的任何最左前缀来查找行
4. 当有表连接的时候，从其他表检索行数据
5. 查找特定索引列的min或max值
6. 如果排序或分组时在可用索引的最左前缀上完成的，则对表进行排序和分组
7. 在某些情况下，可以优化查询以检索值而无需查询数据行

1.3 索引的分类

数据库会默认创建索引，但是并不是给主键建立索引，而是给唯一键建里索引的，因为主键的特性是唯一且非空

• 主键索引： 是一种特殊的唯一索引，不允许有空值。（主键约束，就是一个主键索引）
• 唯一索引： 索引列中的值必须是唯一的，但是允许为空值。
• 普通索引： MySQL中基本索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值，纯粹为了查询数据更快一 点。
• 全文索引： 只有在MyISAM引擎上才能使用，只能在CHAR,VARCHAR,TEXT类型字段上使用全文索引

  什么是全文索引，就是在一堆文字中，通过其中的某个关键字等，就能找到该字段所属的记录行，比如有"LOL LPL 牧小农" 通过牧小农，可能就可以找到该条记录。这里说的是可能，因为全文索引的使用涉及了很多细节，我们只需要知道这个大概意思。一般开发中，不贵用到全文索引，因为其占用很大的物理空间和降低了记录修改性，故较为少用。

• 组合索引： 在表中的多个字段组合上创建的索引，只有在查询条件中使用了这些字段的左边字段时，索引才会被使用，使用组合索引时遵循最左前缀集合。

  例如这里由id、name和age3个字段构成的索引，索引行中就按id/name/age的顺序存放，索引可以索引下面字段组合(id，name，age)、(id，name)或者(id)。如果要查询的字段不构成索引最左面的前缀，那么就不会是用索引，比如，age或者（name，age）组合就不会使用索引查询。

  1.4 面试技术名词

• 回表： 数据库根据索引（非主键）找到了指定的记录所在行后，还需要根据主键再次到数据块里获取数据，这种称之为回表
• 覆盖索引： 看我写的一篇文章：面试三轮我倒在了一道sql题上——sql性能优化

• 最左匹配： 指在联合索引中，如果你的 SQL 语句中用到了联合索引中的最左边的索引，那么这条 SQL 语句就可以利用这个联合索引去进行匹配，如果遇到范围查询(>、<、between、like)就会停止匹配。

  select from t where a=1 and b=1 and c =1; #这样可以利用到定义的索引（a,b,c）,用上a,b,c
  select from t where a=1 and b=1; #这样可以利用到定义的索引（a,b,c）,用上a,b
  select from t where b=1 and a=1; #这样可以利用到定义的索引（a,b,c）,用上a,c（mysql有查询优化器）
  select from t where a=1; #这样也可以利用到定义的索引（a,b,c）,用上a
  select from t where b=1 and c=1; #这样不可以利用到定义的索引（a,b,c）
  select from t where a=1 and c=1; #这样可以利用到定义的索引（a,b,c），但只用上a索引，b,c索引用不到

• 索引下推： 称为 Index Condition Pushdown (ICP)，这是MySQL提供的用某一个索引对一个特定的表从表中获取元组”，注意我们这里特意强调了“一个”，这是因为这样的索引优化不是用于多表连接而是用于单表扫描，确切地说，是单表利用索引进行扫描以获取数据的一种方式。

1.5 索引采用的数据结构

1.5.1 哈希表

缺点︰

1、利用hash存储的话需要将所有的数据文件添加到内存，比较耗费内存空间
2、如果所有的查询都是等值查询，那么hash确实很快，但是在企业或者实际工作环境中范围查找的数据更多，而不是等值查询，因此hash就不太适合了

1.5.2 二叉树

缺点∶

无论是二叉树还是红黑树，都会因为树的深度过深而造成io次数变多，影响数据读取的效率

1.5.3 B+树

B树特点:
1、所有键值分布在整颗树中
2、搜索有可能在非叶子结点结束，在关键字全集内做一次查找,性能逼近二分查找
3、每个节点最多拥有m个子树
4、根节点至少有2个子树
5、分支节点至少拥有m/2颗子树(除根节点和叶子节点外都是分支节点)
6、所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列

实例图说明∶
每个节点占用一个磁盘块，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为16和34，P1指针指向的子树的数据范围为小于16,P2指针指向的子树的数据范围为16~34 ,P3指针指向的子树的数据范围为大于34。

查找关键字过程:

1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2. 比较关键字28在区间(16,34 )，找到磁盘块1的指针P2。
3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4. 比较关健字28在区间(25,31 )，找到磁盘块3的指针P2。
5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O 操作第3次】
6. 在磁盘块8中的关健宁列表中找到关健字28。

缺点:

• 每个节点都有key，同时也包含data，而每个页存储空间是有限的，如果data比较大的话会导致每个节点存储的k ey数量变小
• 当存储的数据量很大的时候会导致深度较大，增大查询时磁盘io次数，进而影响查询性能

1.6 索引匹配方式

全值匹配： 全值匹配指的是和索引中的所有列进行匹配

explain select * from staffs where name = 'July' and age = '23' and pos = 'dev';

匹配最左前缀： 只匹配前面的几列

explain select * from staffs where name = 'July' and age = '23';

explain select * from staffs where name = 'July';

匹配列前缀： 可以匹配某一列的值的开头部分

explain select * from staffs where name like 'J%';

explain select * from staffs where name like '%y';

匹配范围值： 可以查找某一个范围的数据

explain select * from staffs where name > 'Mary';

精确匹配某一列并范围匹配另外一列：可以查询第一列的全部和第二列的部分

explain select * from staffs where name = 'July' and age > 25;

只访问索引的查询： 查询的时候只需要访问索引，不需要访问数据行，本质上就是覆盖索引

explain select name,age,pos from staffs where name = 'July' and age = 25 and pos = 'dev';

二、哈希索引

• 基于哈希表的实现，只有精确匹配索引所有列的查询才有效
• 在mysql中，只有memory的存储引擎显式支持哈希索引
• 哈希索引自身只需存储对应的hash值，所以索引的结构十分紧凑，这让哈希索引查找的速度非常快

2.1 哈希索引的限制

1. 哈希索引只包含哈希值和行指针，而不存储字段值，索引不能使用索引中的值来避免读取行
2. 哈希索引数据并不是按照索引值顺序存储的，所以无法进行排序
3. 哈希索引不支持部分列匹配查找，哈希索引是使用索引列的全部内容来计算哈希值
4. 哈希索引支持等值比较查询，也不支持任何范围查询
5. 访问哈希索引的数据非常快，除非有很多哈希冲突，当出现哈希冲突的时候，存储引擎必须遍历链表中的所有行指针，逐行进行比较，直到找到所有符合条件的行
6. 哈希冲突比较多的话，维护的代价也会很高

2.2 案例

当需要存储大量的URL，并且根据URL进行搜索查找，如果使用B+树，存储的内容就会很大：select id from url where url=""

也可以利用将url使用CRC32做哈希，可以使用以下查询方式：select id fom url where url="" and url_crc=CRC32("")

此查询性能较高原因是使用体积很小的索引来完成查找

三、组合索引

当包含多个列作为索引，需要注意的是正确的顺序依赖于该索引的查询，同时需要考虑如何更好的满足排序和分组的需要

案例： 建立组合索引 a,b,c ，不同SQL语句使用索引情况

四、聚簇索引与非聚簇索引

4.1 聚簇索引

• 不是单独的索引类型，而是一种数据存储方式，指的是数据行跟相邻的键值紧凑的存储在一起，将数据存储与索引放到了一块，找到索引也就找到了数据
• 如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有唯一索引，InnoDB会隐式定义一个主键来作为聚簇索引。InnoDB 只聚集在同一个页面中的记录。包含相邻健值的页面可能相距甚远。

4.2 非聚簇索引

• 数据文件跟索引文件分开存放，将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行，myisam通过key_buffer把索引先缓存到内存中，当需要访问数据时（通过索引访问数据），在内存中直接搜索索引，然后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的原因

• 通过叶子节点指针找到数据页中的数据，所以非聚簇索引是逻辑顺序

五、覆盖索引

5.1 基本介绍

1. 如果一个索引包含所有需要查询的字段的值，我们称之为覆盖索引
2. 不是所有类型的索引都可以称为覆盖索引，覆盖索引必须要存储索引列的值
3. 不同的存储实现覆盖索引的方式不同，不是所有的引擎都支持覆盖索引，memory不支持覆盖索引

5.2 优势

1、索引条目通常远小于数据行大小，如果只需要读取索引，那么mysql就会极大的较少数据访问量
2、因为索引是按照列值顺序存储的，所以对于IO密集型的范围查询会比随机从磁盘读取每一行数据的IO要少的多
3、一些存储引擎如MYISAM在内存中只缓存索引，数据则依赖于操作系统来缓存，因此要访问数据需要一次系统调用，这可能会导致严重的性能问题
4、由于INNODB的聚簇索引，覆盖索引对INNODB表特别有用

5.3 案例演示

1、当发起一个被索引覆盖的查询时，在explain的extra列可以看到using index的信息，此时就使用了覆盖索引
2、在大多数存储引擎中，覆盖索引只能覆盖那些只访问索引中部分列的查询。不过，可以进一步的进行优化，可以使用innodb的二级索引来覆盖查询。

例如：actor使用innodb存储引擎，并在last_name字段又二级索引，虽然该索引的列不包括主键actor_id，但也能够用于对actor_id做覆盖查询

六、优化小细节

• 当使用索引列进行查询的时候尽量不要使用表达式，把计算放到业务层而不是数据库层
• 尽量使用主键查询，而不是其他索引，因为主键查询不会触发回表查询
• 使用前缀索引

  有时候需要索引很长的字符串，这会让索引变的大且慢，通常情况下可以使用某个列开始的部分字符串，这样大大的节约索引空间，从而提高索引效率，但这会降低索引的选择性，索引的选择性是指不重复的索引值和数据表记录总数的比值，范围从1/#T到1之间。索引的选择性越高则查询效率越高，因为选择性更高的索引可以让mysql在查找的时候过滤掉更多的行。
  ​ 一般情况下某个列前缀的选择性也是足够高的，足以满足查询的性能，但是对应BLOB,TEXT,VARCHAR类型的列，必须要使用前缀索引，因为mysql不允许索引这些列的完整长度，使用该方法的诀窍在于要选择足够长的前缀以保证较高的选择性，通过又不能太长。

--创建数据表
create table citydemo(city varchar(50) not null);
insert into citydemo(city) select city from city;

--重复执行5次下面的sql语句
insert into citydemo(city) select city from citydemo;

--更新城市表的名称
update citydemo set city=(select city from city order by rand() limit 1);

--查找最常见的城市列表，发现每个值都出现45-65次，
select count(*) as cnt,city from citydemo group by city order by cnt desc limit 10;

--查找最频繁出现的城市前缀，先从3个前缀字母开始，发现比原来出现的次数更多，可以分别截取多个字符查看城市出现的次数
select count(*) as cnt,left(city,3) as pref from citydemo group by pref order by cnt desc limit 10;
select count(*) as cnt,left(city,7) as pref from citydemo group by pref order by cnt desc limit 10;
--此时前缀的选择性接近于完整列的选择性

--还可以通过另外一种方式来计算完整列的选择性，可以看到当前缀长度到达7之后，再增加前缀长度，选择性提升的幅度已经很小了
select count(distinct left(city,3))/count(*) as sel3,
count(distinct left(city,4))/count(*) as sel4,
count(distinct left(city,5))/count(*) as sel5,
count(distinct left(city,6))/count(*) as sel6,
count(distinct left(city,7))/count(*) as sel7,
count(distinct left(city,8))/count(*) as sel8 
from citydemo;

--计算完成之后可以创建前缀索引
alter table citydemo add key(city(7));

--注意：前缀索引是一种能使索引更小更快的有效方法，但是也包含缺点：mysql无法使用前缀索引做order by 和 group by。 

• 使用索引扫描来排序

  mysql有两种方式可以生成有序的结果：通过排序操作或者按索引顺序扫描，如果explain出来的type列的值为index,则说明mysql使用了索引扫描来做排序
  ​ 扫描索引本身是很快的，因为只需要从一条索引记录移动到紧接着的下一条记录。但如果索引不能覆盖查询所需的全部列，那么就不得不每扫描一条索引记录就得回表查询一次对应的行，这基本都是随机IO，因此按索引顺序读取数据的速度通常要比顺序地全表扫描慢
  ​ mysql可以使用同一个索引即满足排序，又用于查找行，如果可能的话，设计索引时应该尽可能地同时满足这两种任务。
  ​ 只有当索引的列顺序和order by子句的顺序完全一致，并且所有列的排序方式都一样时，mysql才能够使用索引来对结果进行排序，如果查询需要关联多张表，则只有当orderby子句引用的字段全部为第一张表时，才能使用索引做排序。order by子句和查找型查询的限制是一样的，需要满足索引的最左前缀的要求，否则，mysql都需要执行顺序操作，而无法利用索引排序

• union all,in,or都能够使用索引，但是推荐使用in
• 范围列可以用到索引，范围条件是：<、>,范围列可以用到索引，但是范围列后面的列无法用到索引，索引最多用于一个范围列

• 强制类型转换会全表扫描

  create table user(id int,name varchar(10),phone varchar(11));
  alter table user add index idx_1(phone);
  explain select * from user where phone=13800001234;(不会触发索引)
  explain select * from user where phone='13800001234';(触发索引)

• 更新十分频繁，数据区分度不高的字段上不宜建立索引

  更新会变更B+树，更新频繁的字段建议索引会大大降低数据库性能.
  类似于性别这类区分不大的属性，建立索引是没有意义的，不能有效的过滤数据，
  一般区分度在80%以上的时候就可以建立索引，区分度可以使用 count(distinct(列名))/count(*) 来计算

• 创建索引的列，不允许为null，可能会得到不符合预期的结果
• 当需要进行表连接的时候，最好不要超过三张表，因为需要join的字段，数据类型必须一致
• 能使用limit的时候尽量使用limit
• 单表索引建议控制在5个以内
• 单索引字段数不允许超过5个（组合索引）
• 创建索引的时候应该避免以下错误概念

  索引越多越好(错误)
  过早优化，在不了解系统的情况下进行优化(错误)