索引是存储引擎用于快速查找记录的一种数据结构,我们可以通过合理的使用数据库索引以提高数据库的访问效率。接下来主要介绍在MySQL 数据库中索引类型,以及如何创建出更加合理且高效的索引技巧。
MySQL数据库的内部索引是由不同的存储引擎实现的,本文主要介绍一下 InnoDB存储引擎中的索引,InnoDB引擎中的索引是使用 B+树 的结构来存储的。
InnoDB引擎中的B+树结构
接下来我们看一下B+ 树结构,如下图:
首先,说一下B+ 树的特点:
叶子节点(即最下面的一层)存储关键字(索引字段的值)信息及对应的整行数据记录,即叶子节点存储了所有记录的关键字信息。
非叶子节点只存储关键字的信息及子节点的指针。
每个叶子节点相当于MySQL中的一个数据页,同层级的叶子节点以双向链表的形式相连。
每页中存储了多条记录,记录之间使用单链表连接组成了一条有序的链表,顺序是按照索引字段排序的。
B+ 树中查询数据时,每次查询都是从根节点开始,一直需要搜索到叶子节点。
MySQL中页是InnoDB引擎中存储数据的基本单位(块是文件系统操作的最小单位,扇区是磁盘操作的最小单位),数据是按数据页为单位来读写的,和磁盘交互的时候都是以页来进行的,每个页的大小默认是16kb。也就是说,当需要读取一条记录的时候,并不是将这个记录本身从磁盘读取出来,而是以页为单位,将整个也加载到内存中,一个页中可能有很多记录,然后在内存中对页通过二分法进行查询。
整体上来说MySQL中的索引用到了B+树,链表,二分法查找,做到了快速定位目标数据,快速范围查找。
InnoDB引擎中的索引类型
InnoDB引擎中有2种索引类型:主键索引(聚集索引)、辅助索引(非聚集索引)。
主键索引:每个表只有一个主键索引,叶子节点同时保存了主键的值以及对应记录的数据。
辅助索引:叶子节点保存了索引字段的值以及主键的值,与聚簇索引的区别在于辅助索引的叶子节点中存放的是主键索引的键值。
如下Person 表,id 作为主键索引,name 作为辅助索引。
结合如上图中 Person表,InnoDB引擎数据查询过程如下:
如果需要查询 id=1 的数据,只需要通过主键索引(聚集索引)中查询就可以了。
如果需要查询 name="Jacy" 的数据,需要使用非聚集索引与聚集索引,需要2步:
首先,通过辅助索引中查询 name="Jacy" 的数据,获取id的值为 12。
然后,根据id再到主键索引中查询 id=12 的数据记录。
如上,这个查询过程在MySQL中叫做 回表,下面我们会具体介绍回表。
聚集索引(主键索引)
聚集索引中键值的逻辑顺序决定了表中相应行的物理顺序(索引中的数据物理存放地址和索引的顺序是一致的),可以这么理解:只要是索引是连续的,那么数据在存储介质上的存储位置也是连续的。 比方说:想要到字典上查找一个字,我们可以根据字典前面的拼音找到该字,注意拼音的排列时有顺序的。
聚集索引就像我们根据拼音的顺序查字典类似,可以大大的提高效率。在经常搜索一定范围的值时,通过索引找到第一条数据,根据物理地址连续存储的特点,然后查询相邻的数据,直到到达条件截止项。
每个表一定会有一个聚集索引,整个表的数据存储以B+ 树的方式存在文件中,叶子节点中的key为主键值,data为完整的整行记录的信息,非叶子节点存储主键的值。
通过聚集索引查询数据只需要按照B+ 树的搜索过程,即可以查询到对应的记录。聚集索引按照如下规则创建:
当定义了主键后,InnoDB会利用主键来生成其聚集索引。
如果没有主键,InnoDB会选择第一个非空的唯一索引来创建聚集索引。
如果合适的非空的唯一索引,InnoDB会隐式的创建一个6个字节的自增的列来作为聚集索引,该列的值会随着数据的插入自增。
非聚集索引
索引的逻辑顺序与磁盘上的物理存储顺序不同。非聚集索引的键值在逻辑上也是连续的,但是表中的数据在存储介质上的物理顺序是不一致的,即记录的逻辑顺序和实际存储的物理顺序没有任何联系。索引的记录节点有一个数据指针指向真正的数据存储位置。
非聚集索引就像根据偏旁部首查字典一样,字典前面的目录在逻辑上也是连续的,但是查两个偏旁在目录上挨着的字时,字典中的字却很不可能是挨着的。
每个表可以有多个非聚集索引,B+ 树结构,叶子节点的key为索引字段的值,data为主键的值。非叶子节点只存储索引字段的值。
通过非聚集索引查询记录的时候,可能需要2次操作,先在非聚集索引中查询出主键,然后再到聚集索引中查询出主键对应的行记录,也就是进行两次 B+树查询。
InnoDB引擎中B+树的数据查询过程
我们在查询过程中,当使用多个索引时,InnoDB引擎使用的哪个索引,为什么有时候虽然使用了索引,但看执行计划却显示没有使用索引,这弄清楚这些之前。我们先看一下B+ 树查询数据的过程。
主键或唯一索引查询
如上图,所有的数据都是唯一的,我们查询 26 的记录,过程如下:
将Data page1页加载到内存,在内存中采用二分法查找。
确定26位于[20,40) 中间,然后再去加载20关联的 Data page3页。
将Data page3页加载到内存中,通过采用二分法找到26 的记录后退出。
非唯一索引查询
如上图,数据为并不是唯一的,我们查询26 的所有记录,过程如下:
将Data page1页加载到内存,在内存中通过二分法查找。
确定26位于 [20,40)中间,然后再去加载20关联的 Data page3 页。
将Data page3 页加载到内存中,通过二分法找到最后一个小于 26的记录,即 23,然后通过链表从23 开始向后访问,找到所有的26记录,直到遇到第一个大于26的值时停止。
范围查询
如上图,查询 [25,45] 所有记录,由于数据页之间是双向链表升序结构,页内部的数据是单项升序链表结构,所以只用找到范围的起始值所在的位置,然后通过依靠链表访问两个位置之间所有的数据即可,过程如下:
将Data page1 页加载到内存,在内存中通过二分法查找。
确定25位于 20关联的Data page3 页中,45位于40关联的Data page4 页中。
将Data page3 页加载到内存中,通过二分法找到第一个25的记录,然后通过链表结构继续向后访问Data page3页中的 26,当Data page3页访问完毕之后,通过Data page3页的nextpage指针访问下一页Data page4 页,同样加载到内存中,通过二分法查找所有小于45的记录。
模糊匹配查询
如上图,我们查询以 b 字母开头的所有记录,过程如下:
将Data page1 页数据加载到内存中。
通过二分法查找最后一个小于等于b 的值,即b,以及第一个大于b的,即z。b指向叶节点Data page3 页,z指向叶节点Data page5 页,确定以f开头的记录可能存在于[Data page3,Data page5)这个范围的页内,即Data page3、Data page4 这两页中。
依次加载Data page3 到内存中,通过二分法找到第一条b 开头的记录,然后以链表方式继续向后访问Data page4 页中的记录,即可以找到所有以 b 开头的记录。
当我们在SQL中使用LIKE %b%全模糊查询时,执行过程是什么样的呢?
如上图,b在每个页中都存在,我们通过Data page1 页中的记录是无法判断包含b的记录在哪些页的,只能加载所有叶子节点(页),然后遍历所有记录进行过滤,才可以找到包含b 的记录。所以如果使用了LIKE %b%全模糊查询,索引对查询是无效的。
复合索引的最左匹配原则
当B+ 树的数据项是复合的数据结构,比如(name,age,sex) 的时候,B+ 树是按照从左到右的顺序来建立搜索树的,比如当使用 (Tony, 20, 男) 查询时,B+ 树会优先比较 name 来确定下一步的查询方向,如果name 相同再依次比较 age 和sex ,最后得到查询的数据。
但使用(20, 男)这样的没有name的数据来查询的时候,B+ 树则不知道下一步该查哪个节点,因为建立搜索树的时候name 就是第一个索引字段,必须要先根据name 来搜索才能知道下一步去哪里查询。
比如当使用 (Tony, 男) 查询时,B+ 树可以用name 来指定搜索方向,但下一个字段age 的缺失,所以只能把名字等于Tony 的数据都找到,然后再匹配性别是男 的数据了, 即索引的最左匹配特性,如上图。
同时,在上图中,将 a, b, c 3个字段建立为复合索引(a,b,c),索引中数据的顺序是以a asc, b asc, c asc这种排序方式存储在节点中的,索引先以a字段升序,如果a相同的时候,再以b字段升序,b相同的时候,再以c字段升序。
我们分别看下,当使用以下字段进行查询时,查询过程是什么样子的。
查询 a=1 的记录
由于页中的记录是以a asc,b asc,c asc这种排序方式存储的,所以a字段是有序的,可以通过二分法快速查询到,过程如下:1.将Data page 1加载到内存中,通过二分法查找,可以确定a=1的记录位于{1,1,1}和{1,6,1}内,关联Data page2与Data page3 页。2.加载Data page 2 页到内存中,通过二分法快速找到第一条a=1的记录,然后通过链表向下一条及下一页Data page4 页进行查询,直到找到第一个不满足a=1的记录为止。查询 a=1 and b=6 的记录
首先可以确定a=1 and b=6的记录位于{1,6,1}内,关联Data page3 页并加载到内存中,后续查找过程和a=1 查找步骤类似。查询 c=1 的记录
这种情况通过Data page 1页中的记录,无法判断c=1的记录在哪些页中的,只能加载索引树所有叶子节点,对所有记录进行遍历,然后进行过滤,此时索引是无效的。查询 b=1 and c=1 的记录
同上,这种也无法利用索引,只能进行全表扫描,此时索引无效。查询 a=1 and c=1 的记录
这种只能利用到索引中的a字段,通过a 确定索引范围,然后加载a关联的所有记录,再对c的值进行判断过滤。查询 a=1 and b>=0 and c=1 的记录
这种情况只能先确定a=1 and b>=0所在页范围,然后对这个范围的所有页进行遍历,c字段在这个查询的过程中,是无法确定c的数据在哪些页的,此时c的索引失效,只有a、b能够有效的确定索引页的范围。
总结,对于复合索引失效的可能原因有以下几点:
复合索引的生效原则是从前往后依次使用生效,如果中间某个索引没有使用,那么仅断点前面的索引部分起作用,断点后面的索引不起作用,造成断点的原因一般有:
前边的任意一个索引没有参与查询,后面的不生效。
前边的任意一个索引失效,当前索引及后面全部不生效。
前边的任意一个索引字段参与的是范围查询(>、<、between),后面的不生效。
索引区分度
如上图,上面是两个有序的数组,都是10条记录,如果我们需要查询值为6 的所有记录,查询这两个数组哪个更快一些?
我们使用二分法查找包含6 的所有记录过程如下:先使用二分法找到最后一个小于6的记录,然后从这条记录向后获取下一个记录,依次与6 比较,直到遇到第一个大于6 的数字结束,或者到达数组末尾结束,通过这种方法找到6 的记录,第一个数组的查询更快的一些。因为第二个数组中含有6的比例更多的,需要访问以及匹配的次数更多一些。
这里涉及数据的区分度问题:索引区分度 = count(distint 字段) / count(字段)。
当索引区分度高的时候,查询数据要更快一些。当索引区分度太低,说明重复的数据比较多,查询的时候基本上接近于全索引数据的扫描了,此时查询速度是比较慢的。
如上图中,第一个数组的索引区分度为 0.9,第二个数组的索引区分度为0.2,所以第一个有序数组的查询效率更快一些。
结合实例理解索引的正确使用方式
为了更好地理解上述内容,我们以如下测试数据 nickname_information 表为例,其包含编号、姓名、性别、昵称 4个字段,其中除性别字段存在重复值,其余各字段均不重复,共300万条测试数据。
包含多个索引时,查询如何选择?
我们在name、sex 两个字段上分别创建索引 idx_name,idx_sex,如下:
查询姓名为testops1000001 并且性别为女的所有信息:
我么可以看到执行之间不到1ms,name与sex都是索引字段,那么实际执行时使用的是哪个索引?
我们或许会说是根据WHERE 子句后的索引字段顺序,name 位于WHERE 第一个,所以走的是name字段所在的索引?执行过程如下:
首先,根据name 所在的索引找到testops1000001 对应的主键索引。
然后,根据主键索引查询所有数据记录。
最后,遍历所有数据记录过滤出sex=1 的值。
我们看一下 name="testops1000001" 查询速度,如下:
那么索引的选择真的与WHERE子句的索引字段顺序有关么?我们把name 和sex 的顺序对调一下,如下:
查询速度仍然很快,这次是不是先通过sex 索引查询出数据,然后再过滤name 呢?我们再来看一下sex=1查询速度:
看上面,查询耗时220毫秒,150万数据,因此,肯定不是使用的sex 的索引。我们使用 explain来看一下SQL执行计划。
我们通过执行计划,可以看到该SQL中可能使用的索引(possible_keys)包含idx_name,idx_sex ,但实际使用的索引(key)是idx_name。
因此,当WHERE子句中包含多个索引字段并且关系是 AND 时,会使用索引区分度高的索引字段,如上例子中,显然name 字段不存在重复度,并且age 字段的重复度很高,因此会使用name 查询会更快一些。
模糊查询
如上两个SQL查询语句,第一个使用后模糊查询("testops1000%"),第二个使用全模糊查询(%testops1000%")。
第一个SQL语句可以利用到name 字段上面的索引,第二个SQL语句因无法确定需要查找的值所在的范围的,只能全表扫描,无法利用索引,所以速度比较慢。
WHERE 子句中使用 LIKE 进行模糊查询时,在关键词前加通配符或者前后都加通配号都无法使用索引,从而引发全表扫描。解决LIKE "%abc%" 时索引不被使用的方法就是添加覆盖索引(只访问索引的查询,索引和查询列一致,只需扫描索引而无须回表)。
回表
当需要查询的字段在索引树中不存在时(非索引字段),需要再次到聚集索引中去获取,这个过程叫做回表,如查询: