前言
大家都知道 MySQL 的数据都是保存在磁盘的,那具体是保存在哪个文件呢?MySQL 存储的行为是由存储引擎实现的,MySQL 支持多种存储引擎,不同的存储引擎保存的文件自然也不同。InnoDB 是我们常用的存储引擎,也是 MySQL 默认的存储引擎。本文主要以 InnoDB 存储引擎展开讨论。InnoDB简介
InnoDB是一个将表中的数据存储到磁盘上的存储引擎。而真正处理数据的过程是发生在内存中的,所以需要把磁盘中的数据加载到内存中,如果是处理写入或修改请求的话,还需要把内存中的内容刷新到磁盘上。而我们知道读写磁盘的速度非常慢,和内存读写差了几个数量级。所以当我们想从表中获取某些记录时,InnoDB存储引擎需要一条一条的把记录从磁盘上读出来么?想要了解这个问题,我们首先需要了解InnoDB的存储结构是怎样的。InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位innodb_page_size选项指定了MySQL实例的所有InnoDB表空间的页面大小。这个值是在创建实例时设置的,之后保持不变。有效值为64KB,32KB,16KB(默认值 ),8kB和4kB。也就是在一般情况下,一次最少从磁盘中读取16KB的内容到内存中,一次最少把内存中的16KB内容刷新到磁盘中。InnoDB行格式
我们平时是以记录为单位来向表中插入数据的,这些记录在磁盘上的存放方式也被称为行格式或者记录格式。一行记录可以以不同的格式存在InnoDB中,行格式分别是compact、redundant、dynamic和compressed行格式。可以在创建或修改的语句中指定行格式:mysql5.0之前默认的行格式是redundant,mysql5.0之后的默认行格式为compact , 5.7之后的默认行格式为dynamic-- 创建数据表时,显示指定行格式
CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称;
-- 创建数据表时,修改行格式
ALTER TABLE 表名 ROW_FORMAT=行格式名称;
-- 查看数据表的行格式
show table status like '<数据表名>';
变长字段长度列表中只存储值为 非NULL 的列内容占用的长度,值为 NULL 的列的长度是不储存的 。
并不是所有记录都有这个 变长字段长度列表 部分,比方说表中所有的列都不是变长的数据类型的话,这一部分就不需要有
首先统计表中允许存储NULL的列有哪些。
根据列的实际值,用0或者1填充NULL值列表,1代表该列的值为空,0代表该列的值不为空。
如果表中没有允许存储 NULL 的列,则 NULL值列表 也不存在了。
名称 | 大小(单位:bit) | 描述 |
预留位1 | 1 | 未使用 |
预留位2 | 1 | 未使用 |
delete_mask | 1 | 标记改记录是否被删除 |
min_rec_mask | 1 | B+树非叶子节点中最小记录都会添加该标记 |
n_owned | 4 | 当前记录拥有的记录数 |
heap_no | 13 | 当前记录在记录堆的位置信息 |
record_type | 3 | 记录类型 0:普通记录 1:B+树非叶子节点记录2:最小记录3:最大记录 |
next_record | 16 | 下一条记录的相对位置 |
InnoDB数据页结构
数据页代表的这块16KB大小的存储空间可以被划分为多个部分,不同部分有不同的功能名称 | 中文名 | 大小 | 描述 |
File Header | 文件头部 | 38字节 | 页通用信息 |
Page Header | 页面头部 | 56字节 | 页专有信息 |
infimun + supermun | 最小记录和最大记录 | 26字节 | 虚拟的行记录 |
User Rcords | 用户记录 | 不确定 | 实际存储的行记录内容 |
Free Space | 空闲空间 | 不确定 | 页中未使用的空间 |
Page Directory | 页面目录 | 不确定 | 页中一些记录的相对位置 |
File Tariler | 文件尾部 | 8字节 | 校验页的完整性 |
这些记录,就如下图所示,存储在User Rcords里先创建一个表:
CREATE TABLE test(
a1 INT,
a2 INT,
a3 VARCHAR(100),
PRIMARY KEY (a1)
) CHARSET=ascii ROW_FORMAT=Compact;
test表中插入几条记录:
INSERT INTO test VALUES(1, 10, 'aaa');
INSERT INTO test VALUES(2, 20, 'bbb');
INSERT INTO test VALUES(3, 30, 'ccc');
INSERT INTO test VALUES(4, 40, 'ddd');
delete_mask这个属性标记着当前记录是否被删除。这些被删除的记录之所以不立即从磁盘上移除,是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗,所以只是打一个删除标记而已。所有被删除掉的记录都会组成一个所谓的垃圾链表,在这个链表中的记录占用的空间称之为所谓的可重用空间,之后如果有新记录插入到表中的话,可能把这些被删除的记录占用的存储空间覆盖掉。
min_rec_maskB+树的每层非叶子节点中的最小记录都会添加该标记,min_rec_mask值都是0,意味着它们都不是B+树的非叶子节点中的最小记录。
n_owned在页目录分组时使用,每个组的最后一条记录(也就是组内最大的那条记录)的头信息中的n_owned属性表示该记录拥有多少条记录,也就是该组内共有几条记录。
heap_no这个属性表示当前记录在本页中的位置,从图中可以看出来,我们插入的4条记录在本页中的位置分别是:2、3、4、5。heap_no值为0和1的记录,称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录,一个代表最大记录。
record_type这个属性表示当前记录的类型,一共有4种类型的记录,0表示普通记录,1表示B+树非叶节点记录,2表示最小记录,3表示最大记录。
next_record它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。比方说第一条记录的next_record值为32,意味着从第一条记录的真实数据的地址处向后找32个字节便是下一条记录的真实数据。下一条记录指得并不是按照我们插入顺序的下一条记录,而是按照主键值由小到大的顺序的下一条记录。而且规定Infimum记录(也就是最小记录) 的下一条记录就是本页中主键值最小的用户记录,而本页中主键值最大的用户记录的下一条记录就是 Supremum记录(也就是最大记录)。
Page Directory(页目录)
现在我们了解了记录在页中按照主键值由小到大顺序串联成一个单链表,单向链表的特点就是插入、删除非常方便,但是检索效率不高,最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块,专门给记录做一个目录,通过二分查找法的方式进行检索,提升效率。1:将所有正常的记录(包括最大和最小记录,不包括标记为已删除的记录)划分为几个组。2:每个组的最后一条记录(也就是组内最大的那条记录)的头信息中的n_owned属性表示该记录拥有多少条记录,也就是该组内共有几条记录。3:将每个组的最后一条记录的地址偏移量单独提取出来,用作查找。注意:这个页目录是为主键服务的。需要注意的是:第一:第一个小组,也就是最小记录所在的分组只能有1个记录;第二:最后一个小组,就是最大记录所在的分组,只能有1-8条记录;第三:剩下的分组中记录的条数范围只能在是 4-8 条之间;分组是按照下边的步骤进行:初始情况下一个数据页里只有最小记录和最大记录两条记录,它们分属于两个分组。
之后每插入一条记录,都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽,然后把该槽对应的记录的n_owned值加1,表示本组内又添加了一条记录,直到该组中的记录数等于8个。
在一个组中的记录数等于8个后再插入一条记录时,会将组中的记录拆分成两个组,一个组中4条记录,另一个5条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。
INSERT INTO test VALUES(5, 50, 'eee');
INSERT INTO test VALUES(6, 60, 'fff');
INSERT INTO test VALUES(7, 70, 'ggg');
INSERT INTO test VALUES(8, 80, 'hhh');
INSERT INTO test VALUES(9, 90, 'iii');
INSERT INTO test VALUES(10, 100, 'jjj');
INSERT INTO test VALUES(11, 110, 'kkk');
INSERT INTO test VALUES(12, 120, 'lll');
这里为了便于理解,图中只保留了用户记录头信息中的n_owned和next_record属性。
因为各个槽代表的记录的主键值都是从小到大排序的,所以我们可以使用二分法来进行快速查找。
所以在一个数据页中查找指定主键值的记录的过程分为两步:
1.通过二分法确定该记录所在的槽,并找到该槽所在分组中主键值最大的那条记录。2.通过记录的next_record属性遍历该槽所在的组中的各个记录。
比方说我们查找主键值为x的记录,计算中间槽的位置(min+max)/2 =mid,查看mid槽对应的主键值y,若x<y,则min不变,max=mid,若x>y,则max不变,min=mid。依此类推。
举例:我们想找主键值为6的记录,过程是这样的计算中间槽的位置:(0+3)/2=1,所以查看槽1对应记录的主键值为4,因为4 < 6,所以设置low=1,high保持不变。因为high - low的值为1,所以确定主键值为6的记录在槽2对应的组中。我们可以很轻易的拿到槽1对应的记录(主键值为4),该条记录的下一条记录就是槽2中主键值最小的记录,该记录的主键值为5。所以我们可以从这条主键值为5的记录出发,遍历槽2中的各条记录找到主键为6 的数据。
注意:若查到数据在槽2的分组中,由于槽2是指向最后一个记录,所以需要向上找一个槽位,定位到上一个槽位最后一行,然后再向下找。
File Header(文件头部)
B+树索引
InnoDB数据页的主要组成部分。各个数据页可以组成一个双向链表,而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表,每个数据页都会为存储在它里边儿的记录生成一个页目录。再通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽。在一个页中的查找:以主键为搜索条件这个查找过程我们已经很熟悉了,可以在页目录中使用二分法快速定位到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件对非主键列的查找的过程可就不这么幸运了,因为在数据页中并没有对非主键列建立所谓的页目录,所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录,然后对比每条记录是不是符合搜索条件。
1:定位到记录所在的页。
2:从所在的页内中查找相应的记录。在没有索引的情况下,不论是根据主键列或者其他列的值进行查找,由于我们并不能快速的定位到记录所在的页,所以只能从第一个页沿着双向链表一直往下找,在每一个页中根据我们上面聊过的查找方式去查找指定的记录。
索引
此时我们再来插入一条记录:test表中插入几条记录:
INSERT INTO test VALUES(1, 10, 'aa');
INSERT INTO test VALUES(2, 20, 'bb');
INSERT INTO test VALUES(4, 40, 'dd');
INSERT INTO test VALUES(3, 30, 'cc');
因为上面定义了,一个页最多只能放3条记录,所以我们不得不再分配一个新页:页1中用户记录最大的主键值是4,而页2中有一条记录的主键值是3,因为4 > 3,所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求,所以在插入主键值为3的记录的时候需要伴随着一次记录移动,也就是把主键值为4的记录移动到页2中,然后再把主键值为3的记录插入到页1中。最后形成如图所示。这个过程叫做页分裂。真实数据存储中,数据页的编号并不是连续的,当我们在test表中插入多条记录后,可能是这样的效果:因为这些16KB的页在物理存储上可能并不挨着,所以如果想从这么多页中根据主键值快速定位某些记录所在的页,我们需要给它们做个目录,每个页对应一个目录项,每个目录项由页中记录的最小主键值和页号组成。我们为上面几个页做目录,则如图:比方说我们想找主键值为5的记录,具体查找过程分两步:
1:先从目录项中根据二分法快速确定出主键值为5的记录在目录2中(因为 4 < 5 < 7),它对应的数据页是页23。
2:再根据前边说的在页中查找记录的方式去页23中定位具体的记录。这个目录有一个别名,称为索引。InnoDB中的索引方案
聚簇索引
1:使用记录主键值的大小进行记录和页的排序
2:B+树的叶子节点存储的是完整的用户记录。我们把具有这两种特性的B+树称为聚簇索引,所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建,InnoDB存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是,在InnoDB存储引擎中,聚簇索引就是数据的存储方式(所有的用户记录都存储在了叶子节点),也就是所谓的索引即数据,数据即索引。二级索引
使用记录a2列的大小进行记录和页的排序
页内的记录是按照a2列的大小顺序排成一个单向链表。
各个存放用户记录的页也是根据页中记录的a2列大小顺序排成一个双向链表。
存放目录项记录的页分为不同的层次,在同一层次中的页也是根据页中目录项记录的a2列大小顺序排成一个双向链表。
B+树的叶子节点存储的并不是完整的用户记录,而只是a2列+主键这两个列的值。
目录项记录中不再是主键+页号的搭配,而变成了a2列+页号的搭配。
索引的代价
1:空间上的代价每建立一个索引都要为它建立一棵B+树,每一棵B+树的每一个节点都是一个数据页,一个页默认会占用16KB的存储空间。
2:时间上的代价每次对表中的数据进行增、删、改操作时,都需要去修改各个B+树索引。B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录,还是内节点中的记录(也就是不论是用户记录还是目录项记录)都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏,所以存储引擎需要额外的时间进行一些记录移位,页面分裂、页面回收等操作来维护好节点和记录的排序。总结
通过对InnoDB存储逻辑分析,我们可以清楚的了解到mysql中是怎样对数据进行存储的。并且对索引树的结构进行分析,帮助我们在工作中更加合理的使用索引。