xyZGHio

本是青灯不归客,却因浊酒恋风尘

0%

MySQL之InnoDB存储引擎:索引

索引一直是MySQL的重点内容,这里主要介绍下InnoDB引擎下索引的结构

abstract.png

聚簇索引

在InnoDB存储引擎中,虽然一个数据页内各记录之间的关系是一个单向链表,但由于有Page Directory页目录的存在。故如果在一个数据页内根据主键查找某个记录的话,就可利用Page Directory页目录进行二分查找来缩小遍历范围、提高查找效率。(当然如果在数据页内不是使用主键来查找记录的话,Page Directory页目录就爱莫能助了,只能从头来遍历该数据页内的记录链表)

而就各数据页的关系而言,则是一个双向链表。那么问题来了,在根据主键查找记录的过程中如何先找到记录所在的某个数据页?显然如果依靠遍历这个数据页的链表来实现的话,效率会非常非常低。由此可见,我们同样需要为各数据页来建立一个目录,即所谓的索引。具体地,我们通过一个例子来展示

figure 1.jpeg

首先,根据上图我们可以看到记录数据的数据页有5号页、8号页、3号页、7号页。这里处于简洁的考虑,对于记录我们只画了记录的数据内容部分,其中红色的字段为主键,可以看到各数据页内部是一个按记录大小从小到大排序的单向记录链表,而在各数据页之间则是双向链表的关系(这里我们假设每个数据页只能存放下3条用户记录)。为了能够根据记录主键快速定位到上述四个数据页其中的某一个,我们建立了两个数据页:25号页、29号页。在这两个数据页中存放的记录,我们称之为目录项记录(这里同样为了便于画图我们假设每个数据页只能存放下3条目录项记录)

  1. 对于这个目录项记录而言,可以看到其数据内容部分有两个字段,分别为所指向页的记录最小主键值、所指向的页号,即主键值+页号。其表示了其所指向的数据页的记录主键值的下限
  2. 对于存放目录项记录的数据页而言,其内部依然是一个按主键值从小到大排序的单向链表
  3. 对于同一层中存放目录项记录的各数据页(即这里的25号页、29号页)而言,同样亦是一个按页内目录项记录主键值从小到大排序的双向链表

由于有了25号页的存在,我们就可以根据所查记录的主键来快速判定相应的记录是在5号页、8号页、还是3号页当中了。例如期望查找一个主键为18的记录,我们可先利用25号页的Page Directory页目录进行二分查找来缩小遍历目录项记录链表的范围,从而快速定位到 11,5 这条目录项记录(因为下一条目录项记录表示其所指向的数据页记录主键下限是21,而我们所查找的主键为18),然后根据这条目录项记录的页号值即可快速定位到5号数据页中了,剩下的就是数据页内的查找,这个前面已经讲了很多次,此处就不再赘述了 。29号页的作用同理。这里由于数据量不大,在这一层次中,我们只需两个数据页——25号页、29号页即可。事实上在日常使用中,同一层中通常往往有很多个数据页。那么问题就来了,如何根据所查记录的主键快速判定是在25号页、还是29号页中呢?聪明的朋友可能已经想到了,我们可以使用同样的方法对25号页、29号页再建立一个数据页——即上图的24号页

事实上,上图即是一个B+树 。对于这棵树而言,其非叶子节点(24号页、25号页、29号页)即是所谓的索引,其作用最终都是用于快速定位到该树下的某个叶子节点;而叶子节点(5号页、8号页、3号页、7号页)则是存储了我们用户存放到InnoDB中的数据。所以在InnoDB下,数据即索引、索引即数据,故数据页有时又被称作为索引页

可以看到,在上图的例子中,我们一方面使用用户记录的主键来建立索引;另一方面通过叶子节点实现了对用户记录数据的存储(含隐藏列),故我们称其为聚簇索引。在InnoDB中,聚簇索引是InnoDB存储引擎自动建立的,不需要我们通过SQL语句显式地创建

Note

  1. 我们可以看到在聚簇索引中,对于 B+树下同一层中的各数据页之间的双向链表、数据页内的各记录(目录项记录或用户记录)之间的单向链表 均是按照主键从小到大的顺序进行链接的。为此,InnoDB存储引擎需要通过页面分裂、记录移位等方式来维护上述各个链表的顺序关系。所以,一般地推荐使用单增变化的主键(比如使用AUTO_INCREMENT修饰),而不是使用随机变化的主键(比如UUID),以避免造成性能上大量的不必要的的损耗

  2. 对于MySQL的MyISAM存储引擎而言,数据(即用户记录)和索引是分开存储的。前者在被添加上行号信息后存储到数据文件中,后者则是被存储到索引文件中。即数据是数据、索引是索引。在使用索引的过程中,先通过索引文件获取相应用户记录的行号,然后再在数据文件中通过行号来获取相应的用户记录。故在MyISA存储引擎中,索引均是二级索引,即继续进行回表操作

二级索引

在聚簇索引中,其可以大大提高根据主键查找记录的效率。但如果用户不是使用主键进行查找的话,是不是就只能靠遍历存放记录的各数据页链表来进行查找了呢?答案显然不是,我们还可以显式地为某个非主键字段来建立一颗新的B+树,即所谓的二级索引

