一、MySQL为什么要选择B+树来存储索引？

MySQL的索引选择B+树作为数据结构来进行存储，其本质原因在于可以减少IO次数，提高查询效率，简单来说就是保证在树的高度不变的情况下可以存储更多的数据。

（一）IO角度

在MySQL的数据库中，表的真实数据和索引数据都是存储在磁盘中，我们在进行数据读写时必然会涉及到IO问题，IO本质是硬件方面的问题，但是在做索引设计的时候尽可能考虑如何提高IO的效率，一般来说提高IO效率主要有两个维度的考虑，减少IO次数和减少IO量，所以要遵循这两个原则。

（二）分而治之

数据在进行存储时数据量是无法预估的，当表的数据量非常大的时候，我们没办法一次性将所有的数据都读取到内存中，因此这个时候就要采用分而治之的思想，将数据进行分块读取，这个时候就需要考虑设计合理的块大小。

（三）数据块的大小

数据在磁盘存储的时候有时间局限性和空间局限性，内存跟磁盘在进行数据交互的时候不是需要啥数据就选择性的从磁盘将数据读取到内存中，而是一次性将所有相关的数据全部加载到内存中，在从磁盘进行数据读取的时候有一个最基本的逻辑单位称为页，数据页的大小一般是4KB或8KB，这跟操作系统有关系，我们在读取数据的时候一般会按照数据页的整数倍大小进行读取，比如innodb存储引擎每次读取16KB大小的数据。在MySQL中一般都是每次读取16KB大小的数据，这个读取大小可以通过参数进行调整，比如innodb中的innodb_page_size这个参数，当然一般情况下我们不会调整这个参数大小。

（四）数据格式

确定好数据块大小之后，此时应该考虑数据的存储格式，我们在使用索引时基本是根据某一个或多个索引列的值来进行整行数据或者某些字段的读取，比如select * from table where id = 10;这个语句就是根据id值去检索整行记录，因此整体的数据格式可以设计成K-V格式的数据，K是索引列的值，然后进一步考虑V值的设计。

（五）数据存储

正常情况下，当需要从磁盘读取一行记录的时候，需要知道一些和记录相关的信息才可以读取到记录，比如：文件名称、偏移量、数据长度，知道这些信息后就可以定位到任何一条记录，所以我们考虑将上面步骤的V值设计成刚才的那几个字段，但是需要考虑到一件事情，如果刚才那几个字段信息作为索引信息的话，那么在进行读取数据的时候，首先要打开一个文件，读取到刚刚的那几个字段信息，然后根据字段信息再去对应数据文件中找到相应的行记录，如果打开一次文件就是一次IO的话，至少需要2次IO才能读取到想要的数据记录，这点跟之前所说的减少IO次数原则相违背，所以最好的方式是将数据记录直接作为V值进行存储，那么在读取数据时可以直接根据索引列的K值读取到对应的行记录V值，只不过此时需要将索引和数据绑定存储，在MySQL中，Innodb存储引擎就是这样存储的，数据文件和索引文件全部位于后缀为ibd的文件中。

（六）数据结构

前面确定好了数据块大小、数据格式、数据的存储方式，接下来需要考虑存储数据的数据结构。支持K-V格式的数据结构有很多，比如哈希表、二叉树、BST、AVL、红黑树，但是MySQL最终选择了B+树作为索引的数据结构。

1.哈希表

使用哈希表可以进行数据存储，但是哈希表本质上是无序的散列表，因此在进行范围查询的时候就必须要进行挨个比对，其查询效率比较低，此外哈希表会存在哈希碰撞或者哈希冲突问题，如果使用这种数据结构就需要设计出性能优良的哈希算法，因此哈希表并不是很适用。但是在MySQL中，MEMORY存储引擎支持哈希索引，InnoDB存储引擎支持自适应哈希。

2.二叉树、BST、AVL、红黑树

