1. 认识索引

索引是一种常见的数据库优化手段，设计优良的索引能够大幅提升数据库的查询效率，提升并发能力。

举一个例子来说，一本《新华字典》收录了日常使用的常见汉字，如果要查其中的一个字，可以采用如下的办法：

  • 一页一页的翻，直到找到该字；
  • 利用拼音索引，找到这个字对应的页码，根据页码去这一页查看；
  • 利用偏旁部首检字法，找到这个字对应的页码，根据页码去这一页查看。

上面三种办法，第一个办法是最慢的，第二和第三种办法，适用于不同的应用场景，如果只知其字不知其音，则偏旁部首检字法较快，如果知道这个字的读音，那么拼音检字法是最快的。

实际上数据库也可以看作是一本收录了所有业务数据的大字典，要检索这本大字典里的数据，可以一个记录一个记录的去遍历查找，也可以编制一个索引，利用索引提升查询效率。

一言以蔽之，索引是为了提高查询的效率出现的。

2. 常见的索引模型及其数据结构

索引的实现方式有很多种，实际上索引也是一种数据的组织方式。就像字典的偏旁部首索引和拼音索引，只是用了不同的方式将字和页码对应了起来。

比较常见的索引模型有下面几种：

  • 哈希表
  • 有序数组
  • 查找树

2.1 哈希表

查找最快的方法是什么？这是一个值得思考的问题，如果有下面一个函数：

浅析索引技术（一） - 图1#card=math&code=value%20%3D%20f%28key%29)

其中key是要找的关键字，value是存储位置，那么我们可以利用这个函数，直接找到key的保存位置，这种方式的时间复杂度是O(1)，基本上找不到比这种方式还快的了。

在《数据结构》这门课程中，这种查找方式被称为散列（hashing）或者哈希。

散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。对应关系f称为散列函数。

散列既是一种存储方式，也是一种查找方式。

下图展示了一个理想的散列表：

image.png

从上图能得出一个结论：

散列技术最适合的是等值查询。

但是散列技术有一个问题，即冲突（collision）问题，问题是这样的，假设存在两个key：key1和key2，其中key1!=key2，但是两个key的散列值却一样，即f(key1)=f(key2)，这样就会出现数据查找错误问题。

为了解决冲突问题，人们提出了多种方案，常见的简单方案有分离链接法和开放定址法。由于本文不是专门描述数据结构和算法的，并不会用很多的篇幅详细描述这两种方法。

下面我们来描述一下分离链接法，其做法是将散列到同一个值的所有元素保留到一个表中。我们一般用链表实现，下面的图展示了这种方法：

image.png

这种情况下，f(36)=f(16)=6，在寻找关联字16的时候，搜索到的实际上是一个数组{36,16}，那么此时只需要做一个数组的查找即可得到想要的值。

需要注意的是，我并没有强调散列值是有序的，散列值也不会是有序的，因此如果哈希索引用作范围查找的时候，可能会出现遍历所有散列值的情况，效率非常低下。这一点再次印证了上面的结论：

散列技术最适合的是等值查询。

2.2 表查找

表是最简单的一种ADT，它的定义是零个或者多个数据元素的有限序列。举一个简单的例子，图书馆里书架上的书籍，就可以看作是一个元素为书的表。

表可以有多种实现方式，比如我们可以用数组去实现，也可以用链表来实现。在Java中，对应的也有两种List类型ArrayList和LinkedList。

之前的章节中提到散列技术不适合范围查找，实际上范围查找正是表的长项。

image.png

上图是一个顺序表，注意顺序表不是有序表。在这张表上要查询一个元素时，需要从头到尾遍历一遍，最好的情况，时间复杂度是O(1)，最坏的情况，时间复杂度是O(n)，顺序表的平均查找次数为(n+1)/2，因此其时间复杂度仍旧是O(n)。在这样一种数据结构上进行范围查找，显然是不太好的。

但是如果是有序表，情况会变得很不一样：

image.png

在这样的一个数据结构上，我们要查找一个元素，对于算法的不二选择就是二分查找。实际上二分查找这个算法虽然简单，但是广泛的应用于数据库系统中。

二分查找的基本思路是：在顺序表中，取中间元素作为比较对象，若给定值和中间记录相等，查找成功；若给定值小于中间元素，则在左半区继续进行二分查找，若给定值大于中间元素，则在右半区继续进行二分查找，直到成功（或失败）为止。

实际上二分查找的算法还包括了递归的思想，这里不再展开。

