MySQL索引

MySQL索引

Scroll Down

索引其实就是一种优化查询的数据结构,比如Mysql中的索引是用B+树实现的,而B+树就是一种数据结构,可以优化查询速度,可以利用索引快速查找数据,所以能优化查询。常用数据结构:哈希表、完全平衡二叉树、B树、B+树等等

为什么哈希表、完全平衡二叉树、B树、B+树都可以优化查询,为何Mysql独独喜欢B+树?

哈希表有什么特点?

假如有这么一张表(表名:sanguo):

MySQL索引2.jpg

现在对name字段建立哈希索引:
MySQL索引3.jpg

注意字段值所对应的数组下标是哈希算法随机算出来的,所以可能出现哈希冲突。那么对于这样一个索引结构,现在来执行下面的sql语句:

select * from sanguo where name='周瑜'

可以直接对‘周瑜’按哈希算法算出来一个数组下标,然后可以直接从数据中取出数据并拿到所对应那一行数据的地址,进而查询那一行数据。 那么如果现在执行下面的sql语句:

select * from sanguo where name>'周瑜'

则无能为力,因为哈希表的特点就是可以快速的精确查询,但是不支持范围查询。

如果用完全平衡二叉树呢?

还是上面的表数据用完全平衡二叉树表示如下图(为了简单,数据对应的地址就不画在图中了。):
MySQL索引4.jpg

图中的每一个节点实际上应该有四部分:

  1. 左指针,指向左子树

  2. 键值

  3. 键值所对应的数据的存储地址

  4. 右指针,指向右子树

另外需要提醒的是,二叉树是有顺序的,简单的说就是“左边的小于右边的”假如我们现在来查找‘周瑜’,需要找2次(第一次曹操,第二次周瑜),比哈希表要多一次。而且由于完全平衡二叉树是有序的,所以也是支持范围查找的。

如果用B树呢?

还是上面的表数据用B树表示如下图(为了简单,数据对应的地址就不画在图中了。):

MySQL索引5.jpg

可以发现同样的元素,B树的表示要比完全平衡二叉树要“矮”,原因在于B树中的一个节点可以存储多个元素。

如果用B+树呢?

还是上面的表数据用B+树表示如下图(为了简单,数据对应的地址就不画在图中了。):

MySQL索引6.jpg

我们可以发现同样的元素,B+树的表示要比B树要“胖”,原因在于B+树中的非叶子节点会冗余一份在叶子节点中,并且叶子节点之间用指针相连。

那么B+树到底有什么优势呢?

这里我们用“反证法”,假如我们现在就用完全平衡二叉树作为索引的数据结构,我们来看一下有什么不妥的地方。实际上,索引也是很“大”的,因为索引也是存储元素的,我们的一个表的数据行数越多,那么对应的索引文件其实也是会很大的,实际上也是需要存储在磁盘中的,而不能全部都放在内存中,所以我们在考虑选用哪种数据结构时,我们可以换一个角度思考,哪个数据结构更适合从磁盘中读取数据,或者哪个数据结构能够提高磁盘的IO效率。 回头看一下完全平衡二叉树,当我们需要查询“张飞”时,需要以下步骤

  1. 从磁盘中取出“曹操”到内存,CPU从内存取出数据进行比较,“张飞”<“曹操”,取左子树(产生了一次磁盘IO)

  2. 从磁盘中取出“周瑜”到内存,CPU从内存取出数据进行比较,“张飞”>“周瑜”,取右子树(产生了一次磁盘IO)

  3. 从磁盘中取出“孙权”到内存,CPU从内存取出数据进行比较,“张飞”>“孙权”,取右子树(产生了一次磁盘IO)

  4. 从磁盘中取出“黄忠”到内存,CPU从内存取出数据进行比较,“张飞”=“张飞”,找到结果(产生了一次磁盘IO)

同理,回头看一下B树,我们发现只发送三次磁盘IO就可以找到“张飞”了,这就是B树的优点:一个节点可以存储多个元素,相对于完全平衡二叉树所以整棵树的高度就降低了,磁盘IO效率提高了。

而B+树是B树的升级版,只是把非叶子节点冗余一下,这么做的好处是为了提高范围查找的效率。

到这里可以总结出来,Mysql选用B+树这种数据结构作为索引,可以提高查询索引时的磁盘IO效率,并且可以提高范围查询的效率,并且B+树里的元素也是有序的。

