InnoDB索引与底层原理

索引介绍

索引：一颗B+树，除了叶子节点外，其余的节点都作为目录项，且都是有序排列的

• 在目录项page里面，一条记录对应着下层的一个page

  一条记录至少有两个列：列1作为主键 记录该page最小的主键值；列2记录该page的页号

• 在叶子节点才真正地存放数据

  • 聚簇索引：以主键为主键，叶子节点存储完整的用户记录

  • 二级索引：以某列为主键，叶子节点列1为索引列，列2为原数据表里的主键；目录项节点为索引列的值+主键值+页号（保证除页号外是唯一的）

    即二级索引的叶节点为了节省空间，不实际存储用户记录，需要回表

  • 联合索引：以多个列作为排序规则，叶子节点为所有用于排序的列+主键；目录项节点为用于排序的列+页号，必须使用到第一个列才能用到联合索引，否则用不上

一个页面至少需要有两条记录，否则会导致相同数量的记录耗费很多的目录层级，且创建索引是有代价的，一是存储它的空间代价，二是数据crud时调整索引的时间代价

当写下select * from student where uid = 3;时，如果uid有索引=》存储引擎请求内核=》磁盘IO读取索引文件到内存上=》用索引的数据构建B树来加速搜索

innoDB默认使用B+树构建索引（树高，平均，范围查询）

第一个原因是：B树每个节点既存key也存data，但由于每个节点的存储空间有限，这种存储方式会导致每个节点能存储的key数据量变小，当需要存储的数据量很大时，会导致B树的高度变高；而B+树的话非叶子节点只包含key值，数据都存放在叶子节点上，这样每个磁盘块就能容纳更多的键值对，树的高度就会比较小，在进行索引搜索的时候就能减少B+树访问磁盘的IO次数，提高数据的读取效率

其次是因为B+树的所有数据都存放在叶子节点上，所以要是在B+树上搜索关键字，找到的时间是平均的，不会像B树那样，越靠近根节点的数据找到得越快

最后是B+树的所有叶子节点都被连接成了有序的链表结构，范围查询的时候可以沿着链表进行顺序遍历，不需要回溯到内部节点，提高了范围查询的效率

索引细节

覆盖索引

减少树的搜索次数，显著提升查询性能，即建立联合索引，将查询的值也加入到索引中，这样目标值已经在索引树上，可以直接提供查询结果，不需要回表

最左前缀原则

B+树这种索引结构，可以利用最左前缀来定位记录，只要检索的值满足最左前缀，就能利用索引来加速检索（这个最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符）

基于这个原则，建立联合索引时如果可以通过调整顺序，可以少维护一个索引，则这个顺序就是需要优先使用的（比如有（a，b）索引后，就不需要单独为a建立索引了）

索引下推

MySQL5.6之后，在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数

普通索引和唯一索引

普通索引允许在索引列中存在重复值；唯一索引要求索引值是唯一的

• 查询过程的区别：普通索引查找到第一个满足条件的记录后还需要找下一个记录，但由于InnoDB是按数据页为单位进行读写的，当读到第一个满足条件的记录时会将整个16KB的页读到内存，所以和唯一索引的查询效率相差无几

• 更新过程的区别：普通索引在进行更新操作时，如果要更新的记录不在内存中的话，可以利用到change buffer，减少随机磁盘访问，可以明显提升更新性能；而唯一索引进行更新操作时需要判断更新操作有没有冲突，不能使用change buffer

  change buffer：

  当更新一个数据页的时候如果它在内存上就直接更新；如果数据页不在内存上的话，innoDB会将更新操作缓存在change buffer中，下次查询访问到这个数据页将它读到内存之后，再利用change buffer进行数据页的更新（这个过程叫做merge，会定期、访问到数据页、正常关闭数据库时触发）

  对于写多读少的业务来说，写完就访问页面的概率比较小，此时change buffer的效果最好

  而如果写完后立刻做查询，那么把更新记录到change buffer之后要立刻做merge，反而增加了change buffer的维护代价

索引选择

优化器会选择索引，找到最优执行方案，判断标准有扫描行数（包括回表查询的代价也会计算进去）、是否使用临时表、是否排序等等