这几种树形结构也支持K-V结构的数据存储，但是它们的共同的特点是至多只有两个分支，那么在进行数据存储时，对于一个三层的树至多可以存储7个数据结果值，所以能够存储的数据量很小，如果想要存储更多的数据，只能增加树的高度，而树的高度变高之后又会导致IO次数变多，影响查询效率。那么此时需要思考如何在不改变树高度的情况下存储更多的数据，前面的几种树形结构存储数据少的原因在于其分支最多只有两个，所以此时可以考虑增加树的分支结构，因此就产生了B-树。

3.B-树

在B-树这种数据结构中每一个节点的数据块中包含三种类型的数据，分别是key值、行记录和指针，当需要进行数据读取的时候只需要一层一层向下检索即可。

在上图中，如果要读取28这条记录，那么只需要读取磁盘块1/3/8就可以将数据记录读取出来，如果一个磁盘块大小是16KB的话，那么读取48KB就可以读取到目标行记录。此时需要考虑一个问题，这样3层的B-树存满的情况下可以存储多少条数据记录，假设一个一条数据记录是1KB大小，那么第一层至多存储15条记录，第二层至多存储16（第二层子节点数）15（每个节点可以存储的行记录数）=240条记录，第三层至多可以存储1616*15=3840条记录，那么三层的B-树存满的情况下最多可以存储15+240+3840=4095条记录，此时可以看到能够存储的数据量依然不是很大，如果想要存储更多数据的话只能将树变高，变成4层或5层，这样以来又会增加IO次数还是会影响查询效率。这个时候就需要进一步分析为何B-树能够存储的数据还是很少，经过分析可以知道，B-树中每个磁盘块中的data占用了大量空间，所以此时B+树应运而生。

4.B+树

在B+树数据结构中，所有行记录的data数据都存储在树形结构的叶子节点中，非叶子节点只存储键值和指针，在进行数据检索时可以从根节点向下检索，也可以在叶子节点中从前向后或者从后向前检索，因为所有的叶子也是用一个双向链表来维护的，对任意一个叶子节点来说都可以向前或者向后查找。

在上图中，所有的data都存储在叶子节点中，也就是说第一层和第二层省掉了大量的data的存储空间，那么可以用来存储更多的数据，假设一个数据行的data还是1KB的大小，一个key加上一个指针的大小为10个字节，那么可以计算下这种树形结构可以存储多少数据，第一层一个数据块，第二层161024/10=1638个数据块，第三层1638161024/10=2683044个数据块，第三层每个数据块又可以存储16条记录，那么四层B+树可以存储的总记录数为268304416=42928704条记录，由此可以发现，B-树和B+树的数据存储不是一个量级，在相同树高的情况下，B+树可以存储更多的数据。
综上可以，MySQL为什么要选择B+树作为索引的数据结构了，刚才在计算过程中，我们做了一个假设，键值+指针一共占用了10个字节，如果这两种数据类型占用100个字节的话，那么整体的数据存储能力会缩小2个数量级，因此在回答索引树高度的时候不能具体到3层或者4层，可以给个标准说法：一般情况下，3~4层的B+树足以支撑千万级别数据量存储。

二、索引有哪些分类？

（一）从数据结构角度

哈希索引、B+树索引、FULLTEXT索引、R-Tree索引（用于对GIS数据创建SPATIAL索引）。

（二）从物理存储角度

聚簇索引、非聚簇索引。在MySQL的innodb存储引擎中，数据在进行插入的时候必须要跟某一个索引列进行绑定存储，如果有主键选择主键、没有主键选择唯一键、如果没有唯一键那么系统会自动生成一个6字节的rowid作为隐藏主键进行存储，因此：

1.聚簇索引

跟数据绑定存储的索引称之为聚簇索引。

2.非聚簇索引

没有跟数据绑定存储的索引称之为非聚簇索引。一张表中只有一个聚簇索引，非聚簇索引的叶子节点中存储聚簇索引的列值。

