MySQL索引

索引用于提高查询效率，常见的索引数据结构有：哈希表、有序数组和搜索树。

  • 哈希表以key-value形式存储，通过哈希函数查找key的位置获取对应value值。存储的数据是无序的，因此在做范围查询时需要全表扫描，性能很差
  • 有序数组是按顺序排列的，通过二分法能快速查询到对应数据，包括范围查询。但更新效率太低，往中间插入新数据时需要挪动后面的所有记录。适用于静态只读数据
  • 二叉树的特点在于每个节点的左儿子小于父节点，右儿子大于父节点，通过树搜索效率很高。但二叉树索引不止存在于内存，也存在于磁盘上，如果二叉树树高太深，也需要遍历多次磁盘，效率大打折扣。因此更多数据库系统都采用N叉树或B+树，减少磁盘遍历次数。

Innodb索引

在Innodb中，表是根据主键顺序以索引形式存放的，也就是索引组织表，数据都存放在B+树中。索引类型分为主键索引和非主键索引，主键索引也称聚簇索引(clustered index)，存放了整行的数据；非主键索引又称二级索引，存放的是key和主键值。查询主键时只需要查询主键上的B+树，查询非主键索引需要先查询非主键索引上的B+树，再去主键B+树上查询一次，也就是回表。

主键自增

在创建主键时，可加入AUTO_INCREMENT声明该主键为自增，插入记录时能自动将当前最大值+1作为下一条记录的主键，这样每次插入都是追加，不用挪动其它记录，也就不会造成数据页分裂。

如果用业务字段作为主键则很难保证有序，业务字段长度较大会导致二级索引也比较大，而自增列即使用bigint也就8个字节，因此往往更建议使用自增列而非业务字段。

覆盖索引

在通过select id from test where name=’lu’查询ID值时，ID为主键，name索引则已包含ID值，因此可以直接在name索引上获取结果，而不需要回表，则称之为覆盖索引。覆盖索引能够减少索引树搜索次数，提升查询性能。

最左前缀原则

当我们使用模糊查询时，例如利用select * from test wher name like ‘lu%’查询名字开头为lu的信息时，也能使用name上的索引。最左前缀原则可以是联合索引的最左N个字段，也可以是字符串索引的最左N个字符。

基于最左前缀原则，我们在评估建立联合索引时，需要考虑索引的复用能力，将复用率最高的字段放在最左端。当我们建立联合索引index(a,b)时，意味着我们不再需要在a字段上再建一个独立的索引，如果调整索引顺序能够少维护一个索引，那这个顺序应该优先考虑。如果查询单独查询b字段，是无法使用这个联合索引，需要建立一个独立索引，需要考虑空间因素，如果字段b比a要大的多，更建议创建(b,a),(a)两个索引

mysql> show index from t;
+-------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name    | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t     |          1 | idx_id_name |            1 | id          | A         |          10 |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | idx_id_name |            2 | name        | A         |          10 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
mysql> explain select count(*) from t where name='lu';
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+--------------------------+
| id | select_type | table | partitions | type  | possible_keys | key         | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+--------------------------+
|  1 | SIMPLE      | t     | NULL       | index | NULL          | idx_id_name | 68      | NULL |   10 |    10.00 | Using where; Using index |
+----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+--------------------------+

上述这种查询，虽然where中的列不满足最左前缀原则，但其能通过覆盖索引的方式利用到复合索引

索引下推

