mysql性能优化1:深入认识索引

前言

在定位现网问题的过程中，经常会发现数据库cpu接近百分百，死锁，页面查询缓慢等问题，这些可能都涉及一个概念——数据库性能优化，说到 数据库 性能优化,就不得不提索引。

正确 的创建 合适 的索引是提升数据库查询性能的 基础 ，本文将重点梳理与索引有关的概念，以便于让大家更好地认识、理解并用好索引。

现网问题现象

mysql cpu告警

慢查询

死锁

以上种种问题，究其原因，多数与索引脱不了干系，如果你遇到了类似的问题，该怎么去定位与分析，你是否有一套完整的方法论呢？如果不确定，那么你来对了，请仔细阅读以下内容，全面地认识下索引，本文将以5W1H的方式展开。

注：5W: What,Why,Who,When,Where 1H: How

为什么要用到索引(Why)

在讲为什么要用到索引之前，我们先试着思考一个问题 :

如果让你来实现，从表中大量的行中查询满足条件的记录，你会怎么做？

能够想到的最简单的方式应该是表轮询，通过遍历的方式逐行对比（全表扫描），过滤出期望的结果。
-- 理论上功能可以实现，但其算法的时间复杂度为O(N)，当表的数据量非常大时，性能怎么保证？

接着思考下第二个问题：

那么，怎么才能提升查询的性能呢？

哦，为了提升查询的性能，好像有一种算法叫二分查找，这种的查找的方式好像可以提升性能。
-- 好像有这么回事，但如果没记错的话，二分查找应该是有条件的，比方说数据肯定要按照顺序排列好吧？我们知道，数据中的记录一般是无序的，如果按此方案，岂不是要先排序，再查找，这样一来带来的开销岂不更大？

顺着这个思路，我们再看下第三个问题：

那么，这个问题究竟该怎么解决呢？

呃，如果每次查询前都先 排序 再查询，这样性能肯定不高，我可以在另外一个地方先将记录排好序（异步），后续进行查询的时候就直接从我排序好结果中查找，此时就可以使用二分查找的方法来实现高性能了。

好像有那么点意思了，其实，这里的“在另外一个地方先将记录排好序”，给这种方式起个好听的名字，就叫“索引”，这就解释了为什么需要索引的问题：

• 索引能极大的减少存储引擎需要扫描的数据量（类似二分查找的方式，减少扫描数量）

• 索引可以把随机IO变成顺序IO（查询前先排序）

• 索引可以帮助我们在进行分组、排序等操作时，避免使用临时表（复杂场景下复杂操作）

在弄明白了为什么要用索引的问题之后，我们来看下索引的定义。

什么是索引（What）

参考下百度百科的介绍：

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑 指针 清单。索引的作用相当于图书的目录，可以根据目录中的 页码 快速找到所需的内容。

索引是为了加速对表中数据行的检索而创建的一种分散的存储结构。索引是针对表而建立的，它是由数据页面以外的索引页面组成的，每个索引页面中的行都会含有逻辑指针，以便加速检索物理数据。

在数据库关系图中，可以在选定表的“索引/键” 属性页 中创建、编辑或删除每个索引类型。当保存索引所附加到的表，或保存该表所在的关系图时，索引将保存在数据库中。

注：参考 https://baike.baidu.com/item/%E7%B4%A2%E5%BC%95/5716853

简而言之：

索引 是为了加速对表中数据行的检索而创建的一种分散存储的 数据结构 ，其原理如下图所示：

索引是谁实现的（Who）

索引是由数据库存储引擎实现的，不同的数据库存储引擎其实现方式存在差异，mysql常用的存储引擎包括myisam和innodb等，其中 mysql 5.5之前默认的存储引擎为myisam，mysql 5.5及以后的版本默认为innodb。

注：参考下图，了解下Mysql体系结构及常用的存储引擎（标红部分）

什么时候会用到索引（When or Where）

在查询的 sql 中，如果where条件列加了索引，则有可能会用到索引,而以下sql语句是否会用到索引呢？

• insert into table values (…);

• update table set ? where ?;

• delete from table where ?;

答案是都有可能的。增删改本质上有两部分： 先将数据读取出来，再对数据进行修改 。前一部分读取操作是当前读，需要获取最新版本的数据，insert可能会触发unique检查，也算当前读。

注：关于当前度和快照读，请参考相关材料或关注本公众号后续系列文章

怎么实现索引（How）

顺着在为什么要使用索引中提到的结论，利用索引可以事先将需要查询的信息进行排序，以便于后续查询时首先利用二分查找算法，提升效率。

由索引的概念可知，索引是一种 数据结构 ，这种数据结构可以加速对表的检索，说到数据结构，自然想到常用的数据结构: 数组、栈、队列、链表、树、图、堆、散列表等，那么，mySql的索引应该采用哪种数据结构呢？

mysql中索引使用的是树形结构来实现索引，树的结构又分为二叉树、二叉查找树、平衡二叉树（AVL树，红黑树）、B树、B+树、B*树、Trie树等，mySql索引使用的哪种树以及为什么选取这种树？下面简单做下分析。

注： https://www.cnblogs.com/maybe2030/p/4732377.html

二叉查找树（Binary Search Tree）

二叉查找树定义 ：又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2) 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点值；

3) 左、右子树也分别为二叉排序树；

4) 没有键值相等的节点。

二叉查找树示例图：

分析： 二叉查找树进行中序遍历，即可得到有序的数列。

弊端: 它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度(左斜树、右斜树)。原因在于插入和删除元素的时候，树没有保持平衡 。

