面试时,只要问到数据库,都会被问到索引相关的知识,所以什么是索引呢?

简单地说,索引就像书的目录一样,为了提高查询效率的一种工具。

索引模型

索引也分为好几类,这里作一下小总结

哈希表是一种以键值对(key-value)形式存储数据的结构。我们只要给出待查找的key,它就能很快地找到对应的value。最常见的是Java里面的HashMap,用一个数组存储元素,当出现冲突的时候使用拉链法处理,甚至还能转换为树以减少查询的时间复杂度。

很明显,它适于等值查询的场景,但是解决范围查询就不大行。

从常见的数据结构中也可知,有序数组在等值查询和范围查询中性能非常优秀。但是,有序数组索引只适用于静态存储引擎,如果需要变化的话,就要挪动后面所有的记录,代码太高。

此时,可以考虑一下使用二叉搜索树,它的特点是每个节点的左子树结点小于父结点,而父结点又大于右子树的结点。这个数据结构又优化了数组增删元素的缺点,但是它又有更多需要考虑的情况。比如,如果它是平衡的话,它的查询复杂度可以稳定在$O(log_N)$,但是维持它平衡,更新时需要的时间复杂度也是$O(log_N)$(是怕它退化成链表)。

而且,相比于多叉树而言,二叉树的树高太高了。因为索引是存放在磁盘中,想象在机械硬盘时代,从磁盘随机读取一个数据块需要10ms的寻址时间,如果树高为20,那查一个数组需要20*10=200ms,这多慢啊!

以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。树高为4时,就能存1200^3,约为17亿,且不说存储在内存中的数据,就算全部都要从磁盘中取,也只是需要访问3次,查询时间快了不少。

上面是简简单单地说了一些模型,其实更多的是与数据结构的特别有关,记录一下。

InnoDB的索引模型

在InnoDB中,使用B+树索引模型,所有的数据都是存储在B+树中的。

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

假如有这么个语句,主键id,索引k,还有普通字段name

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

dcda101051f28502bd5c4402b292e38d.png

可以看出,根据叶子节点的内容,索引类型分为主键索引和非主键索引。

主键索引,也叫聚簇索引clustered index,它的叶子节点存放的是整行数据。

非主键索引,也叫二级索引secondary index,它的的叶子节点内容是主键的值。

它们的查询有什么区别呢?

  • 如果是select * from T where id = 100 ,那就从主键开始查,搜索ID这颗B+树(左边那颗)。
  • 如果是select * from T where k = 1,即普通索引查询方式,先查k索引树(右边那颗),拿到ID=100,再到ID索引树(左边那颗)搜索一次。这也称为回表

维护

看上图的B+树,如果我再插入一个ID=700的值,它只要在R5后面插入一个新记录就行。但是如果插入的ID=400,这就需要挪动后面的数据,空出位置。并且,如果R5所在的数据页已经满了,它就要申请一个新的数据页,然后再挪动部分数据过去。这个过程叫做页分裂,会影响性能,还会影响数据页的利用率。反过来,如果是删除数据,那也会有页合并,可以理解为页分裂的逆过程。这就是它的基本维护过程。

案例

你可能在一些建表规范里面见到过类似的描述,要求建表语句里一定要有自增主键。当然事无绝对,我们来分析一下哪些场景下应该使用自增主键,而哪些场景下不应该。

定义表时,尝尝会自定义一个主键,然后让它自增。此后插入新记录时,可以不用指定ID值,系统会自动获取当前ID最大值+1作为下一个记录的ID。并且,索引顺序是根据主键ID来定的,这样新增记录是直接往后追加,不会导致页分裂等。而使用有业务逻辑的字段做主键,往往不容易保证有序插入,写数据成本较高。

再想想普通索引,它的叶子节点是主键,很显然,主键长度越小,普通索引的叶子节点越小,普通索引占用的空间也越少。因此,从性能和存储空间方面考量,自增索引往往是更合理的选择。