那么,一个B+树的节点中到底存多少个元素合适呢?

其实也可以换个角度来思考B+树中一个节点到底多大合适?

答案是:B+树中一个节点为一页或页的倍数最为合适。 因为如果一个节点的大小小于1页,那么读取这个节点的时候其实也会读出1页,造成资源的浪费;如果一个节点的大小大于1页,比如1.2页,那么读取这个节点的时候会读出2页,也会造成资源的浪费;所以为了不造成浪费,所以最后把一个节点的大小控制在1页、2页、3页、4页等倍数页大小最为合适。

那么,Mysql中B+树的一个节点大小为多大呢?

这个问题的答案是“1页”,这里说的“页”是Mysql自定义的单位(其实和操作系统类似),Mysql的Innodb引擎中一页的默认大小是16k(如果操作系统中一页大小是4k,那么Mysql中1页=操作系统中4页),可以使用命令SHOW GLOBAL STATUS like 'Innodb_page_size'; 查看。

MySQL索引7.png

并且还可以告诉你的是,一个节点为1页就够了。

为什么一个节点为1页(16k)就够了?

解决这个问题,我们先来看一下Mysql中利用B+树的具体实现。

Mysql中MyISAM和innodb使用B+树

MySQL索引8.jpg

通常我们认为B+树的非叶子节点不存储数据,只有叶子节点才存储数据;而B树的非叶子和叶子节点都会存储数据,会导致非叶子节点存储的索引值会更少,树的高度相对会比B+树高,平均的I/O效率会比较低,所以使用B+树作为索引的数据结构,再加上B+树的叶子节点之间会有指针相连,也方便进行范围查找。上图的data区域两个存储引擎会有不同。

MyISAM中的B+树

MYISAM中叶子节点的数据区域存储的是数据记录的地址

主键索引

MySQL索引9.jpg

辅助索引

MySQL索引10.jpg

MyISAM存储引擎在使用索引查询数据时,会先根据索引查找到数据地址,再根据地址查询到具体的数据。并且主键索引和辅助索引没有太多区别。

InnoDB中的B+树

InnoDB中主键索引的叶子节点的数据区域存储的是数据记录,辅助索引存储的是主键值

主键索引

MySQL索引11.jpg

MySQL索引12.jpg

辅助索引

MySQL索引13.jpg

Innodb中的主键索引和实际数据时绑定在一起的,也就是说Innodb的一个表一定要有主键索引,如果一个表没有手动建立主键索引,Innodb会查看有没有唯一索引,如果有则选用唯一索引作为主键索引,如果连唯一索引也没有,则会默认建立一个隐藏的主键索引(用户不可见)。另外,Innodb的主键索引要比MyISAM的主键索引查询效率要高(少一次磁盘IO),并且比辅助索引也要高很多。所以,我们在使用Innodb作为存储引擎时,我们最好:

  1. 手动建立主键索引

  2. 尽量利用主键索引查询

回到我们的问题:为什么一个节点为1页(16k)就够了?

对着上面Mysql中Innodb中对B+树的实际应用(主要看主键索引),可以发现B+树中的一个节点存储的内容是:

  • 非叶子节点:主键+指针

  • 叶子节点:数据

那么,假设我们一行数据大小为1K,那么一页就能存16条数据,也就是一个叶子节点能存16条数据;再看非叶子节点,假设主键ID为bigint类型,那么长度为8B,指针大小在Innodb源码中为6B,一共就是14B,那么一页里就可以存储16K/14=1170个(主键+指针),那么一颗高度为2的B+树能存储的数据为:117016=18720条,一颗高度为3的B+树能存储的数据为:11701170*16=21902400(千万级条)。所以在InnoDB中B+树高度一般为1-3层,它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO,所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。所以也就回答了我们的问题,1页=16k这么设置是比较合适的,是适用大多数的企业的,当然这个值是可以修改的,所以也能根据业务的时间情况进行调整。

最左前缀原则

我们模拟数据建立一个联合索引

select*,concat(right(emp_no,1),"-",right(title,1),"-",right(from_date,2))from employees.titles limit10;

MySQL索引14.jpg

那么对应的B+树为

MySQL索引15.jpg

我们判断一个查询条件能不能用到索引,我们要分析这个查询条件能不能利用某个索引缩小查询范围

