索引常见面试题

索引常见面试题

什么是索引

索引对于数据库而言就相当于目录对于书.能够提高查找的效率,相当于是利用空间换时间.索引的存在能够让存储引擎更快地获取到目标数据.

存储引擎的主要功能就是存储数据,为数据创建索引以及更新,查询数据.MySQL的存储引擎有InnoDB,MyISAM,Memory等,MySQL5.5之后的存储引擎默认为InnoDB.

索引的分类

按数据结构分类

MySQL的索引可以分为B+Tree索引,Hash索引,Full-Text索引.

InnoDB是MySQL5.5之后默认的存储引擎,在InnoDB中最常使用的是B+Tree索引.

在创建表时,InnoDB存储引擎会根据不同的场景选择不同的列作为索引.

有主键,默认使用主键作为聚簇索引的key

没有主键,就选择非空的唯一列作为聚簇索引的key

否则InnoDB会自动生成一个隐式的自增id作为聚簇索引的key

除此之外,其他索引属于辅助索引(二级索引/非聚簇索引)

上述索引默认使用的都是B+Tree索引.

B+Tree的特点:除了叶子结点外的结点存储的都是索引值,父节点中的索引值在子节点中也所有体现.所有叶子节点按照顺序会连成一个单向链表

主键索引和二级索引的区别是存储在叶子结点中的值不同,主键索引中的叶子结点存储的是表中的全部信息,而二级索引中的叶子结点存储的是主键的值,因此在用二级索引查询时,如果查询的结果不止是主键本身就需要在得到主键值后再在主键索引中查找到目标结果,也就是回表

B+Tree存储千万级别的数据也只需要3-4层高度,因此查询效率非常高.

MySQL InnoDB选择B+Tree作为索引的数据结构的原因

1. 与B+Tree相比,BTree在非叶子节点存储的是全部信息而非索引值,因此B+Tree的查询效率更高
2. 与二叉树相比,B+Tree查询千万级别的数据的时间复杂度也为O(3~4),而二叉树的查询效率为O(logN),B+Tree的查询效率要高于二叉树
3. 与Hash相比,尽管Hash的查询效率为O(1),但Hash不支持范围查询.B+Tree支持范围查询,适用性更广.

按物理存储分类

索引分为主键索引和二级索引.区别就是二级索引在查询到的结果是目标的主键值,可能需要进行回表操作

按字段特性分类

索引分为主键索引,唯一索引,普通索引,前缀索引.

主键索引

主键索引就是以主键字段作为索引,一张表中最多只有1个主键索引,且不为空

唯一索引

唯一索引是建立在unique字段上索引,一张表中可以有多个唯一索引,每一个唯一索引中的列必须唯一,但可以为空.

普通索引’

普通索引就是建立在普通字段上的索引.

前缀索引

前缀索引是指选取字符类型的字段的前几个字符作为索引.目的是减少索引占用的空间,提升查询效率

按字段个数分类

索引分为单列索引和联合索引.

单列索引就是以单个列作为索引

联合索引就是将多个字段组合起来构成一个索引.

联合索引遵循最左匹配原则,例如某一个联合索引(a,b,c),对a先排序,然后对b排序,最后对c排序.因此在使用联合索引时,如果忽略左面的索引而使用右面的索引时不生效的.因为但看后面的某一个索引,其顺序是无序的.

因此,范围查询也可能导致联合索引失效.

那么联合索引在找到符合第一个索引的结果后是如何判断

MySQL5,6之前,是将得到的主键值进行回表,在主键索引中找到记录后判断后续条件是否符合

MySQL5.6之后引入了索引下推优化,不需要大量的回表操作,在联合索引遍历的过程中,对满足条件的结果先判断后续条件是否符合,如何不符合则直接跳过,符合后再进行回表

建立联合索引时,根据最左匹配原则,选取索引的顺序是非常重要的.区分度大的索引应该放在靠左的位置.

区分度 = 单列中不同的值的个数/表中所有行

索引的适用场景和非适用场景

索引的优点就是查询效率高,但索引也是有缺点的

1. 需要占用额外的物理空间,数据越多,占用空间越大
2. 创建索引和维护索引需要消耗时间
3. 会降低增删改的效率.每次增删改索引时,B+Tree都需要动态维护.

1. 索引的适用场景

   适用于字段有唯一性限制,经常使用Where字段查询,经常用Group By 和 Order By(建立好索引后,就不需要再查询到结果后再一次排序了)

2. 索引的非适用场景

   Where,Group By,Order By中用不到的字段.

   字段中存在大量重复数据,比如性别.

   表数据比较少

   经常更新的字段

如何优化索引

