MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

时间:2023-12-31 18:52:20

以下内容来自掘金小册 MySQL 是怎样运行的:从根儿上理解 MySQL

版权归原作者所有!

InnoDB数据页结构

  1. InnoDB为了不同的目的而设计了不同类型的页,我们把用于存放记录的页叫做数据页

  2. 一个数据页可以被大致划分为7个部分,分别是

  • File Header,表示页的一些通用信息,占固定的38字节。
  • Page Header,表示数据页专有的一些信息,占固定的56个字节。
  • Infimum + Supremum,两个虚拟的伪记录,分别表示页中的最小和最大记录,占固定的26个字节。
  • User Records:真实存储我们插入的记录的部分,大小不固定。
  • Free Space:页中尚未使用的部分,大小不确定。
  • Page Directory:页中的某些记录相对位置,也就是各个槽在页面中的地址偏移量,大小不固定,插入的记录越多,这个部分占用的空间越多。
  • File Trailer:用于检验页是否完整的部分,占用固定的8个字节。
  1. 每个记录的头信息中都有一个next_record属性,从而使页中的所有记录串联成一个单链表

  2. InnoDB会为把页中的记录划分为若干个组,每个组的最后一个记录的地址偏移量作为一个,存放在Page Directory中,所以在一个页中根据主键查找记录是非常快的,分为两步:

  • 通过二分法确定该记录所在的槽。
  • 通过记录的next_record属性遍历该槽所在的组中的各个记录。
  1. 每个数据页的File Header部分都有上一个和下一个页的编号,所以所有的数据页会组成一个双链表

  2. 为保证从内存中同步到磁盘的页的完整性,在页的首部和尾部都会存储页中数据的校验和和页面最后修改时对应的LSN值,如果首部和尾部的校验和和LSN值校验不成功的话,就说明同步过程出现了问题。

InnoDB记录结构

  1. 页是MySQL中磁盘和内存交互的基本单位,也是MySQL是管理存储空间的基本单位。

  2. 指定和修改行格式的语法如下:

    CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称
    
    ALTER TABLE 表名 ROW_FORMAT=行格式名称
  3. InnoDB目前定义了4种行格式

COMPACT行格式

具体组成如图:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

Redundant行格式

具体组成如图:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

Dynamic和Compressed行格式

这两种行格式类似于COMPACT行格式,只不过在处理行溢出数据时有点儿分歧,它们不会在记录的真实数据处存储字符串的前768个字节,而是把所有的字节都存储到其他页面中,只在记录的真实数据处存储其他页面的地址。

另外,Compressed行格式会采用压缩算法对页面进行压缩。

一个页一般是16KB,当记录中的数据太多,当前页放不下的时候,会把多余的数据存储到其他页中,这种现象称为行溢出

B+树索引

  • 每个索引都对应一棵B+树,B+树分为好多层,最下边一层是叶子节点,其余的是内节点。所有用户记录都存储在B+树的叶子节点,所有目录项记录都存储在内节点。
  • InnoDB存储引擎会自动为主键(如果没有它会自动帮我们添加)建立聚簇索引,聚簇索引的叶子节点包含完整的用户记录。
  • 我们可以为自己感兴趣的列建立二级索引二级索引的叶子节点包含的用户记录由索引列 + 主键组成,所以如果想通过二级索引来查找完整的用户记录的话,需要通过回表操作,也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。
  • B+树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表,而且每个页内的记录(不论是用户记录还是目录项记录)都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话,则页面和记录先按照联合索引前边的列排序,如果该列值相同,再按照联合索引后边的列排序。
  • 通过索引查找记录是从B+树的根节点开始,一层一层向下搜索。由于每个页面都按照索引列的值建立了Page Directory(页目录),所以在这些页面中的查找非常

首先我们需要知道在innoDB中一条记录的格式:

将记录格式的其他信息去掉并把它竖起来的效果就是这样

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

把一些记录放到页里边的示意图就是:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

注意record_type的取值不同,代表着该条记录有不同的含义:

一个页面里面里的记录通过next_record指针串成一个链表,为了查找方便,为这个链表设置了两个虚拟头节点: 最小记录和最大记录:

record_type = 1表示是最小记录,record_type = 3表示是最大记录。

record_type = 0表示是普通用户记录。

record_type = 2表示是索引项目记录。这个后面再说。

页分裂

假设我们的每个数据页最多能存放3条记录(实际上一个数据页非常大,可以存放下好多记录),innoDB在插入数据项的时候,会按照主键值的大小顺序串联成一个单向链表:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

上图中的三条记录按照主键(橙色)由小到大的顺序串成一个链表

此时我们再插入一条记录,因为页10最多只能放3条记录,所以我们不得不再分配一个新页:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

