InnoDB存储引擎支持以下几种索引：
1）B+树索引
2）哈希索引：InnoDB会根据使用情况自动生成自适应哈希索引，不需要人为干预。
3）全文索引
注意：B+树索引并不能找到数据所在的行，而是找到数据行所在的页，将页加载到内存中，然后再内存中寻找，得到需要的数据。
一、数据结构与算法
关于这部分，在其他文集单独有介绍。请参考我其他的文章：https://www.jianshu.com/nb/48308723，在这里不再做详细的介绍了。
二、B+树索引
关于索引的细节可以查看我的这篇文章：https://www.jianshu.com/p/a1ced64b7a76
B+树索引的本质就是B+树在数据库中的实现。B+树索引在数据库中的特点就是高扇出性（通常指负载能力的高低，这里指数据库的IO次数），因为其树高通常在2 ~ 4层，只需要2 ~ 4次的磁盘IO。
B+树索引又可分为聚集索引和辅助索引，内部都是B+树的，区别在于，聚集索引的叶子节点存放的是一整行数据，而辅助索引的叶子节点存放的是聚集索引的值。
2.1 聚集索引
聚集索引就是按照每张表的主键构造一个B+树，同时叶子节点存放整行记录数，也将聚集索引的叶子节点称为数据页。每个数据页都通过一个双向链表进行链接。而在非数据页节点，存放的是键值和偏移量。
每张表只有一个聚集索引的B+树，并且查询优化器倾向于使用聚集索引。因为可以在聚集索引的叶子节点 上直接找到数据。由于定义了数据的逻辑顺序，聚集索引能够快速的找到范围内的数据。
2.2 辅助索引
辅助索引也称为非聚集索引，叶子结点并不包含行的所有记录。其叶子节点包含键值和一个书签（bookmark）。该书签用来告诉存储引擎在哪里可以找到与索引相应的行记录。因为Innodb是索引组织表，所以该书签就是该行记录的聚集索引键值。
当通过辅助索引去索引某条数据时，会先在辅助索引中去寻找到聚集索引的键，然后再聚集索引中根据键再去找到对应的行数据。如果辅助索引和聚集索引的树高都是3的话，则此次查询共经过了6次IO。
三、Cardinality
并不是在任何的查询条件上都需要加上索引，根据经验，只有访问表中很少一部分数据时，索引才有意义。例如对于性别等字段，他们可选取的范围很小，称为低选择性。
那么如何确定索引是否是高选择性呢？通过show index中的Cardinality值来确定。该值表示索引中不重复记录数量的预估值，且该值不是一个精确的值。在实际应该用中，cardinality/n_rows_in_table应尽可能的接近1。如果该值非常小，则用户需要考虑是否有建立索引的必要。
Cardinality是如何统计的呢？
每种存储引擎对B+树的实现是不同的，所以该统计是在存储引擎层进行的。
在生产环境中，索引的更新操作很频繁，如果每次都对Cardinality进行统计，必然会造成很大的性能开销，通常来说，数据库对于cardinality的统计都是通过采样（sample）来完成的。
更新cardinality的策略：
1）表中1/16的数据已发生变化
2）stat_modified_counter > 2 000 000 000：当修改次数达到该值，就更新。
我们举个例子，如下图所示：
mysql> show index from bssp.bssp_sys_menu;
+---------------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+---------------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| bssp_sys_menu | 0 | PRIMARY | 1 | id | A | 42 | NULL | NULL | | BTREE | | | YES | NULL |
| bssp_sys_menu | 1 | INX_STATUS | 1 | is_enable | A | 1 | NULL | NULL | YES | BTREE | | | YES | NULL |
| bssp_sys_menu | 1 | INX_STATUS | 2 | is_public | A | 2 | NULL | NULL | YES | BTREE | | | YES | NULL |
| bssp_sys_menu | 1 | IDX_LABEL | 1 | label | A | 42 | NULL | NULL | | BTREE | | | YES | NULL |
| bssp_sys_menu | 1 | IDX_PARENT_ID | 1 | parent_id | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
+---------------+------------+---------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
5 rows in set (0.01 sec)
在上面的表中，我们看到了总共有5个索引，其中表记录总共有42条，其中有两个cartinality的值是42，分别是主键id和lable字段，cartinality/表行数 = 1，符合建立索引的条件，而在两个状态字段is_enable和is_public，则不太适合，而parent_id则可以根据后面的数据量自行调整。
四、B+树索引的使用
4.1 联合索引
先模拟一个联合索引的存储结构是什么样子的，以两个key 做联合索引，仍然是在一棵树上，排序先比较前面的key，在比较后面的key，如下图：
联合索引结构
举个例子描述下最左匹配：
有一张学生表，字段分别是name，age，adrress...等，将name和age做为联合索引（name，age），依靠最左匹配原则，会有下面四种情况查询条件：
1 where name = ? and age =? # 走组合索引
2 where age =? and name = ? # 走组合索引
3 where name = ? # 走组合索引
4 where age =? # 不走组合索引
上面1、2、3中会走组合索引，因为其满足最左匹配原则，至少有name字段是可以匹配到索引，2中之所以能够走索引，是因为在mysql的server中查询优化器会对sql重新排序，达到最优的效果。4则完全无法匹配到组合索引。
实际验证一下，在最后一种情况中，extra中using where using index，使用了索引的部分，但是不是左前缀，仍然扫描了全表：
student
mysql> explain select * from bssp.student where name = '张三' and age = 35;
+----+-------------+---------+------------+------+---------------+--------------+---------+-------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+--------------+---------+-------------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | idx_name_age | idx_name_age | 1028 | const,const | 1 | 100.00 | Using index |
+----+-------------+---------+------------+------+---------------+--------------+---------+-------------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)
mysql> explain select * from bssp.student where name = '张三';
+----+-------------+---------+------------+------+---------------+--------------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+--------------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | idx_name_age | idx_name_age | 1023 | const | 1 | 100.00 | Using index |
+----+-------------+---------+------------+------+---------------+--------------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)
mysql> explain select * from bssp.student where age = 35 and name = '张三' ;
+----+-------------+---------+------------+------+---------------+--------------+---------+-------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+--------------+---------+-------------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | idx_name_age | idx_name_age | 1028 | const,const | 1 | 100.00 | Using index |
+----+-------------+---------+------------+------+---------------+--------------+---------+-------------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)
mysql> explain select * from bssp.student where age = 35;
+----+-------------+---------+------------+-------+---------------+--------------+---------+------+------+----------+--------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+-------+---------------+--------------+---------+------+------+----------+--------------------------+
| 1 | SIMPLE | student | NULL | index | idx_name_age | idx_name_age | 1028 | NULL | 3 | 33.33 | Using where; Using index |
+----+-------------+---------+------------+-------+---------------+--------------+---------+------+------+----------+--------------------------+
1 row in set, 1 warning (0.00 sec)
4.2 覆盖索引
上面由于使用了select * 进行查询，导致了回表。当使用select id from table where 普通索引 = '某值'时，这时使用了索引覆盖（using index）。
举例子，分别执行以下两个sql，在结果一回表的过程中，没有使用到索引覆盖，而在结果二中，使用到了索引覆盖：
explain select * from bssp_sys_menu where parent_id = 101;
explain select id from bssp_sys_menu where parent_id = 101;
结果1：回表
结果2：索引覆盖
尽量使用索引覆盖能减少磁盘的io，因为避免了回表。
4.3 MRR（Mutil-Range Read）
MRR 通过把「随机磁盘读」，转化为「顺序磁盘读」，从而提高了索引查询的性能。
在mysql中有两个配置：
mrr: on/off
mrr_cost_based: on/off
#开启mrr
set optimizer_switch='mrr=on';
#基于成本的逻辑判断开关,开启的话mysql会判断是否需要使用mrr
set optimizer_switch='mrr_cost_based=on';
开启mrr并且sql确实用到后会在explain语句中看到，如下：
explain select * from bssp_sys_menu where parent_id between 100 and 104;
MRR
如上图我们在查找范围数据时，会在二级索引拿到数据的主键id，及聚簇索引的key，这时候需要回表到聚簇索引，如果没有MRR，则我们拿到的id可能是乱序的，这样到磁盘读取数据会导致磁盘重复转动，经过MRR排序后，会在聚簇索引顺序读取。
MRR好处：
1）使数据访问变得较为顺序。查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找。
2）减少缓冲池中页被替换的次数。
3）批量处理对键值的查询操作。
对于InnoDB和MyISam的的范围查找和JOIN操作，MRR的工作方式如下：
1）将查询到的辅助索引键值存放到缓存中，这是缓存中的数据时根据辅助索引的键值排序的。
2）将缓存中的键值根据rowid进行排序。
3）根据rowid的排序顺序来访问实际的数据文件。
4.4 ICP（Index Condition Pushdown，索引下推）
要想深入理解 ICP 技术，必须先理解数据库是如何处理 where 中的条件的，对 where 中过滤条件的处理，根据索引使用情况分成了三种：index key, index filter, table filter。
摘自https://www.cnblogs.com/digdeep/p/4994130.html
1. index key
用于确定SQL查询在索引中的连续范围(起始范围+结束范围)的查询条件，被称之为Index Key。由于一个范围，至少包含一个起始与一个终止，因此Index Key也被拆分为Index First Key和Index Last Key，分别用于定位索引查找的起始，以及索引查询的终止条件。也就是说根据索引来确定扫描的范围。
2. index filter
在使用 index key 确定了起始范围和介绍范围之后，在此范围之内，还有一些记录不符合where 条件，如果这些条件可以使用索引进行过滤，那么就是 index filter。也就是说用索引来进行where条件过滤。
3. table filter
where 中的条件不能使用索引进行处理的，只能访问table，进行条件过滤了。
通过上面可以得到mysql的where条件过滤分为三个步骤：index key -> index filter -> table filter.
在 MySQL5.6 之前，并不区分Index Filter与Table Filter，统统将Index First Key与Index Last Key范围内的索引记录，回表读取完整记录，然后返回给MySQL Server层进行过滤。而在MySQL 5.6之后，Index Filter与Table Filter分离，Index Filter下降到InnoDB的索引层面进行过滤，减少了回表与返回MySQL Server层的记录交互开销，提高了SQL的执行效率。
所以所谓的 ICP 技术，其实就是 index filter 技术而已。只不过因为MySQL的架构原因，分成了server层和引擎层，才有所谓的“下推”的说法。所以ICP其实就是实现了index filter技术，将原来的在server层进行的table filter中可以进行index filter的部分，在引擎层面使用index filter进行处理，不再需要回表进行table filter。
如下表示使用了索引下推：
mysql> explain select * from bssp.bssp_sys_menu where parent_id > 1000;
+----+-------------+---------------+------------+-------+---------------+---------------+---------+------+------+----------+-----------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------------+------------+-------+---------------+---------------+---------+------+------+----------+-----------------------+
| 1 | SIMPLE | bssp_sys_menu | NULL | range | IDX_PARENT_ID | IDX_PARENT_ID | 9 | NULL | 5 | 100.00 | Using index condition |
+----+-------------+---------------+------------+-------+---------------+---------------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)
网友评论