首页 > Mysql索引知识点汇总——面试必会
头像
ll201901232220563
发布于 2021-08-03 09:44
+ 关注

Mysql索引知识点汇总——面试必会

先介绍一下我自己,去年秋招中的一员,在字节实习过,拿到了腾讯、字节、美团、网易、pdd等互联网offer以及农商行、农行、招商银行、上交所、招行、深信服、华为等offer。本人目前美团正式员工,需要内推的欢迎来找我。

接下来一段时间内我会整理一些关于mysql的知识点,做一个mysql的专题,也算是自己回顾的笔记,各位正在准备秋招的学弟学妹们,欢迎关注公众号JerryCodes,定期分享面试必备八股文,技术实战经验等。

Mysql 作为互联网中非常热门的数据库,其底层的存储引擎和数据检索引擎的设计非常重要,尤其是 Mysql 数据的存储形式以及索引的设计,决定了 Mysql 整体的数据检索性能。

索引的作用是数据的快速检索,而快速检索实现的本质是数据结构。通过不同数据结构的选择,实现各种数据快速检索。例如在一个亿的数据中查找是否存在一个数,有几种方式?

  1. 顺序查找,那需要一亿次才能找到。。。

  2. 先对数据进行有序的整理,再进行二分查找,大约需要30次左右就可以找到。。。

  3. 构建一个非常大的HashMap,然后将这一亿个对象塞进去,每次找的时候通过映射关系查找这个对象是否出现过...等等

其实数据查找在数据库中是非常常见的场景,所谓CRUD,大部分场景都是对数据进行查找,那么这个时候索引的设计至关重要。

什么是索引

索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构。

索引可以由哪些数据结构组成

索引可以由hash表、B树、B+树构成,目前最常用的是B+树图片

图片说明

使用索引的好处

合理地使用索引,能够极大地提高数据库的检索效率,当面对大数据表时,使用索引是提高查询效率的常用方式。(这里通常表行数大于3000行使用索引,当数据量过小时,建议使用全表检索。)

什么时候用hashmap,什么时候用B+树

hashmap作为一种特殊的数据结构,能够达到O(1)的查找速度

图片说明

简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的。

(1)如果定位到的数组位置不含链表(当前entry的next指向null),那么查找、添加等操作很快,仅需一次寻址即可;

(2)如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。

所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

在某些语言中,当链表长度过长的时候,会选择

1.对这个hashmap进行扩容 2.将这个链表整理成一个红黑树。

这两种做法都是提升查找效率的方法。

图片

B+树 是一颗多路平衡查找树,是对 B 树的进一步优化。

hashmap不支持范围查找,我们知道当key值发生一点变化,整个hash函数后的值都会发生较大变动。若采用hashmap进行范围查找时,整体的搜索效率会下降至O(N)。因此B+树成为了索引数据结构的不二之选。

为什么B+树适合范围查找?

因为B+树在其叶子节点处有头尾相连的指针,可以用于快速的范围查找。

B树和B+树之间有什么异同

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树

首先B树是搜索二叉树的一种拓展,B-Tree 是一种自平衡的树(所有的叶子节点拥有相同的高度)类型的数据结构。

但是和其它树比,如红黑树、AVL树,他们只有两个孩子:左孩子和右孩子不同;B-Tree 的子节点是大于等于两个孩子。因此,有的时候B树称为M叉树,因为它可以有M个子节点(M>=2)。如图:

图片

假设我们现在有 100W 条记录,对于红黑树而言,树的高度约等于log(100W),也就是24 ,也就是说如果要查找到叶子结点需要 24次磁盘 I/O 操作;

但是 B树,情况就不同了,假设每一个结点可以包含 8 个键(当然真实情况下没有这么平均,有的结点包含的键可能比8多一些,有些比 8 少一些),那么整颗树的高度将最多 log8(100W),大概8层,也就意味着磁盘查找一个叶子结点上的键的磁盘访问时间只有 8 次,这就是 B树提出来的原因所在。

通常情况下B树的高度为2-4层,这也就是说查找某一个键值的行记录最多只需要2-4次,当前机械磁盘一秒钟至少可以搜索100次左右,也就意味着2-4次IO只需要0.02-0.04秒。

B+树相比B树的优点:

1、B+树的层级更少:相较于B树,B+树每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;

(B树非叶子节点存储数据,B+树非叶子节点不存储,整体呈现 “矮胖” 的特点)

2、B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;

(由于非叶子点挂载数据,B树有可能O(1)的复杂度查找到数据,也有可能O(logN)的复杂度,而B+树必须查找到叶子节点上)

3、B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。

4、B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

B树相对于B+树的优点:

如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。