二分查找的时间复杂度是O(logn)，远远好于顺序查找的O(n)。二分查找是基于有序表的，因此首先还要加一步排序操作，幸运的是数据库在组织索引的时候都是有序的。

如果是范围查找，查找[a, b]区间的数据，只需要首先利用二分查找找到元素a，然后向右遍历表，直到查找到b即可。

这个结构堪称完美，不过还是稍微有一些瑕疵，考虑这样一种情况：超时结账台前的队伍很长，此时一个加塞的人要挤到队伍中，那么如果他成功了，他以后的所有人都要向后挪一位。

表也是如此，一个插入操作或者删除操作都会造成表的元素移动，最好的情况下，这种操作的时间复杂度是O(1)，最坏的情况时间复杂度就会变O(n)，平均时间复杂度还是O(n)。

那么就说明这种数据结构适合元素不怎么变化的情况。当然就不适合数据库的索引了，数据库是用来保存数据的，数据不会一成不变。

2.3 树

树是一种稍微复杂点的数据结构，其大部分操作的时间复杂度都是O(logn)，这种结构很常用，InnoDB的索引就是一棵树的结构。

树是n（n>=0）个节点的有限集合。n=0时称为空树。在任意一颗非空树中，有且仅有一个特定的节点称为根（root）；当n>1时，其余节点可以分为m（m>0）个互不相交的有限集，其中每一个集合又是一棵树，称为根的子树。

image.png

上图是一个具体的树的实现。这里说明几个概念：

  • 节点的层次：从根开始定义，根的孩子节点为第二层，以此类推；
  • 树的深度即树中节点的最大深度。

那么上图中树就是一个深度为3的树。

接下来我们会把一些元素组织称一个二叉查找树，并由此来说明基于二叉查找树的索引。

image.png

此时查询一个元素要如何查呢？我们知道二叉查找树的特点是左儿子小于父节点，右儿子大于父节点。那么要找31这个元素，其查找顺序就是：

50—>25—>37—>31

注意上图是一颗平衡二叉树，查找的时间复杂度是O(logn)。

这么看来，一个平衡二叉树，其搜索时间复杂度和有序表一样，那么能否解决有序表添加元素的弊端呢？

下面是一个演示：

image.png

对于二叉树来说，这个操作很简单，但是破坏了平衡性，至于如何维持平衡，可以参考专门描述数据结构的书籍。

总体而言，二叉树的搜索效率接近二分查找，且插入效率高于有序表，是一种优良的数据结构。但是数据库系统也没有应用二叉查找树作为索引的数据结构。

其实原因很简单，仍旧如上图所示，不断写入的节点会增加树的深度，那么随着数据的增多，查找的IO消耗就会增加。为了规避这个问题，数据库系统实际上大量采用了B+树。

2.4 B+树

B+树是B树的一种，在本文中，我们会首先介绍B树。B树也叫做多路查找树，实际上B树就是为了磁盘存储出现的一种数据结构。

现代操作系统上有成千上万的系统文件和不计其数的用户文件，这些文件的管理其实也涉及到了数据结构的设计，如果这些文件按照二叉树的样子设计，那么这棵树会变得很大很深，这就会使得读取的次数变得非常多，基于这种效率上的考虑，人们引入了多路查找树。

多路查找树，其每一个节点的孩子树可以多于两个。

B树有很多变种，数据库系统普遍采用的是B+树。接下来的篇幅中会比较详细的叙述B+树。

B树有一个特点，即每个元素只在树上出现一次，但是B+树则不然，所有的元素都会出现在叶子节点上，也有可能出现在分支节点。同时，每个叶子节点都会保存一个指向下一叶子节点的指针。

如果将上面的二叉树转换成一颗B+树，则一定是如下图所示的样子：

image.png

只有两层，中间节点所有的元素都会出现在叶子节点中，这实际上已经不再是一颗严格的树了。

如果要搜索37这个元素，只要在[31,56)这个指针的指向地址处进行遍历即可，实际需要遍历的元素只有4个，一般使用二分查找进行遍历，其时间复杂度为O(logn)，对于这个例子，其时间复杂度只有O(1)。

2.5 特例

B+树虽然看起来很美，但是B+树要产生最大的效能，需要注意一个重要的概念，即选择度，这个概念很多数据库的书都有详细描述，此处不再赘述。对于低选择度的列，B+树索引的效率并不好，这种选择度低的列最典型的例子就是性别。