（三）从逻辑角度

主键索引、普通索引、唯一索引、组合索引（联合索引）。

（四）回表、覆盖索引、最左匹配原则、索引下推

1.回表

回表表示使用非聚簇索引时，数据库引擎会先根据普通索引（非聚簇索引）去非聚簇索引的索引树上找到匹配的行记录，然后根据非聚簇索引的叶子节点上存储的聚簇索引的列值去聚簇索引的索引树中查找整行记录的过程。
例如：有一张表中包含如下字段：id,name,age,gender,address,其中id是主键，name是普通索引，那么要进行如下SQL语句的查询：select * from table where name = ‘zhangsan’;
上述SQL语句的查找过程是：先根据name的值去普通索引树上进行检索，在普通索引（非聚簇索引）的叶子节点上找到聚簇索引（主键索引）的列值即主键id值，然后根据这个聚簇索引的列值（id值）去聚簇索引的B+树索引树上匹配行记录，在这个过程中一共查找了两颗索引树（非聚簇索引树和聚簇索引树），也就是说进行了多棵树的IO，因此查询效率比较低，所以在生产环境中应该尽量避免回表的产生。

2.覆盖索引

索引覆盖是指一个索引包含了查询所需要的所有数据，从而无需回表从原表（聚簇索引树）中获取数据。
假设有一张表，表中包含如下字段：id,name,age,gender,address，其中id是主键，name是普通索引，那么如果要进行如下SQL语句的查询：select id,name from table where name = ‘zhangsan’;
查找过程如下：在name这个普通索引对应的非聚簇索引树上包含了要查询的name字段，而非聚簇索引的叶子节点上又会存储聚簇索引也就是id这个主键的列值，也就是说要查询的id和name两个字段都可以从非聚簇索引的索引树上一次性全部查询出来，不用再回到id主键对应的聚簇索引树上再进行一次查询。
所以，索引覆盖可以提高查询性能，因此在在生产环境做SQL优化时可以考虑覆盖索引。

（1）SQL性能优化案例

①SQL优化前

SQL优化前通过explain关键可以看到查询并没有走filesort排序，在查询语句中加上order by进行排序后还是很慢，也就是说使用索引排序没有起到优化性能的作用。
既然没有生效，就需要从另外一个角度来考虑：可以根据所有要查询的字段建立一个组合索引以减少回表带来的性能损耗。通过把原来的索引删除掉，重新建立三个字段的索引再次进行查询，发现查询时间缩短到了不到11s。

②SQL优化后

根据三个字段重新建立联合（组合）索引后，查询时间变成不到11s，SQL查询性能优化了十几倍。
在这个案例中，是通过查询字段来建立联合索引的方式节省了回表的性能损耗，本质上是通过覆盖索引来避免了回表。这种SQL优化方案比较适用于查询字段数较少的场景中。如果查询字段数过多，根据很多个字段建立组合索引来进行性能优化并不一定能达到预期效果。

（2）SQL命令

①show processlist：查看连接状态

②show profiles：查看每条语句执行时间

3.最左匹配原则

最左匹配原则主要适用于组合索引，它指的是使用多个列值进行匹配时要严格遵循从左往右的顺序，否则会导致索引失效。

--假设有一张表，表中包含字段：id,name,age,gender,address，其中id是主键，（name，age）是组合索引。现在有如下查询：
1、select * from table where name = 'zhangsan' and age = 10;
2、select * from table where name = 'zhangsan';
3、select * from table where age = 10;
4、select * from table where age = 10 and name = 'zhangsan';
--在上面四个查询中，1、2、4都用到了索引，3用不到，因为3中的where条件中跳过了name字段没有按照建组合索引的字段顺序进行查询因此不。在4中虽然不满足最左匹配原则，但是经过***MySQL优化器***优化之后，age和name两个字段的顺序无论怎样其执行结果都是一样的，所以它也使用到了索引。