在联合索引满足最左前缀原则情况下，不符合最左前缀原则的字段，在5.6之前需要通过前缀字段不断回表来判断非前缀字段的值，而在5.6中引入索引下推优化(index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

假如我们现在A表上有联合索引(name,age)，进行如下查询

select * from a where name like 'lu%' and age=25 and sex=1;

通过前缀索引规则可知，我们通过索引可以找到第一个符合的记录，然后再判断其它条件。在MySQL5.6之前，只能一个一个回表，到主键索引上找出记录再判断；在MySQL5.6引入的索引下推优化，可以在索引遍历时，对索引中的字段先做判断，直到过滤掉不满足条件的记录，减少回表次数。

Multi-Range Read

MySQL5.6支持Multi-Range Read(MRR)优化，MRR在回表查询时会先将secondary Index的查询结果根据主键值进行排序，并按照主键排序的顺序进行查找，将随机IO转化为顺序IO。对于MMR，参数read_rnd_buffer_size指定了其缓冲区的最大内存，并确定一次处理要处理的范围数。

MMR

MRR优化由optimizer_switch参数中的mrr和mrr_cost_based控制，mrr表示是否启用MRR，mrr_cost_based表示是否通过cost based方式启用MRR，若mrr_cost_based为off，则总是启用MRR。默认优化器策略判断消耗的时候，会更倾向于不使用 MRR，我们可以通过Hint的方式提示SQL走MRR

mysql> explain select * from titles where from_date between '1985-09-30' and '1990-09-30';
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | titles | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 2610 |    11.11 | Using where |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select /*+ MRR(titles) */ * from titles where from_date between '1985-09-30' and '1990-09-30';
+----+-------------+--------+------------+-------+---------------+----------+---------+------+------+----------+----------------------------------+
| id | select_type | table  | partitions | type  | possible_keys | key      | key_len | ref  | rows | filtered | Extra                            |
+----+-------------+--------+------------+-------+---------------+----------+---------+------+------+----------+----------------------------------+
|  1 | SIMPLE      | titles | NULL       | range | idx_date      | idx_date | 3       | NULL |  601 |   100.00 | Using index condition; Using MRR |
+----+-------------+--------+------------+-------+---------------+----------+---------+------+------+----------+----------------------------------+
  1. Multi-Range Read Optimization

changer buffer

changer buffer是对insert buffer的扩展，在更新数据页时，如果数据页在内存中则直接更新，如果不在内存则在不影响一致性的前提下将操作记录在change buffer中，待下次访问数据页再从磁盘读取到内存中并执行change buffer，这个过程称之为merge，后台线程会定期进行merge，正常关闭数据库也会执行merge。change buffer是可持久化的，既写入内存，也会写入磁盘。change buffer使用的是buffer pool的内存，由参数innodb_change_buffer_max_size控制，默认为25，最大可以设置为50则表示能占用50%的buffer pool。

唯一索引必须将数据页读到内存中才能做判断，因此唯一索引无法使用change buffer，只能针对普通索引。在写完立马进行读的场景下，会频繁进行merge，增加change buffer的维护工作，建议通过参数innodb_change_buffering关闭change buffer，其它场景都建议通过普通索引配合change buffer使用，减少磁盘IO。

优化器如何选择索引

优化器选择索引的目的，就是为了寻找代价最小的执行计划。扫描行数作为影响执行代价的主要因素之一，扫描的行数越低，则磁盘读取的次数越低，代价也就越小。扫描行数的判断基于统计信息，也就是一个索引上不同值的个数，称之为基数(cardinality)，基数越大，索引的区分度越好。

MySQL通过采样统计获得索引的基数，也就是选择N个数据页，统计其中的不同值，计算一个平均值再乘以页数。当数据不断更新时，变更的数据行超过1/M时，自动触发一次索引统计。当参数innodb_stats_persistent为ON时统计信息持久化存储，N是20，M是10；为off时存储在内存中，N是8，M是16。索引基数可以通过show index或者information_schema.STATISTICS来查看，对于当索引统计信息错误导致索引索引选择错误，可以通过analyze table来重新搜集统计信息。

除此之外，优化器也会考虑到实际扫描行数，当语句需要回表查询时，这部分代价也会计算进去。因此容易导致优化器选择错误索引。

对于这种未正确使用索引的情况，我们可以采取下列三种方式进行处理

  • 采用force index强制选择一个索引，如果我们认为存在更好的索引选择，我们强制它使用指定的索引
  • 修改语句，引导MySQL使用更佳的索引。
  • 新建一个更适合的索引来供优化器选择