MySQL索引

索引的常见模型

• 哈希表：哈希表做索引可能出现散列冲突，一种处理这种情况的方式就是链表法，同一个key拉出一个链表。
  　　哈希表做索引，key可以不是递增的。优点是增加新的key-value时速度会很快；缺点是key不是有序的，所以哈希索引做区间查询速度很慢。
  　　适用场景：等值查询，比如memcached及一些其他的NoSQL引擎。
• 有序数组：等值查询和范围查询效率都很高；但是更新数据效率低下，比如往中间插入一个数据，就得挪动后面所有记录。
  　　适用场景：静态存储引擎。
• BST

索引的实现

• 在MySQL中，索引是在存储引擎中实现的，不同的引擎索引的工作方式不一样，即使多个存储引擎支持同一类型的索引，其底层实现也可能不同。

InnoDB索引模型

• InnoDB中，表中的数据都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表；InnoDB使用了B+树索引模型，每一个索引在InnoDB里面对应一棵B+树。
• 根据叶子节点的内容，索引类型分为主键索引(聚簇索引)和非主键索引(二级索引)。基于主键索引的查询只需搜索主键索引就行。
• 主键索引的叶子节点存放的是整行数据；非主键索引叶子节点存放的是主键的值。基于非主键索引的查询，一般都要经过回表的过程，覆盖索引和索引下推可以优化这个过程。
• 主键长度越小，非主键索引的叶子节点就越小，占用的空间也就越小。

相关概念

• 回表：回到主键索引树搜索的过程。
• 覆盖索引：通过二级索引查询所需数据，如果二级索引中已经覆盖了所要查询字段，就是覆盖索引。
• 索引下推：MySQL5.6引入索引下推优化(index condition pushdown)，可以在索引遍历过程中，根据查询条件对索引中包含的字段先做判断，过滤掉不满足条件的记录，减少回表次数，提高效率。
• 最左前缀原则：在查询过程中，符合最左前缀原则的索引都会被使用到。最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

普通索引、唯一索引

• 查询过程，普通索引，在B+树上找到满足第一个条件的记录后，需要再查找下一个记录，直到碰到第一个不满足条件的记录。
• 而唯一索引，由于索引具有唯一性，在查到满足条件的第一条记录后，就会停止继续检索。
• 查询过程性能差异，当普通索引需要查找的数据页刚好不在本数据页的时候，必须取下一个数据页到内存；而对唯一索引没有这种情况。
• 更新过程性能差异。唯一索引的更新不能使用change buffer，因为唯一索引的更新操作首先要判断唯一性。

数据更新，change buffer

• 对于InnoDB，当更新操作需要用到一个数据页时，如果该数据页在内存中，直接更新；如果数据页还没有在内存中，在不影响数据一致性的前提下，InnoDB会将这些更新操作缓存到change buffer中，此时就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行change buffer中与这个页有关的操作，得到最新的结果(这个过程称为merge)。通过这种方式能保证这个数据逻辑的正确性。
• 除访问数据页会触发merge，系统后台线程会定期merge。在数据库正常关闭(shutdown)过程中，也会执行merge操作。
• change buffer能减少磁盘读操作，语句执行速度回明显提升。而且数据读入内存(读操作)需要占用buffer pool，所以change buffer还能避免占用内存，提高内存利用率。
• change buffer用的是buffer pool中的内存，不能无限增大。大小可以通过innodb_change_buffer_max_size设置，表示的是change buffer的大小最多占用buffer pool的百分比。

基于change buffer和索引，说说InnoDB引擎的表，在表中插入新记录时的处理流程？

• 如果要更新的数据页在内存中，此时使用普通索引和唯一索引没多大差别
  　　1、对于唯一索引，找到数据记录应在的位置，判断没有冲突，插入记录，语句执行结束。
  　　2、对于普通索引，找到数据记录应在的位置，插入记录，语句执行结束。
• 如果要更新的数据页不再内存中，此时InnoDB的处理流程如下：
  　　1、对于唯一索引，需要将数据页读入内存，进行唯一性冲突判断，判断若没有冲突，插入该记录，语句执行结束。
  　　2、对于普通索引，将更新记录在change buffer中，语句就执行结束。没有数据页读入内存的操作。
• 将数据从磁盘读入内存，涉及随机I/O的访问，是数据库里成本最高的操作之一，change buffer减少了随机磁盘访问，所以对更新性能的提升回事很明显的。、

change buffer使用场景

