深入浅出索引

Feb 7, 2019

 MySQL  MySQL  索引  数据库

深入浅出索引

本文是在看极客时间《Mysql实战45讲》时记的笔记，整理下加深理解。

简单来说，数据库索引就是为了提高数据库查询的效率，就像书的目录一样，可以根据目录快速的找到其中的某一个知识点。

索引模型

  • 哈希表
  • 有序数组
  • 搜索树

简单的介绍下以上三种模型：

哈希表是一种以键-值(key-value)存储的数据结构，我们只要输入待查找的key值，就可以找到其对应的值value，哈希的思路很简单，把值放在数组里，通过一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。不可避免的情况下，多个Key值经过哈希运算会出现同一个值的情况，处理这种情况的一种方法是拉出一个链表。

由于哈希表内部的排序并不是递增的，所以新增元素的时候速度会很快，但缺点是因为不是有序的，所以哈希表做区间查询的速度是很慢的。所以，哈希表这种结构只适用于只有等值查询的场景，比如Memcached以及其他Nosql引擎。

有序数组在等值查询和范围查询场景中的性能都非常优秀。但是在需要更新数据的时候就很麻烦了，如果在中间插入一个记录就必须挪动后面所有的记录，成本太高。所以有序数组只适用于静态存储引擎。

N叉树在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用于数据库引擎中了。

不管是哈希还是有序数组，或者 N 叉树，它们都是不断迭代、不断优化的产物或者解决方案。在我们心里要有个概念，数据库底层存储的核心就是基于这些数据模型的，每碰到一个新的数据库，我们都应先关注他的数据模型，这样才能从理论上分析出这个数据库的应用场景。

InnoDB的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。

每一个索引在InnoDB里面都对应一颗B+树。

假设我们有一个主键列为ID的表，表中有字段K，并在K上有索引。

这个表的建表语句：

mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6),两棵树的示意图如下：

从图中我们可以看出来，根据叶子节点的内容，索引分为主键索引和非主键索引。

主键索引的叶子节点存放的是整行的数据，非主键索引的叶子节点存放的是主键的值。

根据上面的索引结构说明，我们可以得出一个问题，基于主键索引和普通索引的查询区别：

  • 如果语句是select * from T where ID = 500;,即主键查询方式，则只需要搜索ID这颗B+树；
  • 如果语句是select * from T where k = 5;,即普通索引查询方式，则需要先搜索k索引树，得到ID的值为500,再到ID索引树搜索一次，这个过程称为回表。

也就是说基于非主键索引查询会多扫描一次索引树。

索引维护

B+树为了维护索引的有序性，在插入新值的时候需要做必要的维护。

建表时，尽量保持有自增主键。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。

而有业务逻辑的字段做主键，则往往不容易保证有序插入。

同时主键的长度越小，普通索引的叶子节点就越小，普通索引占用的空间就越小。

所以从性能和存储空间来看，自增主键往往是更合理的选择。

覆盖索引

如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的值，而ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是常用的性能优化手段。

最左前缀原则

第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

其次考虑的就是空间，比如name 字段是比 age 字段大的 ，那我就建议你创建一个(name,age) 的联合索引和一个 (age) 的单字段索引。

索引下推

在Mysql5.6之前，只能从最左前缀查询到ID开始一个个回表，到主键索引上找出数据行，再对比字段值。

Mysql5.6之后，引入索引下推的优化，可以在遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

总之在满足语句需求的情况下，尽量地减少访问资源是数据库设计的重要原则之一。我们在使用数据库的时候，尤其在设计表结构时，也要以减少资源消耗为目标。

参考资料

极客时间《Mysql实战45讲》

 Tags
 Related