数据库数据存储结构

InnoDB记录存储结构

InnoDB页

将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，InnoDB中页的大小一般为 16KB

行格式

数据在磁盘上存储的格式也叫做行格式
InnoDB的设计者设计了多种行格式，主要的有下面4种。

两个问题：

1. 行格式中计算机如何区别每个部分？
2. 列中名字如何和数据对应起来？

COMPACT行格式

额外信息：服务器为了描述这条记录而不得不额外添加的一些信息。

• 变长字段长度列表：把所有变长类型实际长度都存放在记录的开头部位形成一个列表，按照列的顺序逆序存放。

  实际长度大于1个字节会用两个字节，具体是使用一个字节还是两个字节取决内容的实际长度。判断规则：

  //W=表示编码格式，ASCII-1，GBK-2,UTF8-3,
  //M=表示变长的最大字符
  //L=表示实际字节数
  if W_M<256:1个字节
  if W_M>=256
  {
    L<128:1个字节
    L>=128:2个字节
  }

• NULL值列表：记录数据为NULL的列

  

  1. 先统计允许存储NULL的列，如果表中没有允许存储 NULL 的列，则 NULL值列表 也不存在了。
  2. 将每个允许存储NULL的列对应一个二进制位，二进制位按照列的顺序逆序排列。
  3. MySQL规定NULL值列表必须用整数个字节的位表示，如果使用的二进制位个数不是整数个字节，则在字节的高位补0。

• 记录头信息：

  

名称	大小（单位：bit）	描述
Retention 1	1	没有使用
Retention 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	表示下一条记录的相对位置

• 数据信息：mysql会为每个记录增加默认列

列名	是否必须	占用空间	描述
row_id	否	6字节	行ID，唯一标识一条记录
transaction_id	是	6字节	事务ID
roll_pointer	是	7字节	回滚指针

注意：
CHAR(10)类型，除真实数据以外的8个字节的统统都用空格字符填充
如果主键已经指定了，那么row_id的列就不会自动添加

Redundant行格式

有些区别，不过大致相同。
采用了偏移量来实现，头信息中略有区别，NULL值也会存储。

行溢出数据

VARCHAR(M)最多能存储的数据

COMPACT行格式中，可变长的长度记录最多可以达到2个字节，也就是内容65535个字节，其中包括可变字符长度列表中长度的记录需要2个字节，NULL列表中的1个字节（非NULL则无），于是真实的内容占65532(或者65533),在不同的编码下对应的不同数量的字符长度。

记录中的数据太多产生的溢出

• 而一个页的大小一般是16KB，也就是16384字节，而一个VARCHAR(M)类型的列就最多可以存储65532个字节，这样就可能造成一个页存放不了一条记录的尴尬情况。
• 在Compact和Reduntant行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分（768个字节）数据，把剩余的数据分散存储在几个连续的页中，只在记录的真实数据处用20个字节存储指向这些页的地址，从而可以找到剩余数据所在的页。

除了varchar,text和blob类型都会有这个现象。

Dynamic和Compressed行格式

• 基本和COMPACT格式一样
• Dynamic和Compressed行格式，它们不会在记录的真实数据处存储字符串的前768个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址。
• Compressed行格式和Dynamic不同的一点是，Compressed行格式会把存储到其他页面的数据采用压缩算法进行压缩，以节省空间。

InnoDB数据页结构

数据页结构

记录行在页中的存储

用户的数据会按照指定的行格式存储到UserRecords中，这个部分一开始是不存在的，而是从Free Space这个部分中一点点的划分出。

那么记录行在页中是如何存储的呢？

记录头信息解析

再次回顾头信息里的字节含义：

name	大小（单位：bit）	描述
Retention1	1	没有使用
Retention2	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	表示下一条记录的相对位置

• delete_mask：该记录行是否删除，删除的数据并不会立刻消息，而是标记，待重排列的时候统一处理，另外，已删除的数据空间是可以被覆盖的。
• min_rec_mask：这个属性标记该记录是否为B+树的非叶子节点中的最小记录，之后详解。
• n_owned：当前页管理的记录数，待详解。
• heap_no：表示该记录在页中的（相对）位置，从2开始，因为在infimum+supremum中已经存在了两条“最小记录”和“最大记录”的记录。
• record_type：0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。
• next_record：记录在页中存储的数据结构类似于单链表，因此这个数据表示类似链表中的指针，大小表示从当前真实数据到下一个真实数据的距离。

当记录被删除，并不会从页中立刻消失，而是地址的指向发生变化。

如果我们想找某条数据，当然也可以遍历这条链表进行查找，但是这样效率不高。

一个好的灵感来自书的目录，按章节区分，先确定所属的章，再从章中去找节。

这个“章”在InnoDB中以偏移量来表示，称为“槽”。
槽中存放着所有正常记录（包括最小、最大不包括删除的记录）
每个槽的偏移量以最后一条记录的地址的偏移量来赋值。
最后一条记录中的n_owned表示在当前槽中有多少个记录。

规定：对于最小记录所在的分组只能有 1 条记录，最大记录所在的分组拥有的记录条数只能在 1~8 条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间。

这样处理之后：查询的过程可以简化为下面两个步骤：

1. 通过二分法确定该记录所在的槽。
2. 通过记录的next_record属性组成的链表遍历查找该槽中的各个记录

Page Header