为什么不可以用红黑树做索引

红黑树是一颗平衡二叉树,其查找的复杂度为O(log(N)),当N达到1000W的水平时候,在插入、删除、查找方面效率非常低且很难维护,在数据量小的范围内可以考虑使用红黑树做查找,但不适合做索引。

如何建立合适的索引

建立合适的索引,主要考虑以下几点:

1.在select语句中频繁被当作where筛选条件的可以考虑加索引

2.具有一定唯一标识性的字段

3.重复性不高的字段

哪些字段不适合当索引

  1. 较频繁的作为查询条件的字段应该创建索引;

  2. 唯一性太差的字段不适合单独创建索引,即使该字段频繁作为查询条件;

  3. 更新非常频繁的字段不适合创建索引。

是否建立索引后就可以加速查询

不一定,当我们的数据量很小的时候,有的时候直接全表扫描的速度会比走索引查找数据来的更加快。当数据量上升之后索引的优势才可以体现出来。

什么情况下索引会失效

建立索引是为了方便查询,但不代表sql语句中存在索引字段就可以走索引查找。如使用了like % 、正则表达式、!=、NOT IN这些字段的时候,索引会失效,查询会变成全表查询。

过多的索引会导致什么问题

建立索引是为了方便查询,但也会加重数据存储的负担。再每一次插入/修改/删除数据的同时,也需要维护好索引对应的数据结构。

对于一颗B+树来说,插入/删除数据最多遍历2-4次,但是维护多颗B+树对数据库的压力比较大,当有大量的数据插入时,聚簇索引的插入还算是高效,非聚簇索引下的插入可能会由于索引的插入是无序的导致插入的效率下降,这个时候引出了innodb的插入缓存,当然不是所有的非聚簇索引都可以满足插入缓存的条件,还需要其是非唯一性索引。

总之,过多的索引会造成维护困难,插入/删除效率低下,索引不是越多越好的。

聚簇索引和非聚簇索引有什么区别

聚集索引(聚簇索引):以 InnoDB 作为存储引擎的表,表中的数据都会有一个主键,即使你不创建主键,系统也会帮你创建一个隐式的主键。这是因为 InnoDB 是把数据存放在 B+ 树中的,而 B+ 树的键值就是主键,在 B+ 树的叶子节点中,存储了表中所有的数据。这种以主键作为 B+ 树索引的键值而构建的 B+ 树索引,我们称之为聚集索引。

非聚集索引(非聚簇索引):以主键以外的列值作为键值构建的 B+ 树索引,我们称之为非聚集索引。

非聚集索引与聚集索引的区别

两者的在于非聚集索引的叶子节点不存储表中的数据,而是存储该列对应的主键,想要查找数据我们还需要根据主键再去聚集索引中进行查找,这个再根据聚集索引查找数据的过程,我们称为回表。

明白了聚集索引和非聚集索引的定义,我们应该明白这样一句话:数据即索引,索引即数据。

非聚簇索引是否一定需要回表查询

不一定,当我们select出来的数据只需要在索引字段和主键中就可以满足了,那就没有必要通过主键再去回表查询。

唯一性索引、普通索引、联合索引又有什么区别

唯一性索引:意味着该索引在数据库中该字段是唯一的,行与行之间的字段两两各不相同,若在插入数据的时候发现该索引唯一性被破坏了,那么会报错。

普通索引

普通索引可以允许字段重复。

联合索引

联合索引指的是多列组合形成一个索引。

索引、主键、外键有什么联系

  • 索引:索引的存在是为了方便查找,提高查找效率。如一本词典中,建立偏旁部首作为索引,有利于字的查找。

  • 主键: 是数据行的唯一标识,如人的身份证号码、商品的订单单号,都是唯一性标识,独一无二不可重复。

  • 外键:A表和B表中,B表存放着A中的主键,那么在B中A的主键就叫做外键。外键的设计是体现了关系型数据库的设计思想。

什么是最左前缀原则

MySQL中的索引可以以一定顺序引用多列,这种索引叫作联合索引。

如User表的name、city和sex加联合索引就是(name,city,sex),而最左前缀原则指的是,如果查询的时候查询条件精确匹配索引的左边连续一列或几列,则此列就可以被用到。 如下:

select * from user where name=xx and city=xx ;

//满足最左前缀原则,命中索引(name,city)

select * from user where name=xx ;

// 满足最左前缀原则,命中索引name

select * from user where city=xx ;

// 不满足最左前缀原则,不命中索引

select * from user where name=xx and sex=xx ;

//不满足最左前缀原则,但命中索引name,对sex进行全表查找

