MySQL索引能让查询效率提高这么多缘由是？

背景

我信赖大家在数据库优化的时候都会说到索引，我也不例外，大家也根本上能对数据构造的优化答复个一二三，乃至页缓存之类的都能扯上几句，但是有一次阿里P9的一个面试问我：你能从运算机层面开端说一下一个索引数据加载的流程么？（就是想让我聊IO）

我当场就去世了....由于运算机网络和操纵系统的根基知识真的是我的盲区，不外后面我恶补了，废话不多说，我们就从运算机加载数据聊起，讲一下换个角度聊索引。

正文

MySQL的索引本质上是一种数据构造

让我们先来理解一下运算机的数据加载。

磁盘IO和预读：

先说一下磁盘IO，磁盘读取数据靠的是机械运动，每一次读取数据需要寻道、寻点、拷贝到内存三步操纵。

寻道时间是磁臂移动到指定磁道所需要的时间，一样在5ms以下；

寻点是从磁道中寻到数据存在的阿谁点，均匀时间是半圈时间，假如是一个7200转/min的磁盘，寻点时间均匀是600000/7200/2=4.17ms；

拷贝到内存的时间很快，和前面两个时间比起来可以忽略不计，所以一次IO的时间均匀是在9ms摆布。听起来很快，但数据库百万级别的数据过一遍就到达了9000s，明显就是劫难级别的了。

思考到磁盘IO是非常昂扬的操纵，运算机操纵系统做了预读的优化，当一次IO时，不但把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，由于当运算机拜访一个地址的数据的时候，与其相邻的数据也会很快被拜访到。

每一次IO读取的数据我们称之为一页(page)，详细一页有多大数据跟操纵系统有关，一样为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO。

（忽然想到个我刚毕业被问过的问题，在64位的操纵系统中，Java中的int类型占几个字节？最大是多少？为什么？）

那我们想要优化数据库查询，就要尽量减少磁盘的IO操纵，所以就显现了索引。

索引是啥？

MySQL官方对索引的定义为：索引(Index)是帮忙MySQL高效猎取数据的数据构造。

MySQL 中常用的索引在物理上分两类，B-树索引和哈希索引。

本次主要讲BTree索引。

BTree索引

BTree又叫多路均衡查寻树，一颗m叉的BTree特性如下：

• 树中每个节点最多包括m个孩子。
• 除根节点与叶子节点外，每个节点至少有[ceil(m/2)]个孩子（ceil()为向上取整）。
• 若根节点不是叶子节点，则至少有两个孩子。
• 所有的叶子节点都在统一层。
• 每个非叶子节点由n个key与n+1个指针组成，其中[ceil(m/2)-1] <= n <= m-1 。

这是一个3叉（只是举例，真实会有许多叉）的BTree构造图，每一个方框块我们称之为一个磁盘块或者叫做一个block块，这是操纵系统一次IO往内存中读的内容，一个块对应四个扇区，紫色代表的是磁盘块中的数据key，黄色代表的是数据data，蓝色代表的是指针p，指向下一个磁盘块的位置。

来模拟下查寻key为29的data的历程：

1、按照根结点指针读取文件名目的根磁盘块1。【磁盘IO操纵1次】

2、磁盘块1储备17，35和三个指针数据。我们发明17<29<35，因此我们寻到指针p2。

3、按照p2指针，我们定位并读取磁盘块3。【磁盘IO操纵2次】

4、磁盘块3储备26，30和三个指针数据。我们发明26<29<30，因此我们寻到指针p2。

5、按照p2指针，我们定位并读取磁盘块8。【磁盘IO操纵3次】

6、磁盘块8中储备28，29。我们寻到29，猎取29所对应的数据data。

因而可知，BTree索引使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效力。

但是有没有什么可优化的地方呢？

我们从图上可以看到，每个节点中不仅包括数据的key值，还有data值。而每一个页的储备空间是有限的，假如data数据较大时将会致使每个节点（即一个页）能储备的key的数目很小，当储备的数据量很大时一样会致使B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效力。

B+Tree索引