对于 select * from employees.titles where emp_no=1是能用到索引的,因为它能利用上面的索引所有查询范围,首先和第一个节点“4-r-01”比较,1<4,所以可以直接确定结果在左子树,同理,依次按顺序进行比较,逐步可以缩小查询范围。对于 select * from employees.titles where title='1'是不能用到索引的,因为它不能用到上面的索引,和第一节点进行比较时,没有empno这个字段的值,不能确定到底该去左子树还是右子树继续进行查询。对于 select *from employees.titles where title='1' and emp_no=1是能用到索引,按照我们的上面的分析,先用title='1'这个条件和第一个节点进行比较,是没有结果的,但是mysql会对这个sql进行优化,优化之后会将empno=1这个条件放到第一位,从而可以利用索引。


面试题

索引概念、索引模型

我们是怎么聊到索引的呢,是因为我提到我们的业务量比较大,每天大概有几百万的新数据生成,于是有了以下对话:

Q:你们每天这么大的数据量,都是保存在关系型数据库中吗?

A:是的,我们线上使用的是MySQL数据库

Q:每天几百万数据,一个月就是几千万了,那你们有没有对于查询做一些优化呢?

A:我们在数据库中创建了一些索引(我现在非常后悔我当时说了这句话)

这里可以看到,阿里的面试官并不会像有一些公司一样拿着题库一道一道的问,而是会根据面试者做过的事情以及面试过程中的一些内容进行展开。

Q:那你能说说什么是索引吗?

A:(这道题肯定难不住我啊)索引其实是一种数据结构,能够帮助我们快速的检索数据库中的数据

Q:那么索引具体采用的哪种数据结构呢?

A:(这道题我也背过)常见的MySQL主要有两种结构:Hash索引和B+ Tree索引,我们使用的是InnoDB引擎,默认的是B+树

这里我耍了一个小心机,特意说了一下索引和存储引擎有关。希望面试官可以问我一些关于存储引擎的问题。然而面试官并没有被我带跑...

Q:既然你提到InnoDB使用的B+ 树的索引模型,那么你知道为什么采用B+ 树吗?这和Hash索引比较起来有什么优缺点吗?

A:(突然觉得这道题有点难,但是我还是凭借着自己的知识储备简单的回答上一些)因为Hash索引底层是哈希表,哈希表是一种以key-value存储数据的结构,所以多个数据在存储关系上是完全没有任何顺序关系的,所以,对于区间查询是无法直接通过索引查询的,就需要全表扫描。所以,哈希索引只适用于等值查询的场景。而B+ 树是一种多路平衡查询树,所以他的节点是天然有序的(左子节点小于父节点、父节点小于右子节点),所以对于范围查询的时候不需要做全表扫描

Q:除了上面这个范围查询的,你还能说出其他的一些区别吗?*

A:(这个题我回答的不好,事后百度了一下)

B+ Tree索引和Hash索引区别?

哈希索引适合等值查询,但是无法进行范围查询

哈希索引没办法利用索引完成排序

哈希索引不支持多列联合索引的最左匹配规则

如果有大量重复键值的情况下,哈希索引的效率会很低,因为存在哈希碰撞问题

聚簇索引、覆盖索引

Q:刚刚我们聊到B+ Tree ,那你知道B+ Tree的叶子节点都可以存哪些东西吗?

A:InnoDB的B+ Tree可能存储的是整行数据,也有可能是主键的值

Q:那这两者有什么区别吗?

A:(当他问我叶子节点的时候,其实我就猜到他可能要问我聚簇索引和非聚簇索引了)在 InnoDB 里,索引B+ Tree的叶子节点存储了整行数据的是主键索引,也被称之为聚簇索引。而索引B+ Tree的叶子节点存储了主键的值的是非主键索引,也被称之为非聚簇索引

Q:那么,聚簇索引和非聚簇索引,在查询数据的时候有区别吗?

A:聚簇索引查询会更快?

Q:为什么呢?

A:因为主键索引树的叶子节点直接就是我们要查询的整行数据了。而非主键索引的叶子节点是主键的值,查到主键的值以后,还需要再通过主键的值再进行一次查询

Q:刚刚你提到主键索引查询只会查一次,而非主键索引需要回表查询多次。(后来我才知道,原来这个过程叫做回表)是所有情况都是这样的吗?非主键索引一定会查询多次吗?

A:(额、这个问题我回答的不好,后来我自己查资料才知道,通过覆盖索引也可以只查询一次)

覆盖索引?

