0%

MySQL - 索引简介

本文中描述的相关知识点,都是基于InnoDB引擎下,阅读本文之前,建议先了解B+树相关知识。

索引是个啥

如果你要去图书馆找本书,有两种方式:

  • 一本一本的找;
  • 通过书所属类别确定藏书片区,根据书名首字母确定书架,然后一本一本的找。

第二种方式中,把所有书的所属类别,书名首字母这两个属性提取出来供大家做第一轮第二轮查找,从而确定一个小范围,再进行遍历查找。此时提取出来的书的类别,书名首字母,即使索引。

将上述理论映射到数据库中,假设某个表有百万条记录,存储用户信息,如果此时需要查找生日在1月1日的用户,假设没有数据库索引,你需要遍历所有记录,然后取出所有满足查询条件的用户。建立了数据库索引的话,数据库会通过索引查询的方式,非常快速的查找到满足条件的数据。

实现方式

假设有如下表:

1
2
3
4
5
6
7
8
CREATE TABLE `user` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(10) NOT NULL DEFAULT '',
`contry` varchar(20) NOT NULL DEFAULT '',
`age` int(11) NOT NULL,
`gender` tinyint(4) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

新建如下记录:

1
2
3
4
5
6
7
8
9
10
11
12
INSERT INTO `user` (`id`, `name`, `contry`, `age`, `gender`)
VALUES
(1, 'Allen', 'US', 17, 0),
(2, 'Jack', 'AU', 42, 1),
(3, 'Alice', 'UK', 37, 0),
(4, 'Jim', 'US', 44, 1),
(5, 'Eric', 'DE', 28, 0),
(6, 'Tom', 'UK', 25, 1),
(7, 'Allen', 'FR', 33, 0),
(8, 'Baker', 'UK', 45, 1),
(9, 'Barry', 'FR', 32, 0),
(10, 'Allen', 'US', 27, 0);

聚集索引(主键索引,Primary key)

InnoDB使用B+树来作为索引结构,针对主键索引(又称之为聚集索引),B+树不光存储索引,同时也在叶子节点保存了完整的数据记录,这棵B+树的关键字即是主键,上述例子中,主键id构造的索引如下:

1

如上图所示,当需要查询id为5的记录时,通过B+树的查找逻辑,找到叶子节点,从而获取整行数据。

聚集索引构成一棵B+树,而完整的数据记录也会被保存在聚集索引的B+树的叶子节点中,所以InnoDB要求表必须要有主键。

非聚集索引(辅助索引,Secondary key)

假设我们建立了age列上的索引:

1
alter table `user` add index idx_age(`age`);

则索引构造的B+树如下:

1

注意叶子节点部分,并没有存储完整的数据记录,而是保存了主键的key。因此如果是用辅助索引,需要检索两遍:先用辅助索引查询,得到主键,然后用主键在聚集索引中查询获得数据记录。

非聚集索引之联合索引

假设我们建立了3个字段的联合索引:

1
alter table `user` add index idx_age_contry_name(`age`, `contry`, `name`);

联合索引会将N个字段组合成一个元素,形成一棵B+树,大致如下:

1

查询过程中,会先根据第一列的条件进行查询,查询到满足的值之后,再根据第二列的查询条件继续定位,依次类推。

联合索引的一些特性如下:

  • 最左匹配

    联合索引的一个特性是最左匹配,也就是当一个查询中,有多个查询条件时候(sql编写顺序无所谓),查询条件需要精确匹配联合索引的左边连续几个列,此时联合索引便可以被用到(用到联合索引的部分列),例如:

    • age=15 and contry='US' and name='Eric':是一个全匹配
    • age=15 and contry='US':是一个最左匹配,也能用上联合索引,但是只能用上联合索引的agecontry两列
    • age=15:也是一个最左匹配,也能用上联合索引,但是只能用上联合索引的age
    • contry='US' and name='Eric':并没有从联合索引的最左列开始匹配,因此无法用上索引
    • age=15 and name='Eric':只能用上age部分的索引,因为缺少了中间字段

    为啥会有最左匹配的特性呢?我们知道B+树的构造过程中,需要对比插入元素和树中节点的比较结果,来确定元素的插入位置。联合索引生成的B+树中,会优先以第一列的比较结果来定位,第一列值相等的时候,会继续使用第二列的比较结果,依次类推,因此一定要第一列的精确查询条件,才能定位到某些子树,然后才能在子树基础上,继续使用第二列的查询条件,一次类推下去,从而形成一个最左匹配的规则。

  • 范围查询

    当联合索引遇到范围查询条件之后,后面的列便无法使用索引,例如:

    • age>15 and contry='US' and name='Eric':能使用age列的索引,但是无法使用完整的联合索引

    在B+树数据结构中进行范围查询,可以先查询到最小/最大值,然后通过叶子节点上的链表指针,按照顺序遍历叶子节点,即可得到范围查询结果,因此当联合索引中的某一列使用了范围查询之后,可以认为是B+树已经深入到最底层的叶子节点做范围查询了,无法再在非叶子节点中根据后续列的查询条件进行检索。

    范围查询的原理是根据数据结构做的猜想,未能有相关资料作证。

