MySQL精通知识点笔记-高级篇-索引的数据结构与 InnoDB的数据存储结构(物理)

索引的本质：索引是数据结构。你可以简单理解为排好序的快速查找数据结构，满足特定查找算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高级查找算法。

优点

数据库的IO成本
数据的唯一性
以加速表和表之间的连接
减少查询中分组和排序的时间

缺点

创建索引和维护索引要耗费时间
要占磁盘空间
会降低更新表的速度

1 索引设计思路(InnoDB——B+树)

首先建立一个普通的表，表中存储数据

mysql> CREATE TABLE index_demo(
	-> c1 INT,
	-> c2 INT,
	-> c3 CHAR(1),
	-> PRIMARY KEY(c1)
	-> ) ROW_FORMAT = Compact;

用一个简单的结构存储每一行数据

record_type ：记录头信息的一项属性，表示记录的类型，
- 0 表示普通记录、
- 2 表示最小记录、
- 3 表示最大记录、
- 1 表示目录行，下面会用到
一个数据库由多个页组成，每个页内的数据按照主键大小排序，就会形成如图
如果数据库很大，页就会很多，我们建立一个标志每个页的目录项，就会方便检索到目标页。查询的时候先查询目录项，再查询具体页的内容
- key：所指向的页的最小值
- page_no：页的具体序号
页特别多的时候，就需要对目录项进行存储，存储结构使用与存储数据一致的结构，方便存储与管理

在这里插入图片描述

随着页数增加，目录页也变多，为了索引快一点，我们同样需要形成索引目录页的目录页

在这里插入图片描述

我们形成的这样的数据结构，称为B+树

为什么数据存储的B+树一般不超过4层/为什么查询一般不超过四次读取？

假设一个页只能存储一百条记录
如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 100 条记录。
如果B+树有2层，最多能存放 1000×100=10,0000 条记录。
如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录。
如果B+树有4层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。这个数量级已经相当多，绝大多数情况下都已经够用

2 常见索引分类

索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。

2.1 聚簇索引

按照主键的大小做索引的根据，用B+树结构存储，同时存储了主键索引与完整记录

重点在于叶子节点存储了完整记录，不仅包括主键，还包括除主键外的所有列值

2.2 二级索引(辅助索引、非聚簇索引)

按照非主键字段内容作为排序依据，同样用B+树存储，但是叶子节点只存储了索引对应的主键值

重点在于叶子节点只存储了索引字段和相对应的主键字段

这个区别也引出了二级索引一个常见的操作：回表
回表：指我们从二级索引中找到对应索引数据，取得相应主键，再依据主键在聚簇索引中查所需要的其他列，这个过程称为回表

正如前文所述，二级索引中存储了索引字段和主键字段，如果需要返回的字段中仅包含这两个字段，那么不需要回表，直接返回即可。
换句话说，回表这一操作并不是所有情况都要进行

2.3 联合索引

多个列同时组合成的联合索引
比如用某个表中，用id，name，job 三个值组成索引，那么排序的时候就会先看id，id相同再看name，以此类推。
因此，联合索引指定的顺序非常重要，决定了整个B+树的结构。

注意：对多个字段建立联合索引和对多个字段分别建立二级索引是完全不同的！！！！

联合索引只会生成一个B+树，分别建构时建立的是多个B+树
联合索引使用时，必须按照建构顺序对搜索条件进行排序，否则就会索引失效

InnoDB的B+树索引的注意事项

根页面位置万年不动
内节点中目录项记录的唯一性
一个页面最少存储2条记录

3 MyISAM中的索引方案

注：这里的B树指的是B+树，国内叫B+树比较多

索引 / 存储引擎	MyISAM	InnoDB	Memory
BTree索引	支持	支持	支持
叶子节点存储内容	数据记录地址	数据行所有内容
默认索引结构	B	B	Hash

因为叶子节点存储内容的不同，也就引出了InnoDB与MyISAM的索引方式的区别：

