深入浅出数据库索引

一、索引的常见模型

1. 哈希表

是键值对(key-value)存储结构,只要根据 key 就可以找到 value。

可以理解为一个数组,对 key 进行哈希计算,换算成一个确定的位置,把 value 放入此位置。

因为存储hash冲突的情况,多个value可能在同一个位置上,使用链表,后来的就追加到链表中。

例如存储身份证号和名字的信息:

这种结构只适用于 等值查询 场景,如果要找某个区间的用户就需要全部扫描一遍了。

2. 有序数组

按照身份证号递增的顺序保存。

有序数组非常适合 等值查询和范围查询

例如查找 [ID_X, ID_Y] 内的,先用二分法找到 ID_X,然后向右遍历,直到找到大于 ID_Y 的就结束了。

有序数组的优势是查询效率高,缺点是更新麻烦,插入一个记录就需要挪动后面所有的记录,效率低。

有序数组索引只适用于 静态存储引擎 ,不会修改的数据情况。

3. 搜索树

先看最经典的二叉树:

二叉树中,左儿子 < 父节点,父节点 < 右儿子。

例如查找 ID_2,路径就是:

UserA -> UserC -> UserF -> User2

二叉树搜索效率最高,但实际数据库却不适用二叉树,因为索引是需要写到磁盘上的,例如一棵100万节点的二叉树,高度是20,一次查询需要访问20个数据块,从磁盘随机读一个数据块需要10ms左右的寻址时间,那么这个查询就需要200ms,很慢了。

所以需要使用N叉树,每个节点可以有多个儿子,儿子间从左到右递增,这样可以让查询过程访问尽量少的数据块儿。

二、InnoDB 索引

1. 为什么使用 B+ tree 索引模型?

例如插入数据:1,a,b,c,d,e。

二叉树的结构:

红黑树的结构:

B+ tree 的结构:

二叉树上面说过,效率太低,高度完全不可控,红黑树优化了不少,但高度仍然不可控,B+ tree 的高度恒定,而且只在叶子节点中存储数据,叶子节点间也是顺序链接的,做范围查找时非常高效。

2. 为什么建议使用自增主键?

涉及到1个概念:页分裂。

插入时,如果新值比现有值都大,那么只需要在后面插入即可,否则需要挪动现有数据。

如果插入目标位置的数据页满了,就要申请新的数据页,并挪动数据。

所以自增ID能够连续申请页空间,提升空间的操作效率和利用率。

三、MySQL 索引的3个重要概念

例如有一个表:

有2个索引,ID 和 k。

InnoDB 主键索引的叶子节点存储的是行数据,非主键索引的叶子节点存储的是主键。

查询 k 在 [3,5] 区间内的所有行数据:

select * from T where k betweet 3 and 5

在 k 索引树上找到符合条件的,得到 ID 值,回到 ID 索引树取得行数据。

回到主键索引搜索的过程称为 回表

1. 覆盖索引

上面的查询如果改为:

select ID from T where k betweet 3 and 5

只查询ID这个字段,那么只搜索 k 树索引即可,不需要回表了。

索引 k 已经覆盖了我们的查询需求,这种情况称为 覆盖索引

覆盖索引可以显著提升查询性能,所以做优化时可以考虑是否适合使用此方式。

例如用户表,有身份证号、姓名字段,身份证号是唯一的,建了一个索引。

如果业务中有根据身份证号搜索姓名的高频需求,就可以创建一个( 身份证号+姓名 )的联合索引,实现覆盖索引,即使增加了索引的维护成本也是值得的。

2. 最左前缀原则

索引项是按照字段顺序排序的。

查询“张三”时,会快速定位到 ID_4,然后向后遍历需要的结果。

查询“张%”也可以用这个索引,定位到 ID_3,向后找,直到不满足条件为止。

所以,只要满足最左前缀就可以用到索引。

涉及到一个问题:如何安排索引内的字段顺序?

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

3. 索引下推

例如用户表有字段:ID,name,age,ismale …,建有一个索引(name,age)。

现在查询:

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

MySQL5.6 之前,查询过程是:

根据索引找到以“张”开头的名字的ID,然后回表,进一步判断 age 和 ismale。

在 5.6 引入了 索引下推 ,在索引中找到“张”开头的以后,先在索引中判断其 age 是否符合条件,因为 age 已经在索引中,不需要回表判断了,把 age 不符合要求的先过滤掉,然后再回表判断 ismale,这就减少了回表次数,提升了查询效率。

内容整理自丁奇的《MySQL实战45讲》

点击:point_down: 阅读原文 查看 文章列表

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章