性别只有两种，因此一个1000万的表，很可能500万的male记录和500万的female记录。

Oracle中有一种特殊的索引用来优化这种低选择度列的优化，即bitmap索引。

image.png

上图是一个位图索引的示意图。我们把F和M分别做成一个bitmap，其长度和表记录数相同，用0和1表示是否是F或者M。

位图索引保存了rowid，可以迅速定位到记录存在的那一行，实现加速查询。

MySQL InnoDB引擎并不支持位图索引，位图索引本身也并不适合OLTP系统，因为每当用户更新一条记录时，比如更新Gender=F的记录，那么所有Gender=F的记录都会被加锁，只有commit之后才会释放。这种加锁机制是一个很重的操作，并不适合要求快速响应的OLTP系统。

3. InnoDB的索引

3.1 一条SQL是如何使用索引的

以前文中的一个索引和表为例：

  1. create table t
  2. (
  3.    id int primary key,
  4.    col int,
  5.    key (col)
  6. );

image.png

如果我们要执行这样一个SQL：

select * from t where col >= 51;

那么其对索引的检索步骤应该是这样的：

  1. 在索引上找到col>=51的最小记录，即col=56这一条，得到对应的主键Id值；
  2. 在主键索引上利用上一步查询到的主键Id检索所有数据；
  3. 去索引上取下一个col值，得到Id；
  4. 在主键索引上利用上一步查到的Id检索所有数据；
  5. 循环以上步骤直到不满足条件。

这个过程一定会去表上进行检索，这个过程称为回表。上面这个例子里，一共回表的次数是6次。回表是一种比较费时的操作，多了一次IO，拖慢了效率，很多时候索引优化要考虑的一点就是解决回表问题。这个在讲述索引覆盖的时候在详细描述这个问题。

3.2 高性能索引策略

3.2.1 索引的区分度

之前的章节中提到了一种位图索引，这种索引是为了那种区分度低的列专门设计的。我们可以给一个近似的公式来说明索引的区分度：

区分度 = 命中的行数 / 所有记录数

回到上面的例子里，一个1000万的表，Gender只有两种F或者M，每一种Gender的记录数都差不多，500万左右，那么区分度是0.5。

如果用SQL来计算一个列的区分度，那么语句一般是这样的：

select count(distinct col1)/count(*) from t;

可以看到，区分度最大的就是主键，唯一键之类的列，最终结果接近1，越趋近于1，区分度越高，索引效果越好，越趋近于0，区分度越低，索引效果越差。

这种区分度就不太适合用B+树索引了，索引我们在设计索引的时候首先要考虑的一个问题就是这个列区分度如何，如果太低，那就没有必要建立索引了，而且InnoDB也并不支持位图索引。

3.2.2 最左前缀原则

一个表上并不是索引越多越好，相反越来越多的索引还会占用不少存储空间，也会增加写入的成本。

比如这样一张表：

create table test
(
   a int primary key,
   b int,
   c int,
   d int,
   e varchar(12)
);

这个表上的的查询如下：

select * from test where b = ? and c = ?;
select * from test where b = ?;
select * from test where b = ? and c=? and d=?;

这个表的索引应该怎么加？我在实践中见过很多这样的案例，最后的结果大部分都是这样的：

create table test
(
   a int primary key,
   b int,
   c int,
   d int,
   e varchar(12)，
   key (b),
   key (b ,c),
   key (b, c, d)
);

上面这些索引里，只有（b,c,d）这个就够了。这就是本节要讲的索引最左前缀原则。

如果(b,c,d)上有一个联合索引，那就相当于有了三个索引：(b)，(b,c)，(b,c,d)，上面的查询都可以用到索引。这种现象叫做最左前缀，但是注意，这个查询是没有办法用到索引的：

select * from test where c = ? and d = ?;

最左前缀原则的存在，可以让索引的设计上不再那么冗余，这么一来，如何决定联合索引的顺序就是一个要提到台面上来的问题了。这种时候，一般需要DBA结合业务需求，设计出良好的联合索引来。

3.2.3 索引覆盖

之前的章节中有提及到“回表”的概念，即一个查询命中索引之后，还需要根据索引记录的主键去表中检索，取回需要的数据。

这个回表的过程就是一次IO的过程，而计算机中提升性能的一个关键点就是减少IO的次数，如果能够不回表就好了。