（1）MySQL架构

MySQL架构由client客户端、MySQL server服务器层、存储引擎层组成，server层又由连接器、分析器、优化器、执行器组成。因此，MySQL优化器是MySQL架构中的一部分。

4.索引下推（ICP: Index Condition Pushdown）

ICP是针对MySQL使用索引从表中检索数行记录的情况进行优化，如果没有ICP，那么存储引擎会根据索引来定位到记录，然后将结果返回给MySQL的server层，然后在server层对where条件进行筛选。在启动ICP之后，如果where条件的一部分可以通过使用索引来求值，那么MySQL会把这部分的where条件筛选下推到存储引擎中。

（1）索引下推的使用规则

①当需要访问完整的行记录时，ICP用于range、ref、eq_ref和ref_or_null访问方法

②ICP可以用于innodb表和myisam表，包括分区的innodb表和myisam表

③对于innodb表，ICP仅用于二级索引。ICP的目标是减少整行的读取次数从而较少IO操作

④在虚拟列上创建的二级索引不支持ICP

⑤引用子查询的条件不能下推

⑥引用存储函数的条件不能下推

⑦触发器条件不能下推

⑧不能将条件下推到包含对系统变量引用的派生表中

假设有一张表，表中包含以下字段：id,name,age,gender,address，其中id是主键，（name，age）是组合索引，现有如下查询：select * from table where name = ‘zhangsan’ and age = 10;
如果没有索引下推：MySQL在执行上面这条SQL语句时，会先根据name的值去存储引擎中拉取数据，然后将数据返回到MySQL server层，然后在server层对age进行条件过滤，最终把符合条件的结果返回给客户端。
如果有索引下推：MySQL在执行上面的SQL语句时，会直接根据name和age的值去存储引擎中拉取数据，而无需在server层对数据进行条件过滤。
所谓的索引下推指的是将条件的筛选从server层下推到存储引擎层。
索引下推默认是开启的，可以通过optimizer_switch中的index_condition_pushdown条件来设置开启或关闭。

SET optimizer_switch = 'index_condition_pushdown=off';
SET optimizer_switch = 'index_condition_pushdown=on';

三、如何设计优良的索引？

（一）索引列占用的空间越小也好

（二）通过count(distinct(column_name))/count(*)计算索引列的离散度，值越大也适合做索引

（三）在where条件后的order by字段上添加索引，如果有where条件则跟where条件一起创建索引，如果没有则只是给order by条件创建索引

（四）在join on的条件字段上添加索引

（五）索引个数过多会增加索引维护成本

（六）频繁更新的字段不适合做索引，因为会增加索引维护成本

（七）随机无序的值不适合做索引，比如身份证号、UUID

（八）索引列在设计时最好不要为null

（九）可以根据列前缀建立索引（计算列的前面某些连续字母的离散度确定根据哪几个字母建立索引）

四、造成索引失效的情况

（一）索引列上使用函数(replace/substr/concat/sum/count/avg)、表达式

（二）数据类型不匹配，当查询条件的数据类型和索引字段的数据类型不匹配

（三）like查询条件的关键字前面加%

（四）在组合索引中不满足最左匹配原则

（五）使用is not null

（六）MySQL优化器在分析时发现全表扫描效率比使用索引快的时候

（七）使用or关键字会导致索引失效

五、主键为什么建议选择自增主键？

如果选择自增主键，每次新增数据时都是以追加的形式进行，在当前页索引写满之后，只需要申请一个新的页继续写入即可，不会产生页分裂问题。
如果采用业务字段作为主键的话，新增数据不一定是顺序的，需要挪动数据，页面写满索引时还需要进行页分裂，为了保持索引的有序性会造成写数据的成本较高。

六、如何查看SQL是否使用了索引？

（一）查看执行计划

使用explain查看执行计划可以判断查询中是否用到了索引，以便进行SQL优化。

