索引详解
为什么使用索引
索引是存储引擎用于快速找到数据记录的一种数据结构,类似教科书的目录部分,通过目录中找到对应的文章页码,便可快速定位到需要的文章。Mysql的索引也是一样的道理,避免了查找数据的时候进行全表扫描。
左侧为全表扫描,其时间复杂度为O(n)
,右侧为二叉树,其时间复杂度为O(logn)
。
索引主要为了减少磁盘IO
索引概述
定义:索引(Index)是帮助MySQL高效获取数据的数据结构。
索引是一种数据结构
是一种排序好后用来快速查找的数据结构
索引的具体实现由存储引擎完成,所以每种存储引擎的索引不一定完全相同
存储引擎可以定义每个表的最大索引和最大索引长度。所有才能出引擎支持每个表至少16个索引,总索引长度至少为256个字节。有些存储引擎支持更多的索引数和更大的索引长度。
优点
通过降低数据库IO次数,提高检索效率
通过唯一索引,可以保证数据库表中的每一行数据的唯一性
在实现数据的参考完整性方面,可以加速表和表之间的连接。换句话说,对于有依赖关系的子表和父表联合查询时,可以提高查询速度。
在使用分组和排序子句进行数据查询时,可以显著减少查询分组和排序的时间,降低了CPU的消耗
缺点
创建索引和维护索引要耗费时间,随着数量的增加,锁耗费的时间也会增加
索引需要占磁盘空间,除了数据表占数据空间外,每个索引还要占用一定的物理空间存储在磁盘上。如果有大量的索引,索引文件就可能比数据文件更快达到最大文件尺寸。
虽然索引大大提高了查询速度,同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据维护的速度。
InnoDB中索引推演
创建表:
新建一张表,并且规定行格式Compact
,如下图:
record_type
:记录头信息的一项属性,表示记录的类型,0代表普通记录、2代表最小记录、3代表最大记录next_record
:行与行之间采用单向链表相互关联,表示以一条地址相对于本条记录地址的偏移量各个列的值
:这里记录表index_demo
的三个列的值其他信息
一个数据也的大小为16kb,可以存储很多条记录,这里以三条为例,行在数据页的表示如下:
单页情况
比如向表index_demo
插入3条数据:
因为各个页中的记录并没有什么规律,我们不知道搜索条件匹配哪儿些页的哪儿些行,所以不得不遍历所有的数据也以及所有的行。为了可以使用二分法在页内查找,并且易于统计最小记录与最大记录,页内的记录将会采用有序的方式存储:
插入的三条数据,需要按照主键进行排序放入页中,如果插入顺序不一致,将会发生移动
记录之间以单项链表相互连接
页有页头跟页尾两个记录
当发生查询时,直接针对主键进行二分查找,可快速定位所在记录。
多页情况
假设现在再向表中插入一条数据:
因为行数已经超过页可存储的大小,这时将会自动分配新的页:
为了保证数据的排序(方便查找),也就是下一个数据也中记录的主机值一定要大于上一个页中记录的主键值,主键4的数据会与主键5的数据相互移动位置,以保证有序:
记录向其他页移动的过程,称为页分裂。
给页建立目录项
由于页的编号可能是不连续的,所以向插入多条记录后,页的状态可能是如下情况:
当数据越来越多时,页就会越来越多。当查询某个数据时:
因为这些16kb的页仅仅在逻辑上是连续的,在物理上存储上可能是不连续的
所以要查询某个数据时,就要依次遍历所有的页找到目标记录所在的范围
如果页特别的多,这将是一个非常耗时的行为
所以,可以通过给页建立目录项来提供更快速的查找:
以
页10
为例,它对应的目录项为目录项1
一个目录项中,包含了当前目录项最小的主键
key
,以及在这个范围内的行所在的页号page_no
我们只需要将目录项在物理存储其上连续存储,即可以使用二分法的方式,快速的定位某个主键所在的页
目录项记录页
上述结构有如下缺点:
当数量越来越大的时候,目录项也会越来越大
目录项采用连续的物理空间存储,当发生删除、增加的情况下,目录项也会发生增加、删除操作,此时会发生数组元素前移、后移的情况,对性能损失也较大
解决办法:
目录项采用连续物理空间存储缺点较多,改为单链表存储
因为目录项之间的关系与行之间的关系类似,我们页使用页来存储目录项
目录项记录只有
主键值
和页编号
两个列,而数据记录则是具体的表的行数据如下图,使用
record_type=1
来表示目录项记录,而数据页记录,则使用record_type=0
多个目录项记录页
缺陷:
随着数据的继续增大
因为一个页只能存储16kb的数据,所以单个目录项记录页可能无法存储所有的记录
这时可以像数据页一样,横向扩展数据页
目录项记录页的目录页
生成一个更高级目录项的 页33 ,这个页中的两条记录分别代表页30和页32,如果用户记录的主键值在 [1, 320) 之间,则到页30中查找更详细的目录项记录,如果主键值 不小于320 的话,就到页32中查找更详细的目录项记录。
这就是B+树。
B+Tree
一个B+树的节点其实可以分成好多层,规定最下边的那层,也就是存放我们用户记录的那层为第 0 层,之后依次往上加。
为什么B+树通常不超过四层
树的层次越低,IO的次数就越少。
假设每个叶子结点(数据页)可以存放100行记录,每个非叶子结点(数据项)可以存储1000条记录那么:
如果b+树有1层,工可以存储
100
条记录如果b+树有2层,工可以存储
100 * 1000 = 10,0000
条记录如果b+树有3层,工可以存储
100 * 1000 * 1000 = 1,0000,0000
条记录如果b+树有4层,工可以存储
100 * 1000 * 1000 * 1000 = 1000,0000,0000
条记录
常见索引的概念
聚簇索引
聚簇索引并不是一种单独的索引类型,而是一种数据存储方式,整个索引的B+树都是存放在磁盘中的,也就是索引即数据,数据即索引
。InnoDB默认会自动创建聚簇索引。
术语
聚簇
表示数据行和相邻的键值聚簇的存储在一起。
使用记录主键值得大小进行记录页的排序,这包括三个方面的含义:
页内的记录是按照逐渐的大小顺序排序成一个单项链表
各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表
B+数的叶子结点存储的是完整的用户记录
所谓的完整的用户记录,就是指这个记录中存储了所有列的值。
优点:
数据访问速度更快,因为聚簇索引将索引和数据保存在同一个B+数中,因此从聚簇索引中获取数据比非聚簇索引更快
聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
按照聚簇索引排列顺序,查询显示一定范围数据的时候,由于数据都是紧密相连,数据库不用从多个数据块中提取数据,所以 节省了大量的io操作 。
缺点:
插入速度严重依赖于插入顺序 ,按照主键的顺序插入是最快的方式,否则将会出现页分裂,严重影响性能。因此,对于InnoDB表,我们一般都会定义一个自增的ID列为主键
更新主键的代价很高 ,因为将会导致被更新的行移动。因此,对于InnoDB表,我们一般定义主键为不可更新
二级索引访问需要两次索引查找 ,第一次找到主键值,第二次根据主键值找到行数据
限制:
对于MySQL数据库,目前只有InnoDB数据引擎支持聚簇索引,而MyISAM并不支持聚簇索引
由于数据物理存储排序方式只能有一种,所以每个MySQL的表只能有一个聚簇索引,一般都是这个表的主键
如果没有定义主键,InnoDB会选择非空的唯一索引代替。如果没有这样的索引,InnoDB会饮食的定义一个主键作为聚簇索引。
为了充分利用聚簇索引的聚簇特性,所以InnoDB的表的主键尽量选择有序的ID,而不建议使用无序的id,比如UUID、MD5、HASH、字符串列作为主键无法保证数据的顺序增长。
二级索引(辅助索引,非聚簇索引)
聚簇索引只能在搜索条件为主键值得情况下才能发挥作用,因为B+树的数据都是按照主键进行排序的。那么如果我们想以别的列作为搜索条件,就可以使用非聚簇索引。
回表 我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值,所以如果我们想根据c2列的值查找到完整的用户记录的话,仍然需要到 聚簇索引 中再查一遍,这个过程称为 回表 。也就是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树!
聚簇与非聚簇的区别
聚簇索引的叶子结点存储的就是我们的数据记录,非聚簇索引的叶子结点存储的是数据位置。非聚簇索引不会影响数据表的物理存储数据。
一个表只能有一个聚簇索引,因为只能有一种排序存储的方式,但可以有多个非聚簇索引,也就是多个索引目录提供数据检索
使用聚簇索引的时候,数据的查询效率高,但如果数据进行插入、删除、更新的操作,效率会比非聚簇索引低。
联合索引
是一种非聚簇索引。
每条目录项记录都由
c2
、c3
、页号
这三个部分组成,各条记录先按照c2列的值进行排序,如果记录c2列相同,则按照c3列的值进行排序。B+数叶子结点处的用户记录由
c2
、c3
、主键c1
组成。
InnoDB B+树索引的注意事项
根页面的位置万年不动
B+树的实际生成过程应该是这样的:
每当为某个表创建一个B+树索引的时候(聚簇索引不是认为创建的,默认就有),都会为这个索引创建一个根节点页面。最开始表中没有数据的时候,每个B+树索引对应的根节点既没有用户记录,也没有目录项记录。
随后向表中插入用户记录时,先把用户记录存储到这个根节点中。
当根节点中的可用空间用完时,再继续插入记录,将会把根节点的所有记录复制到一个新分配的页,比如页a中,然后对新页进行页分裂操作,得到另一个新页,比如页b。这时新插入的记录根据键值的大小就会被分配到页a或者页b中,而根节点便升级为存储目录项记录页。
这个过程特别注意的是:一个B+树索引的根节点自诞生之日起,便不会移动。这样只要我们对某个建立了一个索引,那么他的根节点的页号便会被记录到某个地方,然后凡是InnoDB存储引擎要用到这个索引的时候,都会从那个固定的地方取出根节点的页号,从而访问这个索引。
内节点中的目录项记录唯一性(非聚簇索引)
非聚簇索引的内节点中目录项记录的内容是 索引列 + 页号
,但是如果目标列的数据有很多是重复的,比如index_demo
表的数据内容如下:
c1 | c2 | c3 |
---|---|---|
1 | 1 | 'u' |
3 | 1 | 'd' |
5 | 1 | 'y' |
7 | 1 | 'a' |
如果二级索引中目录项记录的内容只是索引列 + 页号
的搭配的话,那么c2简历索引后的b+数,是这样的:
当再有一个新的记录并且他的c2值也为1,他是无法确定到底该插入到什么位置的。
为了解决这个问题,设计者在B+树内的同一个节点的目录项记录除页号这个字段以外又添加了主键作为唯一的标志,如下图:
目录页页3内容由三个部分构成:
索引列的列值
主键值
页号
一个页面中最少存储两条数据
一个B+树只需要很少的层级就可以轻松存储数亿条记录,查询速度很快。这是因为B+树本质上是一个大的多层目录,没经过一个目录时都会过滤掉许多无效的子目录,直到最后访问到存储真是数据的目录。如果一个大的目录只存放一个子目录,目录的层级会非常多,起不到减少IO次数的效果。
MyISAM的索引方案
B树索引适用存储引擎有:
索引/存储引擎 | MyISAM | InnoDB | Memory |
---|---|---|---|
B+Tree/B Tree | 支持 | 支持 | 支持 |
即使多个存储引擎支持同一种类型的索引,但是他们的实现原理也是不同的。Innodb和MyISAM默认的索引是Btree索引;而Memory默认的索引是Hash索引。
MyISAM使用B+Tree
作为索引结构,叶子节点的data存放的是数据记录的地址。
MyISAM索引原理
在MyISAM的数据目录中,MyISAM的索引和数据是分为两个文件存储的:
针对Col1
创建索引,将会生成如下B+Tree:
针对Col2
创建索引,将会生成如下B+Tree:
总结:
MyISAM没有聚簇索引
每为一个字段创建索引,都会生成一个新的B+Tree
他的叶子结点存储的是数据记录地址
索引的代价
空间上的代价
每建立一个索引都要为它建立一棵B+树,每一棵B+树的每一个节点都是一个数据页,一个页默认会占用 16KB 的存储空间,一棵很大的B+树由许多数据页组成,那就是很大的一片存储空间。
时间上的代价
每次对表中的数据进行 增、删、改 操作时,都需要去修改各个B+树索引。而且我们讲过,B+树每层节点都是按照索引列的值 从小到大的顺序排序 而组成了 双向链表 。不论是叶子节点中的记录,还是内节点中的记录(也就是不论是用户记录还是目录项记录)都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏,所以存储引擎需要额外的时间进行一些 记录移位 , 页面分裂 、 页面回收 等操作来维护好节点和记录的排序。如果我们建了许多索引,每个索引对应的B+树都要进行相关的维护操作,会给性能拖后腿。
索引数据结构的合理性
选择数据结构的主要指标是磁盘I/O的次数。如果我们能让索引的数据结构尽量减少硬盘的I/O操作,所消耗的时间也就越来越小。可以说磁盘IO对索引的使用效率至关重要。
数据库的索引都是存在磁盘上的,因为当数据量较大的时候,索引的大小也可能会很大,甚至有好几个G。当使用索引时,不能将整个索引全部加载到内存中,只能逐一加载,那么MySQL衡量查询的效率标准就是磁盘的IO次数。
全表遍历
极其低效
Hash结构
索引的分类
MySQL的索引可以如下分类:
从
功能逻辑
上说,索引主要有 4 种,分别是普通索引
、唯一索引
、主键索引
、全文索引
。按照
物理实现
方式 ,索引可以分为 2 种:聚簇索引
和非聚簇索引
。按照
作用字段个数
进行划分,分成单列索引
和联合索引
。
普通索引
在创建普通索引时,不附加任何限制条件,只是用于提高查询效率。这类索引可以创建在任何数据类型中,其值是否唯一、非空,要由字段本身的完整新约束条件决定。简历索引以后,可以通过索引进行查询。
唯一性索引
使用UNIQUE
参数可以设置索引为唯一性索引,在创建唯一性索引时,限制该索引必须是唯一的,但允许有空值。在一张数据表内可以有多个唯一索引。
主键索引
主键索引是一种特殊的唯一性索引,在唯一性索引的基础上增加了不为空的约束,也就是 NOT NULL
+ UNIQUE
,一张表里最多只有一个主键索引。
这是由主键索引的物理实现方式决定的,因为数据存储在文件中只能按照一种顺序进行存储。
单列索引
在表中的单个字段创建索引。单列索引只根据该字段进行索引。单列索引可以是普通索引,也可以是唯一性索引,还可以是全文索引。
联合索引
联合索引也成为多列索引,是表中多个字段组合创建的索引。该索引指向创建时对应的多个字段,可以通过这几个字段进行查询。但是,只有查询条件中使用了这些字段中的第一个字段时才会被使用。例如,在表中的字段id
、name
和gender
上建立一个多列索引。只有当查询条件中使用了id
字段时,该索引才会被使用,使用组合索引时遵循最左前缀集合
。
全文索引
全文索引是目前是搜索引擎使用的一种关键技术。他能够利用分词技术
等多种算法只能分析出文本文字中关键词的频率和重要性,然后按照一定的算法规则只能的筛选出我们想要的搜索结果。全文索引非常适合大型数据库,对于小的数据集,他的用处比较小。
使用参数FULL TEXT
可以设置索引为全文索引。在定义索引的列上支持全文查找,允许在这些索引列中插入重复值和空值。全文索引只能创建在CHAR
、VARCHAR
或TEXT
类型及其系列类型的字段上,查询数据量较大的字符串类型的字段时,使用全文索引可以提高查询速度。
全文索引分为两种类型:
自然语言全文索引
布尔全文索引:将计算每一个文档对象和查询的相关度。这里相关度是基于匹配的关键词个数,以及关键词在文档中出现的次数。在整个索引中出现次数越少的词语,匹配时相关度就越高。相反,非常常见的单词不会被搜索,如果一个词语在超过
50%
的记录中都出现了,那么自然语言的搜索将不会搜索这类词语。
MySQL数据库从3.23
版本开始支持全文索引,但是MySQL5.6.4
之前,只有MyISAM
支持,5.6.4
版本之后innodb
才开始支持,但是官方版本不支持中文成分词,需要第三方分词插件。在5.7.6
版本,mysql内置了ngram
全文解析器,用来支持亚洲语种的分词。测试或使用全文索引时,需要先确认Mysql的版本、存储引擎、数据类型是否支持全文索引。
随着大数据时代的到来,关系型数据库应对全文索引的需求已力不从心,逐渐被solr
、ElaasticSearch
等专门的搜索引擎锁替代。
空间索引
使用参数SPATIAL
可以设置空间索引。空间索引只能建立在空间数据类型上,这样可以提高系统获取空间数据的效率。MySQL的空间数据类型有:GEMETRY
、POINT
、LINESTRING
、POLYGON
等。目前只有MyISAM存储引擎支持空间索引,而且索引字段不可为空值。这类索引很少用到。
不同存储引擎对不同索引的支持
B-Tree | Full-Text | Hash | |
---|---|---|---|
InnoDB | √ | √ | × |
MyISAM | √ | √ | × |
Memory | √ | × | √ |
NDB | × | × | |
Archive | × | × | × |
使用索引
创建索引
创建表时创建索引
隐式的方式创建索引
声明主键约束时会自动创建索引
声明外键约束时会自动创建索引
声明唯一性约束时会自动创建索引
将会自动添加相关索引。
显式的方式创建索引:
UNIQUE
、FULLTEXT
、SPATIAL
是可选参数,表示唯一索引、全文索引与空间索引。INDEX
、KEY
两者作用相同,都用来创建索引。index_name
用来指定索引的名称。col_name
为需要创建索引的字段列,该列必须从数据表中定义的多个列中选择。length
可选参数,表示索引长度,只有字符串索引类型的字段才能指定索引长度。ASC
或DESC
指定圣墟或者降序的索引值存储。
创建普通索引
创建主键索引
创建唯一性索引
创建多列索引
创建全文索引
在已存在的表上创建索引
使用
ALTER
创建使用
CREARTE INDEX
查看索引
通过建表语句查看:
通过SHOW INDEX
查看:
删除索引
添加了
AUTO_INCREMENT
的主键索引不能被删除
ALTER TABLE ... DROP ..
DROP INDEX
联合索引
MySQL 索引新特性
降序索引
隐藏索引
索引的设计原则
准备数据
调用存储过程插入数据:
哪些情况适合创建索引
1. 字段的数值有唯一性限制
业务上具有唯一特性的字段,即使是组合字段,也必须建成唯一索引。(来源:Alibaba)
说明:不要以为唯一索引影响了 insert 速度,这个速度损耗可以忽略,但提高查找速度是明显的。
2. 频繁作为WHERE查询条件的字段
某个字段在SELECT语句的 WHERE 条件中经常被使用到,那么就需要给这个字段创建索引了。尤其是在数据量大的情况下,创建普通索引就可以大幅提升数据查询的效率。
3. 经常group by和order by的列
索引就是让数据按照某种顺序进行存储或检索,因此当我们使用GROUP BY
对数据进行分组查询,或者使用ORDER BY
对数据进行排序的时候,就需要 对分组或者排序的字段进行索引 。如果待排序的列有多个,那么可以在这些列上建立组合索引
。
4. UPDATE**、**DELETE 的 WHERE 条件列
对数据按照某个条件进行查询后再进行UPDATE
或DELETE
的操作,如果对 WHERE 字段创建了索引,就能大幅提升效率。原理是因为我们需要先根据 WHERE 条件列检索出来这条记录,然后再对它进行更新或删除。如果进行更新的时候,更新的字段是非索引字段,提升的效率会更明显,这是因为非索引字段更新不需要对索引进行维护。
5.DISTINCT 字段需要创建索引
有时候我们需要对某个字段进行去重,使用 DISTINCT,那么对这个字段创建索引,也会提升查询效率。
6. 多表 JOIN 连接操作时,创建索引注意事项
首先, 连接表的数量尽量不要超过 3 张 ,因为每增加一张表就相当于增加了一次嵌套的循环,数量级增长会非常快,严重影响查询的效率。
其次, 对
WHERE
条件创建索引 ,因为WHERE
才是对数据条件的过滤。如果在数据量非常大的情况下,没有 WHERE 条件过滤是非常可怕的。最后,对用于连接的字段创建索引 ,并且该字段在多张表中的 类型必须一致 。比如
course_id
在student_info
表和course
表中都为int(11)
类型,而不能一个为int
另一个为varchar
类型。
7. 使用列的类型小的创建索引
8. 使用字符串前缀创建索引
9. 区分度高(散列性高)的列适合作为索引
10. 使用最频繁的列放到联合索引的左侧
这样也可以较少的建立一些索引。同时,由于"最左前缀原则",可以增加联合索引的使用率。
11. 在多个字段都要创建索引的情况下,联合索引优于单值索引
哪儿些情况不适合创建索引
1. 在where中使用不到的字段,不要设置索引
2. 数据量小的表最好不要使用索引
3. 有大量重复数据的列上不要建立索引
4. 避免对经常更新的表创建过多的索引
5. 不建议用无序的值作为索引
6. 删除不再使用或者很少使用的索引
7. 不要定义冗余或重复的索引
最后更新于