MySQL查询性能优化前，必须先掌握MySQL索引理论

欢迎关注公众号【 Ccww技术博客 】，原创技术文章第一时间推出

越努力，越幸运，

本文已收藏在GitHub中 JavaCommunity , 里面有面试分享、源码分析系列文章，欢迎收藏，点赞

https://github.com/Ccww-lx/JavaCommunity

数据库索引在平时的工作是必备的，怎么建好索引，怎么使用索引，可以提高数据的查询效率。而且在面试过程，数据库的索引也是必问的知识点，比如：

• 索引底层结构选型，那为什么选择B+树？

• 不同存储引擎的索引的体现形式有哪些？

• 索引的类型

  • 组合索引存储方式

  • 查询方式

  • 最左前缀匹配原则

• 覆盖索引是什么？

看着这些，能说出多少，理解多少呢？因此我们需要去探究其内在原理。

那索引是什么？

索引的目的为了加速检索数据而设计的一种分散存储（索引常常很大，属于硬盘级的东西，所以是分散存储）的数据结构,其原理以空间换时间。

快速检索的实现的本质是数据结构，通过不同数据结构的选择，实现各种数据快速检索，索引有哈希索引和B+树索引。

索引底层结构选型，那为什么选择B+树？

数据库索引底层选型归根到底就是为提高检索效率，那么就需要考虑几个问题：

• 算法时间复杂度  

• 是否存在排序

• 磁盘IO与预读

NOTE：考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。

哈希表( Hash Table,散列表 )

哈希表是根据键（Key）而直接访问在内存存储位置的数据结构。

通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。虽然查询时间复杂度为 O (1)，但存在着碰撞问题，最坏情况会导致时间复杂急剧增加;

而且哈希表其只适合精准key（等于）检索，不适合范围式检索，范围检索就需要一次把所有数据找出来加载到内存，没有效率，因此不适合Mysql的底层索引的数据结构。

普通的二叉查找树

为了优化高效范围查询，且时间复杂度小，引入二叉查找树

二叉查找树的时间复杂度是 O(lgn)，由于数据已排序好了，所以范围查询是可以高效查询，

但会存在的问题：左右子节点的深度可能相差很大，最极端的情况只有左子树或者右子树，此时查找的效率为O(n)，检索性能急剧下降，因此也不适合Mysql的底层索引的数据结构。

平衡二叉树（AVL树）

为了优化二叉树左右子树深度相差太大的问题，我们引入了平衡二叉树，即左右子节点的深度差不超过1，平衡二叉树看来好像适合，实现了：

• 范围查找、数据排序

• 查询性能良好O(logn)

NOTE: 上图中一个磁盘块，代表硬盘上的一个存储位置

但是我们还有一个最重要因素需要考虑，磁盘IO与预读，且数据库查询数据的瓶颈在于磁盘 IO,使用平衡二叉树根据索引进行查找时，每读一个磁盘块就进行一次IO，这样没有实现计算机的预读能力，导致检索效率下降，总结出平衡二叉树作为索引的问题

• 太深了（即它只有二条路），深度越大进行的IO操作也就越多

• 太小了，每一次IO才查询磁盘块这么一点数据，太浪费IO了。操作系统规定一次IO最小 4K ，Mysql一次IO 16K ，而图上的磁盘块能明显达不到4K

B+树

为了优化磁盘IO和预读，减少IO操作，条路太少了，那么换成多条路，那么会想到使用 B树 和 B+树 ，但 B树 每个节点限制最多存储两个 key，也会造成IO操作过于频繁，因此优化思路为：尽可能在一次磁盘 IO 中多读一点数据到内存，那么 B+树 也该出场：

• B+树一个节点能存很多索引，且只有B+树叶子节点存储数据

• 相邻节点之间有一些前驱后继关系

• 叶子节点是顺序排列的

相对于B树，B+树的优势有：

• B+树扫库扫表的能力更强

  • B树的数据是存放在每一个节点中的，节点所在的物理地址又是随机的，所以扫表的话，进行的是随机IO

  • B+树的数据是存放在叶子节点的，且在一个叶子节点中的数据是连续的，所以扫表的话，进行的相对的顺序IO

• B+树的磁盘读写能力更强，枝节点不保存数据，而保存更多的关键字。一次IO就能读出更多的关键字

• B+树的排序能力更强，B+树的叶子节点存储的数据是已经排好序的