（二）分析执行计划

1.id

select表示查询的序列号，包含一组数字，表示查询中执行select子句或者操作表的顺序。id号分为三种情况：

（1）如果id相同那么执行顺序从上往下

explain select * from emp e join dept d on e.deptno = d.deptno join salgrade sg on e.sal between sg.losal and sg.hisal;

（2）如果id不同，如果是子查询，id的序号会递增，id值越大优先级越高越先被执行

explain select * from emp where ename not in (select ename from emp where ename like '%S%') ;

（3）如果id有相同的也有不同的，那么id相同的是一组从上往下执行，id值越大的组优先级越高

explain Select dept.*,person_num,avg_sal from dept,(select count(*) person_num,avg(sal) avg_sal,deptno from emp group by deptno) t where dept.deptno = t.deptno ;

2.select_type

用来区分查询类型，是普通查询还是联合查询或者是子查询。

（1）simple：简单查询，不包含子查询和union

explain select * from emp;

（2）primary：如果查询中包含子查询，最外层的查询会被标记成primary

explain select * from emp where ename not in (select ename from emp where ename like '%S%') ;

（3）union：若第二个select出现在union之后，那么该查询类型会被标记成union

explain select * from emp where deptno = 10 union select * from emp where sal >2000;

（4）DEPENDENT UNION：跟union类似，此处的dependent表示union或union all联合而成的结果会受外部表影响

explain select * from emp e where e.empno  in ( select empno from emp where deptno = 10 union select empno from emp where sal >2000);

（5）union result：表示一个union的结果集作为一个单独的表返回，这通常发生在union操作之后，并且可能跟其他表进行join操作

explain select * from emp where deptno = 10 union select * from emp where sal >2000;

（6）SUBQUERY：在查询中作为另一个查询的子查询的查询

explain select * from emp where sal > (select avg(sal) from emp) ;

（7）DEPENDENT SUBQUERY：与SUBQUERY类似，但是这种查询类型依赖于外部查询的某些部分

explain select e.empno,e.ename,e.sal from emp e where e.sal < (select e2.sal from emp e2 where e2.empno = e.mgr)

（8）DERIVED：出现在from子句中的子查询，MySQL会为这个子查询生成一个临时表。这个值表示该查询是为派生表生成的

explain select t.job from (select min(sal) min_sal,job from emp group by job) t where t.min_sal > 2500;

（9）DEPENDENT DERIVED：与DERIVED类似，但是这个查询依赖于外部查询的某些部分（未找到案例）

（10）MATERIALIZED：表示该子查询的结果被物化（即存储在临时表中），以供稍后的join使用，这种类型的子查询在执行时比常规子查询要慢

EXPLAIN 
select * from emp where deptno in (select deptno from (select min(sal) min_sal,deptno from emp group by deptno) a where min_sal < '2000') ;

（11）UNCACHEABLE SUBQUERY：一个子查询的结果不能被缓存，因此每次都会重新计算（未找到案例）

（12）UNCACHEABLE UNION：一个union查询的结果不会被缓存，因此每次都会重新计算（未找到案例）

3.table

表示正在访问哪一张表，表名或者别名，可能是临时表或者union合并结果集。

（1）如果是具体的表名，则表示从实际的物理表中获取数据，当然也可以是表的别名

（2）如果表名是derivedN的形式，表示使用了id为N的查询产生的衍生表

（3）当有union result的时候，表名是union n1,n2等形式，n1,n2表示参与union的id

4.type

表示访问类型，简单来说就是以何种方式去访问我们的数据。其中全表扫描效率最低，因为它是通过暴力方式遍历一张表去寻找数据，效率从最好到最坏的依次是：
system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL。一般情况下，得保证访问类型至少达到range级别，最好能达到ref级别。

（1）ALL

explain select * from emp;

（2）index