M的所有索引都相当于是二级索引，因为都必然要执行回表操作（依据地址回数据文件找具体数据）
M表中可以没有主键，但I中必须有，没有指定也要自动选择或生成字段作为主键。
M的回表更快，因为直接存储数据地址
存储对应着I的特点：索引即数据，数据即索引。

4 InnoDB的数据存储结构(物理)

先总体地看一下存储结构

InnoDB的读写的最小单位为页，页之上还有区和段，逻辑关系如图所示

在这里插入图片描述

主要关注一下页与行之间的关系，两者存在一定联系

在这里插入图片描述

至于上下两种形式是如何转化的，如下图
在这里插入图片描述

从行结构开始了解一下一些存储结构细节

4.1 InnoDB行格式（或记录格式）

InnoDB存储引擎设计了4种不同类型的行格式，分别是Compact、Redundant、Dynamic和Compressed行格式。

# 查看MySQL8的默认行格式：
mysql> SELECT @@innodb_default_row_format;
+-------------------------------------+
| @@innodb_default_row_format |
+-------------------------------------+
| dynamic                                   |
+-------------------------------------+
1 row in set (0.00 sec)
 
# 也可以使用如下语法查看具体表使用的行格式：
SHOW TABLE STATUS like '表名'\G

# 在创建或修改表的语句中指定行格式：
CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称
ALTER TABLE 表名 ROW_FORMAT=行格式名称
 
举例：
mysql> CREATE TABLE record_test_table (
    ->     col1 VARCHAR(8),
    ->     col2 VARCHAR(8) NOT NULL,
    ->     col3 CHAR(8),
    ->     col4 VARCHAR(8)
    -> ) CHARSET=ascii ROW_FORMAT=COMPACT;
Query OK, 0 rows affected (0.03 sec)

4.1.1 COMPACT行格式

变长字段长度列表
- 列中的边长字段的具体长度表示出来
- 长度和字段的顺序是逆序存储

060408	NULL值列表	记录头信息	列1的值	列2的值	····	列n的值

NULL值列表
- 用二进制位表示某列的值是否为null
  - 1 表该列为NULL
  - 0 表该列不为NULL
- 同样是逆序存储

变长字段长度列表	110	记录头信息	列1的值	列2的值	····	列n的值

记录头信息

看图比较直观

在这里插入图片描述

名称	位数	描述
预留位1	1
预留位2	1
delete_mask	1	当前记录被删为1，未被删为1
min_rec_mask	1	B+树每层非叶子节点中的最小记录标记为1，否则为0
n_owned	4	表示当前记录拥有的记录数(页目录的最后一条记录才会存储)
heap_no	13	表示当前记录在记录堆的位置信息(最小0，最大1，其余按序递增)
record_type	3	表示当前记录类型，0普通，1非叶，2最小，3最大
next_record	16	表示下一条记录的相对位置

在这里插入图片描述

4.1.2 Dynamic行格式和Compressed

Dynamic和Compressed行格式内容基本一样，只是细节上有些区别

要了解两者的区别，首先要明确一个问题

行溢出

一页的大小是16KB，但是VARCHAR作为一个可变大小的字段，最长存储大小为65535个字节，远大于16KB，遇到这种极端长的字段，不光单个行存储不能，一个页都存储不下。

行溢出：一个页存放不了一条记录的情况

Compact和Reduntant行格式处理行溢出的方式

在Compact和Reduntant行格式中，使用页的扩展解决行溢出
对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据（存放768个前缀字节），把剩余的数据分散存储在几个其他的页中进行分页存储，然后记录的真实数据处用20个字节存储指向这些页的地址（当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数），从而可以找到剩余数据所在的页

流程如图所示
在这里插入图片描述

Dynamic行格式和Compressed 处理行溢出

Compressed和Dynamic两种记录格式对于存放在BLOB中的数据采用了完全的行溢出的方式。如图，在数据页中只存放20个字节的指针（溢出页的地址），实际的数据都存放在Off Page（溢出页）中。
Compressed行记录格式的另一个功能就是，存储在其中的行数据会以zlib的算法进行压缩，因此对于BLOB、TEXT、VARCHAR这类大长度类型的数据能够进行非常有效的存储。

