再有人问你MySQL索引原理，就把这篇文章甩给他！-技术圈

△Hollis, 一个对Coding有着独特追求的人△

这是Hollis的第 335 篇原创分享

作者 l zyz1992

来源 l Hollis（ID：hollischuang）

索引，可能让好很多人望而生畏，毕竟每次面试时候 MySQL 的索引一定是必问内容，哪怕先撇开面试，就在平常的开发中，对于 SQL 的优化也而是重中之重。

可以毫不夸张的说，系统中 SQL 的好坏，是能直接决定你系统的快慢的。但是在优化之前大家是否想过一个问题？那就是：我们优化的原则是什么？优化SQL的理论基础是什么？

虽然说实践出真知，但是我更相信理论是支撑实践的基础，因为我们不可能毫无目的的去盲目的实践，因为这样往往事倍功半。

所以说了这么多只想告诉大家，在真正的开始索引优化之前，我们需要彻底搞明白索引的原理。这样再谈优化你将觉得更丝滑~

1、索引的本质

索引的本质是一种排好序的数据结构。这个我相信其实大家并不陌生，因为谈到索引很多人自然而然的就会联想到字典中的目录。

没错，这样的类比是很形象的，但是如果再往深处说，恐怕很多小伙伴就有点张口结舌了，那既然你已经知道了索引的本质，那么您就已经有了看这篇文章的基础，相信读完本文的你，一定会对索引的原理有一个全新的了解。

2、索引的分类

在数据库中，索引是分很多种类的（千万不要狭隘的认为索引只有 B+ 树，那是因为我们平时使用的基本都是 MySQL）。而不同的种类很显然是为了应付不同的场合，那索引到底有那些种类呢？下面就让我们来大致的了解下。

2.1、Hash 索引

Hash 索引是比较常见的一种索引，他的单条记录查询的效率很高，时间复杂度为1。但是，Hash索引并不是最常用的数据库索引类型，尤其是我们常用的Mysql Innodb引擎就是不支持hash索引的。主要有以下原因：

Hash索引适合精确查找，但是范围查找不适合

* 因为存储引擎都会为每一行计算一个hash码，hash码都是比较小的，并且不同键值行的hash码通常是不一样的，hash索引中存储的就是Hash码，hash 码彼此之间是没有规律的，且 Hash 操作并不能保证顺序性，所以值相近的两个数据，Hash值相差很远，被分到不同的桶中。这就是为什么hash索引只能进行全职匹配的查询，因为只有这样，hash码才能够匹配到数据。

对于 hash 索引，小伙伴们只需要了解到这里就可以了。

2.2、二叉树

另外，常见的索引使用的数据结构是树结构，首先我们来介绍下最经典的二叉树。

先来介绍下二叉树的特点：

1. 二叉树的时间复杂度为 O(n)
1. 一个节点只能有两个子节点。即度不超过2
1. 左子节点小于本节点，右子节点大于本节点

首先来看一下二叉树的样子

但是在极端情况下会出现链化的情况，即节点一直在某一边增加。如下图

二叉树中，有一种特殊的结构——平衡二叉树，平衡二叉树的特点：

1. 根节点会随着数据的改变而变更
1. 数据量越多，遍历次数越多，IO次数就越多，就越慢（磁盘的IO由树高决定）

2.4、B树（二三树）

了解了二叉树之后，可以进一步谈一下什么是B树了。B 树大概是这样子的：

从B树的结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。

而每页的存储空间是有限的，如果 data 比较大，会导致每个节点的 key 存储的较少，当数据量较大的时候，同样会导致B树很深，从而增加了磁盘 IO 的次数，进而影响查询效率。

好了，说到这里，常见的索引的种类也说完了，上面的内容仅仅是作为一个铺垫，下面我们正式开始 MySQL 的 B+ 树。

2.5、B+树

MySQL 中最常用的索引的数据结构是 B+ 树，他有以下特点：

在 B+ 树中，所有数据记录节点都是按照键值的大小存放在同一层的叶子节点上，而非叶子结点只存储key的信息，这样可以大大减少每个节点的存储的key的数量，降低B+ 树的高度
B+ 树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
B+ 树的层级更少：相较于 B 树 B+ 每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
B+ 树查询速度更稳定：B+ 所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
B+ 树天然具备排序功能：B+ 树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
B+ 树全节点遍历更快：B+ 树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像 B 树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