全索引扫描比全表扫描效率高，主要有两种情况，一种是当前查询走覆盖索引，即要查询的字段刚好是建立索引的字段，这样我们需要的数据直接从索引中就可以获取；另一种情况是使用了索引排序，这样就避免了使用文件排序这种传统排序算法进行排序。

explain  select empno from emp;

（3）range

表示使用索引进行查询时限定了查询的范围，这样在指定的范围内进行查询避免了index的全索引扫描，适用的操作符有：=, <>, >, >=, <, <=, IS NULL, BETWEEN, LIKE, or IN()。

explain select * from emp where empno between 7000 and 7500;

（4）index_subquery：跟unique_subquery类型，使用的是辅助索引

SET optimizer_switch='materialization=off';
EXPLAIN select * from emp where ename not in (select dname from dept where dname like '%SALES' );
SET optimizer_switch='materialization=on';

（5）unique_subquery：子查询的结果由聚簇索引或者唯一索引覆盖

dept表的deptno字段有主键。

SET optimizer_switch='materialization=off';
EXPLAIN select * from emp where deptno not in (select deptno from dept where deptno >20 );
SET optimizer_switch='materialization=on';

（6）index_merge：索引合并，在where条件中使用不同的索引字段

ename，deptno都创建索引。

explain select * from emp where ename='SMITH' or deptno = 10;

（7）ref_or_null：跟ref类似，在ref的查询基础上，加一个null值的条件查询

explain select * from emp  where ename = 'SMITH' or ename is null;

（8）ref：使用了非聚集索引进行数据的查找

alter table emp add index idx_name(ename);
explain select * from emp  where ename = 'SMITH';

（9）eq_ref ：使用唯一性索引进行数据查找

explain select * from emp e,emp e2 where e.empno = e2.empno;

（10）const：这个表至多有一个匹配行

explain select * from emp where empno = 7369;

（11）system：表只有一行记录（等于系统表），这是const类型的特例，平时不会出现

5.possible_keys

查询中可能会用到的索引，只要字段建立索引就会被识别到，但实际查询不一定能用到。

explain select * from emp where ename = 'SIMTH' and deptno = 10;

6.key：实际使用到的索引

7.key_len

索引占用的字节数，通过key_len可以计算索引长度，在不损失精度的情况下长度越短越好

8.ref：显示了哪些列或常量被用来查找索引列，这对于非唯一索引查找有效

explain select * from emp,dept where emp.deptno = dept.deptno and emp.deptno = 10;

9.rows

根据表的统计信息和索引使用情况，大致估算找出目标数据记录需要读取的行数，在保证能检索到目标数据的前提下读取的行数越少越好。

explain select * from emp;

10.filtered

表示过滤掉一部分数据后返回行的预估百分比，最大值为100表示没有对数据进行过滤，从100开始递减的值表示过滤量在增加，rows表示预估会扫描到的行记录，rows*filtered表示与下表连接的行数。

11.extra：提供查询的额外信息

（1）Using filesort

说明MySQL无法利用索引排序，只能利用排序算法进行排序，会消耗额外的位置。

explain select * from emp order by sal;

（2）Using temporary

建立临时表来保存中间结果，查询完成后删除临时表。

explain select ename,count(*) from emp where deptno = 10 group by ename;

（3）Using index

表示查询时使用覆盖索引，即直接从索引中读取数据，而不用访问数据表。如果同时出现Using where则表示索引被用来执行索引键值的查找，否则表明索引被用来读取数据而不是真正的查找。

explain select deptno,count(*) from emp group by deptno limit 10;

（4）Using where

表示使用全表或者全索引扫描后再用where子句对结果进行过滤。当使用全索引扫描时需要添加索引。

explain select * from emp where job='SMITH';

（5）Using join buffer：使用连接查询

explain select * from t3 join t2 on t3.c1 = t2.c1;

（6）Impossible WHERE：where语句的执行结果总是false

explain select * from emp where 1=0;