其实也不难做到，我们知道，索引基于B+树构建，每一个叶子节点上都有所有的索引列值。那么只要我们的查询所需要的数据都在索引内，也就可以进行索引覆盖了，回到上面的例子中，这个SQL是一定可以进行索引覆盖的：

select c from test where b=?;

c列也是索引(b,c,d)的一部分，因此直接在索引树的叶子节点上拿到数据返回用户，不需要再去回表，效率较高。

利用了索引覆盖的查询，在执行计划的Extra列会出现Using index字样。

3.2.4 ICP，MRR和BKA

还是上面的例子，考虑这个SQL：

select * from test where b=2 and d=4;

这个SQL首先会在索引上命中所有b=2的叶子节点，然后获取这些叶子节点上的主键值，利用主键值去回表查询。这个表上的索引没有(b,d)上的索引，也就不能避免回表。

本例中，回表之后需要检索的行数是3行，这三行里进行条件过滤，也就是说回表次数是三次。

从MySQL5.6开始提供了一种叫做索引下推的技术，即ICP技术，这种技术可以直接在索引中进行过滤，减少回表的次数。

在本例中，如果使用了ICP技术，则会在(b,c,d)索引上进行一次过滤，将所有d=4的记录过滤出来，拿到主键值再去进行回表操作，这里只需要回表一次，明显提高了效率。

使用了ICP技术的查询，执行计划中的Extra列会有”Using index condition“字样。

我们现在知道了辅助索引是如何构建的，但是辅助索引的存储顺序和主键索引并不相同。因此在回表的时候，根据主键Id去主键索引上检索，就可能会出现随机IO。至少机械磁盘处理随机IO的能力很差，所以我们还是要想办法降低随机IO。

下面这张图来自MariaDB的博客，说明了回表过程的随机IO：

image.png

如果将辅助索引检索出来的结果集按照PK先排序，然后再去回表查询就好了，因此MariaDB提出了解决方案，如下图：

image.png

这个特性由optimizer_switch参数控制，默认是开启的：

set optimizer_switch='mrr=on';

mrr_cost_based表示是否通过cost base的方式来启用MRR。选择mrr=on,mrr_cost_based=off，总是开启MRR优化。

参数read_rnd_buffer_size用来控制键值缓冲区的大小。

再来考虑更复杂一点的情况，在两表join的时候，是不是也会出现随机IO呢？答案是肯定的，考虑下面的查询：

image.png

这个查询可以画这样一个示意图：

image.png

这样就又出现了随机IO，如果所有数据都在缓冲池里这倒不是什么问题，但是如果需要去磁盘里检索，随机IO的问题就会被放大，BKA算法就是为了解决这个问题出现的，如下图：

image.png

其大致过程如下：

  1. BKA使用join buffer保存由join的第一个操作产生的符合条件的数据。
  2. 然后BKA算法构建key来访问被连接的表，并批量使用MRR接口提交keys到数据库存储引擎去查找查找。
  3. 提交keys之后，MRR使用最佳的方式来获取行并反馈给BKA。

现在就可以看一看BKA和MRR的关系了：

image.png

3.2.5 索引和锁

虽然InnoDB是行级锁，但是它的行级锁是通过辅助索引实现的，这一点让人很困惑。下面来做一个实验：

create table test
(
   a int primary key,
   b int,
   c int,
   d int,
   e varchar(12)
);

除了主键之外没有其他的索引，我们现在看看这个表上都有什么数据：

image.png

那么按照这个表格进行的操作，会有什么样的结果：

图片.png

如果是行级锁，那么b=2的三列会被锁住，而不会锁住b=3的三列，但是实际结果不是这样，事务B在时刻3被锁住了：

image.png

事务A一直没有释放，导致超时回滚。这证明了此时发生的锁，实际上是表级的。现在给b列加上索引，重新执行上面的SQL，结果是事务B此时并不会被阻塞。

鉴于此，在设计表的时候，一定要注意添加索引，以免出现不可预知的锁升级问题，导致大面积并发能力下降。

这种情况在Oracle上不会发生。

4. 小结

索引技术，实际上一系列数据结构技术的综合应用。虽然现在各项技术，思想层出不穷，但是“数据结构+算法”的经典公式仍旧有意义。

索引看似很简单，有时候随手加上一个索引就能解决当下遇到的查询问题，但是索引又不是那么简单的，背后的思想和实现技术又非常复杂。这要求DBA需要全程参与到项目设计中去，参与到代码开发过程中去，在项目中站在一个比较高的高度上审视问题，设计优良的索引。