这里要注意的是,是否满足最左前缀原则与是否存在命中索引并非等价的,如果满足最左前缀原则,那么它的查找必定经过索引。但是如果不满足最左前缀原则,也可能一部分查找满足索引,一部分需要全表扫描。

查询的时候如果两个条件都用上了,但是顺序不同,如 city= xx and name =xx,那么现在的查询引擎会自动优化为匹配联合索引的顺序,这样是能够命中索引的。

由于最左前缀原则,在创建联合索引时,索引字段的顺序需要考虑字段值去重之后的个数,较多的放前面。ORDER BY子句也遵循此规则。

为什么官方建议使用自增长主键作为索引

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

如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置,会造成插入数据时间长,存在内存碎片。

根据阿里JAVA规约中索引规约,总结以下索引使用注意事项

  • 【强制】 业务上具有唯一特性的字段,即使是多个字段的组合,也必须建成唯一索引。

说明:不要以为唯一索引影响了 insert 速度,这个速度损耗可以忽略,但提高查找速度是明显的;

另外,即使在应用层做了非常完善的校验控制,只要没有唯一索引,根据墨菲定律,必然有脏数据产生。

  • 【强制】 超过三个表禁止 join。需要 join 的字段,数据类型必须绝对一致;多表关联查询时,保证被关联的字段需要有索引。说明:即使双表 join 也要注意表索引、SQL 性能。
  • 【强制】 在 varchar 字段上建立索引时,必须指定索引长度,没必要对全字段建立索引,根据实际文本区分度决定索引长度即可。

说明:索引的长度与区分度是一对矛盾体,一般对字符串类型数据,长度为 20 的索引,区分度会高达 90%以上,可以使用 count(distinct left(列名, 索引长度))/count(*)的区分度来确定。left体现了索引的最左前缀原理

  • 【强制】 页面搜索严禁左模糊或者全模糊,如果需要请走搜索引擎来解决。说明:索引文件具有 B-Tree 的最左前缀匹配特性,如果左边的值未确定,那么无法使用此索引。
  • 【推荐】 如果有 order by 的场景,请注意利用索引的有序性。order by 最后的字段是组合索引的一部分,并且放在索引组合顺序的最后,避免出现 file_sort 的情况,影响查询性能。

正例:where a=? and b=? order by c; 索引:a_b_c

反例:索引中有范围查找,那么索引有序性无法利用,如:WHERE a>10 ORDER BY b; 索引a_b 无法排序。

  • 【推荐】 利用覆盖索引来进行查询操作,避免回表。

正例:能够建立索引的种类分为主键索引、唯一索引、普通索引三种,而覆盖索引只是一种查询的一种效果,用 explain 的结果,extra 列会出现:using index。

  • 【推荐】 利用延迟关联或者子查询优化超多分页场景。

说明:MySQL 并不是跳过 offset 行,而是取 offset+N 行,然后返回放弃前 offset 行,返回N 行,那当 offset 特别大的时候,效率就非常的低下,要么控制返回的总页数,要么对超过特定阈值的页数进行 SQL 改写。

正例:先快速定位需要获取的 id 段,然后再关联:SELECT a.

FROM 表 1 a, (select id from 表 1 where 条件 LIMIT 100000,20 ) b where a.id=b.id

  • 【推荐】 SQL 性能优化的目标:至少要达到 range 级别,要求是 ref 级别,如果可以是 consts最好。

说明:

1)consts 单表中最多只有一个匹配行(主键或者唯一索引),在优化阶段即可读取到数据。

2)ref 指的是使用普通的索引(normal index)。

3)range 对索引进行范围检索。

  • 【推荐】 建组合索引的时候,区分度最高的在最左边。

正例:如果 where a=? and b=? ,如果 a 列的几乎接近于唯一值,那么只需要单建 idx_a索引即可。

说明:存在非等号和等号混合时,在建索引时,请把等号条件的列前置。如:where c>? and d=? 那么即使 c 的区分度更高,也必须把 d 放在索引的最前列,即索引 idx_d_c。

  • 【参考】 创建索引时避免有如下极端误解:1)宁滥勿缺。认为一个查询就需要建一个索引。

2)宁缺勿滥。认为索引会消耗空间、严重拖慢更新和新增速度。

3)抵制惟一索引。认为业务的惟一性一律需要在应用层通过“先查后插”方式解决。

总结:

优点:

  1. 索引大大减小了服务器需要扫描的数据量;

  2. 索引可以帮助服务器避免排序和临时表;

  3. 索引可以将随机IO变成顺序IO。

缺点:

  1. 创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加;

  2. 索引需要占物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引,那么需要的空间就会更大;

  3. 当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。

有任何问题,私聊我或者关注公众号JerryCodes,看到了一定解答哦~

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