好了说了这么多的 B+ 树的特点，我们来张图看看 B+ 树到底长什么样子（如果看不懂，也没有关系，下文会一步一步解释说明的）

上面的数据页就是实际存放数据页的地方，且数据页之间是通过双向链表进行连接的，好了到这里我们就将各个索引的类型快速了解了下，下面我们就开始正式B+树的分析。

3、主键目录

我们将上图中的数据页拿出来再细化下，就成了下面的这张图

我们都知道 MySQL 在存储数据的时候是以数据页为最小单位的，且数据在数据页中的存储是连续的，数据页中的数据是按照主键排序的（没有主键是由 MySQL自己维护的 ROW_ID 来排序的），数据页和数据页之间是通过双向链表来关联的，数据与数据时间是通过单向链表来关联的。

也就是说有一个在每个数据页中，他必然就有一个最小的主键，然后每个数据页的页号和最小的主键会组成一个主键目录（就像上图中的左边部分），假设现在要查找主键为 2 的数据，通过二分查找法最后确定下主键为 2 的记录在数据页 1 中，此时就会定位到数据页 1 接着再去定位主键为 2 的记录，我们先知道大致的流程，细节先不要深究，先从宏观看结构原理，再到微观看实现原理。

刚刚上面是说的其实可以理解为是主键索引，主键索引也是最简单的最基础的索引。这个时候大家应该知道为什么你建立了主键查询就能变快了吧？

4、索引页

但是现在假设有很多很多的是数据页，那是不是对应的主键目录会很大很大呢？

那假设有1000万条记录、5000万条记录呢？是不是就算是二分法查找，其效率也依旧是很低的，所以为了解决这种问题 MySQL 又设计出了一种新的存储结构—索引页。例如有下面这样情况，

假设上面的主键目录中的记录是非常非常多的，此时上面的结构是演变成这样子的，MySQL 会将里面的记录拆分到不同的索引页中，也就是下面这样子的

索引页中记录的是每页数据页的页号和该数据页中最小的主键的记录，也就是说最小主键和数据页号不是单纯的维护在主键目录中了，而是演变成了索引页，索引页和数据页类似，一张不够存就分裂到下一张。

假如现在要查找 id=20 的这条记录，咦？那我应该到哪个索引页中查找该条记录呢？所以这个时候肯定是需要去维护索引页的。

没错，MySQL 也是这么设计的，也就是说 MySQL 同时也设计出了用于维护索引页的数据结构，其实也还叫索引页，只不过他们是在不同的层级，类似下面这样子的：

也就是说维护索引页的索引页是在真正存储记录和数据页的索引页的上一层，现在如果你想查找 id=20 的这条记录，那就是从最上层的索引页开始查找，通过二分法查找，很快就能够定位到 id=20 s这条记录是在索引页 2 上，然后到就索引页 2 上面查找，接着就是和之前一样了（注意，索引页中的记录也是通过单向链表连接的），根据各个最小的主键能够定位到 id=20 是在数据页5上，假设数据页5是这样子的

那这个时候你是不是能够想明白数据是怎么定位的了呢？

5、索引页的分层

好，既然你已经知道到索引页太多会往上一层扩散，那现在假设上一层的索引页记录也太多了，那该怎么办？很简单，继续分裂，再往上一层继续，不废话，我来画图帮助大家理解

我看明白了，你看明白了吗？我们来模拟一个查找的过程，假设你要查找 37 这条记录，说实话我根本不知道这条记录在哪里。好，现在我们就来模拟 MySQL 的查找过程，首先从最顶层的索引页开始查找，因为 id=37，因此定位到了索引页16，然后到索引页 16 中继续查找，此时同样能够定位到 id=37 在索引页 3 中，然后继续查找，最终能够定位到数据实在数据页 8 中，假设数据页 8 是这样子的

是不是很完美？如果非要我把上面的图画完整，那….小弟义不容辞（图太大了，索引页中数据的链表结构就不画出来了）