页10中用户记录最大的主键值是5,而页28中有一条记录的主键值是4,因为5 > 4,所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求,所以在插入主键值为4的记录的时候需要伴随着一次记录移动,也就是把主键值为5的记录移动到页28中,然后再把主键值为4的记录插入到页10中。我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立:下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂

 B+树索引在空间和时间上都有代价,所以没事儿别瞎建索引。B+树索引适用于下边这些情况:

  • 全值匹配
  • 匹配左边的列
  • 匹配范围值
  • 精确匹配某一列并范围匹配另外一列
  • 用于排序
  • 用于分组

在使用索引时需要注意下边这些事项:

  • 只为用于搜索、排序或分组的列创建索引
  • 为列的基数大的列创建索引
  • 索引列的类型尽量小
  • 可以只对字符串值的前缀建立索引
  • 只有索引列在比较表达式中单独出现才可以适用索引
  • 为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况,建议让主键拥有AUTO_INCREMENT属性。
  • 定位并删除表中的重复和冗余索引
  • 尽量使用覆盖索引进行查询,避免回表带来的性能损耗。

其他的部分见掘金小册!

表空间

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

单表访问方法

访问方法(access method)

两大类

  • 使用全表扫描进行查询
  • 使用索引进行查询

六小类:

const、ref、ref_or_null、range、index、all

const

通过主键或者唯一二级索引列(即该索引列是像主键一样是不含重复值的)与常数的等值比较来定位一条记录是像坐火箭一样快的,所以他们把这种通过主键或者唯一二级索引列来定位一条记录的访问方法定义为:const,意思是常数级别的,代价是可以忽略不计的。不过这种const访问方法只能在主键列或者唯一二级索引列和一个常数进行等值比较时才有效,如果主键或者唯一二级索引是由多个列构成的话,索引中的每一个列都需要与常数进行等值比较,这个const访问方法才有效(这是因为只有该索引中全部列都采用等值比较才可以定位唯一的一条记录)。

对于唯一二级索引来说,查询该列为NULL值的情况比较特殊,比如这样:

SELECT * FROM single_table WHERE key2 IS NULL;

因为唯一二级索引列并不限制 NULL 值的数量,所以上述语句可能访问到多条记录,也就是说 上边这个语句不可以使用const访问方法来执行。

ref

先使用二级索引找到对应记录的id值,然后再回表到聚簇索引中查找完整的用户记录,采用二级索引来执行查询的访问方法称为:ref

对于普通的二级索引来说,通过索引列进行等值比较后可能匹配到多条连续的记录,而不是像主键或者唯一二级索引那样最多只能匹配1条记录,所以这种ref访问方法比const差了那么一丢丢,但是在二级索引等值比较时匹配的记录数较少时的效率还是很高的(如果匹配的二级索引记录太多那么回表的成本就太大了)

注意下边两种情况:

  • 二级索引列值为NULL的情况

不论是普通的二级索引,还是唯一二级索引,它们的索引列对包含NULL值的数量并不限制,所以我们采用key IS NULL这种形式的搜索条件最多只能使用ref的访问方法,而不是const的访问方法。

  • 不论是普通的二级索引,还是唯一二级索引,它们的索引列对包含NULL值的数量并不限制,所以我们采用key IS NULL这种形式的搜索条件最多只能使用ref的访问方法,而不是const的访问方法。

ref_or_null

有时候我们不仅想找出某个二级索引列的值等于某个常数的记录,还想把该列的值为NULL的记录也找出来,就像下边这个查询:

SELECT * FROM single_demo WHERE key1 = 'abc' OR key1 IS NULL;

当使用二级索引而不是全表扫描的方式执行该查询时,这种类型的查询使用的访问方法就称为ref_or_null

range

搜索条件就不只是要求索引列与常数的等值匹配了,而是索引列需要匹配某个或某些范围的值,

如下边这个查询:

SELECT * FROM single_table WHERE key2 IN (1438, 6328) OR (key2 >= 38 AND key2 <= 79);

使用二级索引 + 回表的方式执行,利用索引进行范围匹配的访问方法称之为:range

Index

看下边这个查询:

SELECT key_part1, key_part2, key_part3 FROM single_table WHERE key_part2 = 'abc';

由于key_part2并不是联合索引idx_key_part最左索引列,所以我们无法使用ref或者range访问方法来执行这个语句。但是这个查询符合下边这两个条件:

  • 它的查询列表只有3个列:key_part1key_part2key_part3,而索引idx_key_part又包含这三个列。

  • 搜索条件中只有key_part2列。这个列也包含在索引idx_key_part中。