索引的体现形式

索引在不同的存储引擎中体现形式步一样， 最常见的是：

• Innodb 引擎中体现为聚集索引方式 （索引和数据是存放在同一个文件的）

• Myisam引擎中体现为非聚集索引方式 （索引和数据是存放在两个文件中的）

聚集索引方式（InnoDB存储引擎）

InnoDB存储引擎中，索引和数据是存放在同一个文件的，属于聚集索引 。而且InnoDB会自动建立好主键 ID 索引树, 因此建表时要求必须指定主键的原因。

其中，主键索引（聚集索引）的叶子节点记录了数据，而不是数据的物理地址。辅助索引的叶子节点存放的是主键key。所以当利用辅助索引查找数据时，实际上查了两遍索引（辅助索引和主键索引）:

• 先查询辅助索引树找出主键

• 然后在主键索引树中根据主键查询数据

非聚集索引方式（Myisam存储引擎）

Myisam存储引擎中，索引和数据是存放在两个文件中的，属于非聚集索引 。不管是主键索引还是辅助索引，其叶子节点都是记录了数据的物理地址。

MySQL的索引类型

MySQL索引可以分为：

• 普通索引(index):加速查找

• 唯一索引：

  • 主键索引：primary key ：加速查找+约束（不为空且唯一）

  • 唯一索引：unique：加速查找+约束 （唯一）

• 联合索引：

  • primary key(id,name):联合主键索引

  • unique(id,name):联合唯一索引

  • index(id,name):联合普通索引

• 全文索引full text :用于搜索很长一篇文章的时候，效果最好。

其中，主要理解一下联合索引的问题，存储结构，查询方式。

联合索引

联合索引，多个列组成的索引叫做联合索引，单列索引是特殊的联合索引。 其存储结构如下：

对于联合索引来说其存储结构只不过比单值索引多了几列，组合索引列数据都记录在索引树上，（不同的组合索引，B+树也是不同的），且存储引擎会首先根据第一个索引列排序后，其他列再依次将相等值的进行排序。

NOTE:叶节点第一排，按顺序排序好，第二列，会基于第一列排序好的，将第一列相等的再下一列再排序，依次类推。

联合索引查询方式，存储引擎首先从根节点（一般常驻内存）开始查找，然后再依次在其他列中查询，直到找到该索引下的data元素即ID值，再从主键索引树上找到最终数据。

而且联合索引其选择的原则：

• 最左前缀匹配原则（经常使用的列优先）

• 离散度高的列优先

• 宽度小的列优先

最左前缀匹配原则

最左前缀匹配原则和联合索引的 索引构建方式及存储结构 是有关系的。根据上述理解分析，可以得出联合索引只能从多列索引的第一列开始查找索引才会生效，比如:

假设表user上有个联合索引(a,b,c)，那么 select * from user where b = 1 and c = 2将不会命中索引

原因是联合索引的是存储引擎先按第一个字段排序，再按第二个字段排序，依次排序。

离散度

当索引中的一列离散度过低时，优化器可能直接不走索引，离散度计算方法：

离散度 = 列中不重复的数据量  /  这一列的总数据量

覆盖索引

如果一个索引包含(或覆盖)所有需要查询的字段的值，称为覆盖索，即只需扫描索引而无须回表查询 。 覆盖索引可减少数据库IO，将随机IO变为顺序IO，可提高查询性能。

对于InnoDB辅助索引在叶子节点中保存了行的主键值，所以如果辅助索引(包括联合索引)能够覆盖查询，则可以避免对主键索引的二次查询。比如：

--创建联合索引
create index name_phone_idx on user(name,phoneNum);
--此时是覆盖索引，原因是根据name来查，命中索引name_phone_idx，
--其关键字为name,phoneNum，本身就已经包含了查询的列。
select name,phoneNum where name = "张三";  
--如果id为主键的话，此时也称作覆盖索引，原因：辅助索引的叶子节点存的就是主键
select id,name,phoneNum where name = "张三";

总结

MySQL的索引有很多知识点要掌握，已学习了索引的底层存储结构，不同存储引擎中的索引体现，以及索引类型的基础原理知识分析，可以为后续的数据库优化提供理论知识的支撑，也会更好的理解优化方案。后续会有优化篇章

谢谢各位点赞，没点赞的点个赞支持支持

最后，微信搜《Ccww技术博客》观看更多文章，也欢迎关注一波。