写在前面
面试官:请你描述一下mysql中索引。
我:哦。。索引大概类似字典中的目录,使用索引能够加快我们的查询效率。
面试官:还有呢?
我:没了。
面试官:回去等通知。
我:好的。。
你只看到了索引的第二层,你以为它在第一层,实际上它是第五层——LOL金牌讲师大司马千层博弈论
本片文章将从底层数据结构到应用带你了解索引,让你知其然还知其所以然。
索引结构
从表象上看
在我们创建索引的时候,mysql为我们提供了两种索引结构- HASH
- BTREE
HASH
类比一下我们
java
的HashMap
不难理解:
以key-value的形式检索数据,根据索引值生成hashCode,指向具体的行数据
特点:
- 等值查询非常快,效率为O(1)
- 数据是无序存储的,所以无法支持范围查询
- 重复的hash值很多时,会造成大量的hash冲突,形成链表(链表越长,查询效率越低,所以在jdk1.8的HashMap中将过长的链表转换为了红黑树)
BTREE
这是我们应用最广泛的索引结构,我们一般称为B+树,为什么称它为B+树呢,我们来详细分析一下各种数据结构。
查找二叉树(Binary Search Tree)
我们乱序的插入一些数据
6 3 5 7 8 13 9
- 特点:左子节点 < 根节点 < 右子节点
- 能够实现快速查找和插入,查找的耗时跟数据所在节点的深度有关
但是在极端情况下(按大小顺序插入),可能演变成链表
这样查找一些比较深的数据时,近乎就是遍历整个树了平衡二叉树(AVL Tree)
特点:
- 会通过旋转来保证:左右子树深度差绝对值不能超过 1
假如我们采用这种数据结构,我们可以猜想:
在每一个节点上会存放:
- 1.索引的值
- 2.索引对应行数据的地址
- 3.左右子节点的引用
这里穿插一个页的概念: 我们知道InnoDB(这里不对其他不常用引擎展开讨论)中的数据都是存储在磁盘上的,而我们对数据进行读写时,必须要先将其加载到内存中,InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 16KB。
反观我们上文的结构:我查询“3”这条数据需要进行3次查找(io消耗)
- 每一次加载的数据非常少(每次加载一个节点里的数据,浪费一次io,远远小于innodb中16K的页)
- 当数据量变多时,由于只有两个分叉,导致树的高度会很高,查询底部的数据时,io次数会非常多
多路平衡查找树(B Tree)
通过分裂与合并来保证:分叉数(路数)永远比关键字数多1
如图度数为3的B树,每个节点(页)最多存储2个关键字,最多拥有3个分叉。
- 路数变多,树由“高瘦”变得“矮胖”,查询数据所需的io次数变少
假设:B 树在枝节点和叶子节点存储键值、数据地址、节点引用。
如果我们B树的路数有1000的话,一颗三层的B树可以存储1000x1000x1000约10亿条数据(在只计算叶子节点的情况下),即只需要最多3次io就可以查到近10亿条的数据。
- 这里有个小问题:有些数据在根节点或者叶枝节点,而大部分数据存储在叶子节点,导致每次查询所需的io次数不一致(上层的根节点数据io次数少,下层的叶子节点所需io次数多)。
B+ 树索引 (主角登场)
标准的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,不如全表扫描
其他文章推荐
如果有收获别忘了给个赞哦 =。=