也就是说我们可以直接通过遍历idx_key_part索引的叶子节点的记录来比较key_part2 = 'abc'这个条件是否成立,把匹配成功的二级索引记录的key_part1key_part2key_part3列的值直接加到结果集中就行了。由于二级索引记录比聚簇索记录小的多(聚簇索引记录要存储所有用户定义的列以及所谓的隐藏列,而二级索引记录只需要存放索引列和主键),而且这个过程也不用进行回表操作,所以直接遍历二级索引比直接遍历聚簇索引的成本要小很多,设计MySQL的大叔就把这种采用遍历二级索引记录的执行方式称之为:index

all

最直接的查询执行方式就是我们已经提了无数遍的全表扫描

连接的原理

SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';

在这个查询中我们指明了这三个过滤条件:

  • t1.m1 > 1

  • t1.m1 = t2.m2

  • t2.n2 < 'd'

那么这个连接查询的大致执行过程如下:

  1. 首先确定第一个需要查询的表,这个表称之为驱动表。只需要选取代价最小的那种访问方法去执行单表查询语句(就是说从const、ref、ref_or_null、range、index、all这些执行方法中选取代价最小的去执行查询)
  2. 针对上一步骤中从驱动表产生的结果集中的每一条记录,分别需要到t2表中查找匹配的记录,所谓匹配的记录,指的是符合过滤条件的记录。因为是根据t1表中的记录去找t2表中的记录,所以t2表也可以被称之为被驱动表

整个连接查询的执行过程就如下图所示:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

这个两表连接查询共需要查询1次t1表,2次t2表。当然这是在特定的过滤条件下的结果,如果我们把t1.m1 > 1这个条件去掉,那么从t1表中查出的记录就有3条,就需要查询3次t2表了。也就是说在两表连接查询中,驱动表只需要访问一次,被驱动表可能被访问多次。

内连接和外连接

  • 内连接:对于内连接的两个表,驱动表中的记录在被驱动表中找不到匹配的记录,该记录不会加入到最后的结果集。

  • 外连接:对于外连接的两个表,驱动表中的记录即使在被驱动表中没有匹配的记录,也仍然需要加入到结果集。

    MySQL中,根据选取驱动表的不同,外连接仍然可以细分为2种:

    • 左外连接

      选取左侧的表为驱动表。

    • 右外连接

      选取右侧的表为驱动表。

WHERE子句

WHERE子句中的过滤条件就是我们平时见的那种,不论是内连接还是外连接,凡是不符合WHERE子句中的过滤条件的记录都不会被加入最后的结果集。

ON子句中的过滤条件

ON子句放到外连接中,如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录,那么该记录仍然会被加入到结果集中,对应的被驱动表记录的各个字段使用NULL值填充;把ON子句放到内连接中,MySQL会把它和WHERE子句一样对待,内连接中的WHERE子句和ON子句是等价的

一般情况下,我们都把只涉及单表的过滤条件放到WHERE子句中,把涉及两表的过滤条件都放到ON子句中,我们也一般把放到ON子句中的过滤条件也称之为连接条件。对于左(外)连接和右(外)连接来说,必须使用ON子句来指出连接条件。

内连接和外连接的根本区别就是在驱动表中的记录不符合ON子句中的连接条件时会不会把该记录加入到最后的结果集

连接的本质就是把各个连接表中的记录都取出来依次匹配的组合加入结果集并返回给用户。不论哪个表作为驱动表,两表连接产生的笛卡尔积肯定是一样的。而对于内连接来说,由于凡是不符合ON子句或WHERE子句中的条件的记录都会被过滤掉,其实也就相当于从两表连接的笛卡尔积中把不符合过滤条件的记录给踢出去,所以对于内连接来说,驱动表和被驱动表是可以互换的,并不会影响最后的查询结果。但是对于外连接来说,由于驱动表中的记录即使在被驱动表中找不到符合ON子句连接条件的记录,所以此时驱动表和被驱动表的关系就很重要了,也就是说左外连接和右外连接的驱动表和被驱动表不能轻易互换

连接的原理

对于两表连接来说,驱动表只会被访问一遍,但被驱动表却要被访问到好多遍,具体访问几遍取决于对驱动表执行单表查询后的结果集中的记录条数。

通用的两表连接过程如下图所示:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

如果有3个表进行连接的话,那么步骤2中得到的结果集就像是新的驱动表,然后第三个表就成为了被驱动表,重复上边过程,也就是步骤2中得到的结果集中的每一条记录都需要到t3表中找一找有没有匹配的记录

用伪代码表示一下这个过程就是这样:

for each row in t1 {   #此处表示遍历满足对t1单表查询结果集中的每一条记录

    for each row in t2 {   #此处表示对于某条t1表的记录来说,遍历满足对t2单表查询结果集中的每一条记录

        for each row in t3 {   #此处表示对于某条t1和t2表的记录组合来说,对t3表进行单表查询
if row satisfies join conditions, send to client
}
}
}

