MySQL索引原理 B+Tree总结 - ZhangTory's NoteBlog - 张耀誉的笔记博客

MySQL索引原理 B+Tree总结

打算总结一下SQL优化原理和方法,避免不了索引原理和B+Tree,所以先总结一下B+Tree吧。

MySQL InnoDB 索引原理: B+Tree

B+Tree是B-Tree的一种变形,它的样子大概就是下面这个样。(网图侵删)

  1. B+Tree中所有的叶子节点都在同一层,包括根和中间的节点,都会落到最底层。
  2. 并且非叶子节点不包含数据内容,只包含索引值,这样做的好处就是能在一页中存尽量多的索引节点。所有的数据或数据的指针会存放在叶子节点中。
    等等,这里的一页是指什么?叶子节点到底存的是什么?我们等会儿会在创建索引的时候说到。
  3. 最后,所有的叶子节点相互之间也形成了链表,图上有一点错误,叶子节点之间形成的是双链表,而不是单链表。

综合以上3点,我们可以总结出B+Tree的优点:

  1. 所有的查询都会落到叶子节点,查询性能稳定。
  2. 在一页中能够存放更多的索引节点,就可以把树构造得矮胖,从而减少查询时的IO次数。
  3. 范围查询时不需要回到父节点,而是直接遍历链表即可,减少了IO次数。

创建索引

在知道索引原理后,我们就能很容易理解为什么走索引会更快。
所以当我们在查询时,对于业务常见的列需要构建索引,从而避免全表搜索。
但是创建索引也要尽可能的合理,从而榨干B+Tree的性能。

首先,一张表创建的索引不能过多,否则会影响插入时性能。
因为数据在插入时,B+Tree为了保持有序性会进行一些操作,需要消耗一定的性能。
所以这对我们创建表也提出了一点小小的要求。

另外索引的列不适合太大。
之前我们说非叶子节点不包含数据,是为了在一页中存放更多的索引节点。
这里的一页是数据库存储的单位,在硬盘上是一段连续的空间,InnoDB默认是16K,oracle默认是8K。
你可以想象成一页纸,纸越大,能写的字就越多。
在纸大小一定的情况下,为了让纸能写更多的数据,我们有2个办法:

  1. 把字写小。即非叶子节点不存放数据,这一点B+Tree的特性已经做到了。
  2. 言简意赅。即尽量简短,翻译翻译就是说索引值的大小不要太大。索引的大小在explain中的key_len是有体现的。

还有叶子节点到底存的什么?
聚簇索引中叶子节点直接存放数据;非聚簇索引中,叶子节点存放指针,这个指针就是主键的值。
为什么要这样设计呢?因为一张表可能有多个索引,如果全部都存放全部数据,那么就会有很多冗余数据,造成磁盘空间的浪费,尤其是过去硬盘比较贵的时代。
但是这么一来,使用非聚簇索引时,找到值后还得回到聚簇索引再查询一次,就造成了性能的消耗了,这种情况我们就叫做回表
这么一想,在磁盘空间不紧张的时代,能在非聚簇索引上也存想要的数据,就可以避免回表,查询也就能更快了,这种避免回表的方法,我们叫做覆盖索引

联合索引

为了实现覆盖索引,我们就要对用到的字段做联合索引。当然,联合索引不仅仅是用于覆盖索引,最主要的目的还是进一步提升查询性能。

还是先说说联合索引是如何提升查询性能的。

比如我们的SQL有2个条件:name和create_time,如果我们对这两个字段单独做索引,在执行SQL时就只能用到1个索引。
使用explain可以看到可以使用的索引有2个,但是实际使用的索引,是MySQL自己决定的,他会根据这两个字段的区分度来选择实际使用的索引。
比如name重复的很多,create_time几乎没有重复,那么就会使用create_time作为索引字段,在查找到对应的create_time值后,再对其中满足create_time值的全部行的name进行扫描;
如果create_time重复很多,但是name几乎没有重复,那么就会使用name作为索引字段,在查找到name值后,再对满足name值的全部行的create_time扫描。

于是我们可以想到,如果两个字段都能使用索引,岂不是更快?这就是联合索引了。
比如我们创建index(name, create_time),即创建了一个name字段的B+Tree,在name相同的数据中,又根据create_time字段再创建一个B+Tree,两个B+Tree是包含关系。如果联合索引还有第三个、第四个,那么还会继续往下创建索引。

至于创建索引时每个字段创建的顺序,就需要我们根据业务场景去分析了。

对于联合索引时SQL优化方案,就等下次再详细讲讲。

实现覆盖索引

假如我们要查询一个时间点创建的用户的用户名:select name from User where create_time=123456789
我们现在只做了1个索引index(create_time),那么根据我们之前的知识,在create_time这颗B+Tree上,先匹配到对应的时间点,获取到该时间点的用户id,在拿用户id去主键id索引的B+Tree上查询到name。那id去查name就是一次回表。
如果我们创建了索引index(create_time, name),那么我们先在create_time这颗B+Tree上先匹配到对应的时间点,之后在name这颗B+Tree上就能够直接拿到name,就不需要回表了。

强制索引

我们用explain查看执行计划的时候,有时可能会发现明明使用B索引更好,但MySQL偏偏使用了A索引或直接全表扫描。
为什么呢?因为MySQL自己分析认为走A索引或者全表扫描成本更低,比如使用B索引要回表,而使用全表扫描不会回表,那么就有可能不使用A索引;同理有可能MySQL认为A索引的成本更低,于是使用了A索引。
这种情况一般我们首先要看看创建的索引是否合理,或者使用强制索引force index B强制使用B索引。

添加新评论

电子邮件地址不会被公开,评论内容可能需要管理员审核后显示。