这个时候机智的你是不是已经发现了什么小秘密？他是不是很像一颗二叉树？实际上这就是一颗 B+ 树的结构，这也是数据在磁盘中真正存储的物理结构。B+树的特性是什么呢？B+树，也是二叉搜索树的一种，但是他的数据仅仅存储在叶子节点（在这里就是数据页），像这种索引页+数据页组成的组成的B+树就是聚簇索引(这句话很重要)。

聚簇索引是 MySQL 基于主键索引结构创建的

6、非主键索引

但是现在问题又来了，既然这里强调的是主键索引，那我们平时开发中除了主键索引其他的索引也用的不少，这时候该怎么办？假设你现在对name、age建立索引。现在回顾下主键索引，是不是在插入数据的时候基于主键的顺序去维护一个 B+ 树的？

而实际上非主键索引其原理是一样的，MySQL 都是去维护一颗 B+ 树，说白了，你建立多少个索引，MySQL 就会帮你维护多少的B+树（这下是不是也突然想明白了为什么索引不能建立太多了？以前就知道不能建立太多索引，因为索引也会占用空间，实际上这就是根本原因）

假如现在真的对 name+age 建立索引，那此时是存放的呢？此时 MySQL 根据会 name+age 维护一个单独的 B+ 树结构，数据依旧是存放在数据页中的，只不过是原来数据中的每条记录写的是 id=xx，现在写的是name=xx，age=xx，id=xx，不管怎么样，主键肯定会存放的，先来张图压压惊

在插入数据的时候，MySQL 首先会根据 name 进行排序，如果 name 一样，就根据联合索引中的 age 去排序，如果还一样，那么就会根据主键字段去排序。插入的原理就是这样子的。

此时每个数据页中的记录存放的实际是索引字段和主键字段，而其他字段是不存的（为什么不存放？一样的数据到处存放很浪费空间的，也没必要，所以才会有下面的索引优化），至于查找，原理和过程跟聚簇索引一样，这里就不再赘述，但是，下面说的内容却是至关重要的：假设现在执行这样的SQL：

SELECT name FROM student WHERE name='wx'

那么此时的查询是完美的，使用到了索引且不需要回表

7.回表

是这样子的，现在要根据 name 查找到该条记录，且查询的字段（即 select 后面的查询字段）也仅仅有 name（只要是在 name,age,id 这三个字段中都可以）这个时候是能够直接获取到最终的记录的

换句话说，因为联合索引中的记录也仅仅有 name，age，id，所以在查询的如果也仅仅查询这三个字段，那么在该B+树中就能够查询到想要的结果了。

那现在假设查询的 SQL 是这样子的（我们假设 student 中还有除了name，age，id 其他的字段）

SELECT * FROM student WHERE name='wx'

那这下子就完蛋了，因为你现在虽然根据 name 很快的定位到了该条记录，但是因为 name+age 不是聚簇索引，此时的 B+ 树的数据页中存放的仅仅是自己关联的索引和主键索引字段，并不会存其他的字段，所以这个时候其他的属性值是获取不到的，这时候该怎么办？

这种情况下，MySQL 就需要进行回表查询了。此时 MySQL 就会根据定位到的某条记录中的 id 再次进行聚簇索引查找，也就是说会根据 id 去维护 id 的那么 B+ 树中查找。因为聚簇索引中数据页记录的是一条记录的完整的记录，这个过程就叫回表。

再强调下回表的含义：根据非主键索引查询到的结果并没有查找的字段值，此时就需要再次根据主键从聚簇索引的根节点开始查找，这样再次查找到的记录才是完成的。

最后，让我一起看下 MySQL 对于非主键索引的维护过程：

对于非主键索引（一般都是联合索引），在维护 B+ 树的时候，会根据联合索引的字段依次去判断，假设联合索引为：name + address + age，那么 MySQL 在维护该索引的 B+ 树的时候，首先会根据 name 进行排序，name 相同的话会根据第二个 address 排序，如果 address 也一样，那么就会根据 age 去排序，如果 age 也一样，那么就会根据主键字段值去排序，且对于非主键索引，MySQL 在维护 B+ 树的时候，仅仅是维护索引字段和主键字段。

推荐阅读：

你管这破玩意儿叫 Token?

一举拿下高可用与分布式协调系统设计!

一文读懂微内核架构

欢迎关注微信公众号：互联网全栈架构，收取更多有价值的信息。