1. 前缀索引优化

   使用前缀索引可以减小索引的大小,提升查询效率

   但前缀索引也有一定的局限性

   前缀索引不能用于Order By(严格排序)

   前缀索引不能用于覆盖索引(覆盖索引返回的结果是一个唯一确定值而不是一个范围)

2. 覆盖索引优化

   覆盖索引是对使用二级索引是减少回表操作的一种优化.可以将返回的字段作成联合索引,然后在二级索引时找到符合条件的结果而无需返回整行记录的信息.

3. 主键索引最好是自增的

   主键索引如果是非递增的,那么在添加新纪录的过程中有可能主键对应的纪录会添加到某两个叶子结点之间,这也就意味着需要移动已经添加好的记录.而如果是自增的,每次添加的新记录都会按顺序放在已有记录的最后而无需移动已经添加好的记录.

4. 索引设置为NOT NULL

   当某一个值为NULL时,不同的字段对于NULL的处理是不一样的,因此NULL值对优化器而言更加复杂,难以优化.同时NULL值在更多情况下是一个没有意义的值,但会耗费物理空间.

5. 防止索引失效

   索引失效的场景

   1. 使用左或左右模糊匹配(“%xx”,“%xx%”)时,索引会失效(索引是根据前缀有序排列的,%无法对应)
   2. 查询条件中对索引列作了计算,函数或类型转换操作,索引会失效.(索引存储的是原始值)
   3. 联合索引时需要遵循最左匹配原则,否则会失效.
   4. Where子句中,如果Or前是索引列,Or后是非索引列,索引会失效(Or要求满足一个即可,所以Or后面的要进行全表扫描)

为什么MySQL采用B+树作为索引

索引的目的是为了提高查询的效率.因此设计索引的数据结构的查询效率一定要尽可能的高且要尽可能满足各种查询情况.

1. 要尽可能的在少的磁盘I/O次数下完成查询
2. 既要支持单个查询,也要满足范围查询

首先当存储的数据是有序时,我们可以通过使用二分法来大大降低查询的时间复杂度.

1. 与平衡树,红黑树相比.当数据量比较大时,平衡树的高度会随着数据量的增大而变高,而B+树即使在数据量很大的情况下也会维持一个较低的树高.
2. 与哈希表比,哈希表不支持范围查找,而B+树的叶子结点通过链表连接可以实现范围查找.
3. 与B树相比,B树在非叶子节点中也存储了大量的用户数据,浪费了大量的空间,在查找某个叶子结点时,需要从磁盘中取出大量非目标的用户数据,浪费了资源.

MySQL采用B+树作为索引的原因

1. B+树只有叶子节点中存有记录,在非叶子节点中只存放索引,因此相比于既存放索引又存放数据的B树而言,B+树的非叶子节点可以存储更多的索引,因此B+树可以更矮胖
2. B+树中非叶子节点存有大量的冗余节点.因此在更新树中的节点时只需要更改叶子结点而无需动整个树.
3. B+树的叶子节点之间用链表连接,因此实现范围查询的效率更高.

索引失效有哪些

1. 使用模糊查询的左模糊查询(“%xx”)或左右模糊查询(“%xx%”)

   索引B+树是按照索引值进行有序排列存储的,因此只能根据前缀进行比较,而上述两种模糊查询的前缀是不确定的

2. Where子句中 Or前为索引,Or后为非索引

   Or的含义是实现前后者中的一个即可.因此即使Or前的条件走索引,Or后的非索引条件也会进行全表查询

3. 联合索引时不遵循最左匹配原则

   联合索引就是将多个字段组合在一起创建的索引.如(a,b,c).联合索引要遵循最左匹配原则,也就是先实现a的有序,再实现b的有序,最后实现c的有序.因此如果违反最左匹配原则,就违背了索引的有序性,所以索引会失效.

4. 对索引使用函数,表达式,隐式类型转换等运算

   1. 对索引使用函数

      如select * from user where length(userId) > 1;上述查询过程中就不会使用userId这个主键索引.原因是索引中存储的是原始的索引值,通过函数计算得到的值是不能够走索引的.

      但MySQL8.0中已经实现了函数索引,支持经过函数计算的值实现索引.

   2. 对索引使用表达式

      如select * from user where userId + 1 = 10;

      理由跟上述使用函数相同

   3. 对索引使用隐式类型转换

      整数转换为字符串:select * from user where userPhone = 12345; #userPhone是varchar类型

      字符串转换为整数:select * from user where userPhone = “12345”; #userPhone是int类型

      上述第一种情况索引会失效,而第二种可以走索引.原因是因为MySQL的类型转换支持字符串转为整形但不支持反向转换,也就是说当字符串和数字比较时,会将字符串转换为数字