平衡二叉树（Balanced binary search tree）

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。

平衡二叉树示例图如下所示：

注: AVL树通过旋转的方式完成自平衡的操作（详细请参与相关资料）

平衡二叉树的问题

• 它太深了

  数据处的（高）深度决定着他的IO操作次数，IO操作耗时大

• 太太小了

• 每一个磁盘块（节点/页）保存的数据量太小了

• 没有很好的利用操作磁盘IO的数据交换特性

• 也没有利用好磁盘IO的预读能力（空间局部性原理），从而带来频繁的IO操作

B Tree(多路平衡查找树)

B树也是一种用于查找的平衡树，但是它不是二叉树。

B树的定义： B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

B Tree示例图如下：

B+ Tree（加强版多路平衡查找树）

　B+树是B树的变体，也是一种多路搜索树：
　　其定义基本与B-树相同，B+ Tree与B Tree的区别如下：
　　1) 非叶子结点的子树指针与关键字个数相同；B+节点关键字搜索采用闭合区间（B-树是开区间）
　　2) B+非叶节点不保存数据相关信息，只保存关键字和子节点的引用；
　　3) B+关键字对应的数据保存在叶子节点中
　　4) B+叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系

B+Tree的示例图如下：

为什么选择B+Tree

1. B+树是B-树的变种（PLUS版）多路绝对平衡查找树，他拥有B-树的优势

2. B+树扫库、表能力更强

3. B+树的磁盘读写能力更强

4. B+树的排序能力更强

5. B+树的查询效率更加稳定（仁者见仁、智者见智）

   注：B+树每次遍历都必须走到叶子节点才能得出结论，因此其查询的效率更加稳定，但不一定最快。

了解了索引的数据结构之后，我们来看下mySql的索引体现形式

Mysql B+Tree索引体现形式

Myisam 存储引擎中的索引结构

myisam存储引擎的索引文件由两部分组成： .myi文件及.myd文件，其中.myi文件存放的是索引信息，.myd文件存放的是数据信息。

myisam存储引擎的主键索引示例如下：

myisam存储引擎的联合索引示例如下：

innodb 存储引擎中的索引结构

innodb存储引擎以主键为索引来组织数据的存储，只存在一个.IBD文件，该文件既保存索引信息，又保存数据信息。

主键索引示例如下图所示：

注: 这里注意区分下聚簇索引与非聚簇索引

聚簇索引，是以主键为索引的索引成为聚簇索引或聚集索引。

非聚集索引，不是以主键为索引的索引称为非聚簇索引，或非聚集索引。

innodb中的联合索引示意图如下所示：

注：由上图可知，辅助索引指向的数据其实是主键。

Innodb 与 Myisam 对比

innodb与myisam两种存储引擎中索引的数据结构对比，如下图所示：

参考：数据库为什么要用B+树结构

https://www.cnblogs.com/xyxxs/p/4440187.html

以上，索引相关的概念已介绍完毕，接下来我们再看一些与索引有关的补充内容。

索引的补充知识

列的离散型

问：如上图所示，找出离散型性最好的列？

答： name

结论：离散型越高，选择性就越好

最左匹配原则

对索引中关键字进行计算（对比），一定是从左往右依次进行，且不可跳过

联合索引

单列索引      

节点中只有一个关键字，如在表users的【name】字段上加索引。

联合索引      

节点中有多个关键字,如在表users的 【name,phoneNum】两个字段上加索引。

单列索引是特殊的联合索引

联合索引列选择原则

1，经常用的列优先 【最左匹配原则】

2，选择性（离散度）高的列优先【离散度高原则】

3，宽度小的列优先【最少空间原则】

如何合理创建索引

经排查发现最常用的sql语句：

Select * from users where name =  ? ;
Select * from users where name = ? and phoneNum = ?;

针对这种情况，应该怎么添加索引才合适呢，有人给出的答案如下

解决方案：创建两个联合索引

create index idx_name on users(name);

create index idx_name_phoneNum on users(name,phoneNum);

思考：这种解决方案有什么问题？

答案：根据最左匹配原则，‘ idx_name_phoneNum ’可包含‘index idx_name’，在name列单独创建索引浪费空间且没有必要。

覆盖索引

如果查询列可通过索引节点中的关键字直接返回，则该索引称之为覆盖索引。 覆盖索引可减少数据库IO，将随机IO变为顺序IO，可提高查询性能。

简单来说，如果表users的 【name,phoneNum】两个字段上加了索引，使用如下查询语句可以直接从索引中获取值而不需要到表中再做映射，提高了查询的效率。

select name ,phoneNum from users where name='zhangsan' and phoneNum='15894931365'

这也是不推荐使用select * 的一个原因，使用select * 将无法使用覆盖索引。

总结

本文详细介绍了数据库中的索引相关的概念，重新认识了一下索引，主要了解了：什么是索引，为什么要用索引，哪些地方可以用到索引，索引由谁实现，索引怎么实现，使用的是什么数据结构及相互对比，希望对你有所帮助。

数据库相关的内容及概念很多，本文中的信息较多参考了网络，在学习时，需要梳理出一条主线重点研究，不然很容易淹没在各类信息中，难以形成体系化。 此块信息量很大，不能贪大求全，关键需要考虑的是，在此过程中究竟能有多少可以内化为自己的东西，以便于在使用时可以做到活学活用，而不是“面向搜索引擎编程”。

下一篇将接着梳理下mysql的体系架构，系统性地再深入认识下mysql，加油！

附录