——————————————
文章来源：
https://blog.csdn.net/zl1zl2zl3/article/details/88321108
文章来源：
https://zhuanlan.zhihu.com/p/89935484
面试
问：数据库中最常见的慢查询优化方式是什么？
同学A：加索引。
问：为什么加索引能优化慢查询？
同学A：...不知道
同学B：因为索引其实就是一种优化查询的数据结构，比如Mysql中的索引是用B+树实现的，而B+树就是一种数据结构，可以优化查询速度，可以利用索引快速查找数据，所以能优化查询。
问：你知道哪些数据结构可以提高查询速度？（听到这个问题就感觉此处有坑...）
同学B：哈希表、完全平衡二叉树、B树、B+树等等。
问：那这些数据结构既然都能优化查询速度，Mysql为何选择使用B+树？
同学B：...不知道
提问
SHOW INDEX FROM employees.titles;
有一个titles表，主键由empno，title，fromdate三个字段组成。
那么以下几个语句会用到索引吗?
select * from employees.titles where emp_no=1select * from employees.titles where title='1'select * from employees.titles where emp_no='1' and title=1select * from employees.titles where title='1' and emp_no=1
为什么哈希表、完全平衡二叉树、B树、B+树都可以优化查询，为何Mysql独独喜欢B+树？
哈希表有什么特点？
假如有这么一张表(表名：sanguo)：
现在对name字段建立哈希索引：
注意字段值所对应的数组下标是哈希算法随机算出来的，所以可能出现哈希冲突。那么对于这样一个索引结构，现在来执行下面的sql语句：
select * from sanguo where name='周瑜'
可以直接对‘周瑜’按哈希算法算出来一个数组下标，然后可以直接从数据中取出数据并拿到所对应那一行数据的地址，进而查询那一行数据。那么如果现在执行下面的sql语句：
select * from sanguo where name>'周瑜'
则无能为力，因为哈希表的特点就是可以快速的精确查询，但是不支持范围查询。
如果用完全平衡二叉树呢？
还是上面的表数据用完全平衡二叉树表示如下图（为了简单，数据对应的地址就不画在图中了。）：
图中的每一个节点实际上应该有四部分：
1.左指针，指向左子树
2.键值
3.键值所对应的数据的存储地址
4.右指针，指向右子树
另外需要提醒的是，二叉树是有顺序的，简单的说就是“左边的小于右边的”假如我们现在来查找‘周瑜’，需要找2次（第一次曹操，第二次周瑜），比哈希表要多一次。而且由于完全平衡二叉树是有序的，所以也是支持范围查找的。
如果用B树呢？
还是上面的表数据用B树表示如下图（为了简单，数据对应的地址就不画在图中了。）：
可以发现同样的元素，B树的表示要比完全平衡二叉树要“矮”，原因在于B树中的一个节点可以存储多个元素。
如果用B+树呢？
还是上面的表数据用B+树表示如下图（为了简单，数据对应的地址就不画在图中了。）：
我们可以发现同样的元素，B+树的表示要比B树要“胖”，原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。
那么B+树到底有什么优势呢？
这里我们用“反证法”，假如我们现在就用完全平衡二叉树作为索引的数据结构，我们来看一下有什么不妥的地方。实际上，索引也是很“大”的，因为索引也是存储元素的，我们的一个表的数据行数越多，那么对应的索引文件其实也是会很大的，实际上也是需要存储在磁盘中的，而不能全部都放在内存中，所以我们在考虑选用哪种数据结构时，我们可以换一个角度思考，哪个数据结构更适合从磁盘中读取数据，或者哪个数据结构能够提高磁盘的IO效率。回头看一下完全平衡二叉树，当我们需要查询“张飞”时，需要以下步骤
1.从磁盘中取出“曹操”到内存，CPU从内存取出数据进行比较，“张飞”<“曹操”，取左子树（产生了一次磁盘IO）
2.从磁盘中取出“周瑜”到内存，CPU从内存取出数据进行比较，“张飞”>“周瑜”，取右子树（产生了一次磁盘IO）
3.从磁盘中取出“孙权”到内存，CPU从内存取出数据进行比较，“张飞”>“孙权”，取右子树（产生了一次磁盘IO）
4.从磁盘中取出“黄忠”到内存，CPU从内存取出数据进行比较，“张飞”=“张飞”，找到结果（产生了一次磁盘IO）
同理，回头看一下B树，我们发现只发送三次磁盘IO就可以找到“张飞”了，这就是B树的优点：一个节点可以存储多个元素，相对于完全平衡二叉树所以整棵树的高度就降低了，磁盘IO效率提高了。
而B+树是B树的升级版，只是把非叶子节点冗余一下，这么做的好处是为了提高范围查找的效率。
到这里可以总结出来，Mysql选用B+树这种数据结构作为索引，可以提高查询索引时的磁盘IO效率，并且可以提高范围查询的效率，并且B+树里的元素也是有序的。
那么，一个B+树的节点中到底存多少个元素合适呢？
其实也可以换个角度来思考B+树中一个节点到底多大合适？
答案是：B+树中一个节点为一页或页的倍数最为合适。因为如果一个节点的大小小于1页，那么读取这个节点的时候其实也会读出1页，造成资源的浪费；如果一个节点的大小大于1页，比如1.2页，那么读取这个节点的时候会读出2页，也会造成资源的浪费；所以为了不造成浪费，所以最后把一个节点的大小控制在1页、2页、3页、4页等倍数页大小最为合适。
那么，Mysql中B+树的一个节点大小为多大呢？
这个问题的答案是“1页”，这里说的“页”是Mysql自定义的单位（其实和操作系统类似），Mysql的Innodb引擎中一页的默认大小是16k（如果操作系统中一页大小是4k，那么Mysql中1页=操作系统中4页），可以使用命令SHOW GLOBAL STATUS like 'Innodb_page_size'; 查看。
并且还可以告诉你的是，一个节点为1页就够了。
为什么一个节点为1页（16k）就够了？
解决这个问题，我们先来看一下Mysql中利用B+树的具体实现。
Mysql中MyISAM和innodb使用B+树
通常我们认为B+树的非叶子节点不存储数据，只有叶子节点才存储数据；而B树的非叶子和叶子节点都会存储数据，会导致非叶子节点存储的索引值会更少，树的高度相对会比B+树高，平均的I/O效率会比较低，所以使用B+树作为索引的数据结构，再加上B+树的叶子节点之间会有指针相连，也方便进行范围查找。上图的data区域两个存储引擎会有不同。
MyISAM中的B+树
MYISAM中叶子节点的数据区域存储的是数据记录的地址
主键索引
辅助索引
MyISAM存储引擎在使用索引查询数据时，会先根据索引查找到数据地址，再根据地址查询到具体的数据。并且主键索引和辅助索引没有太多区别。
InnoDB中的B+树
InnoDB中主键索引的叶子节点的数据区域存储的是数据记录，辅助索引存储的是主键值
主键索引
辅助索引
Innodb中的主键索引和实际数据时绑定在一起的，也就是说Innodb的一个表一定要有主键索引，如果一个表没有手动建立主键索引，Innodb会查看有没有唯一索引，如果有则选用唯一索引作为主键索引，如果连唯一索引也没有，则会默认建立一个隐藏的主键索引（用户不可见）。另外，Innodb的主键索引要比MyISAM的主键索引查询效率要高（少一次磁盘IO），并且比辅助索引也要高很多。所以，我们在使用Innodb作为存储引擎时，我们最好：
1.手动建立主键索引
2.尽量利用主键索引查询
回到我们的问题：为什么一个节点为1页（16k）就够了？
对着上面Mysql中Innodb中对B+树的实际应用（主要看主键索引），可以发现B+树中的一个节点存储的内容是：
1.非叶子节点：主键+指针
2.叶子节点：数据
那么，假设我们一行数据大小为1K，那么一页就能存16条数据，也就是一个叶子节点能存16条数据；再看非叶子节点，假设主键ID为bigint类型，那么长度为8B，指针大小在Innodb源码中为6B，一共就是14B，那么一页里就可以存储16K/14=1170个(主键+指针)，那么一颗高度为2的B+树能存储的数据为：117016=18720条，一颗高度为3的B+树能存储的数据为：11701170*16=21902400（千万级条）。所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。所以也就回答了我们的问题，1页=16k这么设置是比较合适的，是适用大多数的企业的，当然这个值是可以修改的，所以也能根据业务的时间情况进行调整。
最左前缀原则
我们模拟数据建立一个联合索引
select*,concat(right(emp_no,1),"-",right(title,1),"-",right(from_date,2))from employees.titles limit10;
那么对应的B+树为
我们判断一个查询条件能不能用到索引，我们要分析这个查询条件能不能利用某个索引缩小查询范围
对于 select * from employees.titles where emp_no=1
是能用到索引的，因为它能利用上面的索引所有查询范围，首先和第一个节点“4-r-01”比较，1<4，所以可以直接确定结果在左子树，同理，依次按顺序进行比较，逐步可以缩小查询范围。对于 select * from employees.titles where title='1'
是不能用到索引的，因为它不能用到上面的索引，和第一节点进行比较时，没有empno这个字段的值，不能确定到底该去左子树还是右子树继续进行查询。对于 select *from employees.titles where title='1' and emp_no=1
是能用到索引，按照我们的上面的分析，先用title='1'这个条件和第一个节点进行比较，是没有结果的，但是mysql会对这个sql进行优化，优化之后会将empno=1这个条件放到第一位，从而可以利用索引。
讲完了索引原理，我们再来回答一下这些常见的面试题：
1、你一般怎么建索引的？
2、讲讲索引的分类？你知道哪些？
3、如何避免回表查询?什么是索引覆盖?
4、现在我有一个列，里头的数据都是唯一的，需要建一个索引，选唯一索引还是普通索引？
5、mysql索引是什么结构的？用红黑树可以么？
6、mysql某表建了多个单索引，查询多个条件时如何走索引的？
1、你一般怎么建索引的？
嗯，这道题其实很基础。但是有没有做过，这题是可以看出来的。
去my.cnf里配置三个配置：
打开慢查询日志slow_query_log=1慢查询日志存储路径slow_query_log_file=/var/log/mysql/log-slow-queries.logSQL执行时间大于3秒，则记录日志long_query_time=3
监控到慢SQL后，就马上开始建索引?
NO,NO,NO….这种时候，应该先考虑你的SQL能不能进行SQL优化。
例如，当只要一行数据时使用 limit 1
查询时如果已知会得到一条数据，这种情况下加上 limit 1 会增加性能。因为 mysql 数据库引擎会在找到一条结果停止搜索，而不是继续查询下一条是否符合标准直到所有记录查询完毕。
然而大多数情况下，业务SQL十分复杂，没法优化。所以就要建立索引了。这个时候，参照如下规则建立索引：
1.索引并非越多越好，大量的索引不仅占用磁盘空间，而且还会影响insert,delete,update等语句的性能；
2.避免对经常更新的表做更多的索引，并且索引中的列尽可能少；对经常用于查询的字段创建索引，避免添加不必要的索引；
3.数据量少的表尽量不要使用索引，由于数据较少，查询花费的时间可能比遍历索引的时间还要短，索引可能不会产生优化效果；
4.在条件表达式中经常用到不同值较多的列上创建索引，在不同值很少的列上不要建立索引。比如性别字段只有“男”“女”俩个值，就无需建立索引。如果建立了索引不但不会提升效率，反而严重减低数据的更新速度；
5.在频繁进行排序或者分组的列上建立索引，如果排序的列有多个，可以在这些列上建立联合索引。
2、讲讲索引的分类？你知道哪些？
从物理存储角度：
聚簇索引和非聚簇索引
从数据结构角度：
B+树索引、hash索引、FULLTEXT索引、R-Tree索引
从逻辑角度:
1.主键索引：主键索引是一种特殊的唯一索引，不允许有空值
2.普通索引或者单列索引
3.多列索引（复合索引）：复合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用复合索引时遵循最左前缀集合
4.唯一索引或者非唯一索引
5.空间索引：空间索引是对空间数据类型的字段建立的索引，MYSQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING、POLYGON。
3、如何避免回表查询?什么是索引覆盖?
这个问题，如果要看详细版，请参阅文章《Innodb中索引的原理》
这里简单说一下。
当能通过读取索引就可以得到想要的数据，那就不需要回表读取行了。一个索引包含了（或覆盖了）满足查询结果的数据就叫做索引覆盖。
例如此时有一张表table1,有一个联合索引(a,b)
执行如下SQL
select a,b from table1
在索引上就能找到结果，就不用回表去查询！
而你执行的是：
select a,b,c from table2
c列在索引上不存在，就需要回表查询。
需要说明的是覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引不存储索引列的值，所以mysql只能用B+ tree索引做覆盖索引。
4、现在我有一个列，里头的数据都是唯一的，需要建一个索引，选唯一索引还是普通索引？
答唯一索引！
首先，在孤尽出的《阿里巴巴JAVA开发规范》中有这么一段话：
【强制】业务上具有唯一特性的字段，即使是多个字段的组合，也必须建成唯一索引。
说明：不要以为唯一索引影响了 insert 速度，这个速度损耗可以忽略，但提高查找速度是明显的；另外，即使在应用层做了非常完善的校验控制，只要没有唯一索引，根据墨菲定律，必然有脏数据产生。
那好，下一问出现了！
为什么唯一索引的插入速度比不上普通索引？为什么唯一索引的查找速度比普通索引快？
这个问题就要从Insert Buffer开始讲起了，在进行非聚簇索引的插入时，先判断插入的索引页是否在内存中。如果在，则直接插入；如果不在，则先放入Insert Buffer 中，然后再以一定频率和情况进行Insert Buffer和原数据页合并(merge)操作。
这么做的优点:能将多个插入合并到一个操作中，就大大提高了非聚簇索引的插入性能。
InnoDB 从 1.0.x 版本开始引入了 Change Buffer，可以算是对 Insert Buffer 的升级。从这个版本开始，InnoDB 存储引擎可以对 insert、delete、update 都进行缓存。
唯一索引的插入比普通索引慢的原因就是:
1.唯一索引无法利用Change Buffer
2.普通索引可以利用Change Buffer
于是乎下一问又来了！
为什么唯一索引的更新不使用 Change Buffer？
因为唯一索引为了保证唯一性，需要将数据页加载进内存才能判断是否违反唯一性约束。但是，既然数据页都加载到内存了，还不如直接更新内存中的数据页，没有必要再使用Change Buffer。
最后回答一下，唯一索引的搜索速度比普通索引快的原因就是:
1.普通索引在找到满足条件的第一条记录后，还需要判断下一条记录，直到第一个不满足条件的记录出现。
2.唯一索引在找到满足条件的第一条记录后，直接返回，不用判断下一条记录了。
5、mysql索引是什么结构的？用红黑树可以么?
这个妥妥答最常见的B+ Tree。
AVL树和红黑树基本都是存储在内存中才会使用的数据结构。在大规模数据数据存储的时候，显然不能将全部数据全部加载进内存，因此如果采用红黑树，就会造成频繁IO，效率低下。
那为啥不用B Tree,而选择B+ tree呢？
这就需要贴一下经典的两张图。B tree是长下面这样的：
注意一下B tree的两个明显特点：
1.树内存储数据
2.叶子节点上无链表
而B+ tree长下面这样的：
注意一下B+ tree的两个明显特点：
1.数据只出现在叶子节点
2.所有叶子节点增加了一个链指针
接下来就可以开始编了～～
比如数据库索引采用B+ tree的主要原因是B Tree在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+ tree应运而生。B+ tree只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，如果使用B Tree，则需要做局部的中序遍历，可能要跨层访问，效率太慢。
提示，我下一问就是:
你刚才说了这么多B tree不行，那你知道为啥Mongodb用B Tree当索引，而不用B+ Tree么？
(从关系数据库和非关系数据库的区别角度去答，不拓展了！仔细想想，在Mongodb里表示二者的关系，你会怎么处理!)
6、mysql某表建了多个单索引，查询多个条件时如何走索引的？
其实，我看到这题的时候，内心一抖。这题让后端开发来答，真的很拼功底！
这里希望大家先看看我的另一篇文章《我是一条DQL》。此题在考优化器的知识！此题是在考察优化器如何抉择索引的！优化器会评估出走哪个索引最优，然后执行。
Mysql在优化器中有一个优化器称为Range 优化器，负责进行范围查询的优化！
那么该优化器计算执行成本有两种方式index dive与index statistics。
它们是MySQL优化器对开销代价的估算方法，前者统计速度慢但是能得到精准的值，后者统计速度快但是数据未必精准。
坦白说写到这里，我内心痛哭流涕，要把index dive和index statistics写明白，真不是一件容易的事，这里只能稍微扯扯。
对于index dive，计算成本的方式为：
COST = CPU COST + IO COST
其中CPU COST指的是处理返回记录所花的开销。而IO COST指的是读取页面的开销。
mysql会对每种索引的执行情况，进行上述成本计算，最后以成本小的方式进行执行。
但是呢，在某些情况下mysql执行index dive的成本太大。因此优化器会选择以index statistics方式进行估算成本。
具体如下：
SHOW INDEX FROM tbl_name [FROM db_name]
此时出来的结果中，有一列名为Cardinality，该值表示索引列中不重复值的个数。
简单来说就是，索引列的唯一值的个数，如果是复合索引就是唯一组合的个数。
这个数值将会作为mysql优化器对语句执行计划进行判定时依据。如果唯一性太小，那么优化器会认为，这个索引对语句没有太大帮助，而不使用索引。
Cardinality值越大，就意味着，使用索引能排除越多的数据，执行也更为高效。