知识点

  • 不是所有的非聚集索引都会产生两次检索

    上面提到通过非聚集索引,会检索两遍数据,不过也有例外。当select中,要查询的列本身就在索引的B+树里面,则不需要二次查询,这种叫做覆盖索引。例如在age contry name三列联合索引中,进行如下查询:

    1
    select age, name from `user` where age = 10;

    通过索引的B+树查询到的节点中,已经包含了索引关联的列的值,即使直接包含可以直接得到结果,因此无需再通过聚集索引查询整条记录。

  • 范围查询不一定会使用索引

    假设在age字段的索引中,进行如下查询:

    1
    select * from `user` where age > 1;

    explain分析:

    1

    可以看到key一列为null,即是实际上并未使用索引,修改查询条件为:

    1
    select * from `user` where age > 50;

    explain分析:

    1

    key一列显示,此次查询能正常使用age索引。

    MySQL会根据非聚集索引查询出来的数量级,与全表数据量进行对比,如果二者较为接近的话,MySQL则认为直接扫描全表,比用非聚集索引查询之后,再用查询出来的主键进行二次查询更好。

  • explain

    怎么定义一个sql查询语句是否用上索引,以及是否有良好的性能呢?可以借助explain命令,对sql进行分析。

    这里不对explain做深入说明,建议系统化的检索explain相关文章。

优化

  • 主键的选择

    从数据库索引优化的角度来看,强烈建议使用一个业务无关的自增ID作为InnoDB引擎的主键。

    • 建议使用单调的字段作为主键

      因为InnoDB使用B+树作为索引数据结构,当插入一条新记录的时候,为了维持B+树的规则,可能会产生节点分裂的操作,如果采用非单调的主键,则每次插入的主键的位置是随机的,所以可能会频繁的分裂节点;而单调递增的字段,始终都会与最右侧的节点进行操作,会大大减少分裂的次数。

    • 建议使用一个业务无关的自增ID作为主键

      背景知识:

      页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

      数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个节点只需一次I/O就可以完全载入。

      如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

      1

      这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

      如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

      1

      此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

  • 不要建立太多的索引

    每次添加,更新,删除一条记录时候,都要更新索引的B+树,如果使用太多的索引的话,会减慢插入,更新,删除操作,因为每个索引都需要$O(log(n))$运算来更新表的索引。

  • 只在区分度高的列上考虑是否需要建立索引,区分度低的列上没有必要建立索引,比如性别,只有男和女,就没有必要建立索引,如果建立索引不但不会提高查询效率,反而会严重降低更新速度。关于区分度这里有个公式判断:

    $selectivity=distinct(COLUMN) \div count(*)$,唯一键的区分度为1,而性别之类的字段,区分度可能就趋近于零了。

最后

  • 为什么用B+树不用红黑树

    详细原理建议阅读文末参考MySQL索引背后的数据结构及算法原理一文中的为什么使用B-Tree(B+Tree)部分。

    数据库的索引数据一般也很大,不可能全部存储在内存中,因此索引往往都是以索引文件的形式存储在磁盘中,所以磁盘的I/O效率就显得尤为重要。

    B+树检索一次数据最多需要$h-1$次I/O,$h$为高度(根节点是常驻内存的),一棵B+树的高度复杂度为$O(h)=l(log_dN)$,$d$为出度(我理解的也就是B+树的阶),通常情况下都超过100,因此$h$一般都非常小。如果采用红黑树,$h$明显就要大很多了,而每次访问节点需要一次磁盘I/O,因此采用红黑树会产生大量的磁盘I/O。

参考



-=全文完=-