覆盖索引(covering index)指一个查询语句的执行只用从索引中就能够取得,不必从数据表中读取。也可以称之为实现了索引覆盖。

当一条查询语句符合覆盖索引条件时,MySQL只需要通过索引就可以返回查询所需要的数据,这样避免了查到索引后再返回表操作,减少I/O提高效率。

如,表covering_index_sample中有一个普通索引 idx_key1_key2(key1,key2)。

当我们通过SQL语句:select key2 from covering_index_sample where key1 = 'keytest';的时候,就可以通过覆盖索引查询,无需回表。

联合索引、最左前缀匹配

Q:不知道的话没关系,想问一下,你们在创建索引的时候都会考虑哪些因素呢?

A:我们一般对于查询概率比较高,经常作为where条件的字段设置索引

Q: 那你们有用过联合索引吗?

A:用过呀,我们有对一些表中创建过联合索引

Q:那你们在创建联合索引的时候,需要做联合索引多个字段之间顺序你们是如何选择的呢?

A:我们把识别度最高的字段放到最前面

Q:为什么这么做呢?

A:(这个问题有点把我问蒙了,稍微有些慌乱)这样的话可能命中率会高一点吧。。。

Q: 那你知道最左前缀匹配吗?

A:(我突然想起来原来面试官是想问这个,怪自己刚刚为什么就没想到这个呢。)哦哦哦。您刚刚问的是这个意思啊,在创建多列索引时,我们根据业务需求,where子句中使用最频繁的一列放在最左边,因为MySQL索引查询会遵循最左前缀匹配的原则,即最左优先,在检索数据时从联合索引的最左边开始匹配。所以当我们创建一个联合索引的时候,如(key1,key2,key3),相当于创建了(key1)、(key1,key2)和(key1,key2,key3)三个索引,这就是最左匹配原则

虽然我一开始有点懵,没有联想到最左前缀匹配,但是面试官还是引导了我。很友善。

索引下推、查询优化

Q:你们线上用的MySQL是哪个版本啊呢?

A:我们MySQL是5.7

Q:那你知道在MySQL 5.6中,对索引做了哪些优化吗?

A:不好意思,这个我没有去了解过。(事后我查了一下,有一个比较重要的 :Index Condition Pushdown Optimization

Index Condition Pushdown(索引下推)

MySQL 5.6引入了索引下推优化,默认开启,使用SET optimizer_switch = 'index_condition_pushdown=off';可以将其关闭。官方文档中给的例子和解释如下:

people表中(zipcode,lastname,firstname)构成一个索引

SELECT * FROM people WHERE zipcode='95054' AND lastname LIKE '%etrunia%' AND address LIKE '%Main Street%';

如果没有使用索引下推技术,则MySQL会通过zipcode='95054'从存储引擎中查询对应的数据,返回到MySQL服务端,然后MySQL服务端基于lastname LIKE '%etrunia%'和address LIKE '%Main Street%'来判断数据是否符合条件。

如果使用了索引下推技术,则MYSQL首先会返回符合zipcode='95054'的索引,然后根据lastname LIKE '%etrunia%'和address LIKE '%Main Street%'来判断索引是否符合条件。如果符合条件,则根据该索引来定位对应的数据,如果不符合,则直接reject掉。有了索引下推优化,可以在有like条件查询的情况下,减少回表次数。

Q:你们创建的那么多索引,到底有没有生效,或者说你们的SQL语句有没有使用索引查询你们有统计过吗?

A:这个还没有统计过,除非遇到慢SQL的时候我们才会去排查

Q:那排查的时候,有什么手段可以知道有没有走索引查询呢?

A:可以通过explain查看sql语句的执行计划,通过执行计划来分析索引使用情况

Q:那什么情况下会发生明明创建了索引,但是执行的时候并没有通过索引呢?

A:(大概记得和优化器有关,但是这个问题并没有回答好)

查询优化器?

一条SQL语句的查询,可以有不同的执行方案,至于最终选择哪种方案,需要通过优化器进行选择,选择执行成本最低的方案。

在一条单表查询语句真正执行之前,MySQL的查询优化器会找出执行该语句所有可能使用的方案,对比之后找出成本最低的方案。

这个成本最低的方案就是所谓的执行计划。优化过程大致如下:

  1. 根据搜索条件,找出所有可能使用的索引

  2. 计算全表扫描的代价

  3. 计算使用不同索引执行查询的代价

  4. 对比各种执行方案的代价,找出成本最低的那一个