在这里插入图片描述

4.1.3 Redundant行格式

Redundant 是MySQL 5.0版本之前InnoDB的行记录存储方式，MySQL 5.0支持Redundant是为了兼容之前版本的页格式。

字段长度偏移列表	记录头信息	列1的值	列2的值	····	列n的值

字段长度偏移列表

少了“变长”两个字：Redundant行格式会把该条记录中所有列（包括隐藏列）的长度信息都按照逆序存储到字段长度偏移列表。
多了“偏移”两个字：这意味着计算列值长度的方式不像Compact行格式那么直观，它是采用两个相邻数值的差值来计算各个列值的长度。

记录头信息内容

名称	位数	描述
预留位1	1
预留位2	1
delete_mask	1	当前记录被删为1，未被删为1
min_rec_mask	1	B+树每层非叶子节点中的最小记录标记为1，否则为0
n_owned	4	表示当前记录拥有的记录数(页目录的最后一条记录才会存储)
heap_no	13	表示当前记录在记录堆的位置信息(最小0，最大1，其余按序递增)
n_filds	10	记录中列的数量
1byte_offs_flag	1	记录字段长度偏移列表中每个列对应的偏移量使用一个字节还是两个字节表示
next_record	16	表示下一条记录的相对位置

4.2 数据页内部结构

重新拿出这个图
在这里插入图片描述
这次关注右侧的页结构，可以分成三部分研究

文件头尾
- File Header（文件头部）（38字节）
- File Trailer（文件尾部）（8字节）
记录行部分
- 主要内容与形式在描述记录行的形式的部分已经介绍完毕
页目录部分
- Page Directory（页目录）
- Page Header（页面头部）56字节

4.2.1 文件头尾

File Header（文件头部）

描述各种页的通用信息。（比如页的编号、其上一页、下一页是谁等）

名称	大小	描述
`FIL_PAGE_SPACE_OR_CHKSUM`	（4字节）	页的校验和(checksum值)
`FIL_PAGE_OFFSET`	（4字节）	页号
`FIL_PAGE_PREV`	（4字节）	上一页页号
`FIL_PAGE_NEXT`	（4字节）	下一页页号
`FIL_PAGE_TYPE`	（2字节）	页类型
FIL_PAGE_LSN	（8字节）	页ui后被修改时对应的日志序列位置(Log Sequence Number)
FIL_PAGE_FILE_FLUSH_LSN	(8字节)	仅在系统表空间的一个页中定义，代表文件至少被刷新到了对应的LSN值
`FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID`	(4字节)	页属于哪个表空间

页的类型主要有如下几种（）

名称	十六进制	描述
fil_page_type_allocated	0x0000	最新分配，还没使用。
`fil_page_undo_log`	0x0002	undo日志。
fil_page_inode	0x003	段信息节点。
fil_page_ibuf_free_list	0x0004	insert buffer空闲列表。
fil_page_ibuf_bitmap:insert	0x0005	buffer 位图。
`fil_page_type_sys`	0x0006	系统页。
fil_page_type_trx_sys	0x0007	事务系统数据。
fil_page_type_fsp_hdr	0x0008	表空间头信息。
fil_page_type_xdes	0x0009	扩展描述。
fil_page_type_blob	0x000A	blob页。溢出页
`fil_page_index`	0x45BF	索引页，数据页

File Trailer（文件尾部）

和File Header中的校验和相对应

前4个字节代表页的校验和
后4个字节代表页面被最后修改时对应的日志序列位置（LSN）

4.2.2 页目录

页目录主要是为了提升检索效率

Page Directory（页目录）

页内的行已经不多，但是为了检索方便，需要对页中的行再进行分组
页目录对每一组的最后一条记录的地址偏移量进行记录，称为槽(slot)

分组方式

第一组只有最小记录1一个记录
最后一组，即最大记录所在分组，有1-8条记录
其余组的记录数再4-8条之间
在每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned 字段(记录行的形式中有提及)。

看图更容易理解
在这里插入图片描述

Page Header（56字节）

在这里插入图片描述