这个过程就像是一个嵌套的循环,所以这种驱动表只访问一次,但被驱动表却可能被多次访问,访问次数取决于对驱动表执行单表查询后的结果集中的记录条数的连接执行方式称之为嵌套循环连接Nested-Loop Join),这是最简单,也是最笨拙的一种连接查询算法。

使用索引加快连接速度

我们知道在嵌套循环连接步骤2中可能需要访问多次被驱动表,如果访问被驱动表的方式都是全表扫描的话,要扫描很多次。 但是别忘了,查询t2表其实就相当于一次单表扫描,我们可以利用索引来加快查询速度。

SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';

为例

原来的t1.m1 = t2.m2这个涉及两个表的过滤条件在针对t2表做查询时关于t1表的条件就已经确定了,所以我们只需要单单优化对t2表的查询了,上述两个对t2表的查询语句中利用到的列是m2n2列,

  • m2列上建立索引,因为对m2列的条件是等值查找,比如t2.m2 = 2t2.m2 = 3等,所以可能使用到ref的访问方法,假设使用ref的访问方法去执行对t2表的查询的话,需要回表之后再判断t2.n2 < d这个条件是否成立。

    这里有一个比较特殊的情况,就是假设m2列是t2表的主键或者唯一二级索引列,那么使用t2.m2 = 常数值这样的条件从t2表中查找记录的过程的代价就是常数级别的。我们知道在单表中使用主键值或者唯一二级索引列的值进行等值查找的方式称之为const,而设计MySQL的大叔把在连接查询中对被驱动表使用主键值或者唯一二级索引列的值进行等值查找的查询执行方式称之为:eq_ref

  • n2列上建立索引,涉及到的条件是t2.n2 < 'd',可能用到range的访问方法,假设使用range的访问方法对t2表的查询的话,需要回表之后再判断在m2列上的条件是否成立。

假设m2n2列上都存在索引的话,那么就需要从这两个里边儿挑一个代价更低的去执行对t2表的查询。当然,建立了索引不一定使用索引,只有在二级索引 + 回表的代价比全表扫描的代价更低时才会使用索引。

另外,有时候连接查询的查询列表和过滤条件中可能只涉及被驱动表的部分列,而这些列都是某个索引的一部分,这种情况下即使不能使用eq_refrefref_or_null或者range这些访问方法执行对被驱动表的查询的话,也可以使用索引扫描,也就是index的访问方法来查询被驱动表。所以我们建议在真实工作中最好不要使用*作为查询列表,最好把真实用到的列作为查询列表

基于块的嵌套循环连接(Block Nested-Loop Join)

扫描一个表的过程其实是先把这个表从磁盘上加载到内存中,然后从内存中比较匹配条件是否满足。

如果表太大,内存里可能并不能完全存放的下表中所有的记录,所以在扫描表前边记录的时候后边的记录可能还在磁盘上,等扫描到后边记录的时候可能内存不足,所以需要把前边的记录从内存中释放掉。我们前边又说过,采用嵌套循环连接算法的两表连接过程中,被驱动表要被访问多次,如果这个被驱动表中的数据特别多而且不能使用索引进行访问,那就相当于要从磁盘上读好几次这个表,这个I/O代价就非常大了,所以我们得想办法:尽量减少访问被驱动表的次数

我们可以在把被驱动表的记录加载到内存的时候,一次性和多条驱动表中的记录做匹配,这样就可以大大减少重复从磁盘上加载被驱动表的代价了。所以提出一个join buffer的概念,join buffer就是执行连接查询前申请的一块固定大小的内存,先把若干条驱动表结果集中的记录装在这个join buffer中,然后开始扫描被驱动表,每一条被驱动表的记录一次性和join buffer中的多条驱动表记录做匹配,因为匹配的过程都是在内存中完成的,所以这样可以显著减少被驱动表的I/O代价。使用join buffer的过程如下图所示:

MySQL之 InnoDB记录结构(转自掘金小册 MySQL是怎样运行的,版权归作者所有!)

最好的情况是join buffer足够大,能容纳驱动表结果集中的所有记录,这样只需要访问一次被驱动表就可以完成连接操作了。这种加入了join buffer的嵌套循环连接算法称之为基于块的嵌套连接(Block Nested-Loop Join)算法。

join buffer的大小是可以通过启动参数或者系统变量join_buffer_size进行配置,默认大小为262144字节(也就是256KB),最小可以设置为128字节。当然,对于优化被驱动表的查询来说,最好是为被驱动表加上效率高的索引,如果实在不能使用索引,并且自己的机器的内存也比较大可以尝试调大join_buffer_size的值来对连接查询进行优化。

另外需要注意的是,驱动表的记录并不是所有列都会被放到join buffer中,只有查询列表中的列和过滤条件中的列才会被放到join buffer中,所以再次提醒我们,最好不要把*作为查询列表,只需要把我们关心的列放到查询列表就好了,这样可以在join buffer中放置更多的记录