深入浅出MySQL索引

1、索引的基本概念

索引是数据库中一个很重要的概念，那么什么是索引呢，通俗的讲，索引是存储引擎用于快速找到记录的一种数据结构，就如同书的目录，当要查找某一行记录时，可以在索引中快速定位所在的位置信息，然后就可直接获取目标行的记录。

既然索引的出现是为了提高查找效率，那么肯定会存在不同的索引结构(模型)，不同的索引模型肯定有其适应的场景，在下面文章中，我们将重点讲解常见的索引模型及其特点。

2、常见的索引模型

用于提高读写效率的数据结构有很多，我们常见的有哈希表、数组和搜索树。

2.1哈希索引

哈希表是以键值对(key-value)存储的数据结构，根据key查找value，只有Memory引擎支持哈希索引，它根据哈希函数将列值key转换成实际物理位置，然后将value存放在该数组中。



但是，多个key经过可以计算后可能会出现同一个位置的情况，这种情况被称为哈希冲突，我们可以用链地址法来解决，其思路是在有冲突的数组索引位置拉出一个链表



哈希索引使用的是散列算法，所以存储的位置很分散，因此该索引适用于等值查询的场景中，不适用于范围查询。

2.2 有序数组索引

数组索引的思路很简单，它可以根据索引的位置快速找到存储的元素，又因为数组是有序的，所以该索引在范围查询中效果较好。



如果仅仅是查询，采用有序数组的索引肯定是非常合适的，但是当向数组中插入数据时，就需要在插入的位置后的元素都向后移，效率很低，因此有序数组索引仅仅适用于查询操作。

2.3 树索引

树也是一种数据结构，它综合数组和链表的特点，在保证检索速度的基础上，同时也保证了数据的插入、删除和修改的速度。

我们以二叉搜索树为例，我们看一下二叉搜索树结构



二叉所搜树定义了在非叶子结点中，左子结点的值小于结点值，右子结点的值大于等于结点值，这样的二叉树称为二叉排序树。加入我们要查找2，它走的路径为7-->3-->1-->2，查询的时间复杂度为O(log(N))，但是这个时间复杂度依赖于这棵树为平衡二叉树。

树是可以存在多叉的，即多叉树中的每个结点存在多个子结点，子结点的数据大小要保障从左到右是递增的。二叉树是搜索效率最高的，但是在数据库中并不适用二叉树，因为索引不仅存在内存中，还要写到磁盘中，为了让一个查询尽可能减少读磁盘次数，就必须让查询访问尽量少的数据块，因此使用最多的是多叉树。



3、InnoDB索引模型分析

通过上面的内容，了解了多叉树由于读写性能的优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。实际上，InnoDB使用的树模型是B+树，数据库表是根据主键的顺序以索引的形式存放的，每一个索引都对应着一个B+树，在学习B+树之前，我们先了解下B树，最后对比说明为什么数据库索引选择B+树而不选择B树。

3.1B树索引

B树是一种多叉自平衡搜索树，它与普通二叉树的区别在于允许每个结点有更多的子结点。它设计思想是将更多相关的数据尽量集中在一起，以便一次读取多个数据，减少磁盘操作的次数，它能够最大化的优化大块数据的读和写操作，加快了了存取速度。



B树有以下特点：

• 关键字分布在整个整棵树中

• 任何一个关键字只会出现在树中的某一个节点

• 搜索效率等价于二分查找

它的优点是可以在内部结点同时存储键和值，因此，将频繁访问的数据存放在靠近根结点的地方将会提高热点数据的查询效率，这种特性使得B树在特定数据重复多次查询的场景中非常的高校。

3.2B+树索引

B+树是对B树的进一步优化，B+树图如下



B+树的特点

• B+树的内部结点只存放键，不存放值，因此可以在内存页中获取更多的键，这有利于更快的缩小查询范围

• B+树的叶子结点是由一条链来连接的，因此，当需要进行一次全部数据遍历的时候，B+树只需要耗费O(logN)的时间就可以找到最小的一个结点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间

3.3对比

在InnoDB中使用的索引是B+树，那么为什么B+树比B树更适合做数据库的索引呢

• B+树的磁盘读写代价更低

