本文共 4618 字,大约阅读时间需要 15 分钟。
本文是作者在了解学习 MySQL 索引时的知识点的总结,对于里面可能出现的不严谨或者错误的地方,希望大家指出。
某一样东西或机制的诞生必定时有着对它所能实现的功能的需求。MySQL 索引机制便是为了快速定位数据地址,提高数据库性能而出现的。索引起到的作用就好似书上的目录,你可以根据目录定位到自己想要读取的内容的大致地址,当然这里用目录打比方是为了说明索引的作用,实际上索引的实现和目录大相径庭。
此节将简单阐述索引的实现,并通过举例说明为什么索引能起到快速定位的作用。
在学习B树之前,建议先了解一下平衡二叉树。
平衡二叉树(Balanced Binary Tree)又被称为AVL树,它是二叉查找树的进一步优化,因为在某写特殊情况下,二叉查找树可能会退化为链表结构,比如在节点为:【1, 2, 3, 4】的时候,二叉查找树的结构会变成这样:
这样看起来它就类似于一个链表,而平衡二叉树通过旋转的方式使左右两个子树的高度差的绝对值小于等于1,虽然可能会有频繁的旋转操作,但相对于二叉查找树来说时间上稳定了很多,此时上面的图可以变化为:
在解决了时间稳定性的问题后,我们会发现由于AVL树是二叉树结构,它的最大节点数大小为:number=2**hight-1
,如果要存储1,000,000
条数据,那么树的高度至少20(2**20=1,048,576
)。
为了降低树的高度,就引入多路的概念,(B树和B+树都是多路平衡查找树,从它们的名字可以看出,B+树是B树的进阶)那么我们就先来看看B树的结构:
图来自
很明显,多路就是开出多个分支,每个节点之间由键、子节点地址指针、数据组成,查找方式和平衡二叉树一样。
对于B树在插入/删除是如何保证平衡性感兴趣的,可以看看这篇文章
为什么每个节点要标注为磁盘块?
磁盘IO时间 = 寻道 + 磁盘旋转 + 数据传输时间,在随机读写时,磁头需要不断移动来找到对应的数据,为了减少I/O次数,磁盘会进行预读,即顺序向后读取一定长度的数据,磁盘预读的单位是页的整数倍。当索引节点的大小等于磁盘块时,那么在预读取时可以一次读取,十分方便。
页是内存的最小存储单位,磁盘块是文件系统读写数据的最小单位,扇区是磁盘的最小存储单位。一个磁盘块由连续几个(2^n)扇区组成,页的大小为磁盘块大小的2^n倍。
在上图我们可以看到一个节点由键、子节点地址指针、数据组成,但是数据的大小是不确定的,如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小。为了解决这个问题,MySQL 在B树的基础上进行了进一步的优化,将数据存储在叶子节点,这就是B+树,它的结构如下所示:
图来自
我们可以看到在MySQL中,B+树的叶子节点通过双向链表的方式进行连接,这是为了当我们在进行范围查找时,只需要找到边界值就可以通过指针去查找其它需要的数据。
B+树下能存储多少数据?
innerdb中页的大小为16KB,如果表的主键为BIGINT(8byte),指针类型大小为8byte,那么一个节点可以存储
16/(8+8)=1k
个键。一个深度为3的B+树可以维护
10**3 * 10**3 * 10**3 =10,000,000,000
条数据。
对于索引的创建,MySQL 主要由以下四种方法:
全文索引:全文索引是用于支持全文信息查找的索引,全文索引通常使用倒排索引来实现,对于倒排索引的举例可以说:以前的索引是每一行文本记录以文档ID作为索引,以文档内容作为记录,但是倒排索引是将单词或记录作为索引,将文档ID作为记录,这样便可以方便地通过单词或记录查找到其所在的文档。
哈希索引:哈希索引是自适应索引,通过hash算法将数据放到对应的hash槽,如果槽中已经有了元素则使用链接法挂载到末尾。
哈希索引的缺点:虽然hash索引可以做到
log(1)
的时间内查找数据,但是由于hash的不连续性,所以无法进行范围查找,无法被用来避免数据的排序操作,对于组合索引,MySQL 哈希索引不能使用部分索引键来查询。哈希索引的使用是由MySQL自己决定的,不能人为设定。
B树索引:用B树或B+树结构存储的索引
spatial索引:空间索引是对空间数据类型的字段建立的索引(GEOMETRY、POINT、LINESTRING、POLYGON),空间索引只能在存储引擎为MYISAM的表中创建。
按照对所加索引的数据的类型进行分类,索引可以分为以下四种:
null
null
Innodb中的索引模型有聚簇模型和非聚簇模型,索引模型不是一种索引模型,而是数据存储的方式。对于聚簇索引来说,它的数据是存储在索引的叶子节点上面的,而非聚簇索引的叶子节点则是存放对应数据的地址,因此MySQL在非聚簇索引中获取数据行的地址后,还要去聚簇索引根据数据行地址获取数据。两者之间的区别如下所示:
上图来自一书
我们可以看到聚簇索引中有两个索引表,一个是主索引,一个是辅助索引(二级索引)。辅助索引保存的是主索引的值,这是因为聚簇索引会发生页分裂,导致原来数据存储的地址可能会发生变化。当页的地址发生变化后,只需要维护主索引的数据就可以了,不需要维护辅助索引。可以说,辅助索引和非聚簇索引没有什么实质的区别,
表上的每个非聚簇索引都是二级索引,又叫辅助索引。
在此文后面,对于二级索引和辅助索引都统一称为辅助索引。
为什么要分为聚簇索引和非聚簇索引?
当数据库某个表有多个字段索引,因为一棵B+树只能存储主键,如果检索的是非主键字段,则又会变成顺序查找。此时就应该要在第二个要检索的列上建立第二套索引,这个索引由独立的B+树来组织。聚簇索引和非聚簇索引就是使用多个B+树来访问同一套表数据的解决方 案。对于聚簇索引存储来说,行数据和主键B+树存储在一起,辅助键B+树只存储辅助键和主键,主键和非主键B+树几乎是两种类型的树。对于非聚簇索引存储来说,主键B+树在叶子节点存储指向真正数据行的指针,而非主键。
聚簇索引所在的B+树的叶子节点通过双向链表的结构,实现了在逻辑上顺序存储,但是在物理上还是随机存储的。
在了解了主索引和辅助索引的存储方式之后,我们就可以分析回表
这一术语了。因为聚簇索引的辅助索引存放的主索引的值,那么通过辅助索引查找数据后,首先经由辅助索引拿到主索引的值,然后通过主索引的值来获取对于的数据。这个首先获取主键,再通过主键去查询数据的过程被称为回表。
经过上面了解了B树的结构、索引的分类、索引存储结构后,我们可以尝试分析一下什么情况下索引会失效。
再次将索引比作目录,很显然,我们在使用目录时,必须要先知道你要查的索引数据。比如它的值或者它开头是什么。
我之前想到如果类比目录的话,那么也许在查找前10个
%xxx%
的索引值时可能会用到索引,就跟查目录一样,通过匹配选出符合条件的索引,但是通过explain
分析发现这个想法是错误的:
接下里就通过 explain
语句分析一下以下这个情况是否会导致索引失效,我的数据量为:
索引字段:
查询条件简单地使用不等式:
对索引进行运算,一定为导致索引失效
like通配符可能会导致索引失效
这两条
type
不一样的原因在于and
使在前面已经通过索引获取到的数据里进行排除,而第5条很显然要通过全表来扫描sex like "男"
。当你尝试第四条这么写时,也不会进行全表扫描,因为MySQL的查询优化器会对语句进行分析和重排序:
explain select count(0) from stu where sex like "男" and id <> 2
对于上图的两条SQL,第二条很显然是全表扫描。但是我们要注意第一条,只要
select
字段是覆盖索引,那么也会使用索引。
对索引是否为空进行判断不会导致索引失效**
即使可以对于索引字段使用
is null
或者is not null
进行查询,但是大部分情况下还是不要使用。因为MySQL对于每条数据的行记录中会有一个空间来记录值为null
的字段,而且对于null
数据的处理不能使用=/in/</<>/!=/not in
这些操作符号。
复合索引可能失效
在删除了id
和name
索引后重建了它们的复合索引,结构如图:
相关操作如下:
可以看到复合索引的失效原因和单值索引差不多,唯一不一样的是只要复合索引里一个索引犯了错,那么就会进行全表扫描。
使用命令:show index from xxx
即可查看,
在这里有个cardinality字段,可以通过它来评估索引是否合理。它会估计索引中不重复记录,如果这个相对值很小,可能就要评估索引是否有意义。比如字段sex
只有值m
/w
,选任何一个值的可能性时50%,那么就没有为它创建索引的必要。
在实际使用中,cardinality/表的数据总数
应该约等于1,如果远小于1的话,那么需要考虑是否要为它建立索引。
FIC为fast index creation(快速索引创建)
是一个比较老的概念了,是在MySQL5.5的时候出的。它是用于对索引的添加/删除进行管理的机制。
在创建索引时,innodb会先在目标表上加上一个S锁,然后添加索引。在删除索引时,innodb只是更新内部视图,将辅助索引的空间标记为可用,然后删除MySQL内部上对该表的索引的定义。而不是像之前那个重建一个表,把原表数据复制进去,添加/删除索引,然后用新表替代旧表。
Online DDL是用于支持在DDL期间进行DML语句的并行操作,在MySQL5.6时加入的,在此之前虽然有OSC实现了部分功能,但还是有很大的局限性。
对于Online DDL有兴趣的可以看看这篇博客
MRR的一种为了减少随机磁盘访问,将随机I/O转换为顺序I/O的处理机制,于MySQL5开始使用。
这种机制很适合在使用辅助索引进行随机访问读取数据,如果表的数据很多,以至于无法放入缓存时的情况。MySQL首先会基于索引进行数据定位并收集满足条件的keys,然后再对这些keys进行排序,这样就由原来的随机/O变成了顺序I/O
。
当不需要进行全表访问时(full table),InnoDB
和MyISAM
不会进行MRR优化,因为如果查询结果可以基于索引得出(比如覆盖索引)。
ICP是一种通过索引从表中检索出数据的优化方式,于MySQL5开始使用。
如果where条件可以使用索引,MySQL会把这部分过滤操作放到存储引擎层,存储引擎通过索引过滤,把满足的行从表中读取出。当选择禁用ICP时,存储引擎会通过遍历索引定位基表中的行,然后返回给Server层,再去为这些数据行进行where条件的过滤。
由此可以看出 ICP可以减少存储引擎必须访问基表的次数以及Server曾必须访问存储引擎的次数。
转载地址:http://bjqgn.baihongyu.com/