你一定能看懂的mysql索引

1,189 阅读6分钟

写在前面

面试官:请你描述一下mysql中索引。
我:哦。。索引大概类似字典中的目录,使用索引能够加快我们的查询效率。
面试官:还有呢?
我:没了。
面试官:回去等通知。
我:好的。。

你只看到了索引的第二层,你以为它在第一层,实际上它是第五层——LOL金牌讲师大司马千层博弈论

本片文章将从底层数据结构到应用带你了解索引,让你知其然还知其所以然。

索引结构

从表象上看

在我们创建索引的时候,mysql为我们提供了两种索引结构

  • HASH
  • BTREE

HASH

类比一下我们javaHashMap不难理解:
以key-value的形式检索数据,根据索引值生成hashCode,指向具体的行数据


特点:

  • 等值查询非常快,效率为O(1)
  • 数据是无序存储的,所以无法支持范围查询
  • 重复的hash值很多时,会造成大量的hash冲突,形成链表(链表越长,查询效率越低,所以在jdk1.8的HashMap中将过长的链表转换为了红黑树)

BTREE

这是我们应用最广泛的索引结构,我们一般称为B+树,为什么称它为B+树呢,我们来详细分析一下各种数据结构。

查找二叉树(Binary Search Tree)

在线模拟:www.cs.usfca.edu/~galles/vis…

我们乱序的插入一些数据
6 3 5 7 8 13 9

  • 特点:左子节点 < 根节点 < 右子节点
  • 能够实现快速查找和插入,查找的耗时跟数据所在节点的深度有关

但是在极端情况下(按大小顺序插入),可能演变成链表

这样查找一些比较深的数据时,近乎就是遍历整个树了

平衡二叉树(AVL Tree)

在线模拟:www.cs.usfca.edu/~galles/vis…

特点:

  • 会通过旋转来保证:左右子树深度差绝对值不能超过 1

假如我们采用这种数据结构,我们可以猜想:
在每一个节点上会存放:

  • 1.索引的值
  • 2.索引对应行数据的地址
  • 3.左右子节点的引用

这里穿插一个页的概念: 我们知道InnoDB(这里不对其他不常用引擎展开讨论)中的数据都是存储在磁盘上的,而我们对数据进行读写时,必须要先将其加载到内存中,InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 16KB。

反观我们上文的结构:我查询“3”这条数据需要进行3次查找(io消耗)

  • 每一次加载的数据非常少(每次加载一个节点里的数据,浪费一次io,远远小于innodb中16K的页)
  • 当数据量变多时,由于只有两个分叉,导致树的高度会很高,查询底部的数据时,io次数会非常多

多路平衡查找树(B Tree)

在线模拟 www.cs.usfca.edu/~galles/vis…

通过分裂与合并来保证:分叉数(路数)永远比关键字数多1
如图度数为3的B树,每个节点(页)最多存储2个关键字,最多拥有3个分叉。

  • 路数变多,树由“高瘦”变得“矮胖”,查询数据所需的io次数变少

假设:B 树在枝节点和叶子节点存储键值、数据地址、节点引用。
如果我们B树的路数有1000的话,一颗三层的B树可以存储1000x1000x1000约10亿条数据(在只计算叶子节点的情况下),即只需要最多3次io就可以查到近10亿条的数据。

  • 这里有个小问题:有些数据在根节点或者叶枝节点,而大部分数据存储在叶子节点,导致每次查询所需的io次数不一致(上层的根节点数据io次数少,下层的叶子节点所需io次数多)。

B+ 树索引 (主角登场)

在线模拟 www.cs.usfca.edu/~galles/vis…

标准的B+树:

在mysql中,B+索引对标准的B+树做了一些改变:

特点:

  • 路数与关键字相等

每个节点存储更多关键字

  • 根节点和枝节点中都不会存储数据(只保存页号与对应页中最小的索引值),只有叶子节点才存储数据。

保证每次查询io(次数/耗时/效率)一致
根节点,枝节点不保存完整数据,能保存更多的关键字

  • 每个叶子节点保存了一个指向相邻叶子节点的指针,形成了一个有序链表的结构。

范围查询更快,全表遍历更快,只需要遍历叶子节点,不用遍历整棵树

索引类型

聚簇索引(主键索引)

B+树的叶子节点存储的是完整的行记录

因为是完整的记录所以叫聚簇么。。

二级索引(非主键索引)

也是由索引建值构成的B+树,只不过叶子节点只保存了索引建值与主键值

举个栗子:以c列创建的二级索引
在查询条件只包含c时,只过一遍c列构成的B+树即可
查询条件包含c列以外的字段时,需要通过c列的B+树拿到主键值,在走一遍主键的B+树,这个过程也叫回表。

联合索引(主键索引)

以(a,b,c)三列创建的联合索引,会先根据a排序,若a相等再根据b排序,若a,b相等再根据c排序,来创建一颗B+树

这也是最左匹配原则的由来:只有查询条件里包含(a)(a,b)(a,b,c)列才会走索引,条件先后顺序无所谓,因为mysql会分析各种成本,来选择最优的执行顺序,即只要查询条件符合索引的排序规则。

使用索引的注意事项

  • 在用于where,order,join on的字段上建立索引

这个大家都懂,不多BB了

  • 在使用like关键字的时候,要使用“key%”后缀匹配(最左匹配原则)

我们知道B+树维护的是一个从小到大顺序的集合。
对于字符串索引B+树的排序规则:先根据第一个字符排序,若第一个字符相对再根据第二个字符排序。。以此类推。
只有使用“key%”才能根据“key”等值查找到满足条件最小的值,再通过链表向后遍历。

  • 频繁更新的值不要作为索引或主键

内部维护了一个有序的B+树,若改变其中的大小会导致B+树中大量的页分裂与合并,会造成很大的开销

  • 主键最好使用int型的自增

理由同上,避免频繁的页分裂

  • 索引的个数不宜太多,可以按照标识度来建立一个复合索引

我们知道每一个索引都会创建一颗B+树,要排序,插入的效率会非常低

  • 区分度(离散度)低的字段(类似性别只有男女两个值)上不要建立索引

区分度低,查询效率低,还需要维护索引,回表多次io,不如全表扫描

其他文章推荐

如果有收获别忘了给个赞哦 =。=