B+树中的内部结点没有存放数据，所以其内部结点与B树相比较也就越小，如果把所有同一内部节点的关键字都存放在同一盘块中，该盘块容纳的关键字数量就会越多，查询数据时读入的内存的关键字机会越多，读写IO的次数就会降低

• B+树的查询效率更稳定

B+树的非叶子结点并不是指向文件内容的结点，仅仅是叶子结点中的关键字索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

• B+树实现了范围查询

B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

4、索引的分类

在B+树中，根据叶子结点的内容，可以将索引类型分为主键索引和非主键索引

• 主键索引

主键索引的叶子结点存放的是所查字段的整行数据，在InnoDB里，主键索引也被称为聚簇索引，它的索引和数据是存入同一个.idb文件中的，因此它的索引结构是在同一个树节点中同时存放索引和数据

• 非主键索引(普通索引)

非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引。

我们了解了主键索引和普通索引之后，那么它们之间有什么区别呢？

• 如果语句是 select * from T where ID=XXX，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；

• 如果语句是 select * from T where k=XXX，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 值，再到 ID 索引树搜索一次。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

那么有没有可能存在这样一种情况，仅仅使用普通索引而不需要回表就可以拿到所需的数据呢？答案是可以的，覆盖索引就可以满足这样的要求。

• 覆盖索引

覆盖索引就是select的数据列只用从索引中就能够取得，不必从数据表中读取，换句话说查询列要被所使用的索引覆盖。即普通索引中除了包含指向的ID之外，也可以存放数据。

因为覆盖索引可以减少树的搜索次数，显著提升查询性能，所有覆盖索引是一个常用的性能优化手段。

• 联合索引

联合索引又可称为复合索引，对于这种类型的索引，MySQL从左到右的使用索引中的字段，一次查询只能使用索引中的一部分，并且是做左侧部分，满足最左前缀原则。

最左前缀原则可以这样理解，例如索引key index(a,b,c)，它就支持索引（a），（a,b），（a,b,c）3种类型的组合进行查找，不支持索引b、c查找。

利用符合索引中的附加列，可以缩小搜索的范围，但使用一个具有两列的索引 不同于使用两个单独的索引。复合索引的结构与电话簿类似，人名由姓和名构成，电话簿首先按姓氏对进行排序，然后按名字对有相同姓氏的人进行排序。如果您知道姓，电话簿将非常有用；如果您知道姓和名，电话簿则更为有用，但如果您只知道名不姓，电话簿将没有用处。

• 唯一索引

唯一索引是索引列中的元素是不可重复的，只能出现一次，它与普通索引有如下的区别

查询操作

普通索引：查找到满足条件的第一个记录后，需要查找下一个记录，直到碰到第一个不满足条件的记录

唯一索引：由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索

因此，普通索引相对于唯一索引要多一些操作。但是，他们之间对于性能的差距却是微乎其微

更新操作

普通索引：当需要更新一个数据页时，如果数据页在内存中就直接更新，而如果这个数据页还没有在内存中的话，在不影响数据一致性的前提下，InnoDB会将这些更新操作缓存在change buffer中，这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行change buffer中与这个页有关的操作。通过这种方式就能保证这个数据逻辑的正确性。

唯一索引：所有的更新操作都要先判断这个操作是否违反唯一性约束，而这必须要将数据页读入内存才能判断。如果都已经读入到内存了，那直接更新内存会更快，就没必要使用change buffer了。

总结

在查询操作中，因为俩者区别不大，选择任何一种都是可以的。在更新操作中，唯一索引相较于普通索引更加消耗IO资源，所以选择普通索引。综合分析来看，选择普通索引。

5、索引下推

简单来说，索引下推是数据库检索数据过程中为减少回表次数而做的优化。

案例

有一个联合索引(name,age)，现在的需求是检索出表中的名字的第一个字是郎，而且年龄是23岁的男生，SQL可以这样写

mysql> select * from tuser where name like '郎%' and age=10 and ismale=1;


MySQL5.6之前，

无索引下推



在最左前缀前提下，只能利用最左边的索引“郎”，找到第一个满足条件的ID，然后进行回表，到主键索引上找出数据行，再对比字段值。

有索引下推



有索引下推可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。即InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在我们的这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。

参考文章

[1]林晓斌.《MySQL实战45讲》

[2]https://www.jianshu.com/p/0371c9569736



关注公众号：10分钟编程

公众回复success领取学习