MySQL索引

索引的常见模型

实现索引的方式有很多种。可用于提高读写效率的数据结构很多。这里有三种常见也比较简单的数据结构,哈希表、有序数组和搜索树。

哈希表是一种以键 - 值(key-value)存储数据的结构。哈希的思路很简单,把值放在数组中,用一个哈希函数把 key 换算成一个确定的位置,然后把数据存放在对应位置。

当多个 key 值经过哈希函数计算,出现同一个值时。处理这种情况的方法就是拉出一个 链表

图中,User2 和 User4 根据身份证号算出来的值都是 N,但没关系,后面还跟了一个链表。假设,这时候你要查 ID_card_n2 对应的名字是什么,处理步骤就是:首先,将 ID_card_n2 通过哈希函数算出 N;然后,按顺序遍历,找到 User2。

需要注意的是,图中四个 ID_card_n 的值并不是递增的,这样做的好处是增加新的 User 时速度会很快,只需要往后追加。但缺点是,因为不是有序的,所以哈希索引做区间查询的速度是很慢的。

你可以设想下,如果你现在要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户,就必须全部扫描一遍了。

所以,哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎。

有序数组在等值查询和范围查询场景中的性能就都非常优秀

在有序数组中,查询数据时用二分法就可以快速得到,查询的时间复杂度是 O(log(N))。

但是在插入数据的时候,必须挪动后边所有的记录,成本很高,所以,有序数组索引只适用于静态存储引擎。比如是一些不会再修改的数据。

二叉搜索树也是课本里经典的数据结构了。

二叉搜索树示意图

二叉搜索树的特点是,左儿子节点小于父节点,父节点又小于右儿子。查询的时间复杂度是O(log(N))。

为了维持 O(log(N)) 的查询复杂度,你就需要保持这棵树是平衡二叉树。为了做这个保证,更新的时间复杂度也是 O(log(N))。

在实际应用中,大多数的数据库存储并不使用二叉树,因为索引不只存在内存中,还要写在磁盘里。如果是一棵 100 万节点的平衡二叉树,树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说,对于一个 100 万行的表,如果使用二叉树来存储,单独访问一个行可能需要 20 个 10 ms 的时间,这个查询可真够慢的。

为了减少查询时读磁盘的次数,就必须让查询过程访问尽量少的数据块。所以不应该使用二叉树,而是使用“N叉”树。

InnoDB 的一个整数字段索引中的这个“N”差不多是1200。当树高是4的时候,就可以存储 1200 的三次方的值,已经高达17亿了。

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

索引是在引擎层实现,不同的存储引擎的索引工作方式也不一样。

InnoDB 索引模型

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

每一个索引在InnoDB 中都对应一棵 B+ 树。

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

假设一张表有主键索引和一般索引,那么在Innodb 中,就有两棵索引树。

主键索引的叶子节点存储的是整行数据,在 InnoDB 中,主键索引也被称之为 聚簇索引(clustered index)。

非主键索引的叶子节点的内容是主键的值。在InnoDB 中,非主键索引也被称为二级索引(secondary inde)。

基于主键索引和普通索引的查询有什么区别?

如果使用主键查询方式,则只需要搜索 ID 这棵树;
如果使用的是索引查询方式,则需要先搜索 k 索引树,得到 k 值对应的 ID 的值,再回到 ID 这棵树搜索一次,这个过程称之为回表

索引维护

为了维护索引的有序性,在插入新值的时候就需要做必要的维护。如上图所示,如果插入了一个 ID 为400 的值,则必须把 R4 之后的数组挪动,空出位置。

而在挪动的时候,如果 R5 所在的数据页已经满了,根据 B+ 树的算法,就需要申请一个新的数据页,然后挪动部分数据过去,这个过程称为页分裂。在这种情况下,除了性能会受到影响,数据的页利用率也会降低。

所以在一些建表规范中,要求建表一定要有自增主键。自增主键的数据模式,正好符合了递增插入的场景。每次插入一条新纪录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂。

而有业务逻辑的字段做主键,则往往不容易保证有序插入,这样写数据成本相对较高。

除了考虑性能外,我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段,比如字符串类型的身份证号,那应该用身份证号做主键,还是用自增字段做主键呢?

由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键,那么每个二级索引的叶子节点占用约 20 个字节,而如果用整型做主键,则只要 4 个字节,如果是长整型(bigint)则是 8 个字节。

显然,主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。

如果表中只有一个索引,而且该索引一定是唯一索引,就要优先考虑 “尽量使用主键查询” 原则,直接将这个索引设置成主键,可以避免每次查询都需要搜索到两棵树。

小结

InnoDB 采用 B+ 树的结构,这种结构能够很好地配合磁盘的读写特性,减少单次查询的磁盘访问次数。

由于InnoDB 是索引组织表,一般情况下都建议创建一个自增主键,这样非主键索引占用的空间最小。

回表

如果一个表中有一个主键索引,有一个普通索引,当使用普通索引查询数据时,会先到普通索引树上查找数据,然后根据查找到的主键的值,回到主键索引树上搜索,这个回到主键索引树搜索的过程,我们称之为回表

覆盖索引

如果在查询的过程中只查询主键,或者说只查询索引树上已有的内容,就可以减少回表,显著提升查询性能。也就是说,在查询里,索引已经“覆盖”了我们的查询需求,我们称之为覆盖索引。

如果一个表有高频请求,同时查询两个字段,那么这个联合索引就有意义了。

最左前缀原则

B+ 树的这种索引结构,是可以利用索引的 “最左前缀”,来定位记录的。

最左前缀原则可以是联合索引的最左 N 个字段,也可以是字符串索引的最左 M 个字符。

如果调整顺序,可以少维护一个索引,那么应该优先考虑这种顺序。

索引下推

我们还是以市民表的联合索引(name, age)为例。如果现在有一个需求:检索出表中“名字第一个字是张,而且年龄是 10 岁的所有男孩”。那么,SQL 语句是这么写的:

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

在MySQL 5.6 之前,这个语句在搜索索引树时,只能使用“张”,找到第一个满足记录的id,然后回表,再比较其他字段。

在 MySQL 5.6 之后引入了索引的下推优化(index coondition pushdown),可以再索引遍历的过程中,对索引中包含的字段做判断,直接过滤掉不满足条件的记录,减少回表次数。

小结

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 索引 数据库中的查询操作非常普遍,索引就是提升查找速度的一种手段 索引的类型 从数据结构角度分 1.B+索引:传统...
    一凡呀阅读 3,031评论 0 8
  • 转载:http://blog.codinglabs.org/articles/theory-of-mysql-in...
    qf1007阅读 1,314评论 0 0
  • 索引的本质 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,...
    mysia阅读 591评论 0 1
  • 零.索引简介 1. 索引是什么 ①MySQL官方对索引的定义是:索引(Index)是帮助MySQL高效获取数据的数...
    一条路上的咸鱼阅读 948评论 0 6
  • 你觉得你是一个脚踏实地的人还是肆意追求梦想的人? 我是一个爱幻想的双鱼 虽然我内心戏很多,虽然我幻想的美好生活很多...
    二二俊阅读 1,244评论 7 13