B+Tree是在B-Tree根基上的一种优化，使其更适合实现外储备索引构造。在B+Tree中，所有数据记载节点都是依照键值大小次序存置在统一层的叶子节点上，而非叶子节点上只储备key值信息，这样可以大大加大每个节点储备的key值数目，落低B+Tree的高度。

B+Tree相关于B-Tree有几点不一样：

非叶子节点只储备键值信息， 数据记载都存置在叶子节点中， 将上一节中的B-Tree优化，由于B+Tree的非叶子节点只储备键值信息，所以B+Tree的高度可以被紧缩到特殊的低。

详细的数据如下：

InnoDB储备引擎中页的大小为16KB，一样表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一样为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大约储备16KB/(8B+8B)=1K个键值（由于是估值，为利便运算，这里的K取值为〖10〗^3）。

也就是说一个深度为3的B+Tree索引可以保护10^3 10^3 10^3 = 10亿 笔记录。（这种运算方式存在误差，并且没有运算叶子节点，假如运算叶子节点其实是深度为4了）

我们只需要停止三次的IO操纵就可以从10亿条数据中寻到我们想要的数据，比起最开端的百万数据9000秒不知道好了多少个华莱士了。

并且在B+Tree上平常有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，并且所有叶子节点（即数据节点）之间是一种链式环构造。所以我们除了可以对B+Tree停止主键的范畴查寻和分页查寻，还可以从根节点开端，停止随机查寻。

数据库中的B+Tree索引可以分为汇集索引（clustered index）和辅助索引（secondary index）。

上面的B+Tree示例图在数据库中的实现即为汇集索引，汇集索引的B+Tree中的叶子节点存置的是整张表的行记载数据，辅助索引与汇集索引的不同在于辅助索引的叶子节点并不包括行记载的全部数据，而是储备响应行数据的汇集索引键，即主键。

当通过辅助索引来查询数据时，InnoDB储备引擎会遍历辅助索引寻到主键，然后再通过主键在汇集索引中寻到完全的行记载数据。

不外，虽然索引可以加快查询速度，提高 MySQL 的处置机能，但是过多地使用索引也会造成以下弊端：

• 创立索引和保护索引要消耗时间，这种时间随着数据量的增添而增添。
• 除了数据表占数据空间之外，每一个索引还要占必然的物理空间。假如要创立聚簇索引，那么需要的空间就会更大。
• 当对表中的数据停止增添、删除和修改的时候，索引也要动态地保护，这样就落低了数据的保护速度。

留意：索引可以在一些状况下加快查询，但是在某些状况下，会落低效力。

索引只是提高效力的一个因素，因此在创立索引的时候应当遵照以下原则：

• 在经常需要搜索的列上创立索引，可以加快搜索的速度。
• 在作为主键的列上创立索引，强迫该列的独一性，并组织表中数据的摆列构造。
• 在经常使用表连接的列上创立索引，这些列主如果一些外键，可以加快表连接的速度。
• 在经常需要按照范畴停止搜索的列上创立索引，由于索引已经排序，所以其指定的范畴是持续的。
• 在经常需要排序的列上创立索引，由于索引已经排序，所以查询时可以利用索引的排序，加快排序查询。
• 在经常使用 WHERE 子句的列上创立索引，加快前提的推断速度。

此刻大家知道索引为啥能这么快了吧，其实就是一句话，通过索引的构造最大化的减少数据库的IO次数，究竟，一次IO的时间真的是太久了。。。

总结

就面试而言许多知识其实我们可以很容易就把握了，但是要以学习为目的，你会发明许多东西我们得深入到运算机根基上才能发明其中神秘，许多人问我如何记住这么多东西，其实学习本身就是一个很无奈的东西，既然我们不克不及不学那为啥不好好学？去学会享受呢？比来我也在恶补根基，后面我会开端更新运算机根基和网络相关的知识的。

我是敖丙，你知道的越多，你不知道的越多，我们下期见！

人才们的 【三连】 就是敖丙创作的最大动力，假如本篇博客有任何错误和倡议，欢迎人才们留言！