mysql会通过采样统计来求得索引的基数，即默认选择N个数据页，然后统计这些页面上的不同值，得到平均值后再乘以这个索引的页面数，当变更数据行数超过1/M之后再自动触发重新做一次索引统计

索引选择异常和处理

当发现explain的结果预估的rows值和实际情况差距较大，可以执行analyze table重新统计索引信息

采用force index强行选择一个索引：select * from t force index(a) where a between 1 and 5000; 缺点在于变更不及时，要等到线上出问题了再去修改sql语句加上force index

考虑修改语句，引导MySql使用我们期望的索引，比如说将order by b改成order by b,a，引导MySql也考虑用a作为索引

或是直接删除掉这个索引，添加一个更合适的索引供优化器使用

正确地使用前缀做索引

• 前缀索引可能会增加扫描行数

使用前缀索引，定义好这个前缀的长度，如果能够形成高区分度，让重复的key值变少，就能够做到既节省空间，又不用额外增加太多的查询成本

先计算该列上有多少个不同的值：select count(distinct email) as L from User;，然后依次选取不同长度的前缀来看这个值：

select 
  count(distinct left(email,4)）as L4,
  count(distinct left(email,5)）as L5,
  count(distinct left(email,6)）as L6,
  count(distinct left(email,7)）as L7,
from SUser;

预设一个可以接受的损失区分度比例a%，然后在返回的L4~L7中，找出不小于L*(1-a%)的值

• 使用前缀索引就无法使用到覆盖索引的优化

因为使用前缀索引查到结果后，系统不确定前缀索引的定义是否截断了完整信息，所以都会再回表查询

如果前缀的区分度不够好的话（比如说身份证前6位都相同），可以用两种方法解决：

• 使用倒序存储：调用reverse()将字段倒序存入
• 使用hash字段：在表上创建一个整数字段保存校验码，同时在这个字段上创建索引，每插入数据时都调用crc32()求校验码

更好地使用innodb索引

挑选一个优秀的列作为索引列

• 索引列的类型尽量小（索引就越小）
• 索引列的基数尽量大（基数：该索引列的不重复数据数量）
• 索引列出现在排序、搜索或分组的列
• 索引列可以只针对字符串的前缀建立
• 索引列尽量设置为AUTO_INCREMENT（防止插入的记录中索引列忽大忽小，发生页面分裂和合并）

了解写出什么样的语句可以用上索引

• 全值匹配（搜索条件的列=索引列，直接二分法快速匹配）
• 匹配一个或多个左边的列
• 匹配列前缀（前缀都是排好序的）
• 匹配范围值
• 精确匹配某一列并且范围匹配另一列
• 用于order by排序（使用索引列免去在内存或文件中排序）
• 用于group by分组
• 比较表达式中索引列单独出现（比如c1<2可以用上索引，2*c1<4就不行）
• 在查询列表里只包含索引列（这样在联合索引中查找到目标时就不需要回表了，即索引覆盖）

避免以下情况：

• 各个列递增或递减不一致
• select选取的列不在联合索引或是二级索引中，尽量避免直接select *
• WHERE子句中出现了非排序使用到的索引列
• 排序列包含非同一个索引的列
• 排序使用了复杂的表达式：比如SELECT * FROM xxx ORDER BY UPPER(c1) LIMIT 10

其他索引

MYISAM里的索引：非聚簇索引，即叶子节点存放的是数据所在地址，而不是数据本身

memory里的哈希索引O(1）搜索效率好+磁盘IO花费少，但哈希表里的数据没有顺序可言，只能用于等值搜索，没办法处理磁盘上的数据然后加载到内存上构建高效的搜索数据结构，因为他没有办法减少磁盘IO次数，只是基于内存上的搜索

Innodb里的自适应哈希索引：自适应即不是自己创建的，而是优化的功能；如果检测同样的二级索引不断被使用，它会根据这个二级索引，在内存上根据二级索引树上的二级索引值，构建一个哈希索引，来加速搜索

使用show engine innodb status\G查看两个重要信息

• RW-latch等待的线程数量，默认分配8个分区，如果同一个分区等待的线程数量过多，考虑关掉自适应哈希
• 比较使用自适应哈希搜索的频率 和 使用二级索引树搜索的频率

可以使用show indexs from 表名查看某个表里的所有索引的信息