数据库索引，看这一篇就够了

前言

索引是一个比较抽象的东西，不同于数据库运维人员，开发人员往往不需要理解的那么深刻，而只需要大概知道它是一个什么东西，在脑海中有一个大致的轮廓图就好了，能够帮助我们更好的使用索引和明白为什么要这么使用，这就达到目的了。因此，本文针对的是开发人员，讲的也比较浅显，请各位大佬轻喷。

索引概述

索引是储存在磁盘中的一种特殊文件(也可能有部分在内存中)。为什么说它特殊呢，它是将数据库表中的某一列或几列的值进行排序后的具有特殊搜索结构的文件。通过它，我们可以快速从数据库表中读取所需的信息。

这是一段很抽象的描述，我们很难想象出它到底是怎样的一种结构。

假设我们有一张100w数据的表，id从1排到了1000000。在没有索引的情况下，我们要查找id=666666的数据，由于是无序的，它也不知道id=666666的数据藏在哪里，只能一条条的逐一排查，运气不好的话，可能扫描到最后一行。

我们所说的扫描过程实际上是将磁盘中的数据加载到内存中的过程，这就是我们通常所说的磁盘IO操作，磁盘IO是非常高昂的操作，访问磁盘的成本大概是访问内存的十万倍左右。因此，我们优化的出发点就有了：要尽可能的减少IO。

我们首先想到的，要是这个100w数据有序就好了，这样就可以用二分法，先扫描50w-100w的数据，再扫描50w-75w的数据。。。这样就可以大幅减少扫描的次数，也就达到了减少磁盘IO的目的。

还有没有更高效的方法呢?

有一种经典的数据结构，二叉树，大概长这样：

这里不讲它的原理啊，特点啊，时间复杂度计算啊等等这些，感兴趣的可以搜索一下。这里只需要知道一点，它的搜索效率很高，但是有一个缺点：每个节点存储的数据量很少。这就导致了同样数量级的数据，在二叉树中不可避免的会增加树的高度，而树高的增加，就会导致IO次数的增多。比如我们要拿到1这个数据，那么读取的顺序将是7-5-2-1，先将7的数据从磁盘加载到内存中，再将5的数据从磁盘加载到内存中，然后是2,1，最终经过4次IO拿到所需数据。如果数据量再大，树高再增加，IO次数也相应的会增多。这里是有一个公式的，高度是与总节点数正相关。

看到这里我们就明白了，树越矮，节点数就越少，所需磁盘IO次数越少，效率就越高。

如果让树矮一点呢?数据量一定的情况下，自然是每个节点挂载的数据越多，节点就越少，树也就越矮!

这就出现了B树的概念。B树是一个多叉树，每个节点可以挂载多个子节点，大概是这么个样子：

很显然，树矮了。

实际上，mysql的InnoDB 引擎使用的正是B树的存储结构，更为准确一点，是B+树，它是在B-树的基础上改进而来，它将表数据只存储在叶子节点上， 而其他非叶子节点只存储索引的key。大概是这么个样子：

这样一个3层的B+树就可以表示千万级的数据。而要访问到最终的数据，只需要3次IO，这在性能上是一个巨大的提升。其实，树的根节点往往在内存中，那么访问磁盘的次数就更少了。

接下来，我们通过主键索引和非主键索引来说明一下整个的索引流程。首先有一张表，表结构长这样：

主键索引

如上图所示，叶子节点中存储的是表中的整行数据，非叶子节点中存储的是主键的key值，我们通过主键ID去查某一条数据的时候，比如说查ID= 8的数据。先将非叶子节点的索引key值加载到内存中，产生一次IO，定位到ID=8的数据应该在P2所指向的磁盘页中，于是系统再执行一次IO操作，将P2指向的磁盘页中的数据加载到内存中，在内存中经过筛选，找到ID=8的数据返回给客户端。这样就完成了ID=8数据的索引查询。整个过程执行了两次IO操作。

再来看一下非主键索引。

非主键索引

非主键索引中以name为索引字段。可以看到跟主键索引不同的是，非主键索引中叶子节点存储的不是完整的表数据，而是表数据的主键ID值。索引查询过程跟主键索引一样，先将非叶子节点的索引key值加载到内存，找到指向的磁盘页，再将磁盘页中的数据加载到内存，在内存中筛选出所需的数据。这个过程也是执行了两次IO操作。

这样就完了吗?

显然不是，因为非主键索引存储的，只是一个主键ID值，而我们需要的是完整的表数据，我们通过两次IO操作拿到主键ID值后，还要再走一遍主键索引的流程，才能拿到完整数据，也就是说，非主键索引查找我们所需的数据，要执行四次IO操作。

通过非主键索引拿到ID，再执行主键索引的过程，叫做回表。是不是很熟悉?

理解了这些，其实再想想为什么不用select *，尽量用到覆盖索引，也就不难理解了，一切的初衷都是为了：减少磁盘IO。