名称	占用空间大小	描述
PAGE_N_DIR_SLOTS	2字节	在页目录中的槽数量
PAGE_HEAP_TOP	2字节	第一个记录的地址
PAGE_N_HEAP	2字节	本页中的记录的数量（包括最小和最大记录以及标记为删除的记录v）
PAGE_FREE	2字节	指向可重用空间的地址（就是标记为删除的记录地址）
PAGE_GARBAGE	2字节	已删除的字节数，行记录结构中delete_flag为1的记录大小总数
PAGE_LAST_INSERT	2字节	最后插入记录的位置
PAGE_DIRECTION	2字节	最后插入的方向
PAGE_N_DIRECTION	2字节	一个方向连续插入的记录数量
PAGE_N_RECS	2字节	该页中记录的数量（不包括最小和最大记录以及被标记为删除的记录）
PAGE_MAX_TRX_ID	8字节	修改当前页的最大事务ID，该值仅在二级索引中定义
PAGE_LEVEL	2字节	当前页在索引树中的位置，高度
PAGE_INDEX_ID	8字节	索引ID，表示当前页属于哪个索引
PAGE_BTR	10字节	非叶节点所在段的segment header，仅在B+树的Root页定义
PAGE_LEVEL	10字节	B+树所在段的segment header，仅在B+树的Root页定义

• PAGE_DIRECTION:新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。
• PAGE_N_DIRECTION：假设连续几次插入新记录的方向都是一致的，InnoDB会把沿着同一个方向插入记录的条数记下来。

File Header

Page Header：记录页内的相关信息
File Header：记录页外的相关信息

• FIL_PAGE_SPACE_OR_CHKSUM：表示当前页面的校验和，对于一个很长很长的字节串来说，我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串，这个比较短的值就称为校验和。比较页之前可以先比较校验和，如果校验和都不一致，那么页面一定不一样，可以大大的节省时间。
• FIL_PAGE_OFFSET：页号。唯一标识。

• FIL_PAGE_TYPE：一般存放记录的数据页的类型其实是FIL_PAGE_INDEX，也就是所谓的B+树叶子节点

  

• FIL_PAGE_PREV和FIL_PAGE_NEXT：一张表中可以有成千上万条记录，一个页只有16KB，所以可能需要好多页来存放数据，FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本页的上一个和下一个页的页号。需要注意的是，并不是所有类型的页都有上一个和下一个页的属性。

File Trailer

如果在数据同步的过程中断电了怎么办？
在页尾同样加上4个字节的校验和做前后对比，判断数据是否正常。
另外还有4个字节的LSN日志序列位置，用来处理如果前后校验和不一致的时候，来回滚数据。

索引

没有索引的情况

• 单页查找：
  1. 以主键为搜索条件：之前讲过页目录和槽的概念，因此这里可以使用目录页的二分法来快速定位。　
  2. 以其它列为搜索条件：这时候没有建立相应的目录，因此需要从从最小记录开始全部遍历一遍。
• 多页查找：
  由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据单页查找的方式去查找指定的记录。

显然，这种查找的效率实在是太低了。

一个简单的索引

先来看一下页中记录的简化图：

当一个页装不下之后会装到多个页中，并且这些页可能都是不连续的，但是满足下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值这样的一个规律。效果如下：

现在建立一个目录，目录中的每一项包含页数和最小主键值两项数据：

这个目录就叫索引。

InnoDB中的索引方案

为了更灵活的管理目录项，采取页的方式同样的去存储目录的信息：

如何区别页中的数据是用户数据还是目录数据？

• 目录项记录行格式中的record_type为1。
• 目录项记录主键值和页的编号两个列。
• 只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0。

除此之外没有其他区别，他们的页面类型都是0x45BF

再做查询：

1. 先查询记录存在的页（由于不唯一，可能存在多个页中）
2. 在页中做之前提到的单页查询。

虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有16KB大小，能存放的目录项记录也是有限的，如果目录项太多，一个页面放不下，就需要多个页面，这时候就需要采取同样的方式对多个目录页再建立一个目录页。

实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点。

聚簇索引

1. 按主键大小记录行和页。
   • 页内按主键大小顺序构成单链表
   • 页之前按主键大小顺序构成双链表
2. B+树的叶子节点存储的是完整的用户记录。

这种聚簇索引并不需要我们在MySQL语句中显式的去创建，InnoDB存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据。

二级索引

聚簇索引通过主键大小顺序来记录，但是如果我们的查询条件不是主键，就不起作用了。
因此需要建立新的索引树，称为二级索引：

与聚簇索引的区别：

1. 真实内容中只有主键和对应的索引列。
2. 以索引列的大小进行记录。

因为二级索引的页节点中只有主键和对应的索引列，所以想要查询完整的数据，必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。

联合索引

使用多个列建立的二级索引就是联合索引。
联合索引先通过第一个字段顺序记录，在第一个记录大小一致的时候通过第二个字段顺序记录。

MyISAM中的索引方案

InnoDB中索引的叶节点中存储了所有的数据，因此索引即数据。
而MyISAM中索引和数据分开了。将表中的记录按照插入时间顺序的存储在一块存储空间上，可以通过行号来访问（定长的情况）。

MyISAM一开始会为主键创建一个B+树索引，只是这个索引的数据只有主键和行号。中建立的索引全部都是二级索引

MySQL中创建和删除索引的语句

MySql会自动的为主键和UNIQUE字段建立聚簇索引。

手动创建：

1. 建表时：INDEX 索引名 (需要被索引的单个列或多个列)
2. 建表后：ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列)

手动删除：
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;