下面即是我们对char类型字段建立的一颗B+树,其示意图如下所示

figure 2.jpeg

由于是对char类型字段建立的索引,故可以从上图看到同一层中的各数据页之间、数据页内的各记录之间均是使用建立索引的字段值(即这里的char类型字段)来进行排序的。与此同时,其与聚簇索引还有两个主要的不同点

  1. 对于非叶子节点(31号页、33号页、36号页)而言,其下的目录项记录的数据内容部分是指定建立索引的字段值+主键值+页号。值得一提的是,乍一看好像不需要在非叶子节点存储用户记录的主键值。但由于是对非主键字段建立的索引,该字段值可能会重复。故如果数据内容部分只有建立索引的字段值+页号的话,仅仅通过建立索引的字段值列,是无法保证目录项记录的唯一性。试想假设在36号页中不是一条目录项记录,而是“yes”,21,2、“zoo”,46,11、“zoo”,50,13 这三条目录项记录的话。当我们新添加一条为56,“zoo”的用户记录,在需要向该树相应叶子节点插入索引时,会无法在36号页中确定唯一的目录项记录,即是在11号页插入还是在13号页中插入新的索引呢。故对于二级索引而言,当索引字段的值均相同时,则继续按主键值进行排序
  2. 对于叶子节点而言,其中记录的数据内容只会存储指定建立索引的字段值+主键值,而不是直接存储相应的完整的用户记录。此举是为了避免重复存储用户记录、浪费空间。因为在聚簇索引中我们已经看到用户记录被完整的存储到了叶子节点中。故在二级索引只是存储了相应用户记录的主键值。即然可以通过二级索引的叶子节点获取到所查记录相应的主键值,那么聪明的小伙伴可能已经猜到该如何利用该主键值找到最终我们需要的用户记录了。没错,通过聚簇索引即可实现,这一过程即为所谓的回表。这也是被称之为二级索引的缘由

Note

  1. 由于例子中完整用户记录的数据内容部分也只有两个字段:主键、char类型字段。所以这里的二级索引的示意图下,叶子节点中看上去好像是存储了用户记录的全部字段。这里为了避免产生此种误解,故特此强调下。至少这里也没有存储记录隐藏列的数据啊,所以还是需要进行回表操作
  2. 假设我们期望查找该字段值为car的记录时,使用二级索引进行查找记录的过程如下:首先,通过B+树的根节点31号页找到33号页,然后在33号页中,可以判定出6号页是肯定有所需记录。但是需要注意的是由于非主键字段具备可重复性,故9号页也是有可能有所需记录的;所以需要分别通过6号页、9号页获取相应主键值并进行回表

联合索引

前面我们提到的二级索引是使用一个非主键的字段来建立索引的。那么是否可以同时使用多个字段来建立一个索引呢?答案当然是可以的。假设我们以f1、f2、f3字段来建立一个索引,即所谓的联合索引。对于联合索引而言,其与上文使用一个字段建立的二级索引基本是一致的,其会依次使用f1、f2、f3字段的排序规则 来对 同一层的各数据页之间、数据页内的各记录之间的链表进行排序。具体地,即先使用f1字段进行排序,在f1字段相同的情况下再使用f2字段进行排序,f3字段同理

当然对于联合索引的B+树而言,非叶子节点下的目录项记录的数据内容依然还是指定建立索引的各字段值+主键值+页号,叶子节点下记录的数据内容依然还是指定建立索引的各字段值+主键值。故其实联合索引本质上依然是一个二级索引,其同样需要进行回表操作

Note

  1. 对f1、f2、f3字段建立联合索引 与 对f1、f2、f3字段分别建立二级索引含义 是完全不同的,前者只会建立一颗B+树,而后者则会建立三颗B+树
  2. 无论是聚簇索引还是二级索引(含联合索引),它们的B+树中根节点的页号一旦建立后就不会发生改变,所以InnoDB只需保存B+树中根节点的页号就可以找到该树了

二级索引的基本操作

前面我们说了,InnoDB存储引擎会帮我们自动建立聚簇索引。故这里来介绍二级索引(含联合索引)的基本操作

1. 创建表时建立索引

通过下面的SQL语句实现在创建表时一并建立索引。当需建立联合索引时,各字段名之间使用,逗号分隔。其中,KEY与INDEX作用相同,任选其一即可

1
2
3
4
CREATE TALBE 表名 (
各字段的信息,
[ {KEY|INDEX} 索引名 (需建立索引的单个字段名或多个字段名) ]
)

2. 修改表以添加索引

对于已存在的表,可以通过ALTER语句实现添加索引

1
ALTER TABLE 表名 ADD {KEY|INDEX} 索引名 (需建立索引的单个字段名或多个字段名);

3. 修改表以删除索引

删除表的索引可通过下面SQL语句实现

1
ALTER TABLE 表名 DROP {KEY|INDEX} 索引名;
请我喝杯咖啡捏~

欢迎关注我的微信公众号:青灯抽丝