什么业务适合直接用业务字段作主键 ?一般都有这样的需求 :

  1. 只有一个索引;
  2. 该索引必须是唯一索引。

没有其它的索引,也不用考虑其它索引的叶子节点大小的问题。

索引的一些原则

基本查询

按照上面的图片,如果我要执行:select * from T where k between 3 and 5,执行流程是怎样的呢?

  1. 在索引树上找到k=3的记录,取得ID=300.
  2. 到ID索引树上查ID=300,得R3(回到主键索引树的进行搜索的过程叫做回表
  3. 在 k 索引树取下一个值 k=5,取得 ID=500;
  4. 再回到 ID 索引树查到 ID=500 对应的 R4;
  5. 在 k 索引树取下一个值 k=6,不满足条件,循环结束。

因为,需要的数据只有在主键索引上有,所以无奈只能回表。

覆盖索引

要是select ID from T where k between 3 and 5,在k索引树上就有ID,这就能直接查出结果不需要回表,也就是说,索引k已经“覆盖了”查询需求,所以可以称之为覆盖索引

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

比如,有一个个人信息表,有身份证号和姓名等信息。有这么个需求:根据身份证号查询个人信息的。一般来讲,是不是只要在身份证号字段上建立索引就行了。如果再建一个(身份证号、姓名)的联合索引,是不是浪费空间了?

其实这得根据需求来,如果有一个高频需要,根据市民身份证号查姓名,这个联合索引就很有意义了,直接使用到覆盖索引,不用回表,减少了语句执行时间。

当然,索引字段的维护也是有代价的。这种冗余索引支持覆盖索引时就需要权衡了。

最左前缀原则

看看上面的例子,如果我还有一个根据身份证号查地址,是不是又得加设计一个新的索引,索引会不会太多了。虽然它的频率可能不高,但是总不能不管它,让它全表扫描吧?

B+树索引结构可以使用索引的“最左前缀”进行定位

下面给出一张图,联合索引是(name, age)。

89f74c631110cfbc83298ef27dcd6370.jpg

当你需要查找名字是“张三”的人时,可以快速定位到ID4,然后往后遍历得到所有需要的结点。

当你需要查找名字第一个字是“张”的人时,你的查询语句变成where name like '张%',这时也能用上索引,定位到ID3,然后往后遍历,直到不满足条件为止。

可以看到,只要满足最左前缀,就可以利用索引加速。最左前缀可以是联合索引的最左N个字段,也可以是字符串索引的最左M个字符

所以建立索引时,需要评估索引复用能力,如果通过调整顺序可以少维护一个索引,那么这个顺序往往就是需要优先考虑的。

另外,如果既有(a, b)联合查询,又有基于a、b各自的查询,如果只查b,是无法使用这个联合索引的,此时又不得不维护另一个索引,这时我们就要考虑空间。按(a, b)这个例子,a应该是大字段,b是小字段。因为要创建一个b的索引,它字段小的话占用空间更小。

索引下推

以市民表的联合索引(name, age)为例。

如果现在有一个需求:检索出表中“名字第一个字是张,而且年龄是 10 岁的所有男孩”。

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

根据前缀索引规则,它能直接定位到ID3,找到记录("张六", 30)。不错,比全表扫描好。

然后呢?

在MySQL5.6前,它只能从ID3开始,往后一个个回表,在主键索引上找到数据行,再对比字段值。

在MySQL5.6引入了索引下推优化(index condition pushdown),可以在索引遍历的过程中,对索引中包含的字段先做判断,直接过滤不满足条件的记录,减少回表次数。

按照上面的例子,即("张六", 30)不合要求,直接过滤,不用回表判断age而是直接在索引信息中判断,然后找下一个,依此类推。

因此,根据上图的数据,索引下推后仅需回表两次,而没有这项优化的话需要回表4次。