• change buffer进行merge的时候才是真正进行数据更新的时刻，而change buffer的主要目的就是讲记录的变更动作缓存下来，所以在一个数据页做merge之前，change buffer记录的变更越多(也就是这个数据页上要更新的次数越多)，收益越大。
• 对于写多读少的业务，页面写完后马上被访问到的概率比较小，此时使用change buffer的效果最好。常见于账单类、日志类系统。

change buffer、redo log

• WAL提升性能的核心机制，确实也是尽量减少随机读写。但是WAL侧重减少“随机写”(将随机写转化成顺序写)，change buffer侧重于减少“随机读”(更新时，避免读盘到内存)。

给字符串类型添加索引

• 假设有表t，字符串字段email。
• 整字段索引
  　　alter table t add index index1(email);，占用空间大；查询时扫描行数最少。
• 前缀索引
  　　alter table t add index index2(email(6));，占用空间小；增加扫描行数；覆盖索引失效。
  　　优化：选择合适的长度，增加区分度，使用下列语句查看不同长度前缀索引有多少个不同的值，不同值越多越好。

    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 t;

函数的对索引的影响

• 对索引字段做函数操作，就用不上索引了；函数操作可能会破坏索引值的有序性，优化器会放弃走树搜索功能（即使对于不改变有序性的函数，也会放弃使用索引）。

常见破坏索引树搜索的操作

• 条件字段函数操作

    -- 前提，表t，created_at datetime default null，index
    -- bad case对索引字段做函数操作，破坏了索引的有序性，会放弃树搜索功能，遍历索引树created_at。
    select count(*) from t where month(created_at)=7;  
    -- 修正，使查询仍走created_at树搜索
    select count(*) from t where
      (created_at >= '2016-7-1' and created_at < '2016-8-1') or
      (created_at >= '2017-7-1' and created_at < '2017-8-1'); 

• 隐式类型转换
  　　类型转换规则，MySQL中，字符串和数字作比较的话，是将字符串转换成数字的。(验证：select "10" > 9)

    -- 前提，表t，phone varchar(12) default null，index
    -- bad case 使用整型条件而非字符串，优化器做了隐式类型转换，也就是对索引字段进行了函数操作。
    select * from t where phone=123456;  
    -- 对优化器来说相当于执行
    select * from t where CAST(phone AS signed int) = 123456;
    -- 修正，使用正确的类型作为条件
    select * from t where phone='123456';

    -- CAST函数加载输入参数上，不会破坏索引
    select * from t where id='99';

• 隐式字符串编码转换
• 字符集编码的转化规则，是将子集向超集转化，如当utf8和utf8mb4同时做比较时，先将utf8转化成utf8mb4字符集，再做比较。
• 情景：表A id int pk, phone varchar(12) default null index, charset=utf8mb4; 表B id int pk, phone varchar(12) default null index, charset=utf8。

  -- bad case
  select a.* from A as a,B as b where a.phone=b.phone and a.id=2;
  -- 这里表A是驱动表，表B是被驱动表，phone是关联字段，执行流程如下：
  -- 1、根据id从表A找到 L2 这一行。
  -- 2、从 L2 中取出phone字段。
  -- 3、根据取出的phone字段去表B中查找匹配条件的行。
  -- 当执行到第三步时，单独改成SQL如下，问题出现了。
  select * from B where phone=$L2.phone.value;
  -- 上面这句SQL中条件的编码是utf8mb4，而表B字符集编码是utf8，需要函数转化，等同于： 
  select * from B where CONVERT(phone USING utf8mb4)=$L2.phone.value;
  -- 同样地，对索引字段做函数操作，优化器放弃走树搜索功能。
  
  -- 如果反过来，表A作为被驱动表，不会对索引造成破坏
  select a.* from A a,B b where a.phone=b.phone and a.id=2;
  -- 此时执行流程步骤3相当于
  select * from a where phone=CONVERT($R2.phone.value USING utf8mb4)；
  -- 可见，函数是加在输入参数上的，所以可以用上被驱动表的索引。

  -- 对bad case的修正
  -- 1、将表B的phone字段改为utf8mb4编码，表大的话不推荐使用
  alter table B modify phone varchar(12) CHARACTER SET utf8mb4 default null;
  -- 2、主动将a.phone转化为utf8编码，避免被驱动表上的字符串编码转换
  select a.* from A as a, B as b where b.phone=CONVERT(a.phone USING utf8) and a.id=2;

• 综上，字符集不同只是产生问题原因之一，被驱动表的索引字段上进行函数操作才是直接导致对被驱动表做全表扫描，放弃树搜索的原因。