# 局部性原理
局部性原理表现在以下两个方面:
- 时间局部性 :如果程序中的某条指令一旦执行,不久以后该指令可能再次执行;如果某数据被访问过,不久以后该数据可能再次被访问。产生时间局部性的典型原因,是由于在程序中存在着大量的循环操作。
- 空间局部性 :一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,这是因为指令通常是顺序存放、顺序执行的,数据也一般是以向量、数组、表等形式簇聚存储的。
在InnoDB中,数据会存储到磁盘上,在真正处理数据时需要先将数据加载到内存,表中读取某些记录时,InnoDB存储引擎不需要一条一条的把记录从磁盘上读出来,InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 16 KB,也就是说,当需要从磁盘中读数据时每一次最少将从磁盘中读取16KB的内容到内存中,每一次最少也会把内存中的16KB内容写到磁盘中。
# InnoDb数据页结构
页是InnoDB管理存储空间的基本单位,一个页的大小默认是16KB
# 页结构
名称 | 占用空间 | 简单描述 |
---|---|---|
File Header(文件头部) | 38字节 | 页的一些通用信息 |
Page Header(页面头部) | 56字节 | 数据页专有的一些信息 |
Infimum + Supremum(最小记录和最大记录) | 26字节 | 两个虚拟的行记录 |
User Records(用户记录) | 不确定 | 实际存储的行记录内容 |
Free Space(空闲空间) | 不确定 | 页中尚未使用的空间 |
Page Directory(页面目录) | 不确定 | 页中的某些记录的相对位置 |
File Trailer(文件尾部) | 8字节 | 校验页是否完整 |
# InnoDB行格式
一行记录可以以不同的格式存在InnoDB中,行格式分别是Compact、Redundant、Dynamic和Compressed行格式。
我们可以在创建或修改表的语句中指定行格式:
create table 表名(列的信息) row_format=行格式名称
alter table 表名 row_format=行格式名称
2
Compact行格式
记录的额外信息
这部分信息是服务器为了描述这条记录而不得不额外添加的一些信息,这些信息分3类,分别是:
- 变长字段长度列表
- NULL值列表
- 记录头信息
变长字段长度列表
MySQL支持一些变长的数据类型,比如VARCHAR(M)、VARBINARY(M)、TEXT类型,BLOB类型,这些数据类型 修饰列称为变长字段,变长字段中存储多少字节的数据不是固定的,所以我们在存储真实数据的时候需要顺便把 这些数据占用的字节数也存起来。在Compact行格式中,把所有变长字段的真实数据占用的字节长度都存放在记 录的开头部位,从而形成一个变长字段长度列表。
CHAR是一种固定长度的类型,VARCHAR则是一种可变长度的类型。 VARCHAR(M),M代表最大能存多少个字符。( MySQL5.0.3以前是字节,以后就是字符)
NULL值列表
Compact行格式会把可以为NULL的列统一管理起来,存一个标记为在NULL值列表中,如果表中没有允许存储 NULL 的列,则 NULL值列表也不存在了。
二进制位的值为1时,代表该列的值为NULL。
二进制位的值为0时,代表该列的值不为NULL。
如有a,b,c 3个字段,若b为空,则列数据中没有存b,只存了a、c,如果没有这个NULL标志位,就无法判断哪个列对于哪个字段了这时候NULL值列表就为101。
记录头信息
这是用于描述记录的记录头信息,它是由固定的5个字节组成。5个字节也就是40个二进制位,不同的位代表不同的意思,如图:
名称 | 大小(单位: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 | 表示下一条记录的相对位置 |
记录的真实数据
除了我们自己定义的列的数据以外,还有三个隐藏列:
列名 | 是否必须 | 占用空间 | 描述 |
---|---|---|---|
row_id | 否 | 6字节 | 行ID,唯一标识一条记录 |
transaction_id | 是 | 6字节 | 事务ID |
roll_pointer | 是 | 7字节 | 回滚指针 |
实际上这几个列的真正名称其实是:DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR。
一个表没有手动定义主键,则会选取一个Unique键作为主键,如果连Unique键都没有定义的话,则会为表默认添加一个名为row_id的隐藏列作为主键,也会使用这个主键去创建默认索引。所以row_id是在没有自定义主键以及Unique键的情况下才会存在的。
记录中的数据太多产生的溢出
一个页的大小一般是16KB,也就是16384字节,而一个VARCHAR(M)类型的列就最多可以存储65533个字节,这样就可能出现一个页存放不了一条记录。
在Compact和Reduntant行格式中,对于占用存储空间非常大的列,在记录的真实数据处只会存储该列的一部分数据,把剩余的数据分散存储在几个其他的页中,然后记录的真实数据处用20个字节存储指向这些页的地址(当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数),从而可以找到剩余数据所在的页。
Dynamic(默认使用的行格式)和Compressed行格式
这两种行格式类似于COMPACT行格式,只不过在处理行溢出数据时有点儿分歧,它们不会在记录的真实数据处存储一部分数据,而是把所有的数据都存储到其他页面中,只在记录的真实数据处存储其他页面的地址。另外,Compressed行格式会采用压缩算法对页面进行压缩。
数据的存储
create table t1(
a int,
b int,
c int,
d int,
e varchar(20),
primary key (a)
);
insert into t1 values(4,3,1,1,'d');
insert into t1 values(1,1,1,1,'1');
insert into t1 values(8,8,8,8,'h');
insert into t1 values(2,2,2,2,'b');
insert into t1 values(5,2,3,5,'e');
insert into t1 values(3,3,2,2,'c');
insert into t1 values(7,4,5,5,'g');
insert into t1 values(6,6,4,4,'f');
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
数据库中每一行数据存储在一个行格式中的列数据中,多个行放置在一个页中,取磁盘的数据时,会以页为单位将整个页放到内存中。
图中默认一个页最多能放4行数据,插入数据的时候会按照主键大小进行排序,比如插入a为4,1,8,2时,最终这四行数据会以链表的形式按照1,2,4,8的顺序存放,页结构中有一个目录项,我们对行数据进行分组,图中以两个行数据为一组,将组头的主键放到目录项中,目录项是一个数组,查询主键的时候可以使用二分法进行查询到对应组,再在组中遍历链表。
当一个页的数据满了的时候,会开辟另一个页,用来存放接下来的行数据,比如再次插入a为5这行数据时,会将8移动到新开辟的页中,5这行数据就放置在原来8的这个位置,当然插入数据的时候主键的顺序是乱序的话,需要进行频繁的移动和排序,这样效率比较低,因此建议设置主键自增长,这样插入数据的效率较高,同时也建议主键设置得比较小,因为主键会冗余的在目录页中存一份,并且如果主键设置得较大的话行数据就大了,页中放的行就少了,如果分多几个页的话会加深树的深度,查找的效率变低。
页与页之间也以指针连接,构成了一个双向链表。
最上面的是目录页,用来存储两个页的目录,它也拥有与下面两个页一样的结构,也会有目录项,行与行之间也会构成链表,只不过下面存的是真实的数据,上面存的是数据所在的位置。这就是简单的BTree+结构。