阿里架构师讲面试:数据库索引

1,609 阅读8分钟

为什么要引入索引

一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,遇到最多的,也是最容易出问题的,还是一些复杂的查询操作,所以查询语句的优化显然是重中之重。

假如一张表有一亿条数据 ,需要查找其中某一条数据,按照常规逻辑, 一条一条的去匹配的话, 最坏的情况下需要匹配一亿次才能得到结果,用大O标记法就是O(n)最坏时间复杂度,这是无法接受的,而且这一亿条数据显然不能一次性读入内存供程序使用, 因此, 这一亿次匹配在不经缓存优化的情况下就是一亿次IO开销,以现在磁盘的IO能力和CPU的运算能力, 有可能需要几个月才能得出结果 。**如果把这张表转换成平衡树结构(一棵非常茂盛和节点非常多的树),假设这棵树有10层,那么只需要10次IO开销就能查找到所需要的数据, 速度以指数级别提升,用大O标记法就是O(log n),n是记录总树,底数是树的分叉数,结果就是树的层次数。**换言之,查找次数是以树的分叉数为底,记录总数的对数,用公式来表示就是:

用程序来表示就是Math.Log(100000000,10),100000000是记录数,10是树的分叉数(真实环境下分叉数远不止10), 结果就是查找次数,这里的结果从亿降到了个位数。因此,利用索引会使数据库查询有惊人的性能提升。

然而, 事物都是有两面的, 索引能让数据库查询数据的速度上升, 而使写入数据的速度下降,原因很简单的, 因为平衡树这个结构必须一直维持在一个正确的状态, 增删改数据都会改变平衡树各节点中的索引数据内容,破坏树结构, 因此,在每次数据改变时,DBMS必须去重新梳理索引树的结构以确保它的正确,这会带来不小的性能开销,也就是为什么索引会给查询以外的操作带来副作用的原因。

索引原理

数据结构 B+树(多路平衡查找树)

单列索引

**索引结点为单个磁盘块,内存每次io加载一个磁盘块数据。**每个节点包括索引key值和next指针。因此索引列key值越小,每个磁盘块可以放更多数据,B+树的分叉数越多,B+树越扁平。

B+树构建过程

参考:www.jianshu.com/p/1775b4ff1…

联合索引

与单列索引的区别为,这里以联合索引列数据作为value值,value比较权重从第一列往后顺序递减。索引key为联合索引字段集合(按照顺序)。

联合索引 bcd , 在索引树中的样子如图 , 在比较的过程中 ,先判断 b 再判断 c 然后是 d 。因此有联合索引的最左匹配原则。

根据联合索引树,找到该索引下的data元素即ID值,再从主键索引树上找到最终数据。(非聚集索引)

聚集索引

树的所有结点(底部除外)的数据都是由主键字段中的数据构成,也就是通常我们指定主键的id字段。最下面叶子结点部分是真正表中的数据。聚簇索引的叶子节点中,包含了一个完整的记录行。 假如我们执行一个SQL语句:

select * from table where id = 1256;

首先根据索引定位到1256这个值所在的叶结点,然后再通过叶结点取到id等于1256的数据行。

非聚集索引

非聚集索引叶子节点只包含索引列和主键值,通过非聚簇索引查找记录要先找到主键,然后通过主键再到聚簇索引中找到对应的记录行,这个过程被称为回表

非聚集索引和聚集索引的区别在于, 通过聚集索引可以查到需要查找的数据, 而通过非聚集索引可以查到记录对应的主键值 , 再使用主键的值通过聚集索引查找到需要的数据,如下图:

不管以任何方式查询表, 最终都会利用主键通过聚集索引来定位到数据,聚集索引(主键)是通往真实数据所在的唯一路径。

覆盖索引

然而,有一种例外可以不使用聚集索引就能查询出所需要的数据, 这种非主流的方法称之为「覆盖索引」查询, 也就是平时所说的复合索引或者多字段索引查询。 文章上面的内容已经指出, 当为字段建立索引以后, 字段中的内容会被同步到索引之中, 如果为一个索引指定两个字段, 那么这个两个字段的内容都会被同步至索引之中。

如果一个索引包含(或覆盖)所有需要查询的字段的值,称为'覆盖索引'。

非聚簇索引中因为不含有完整的数据信息,查找完整的数据记录需要回表,所以一次查询操作实际上要做两次索引查询。而如果所有的索引查询都要经过两次才能查到,那么肯定会引起效率下降,毕竟能少查一次就少查一次。

以上面的age索引为例,它是一个非聚簇索引,如果我想通过年龄查询用户的id,执行了下面一条语句:

select id from userinfo where age = 10;

这种情况是否还有必要去回表?因为我只需要id的值,通过age这个索引就已经能拿到id了,如果还去回表一次不就做了无用的操作了吗?实际上确实是不需要的。索引查询中,如果辅助索引已经能够得到查询的所有信息了,就无需再回表,这个就是覆盖索引。

索引分析和优化

索引规则

  • 最左匹配

**mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配,**比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引,d是用不到索引的,如果建立(a,b,d,c)的索引则都可以用到,a,b,d的顺序可以任意调整。b = 2 如果建立(a,b)顺序的索引,是匹配不到(a,b)索引的。

  • 索引字段尽量小

磁盘块的大小也就是一个数据页的大小,是固定的,如果数据项占的空间越小,key的数量越多,树的分叉越多,树的高度越低。这就是为什么每个数据项,即索引字段要尽量的小。

  • 选择区分度高的列作为索引列

区分度低的话,树的分叉数量少,树的高度更高,需要更多次的IO,效率更低。

  • =和in可以乱序

比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序,mysql的查询优化器会帮你优化成索引可以识别的形式。

  • 尽量的扩展索引,不要新建索引。

比如表中已经有a的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可。

索引下推

在MySql 5.6版本中引入了一个新特性,叫做“索引条件推送(index condition pushdown)”,这也称为索引下推。那么索引下推是这个什么东东呢?其实从**“索引条件推送”这个名字就可以表明,这个特性是可以在索引中的字段进行条件判断,过滤不满足条件的记录,减少回表的次数。**

比如:

select * from person where name like 'A%' and age = 19;(索引字段为name,age)

那么如果没有索引下推的情况下,首先会根据索引查询出名字以A开头的所有记录,然后查询出ID,然后回表去查询对应的ID记录,最后再判断age=19,返回满足条件的语句。因为满足A开头的记录有2条,所以这种情况下,会回表2次。

在索引下推情况下,InnoDB会在索引内部直接判断age=19是否满足条件,过滤掉不满足条件的记录,所以只返回了一条,也就是只需要回表一次。从而提高了性能。

索引应用

  • 唯一索引

唯一索引是一种不允许具有相同索引值的索引,系统在创建该索引时检查是否有重复的键值,每次对更新或增加记录时都会检查这一点。主键索引就是唯一索引。

  • 联合索引

觉得有收获的话帮忙点个赞吧,让有用的知识分享给更多的人

## 欢迎关注掘金号:五点半社

## 关注微信公众号:五点半社(工薪族的财商启蒙)##