InnoDB的存储机制

参考资料：《PostgreSQL指南》 / 《MySQL是怎样运行的》 / PostgreSQL 中文资料 /

InnoDB

InnoDB 是 MySQL 5.7 默认的存储引擎，其他存储引擎还包括 MyISAM、MEMORY 等。下文对 InnoDB 做简单的介绍

1. InnoDB 以页的方式管理磁盘数据，默认情况下页大小是 16KB
2. InnoDB 以行格式的形式保存记录（record），随着技术的发展行格式也在不断进化中

InnoDB 四种行格式

随着 MySQL 的进化，真实的行格式也会随之变化，下面介绍 MySQL 5.7 可用的几种行格式

Compact

1. 变长字段（VARCHAR/TEXT/BLOB 等）列表只保存非 NULL 字段长度且逆序保存，每个单元占用 1 个或者 2 个字节
   1. 变长数据有多种，VARCHAR 是一种；CHAR+变长字符集也是，例如使用 utf8 编码的 CHAR 字符串。VARCHAR 在记录中如果为 NULL 就不会占用空间；CHAR 无论使用定长还是变长字符集，其都会占用一定的存储空间，例如使用 utf8 编码的 CHAR(10)，会占用固定 10 字节的存储空间
2. NULL 值列表使用位域（bit field）表示字段是否为 NULL。NULL 值列表占用整数个字节，未使用的位域补零
3. 记录头信息占用了固定的 5 个字节，其中 next_record 占用两个字节，指向下一条记录的相对位置，所以 Innodb 中每条记录常规数据类型（比如 INT/DOUBLE/CHAR 等）真实数据（包括额外添加的行 ID、事务 ID等）占用的存储空间不大于 64KB。如果需要保存很大的数据，需要使用 TEXT/BLOB 字段类型
   1. record_type 表示当前记录的类型，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录
4. 真实数据
   1. 真实数据长度限制跟记录格式强相关，比如 compact 会把变长数据的一部分保存在记录中但 Dynamic 只会保存变长变量真实数据位置的页信息，所以从理论上来讲 Dynamic 行可以保存更多列
   2. 如果创建表时没有指定 ID 也没有设置 unique 列，系统会自动添加一个 ID 列；事务 ID 和回滚指针是一定会添加的
   3. 非变长字段（CHAR+定长字符集）实际分配多少空间就会占用多少空间，未使用的空间使用空格（0x20）填充

Dynamic & Compressed

MySQL 5.7 默认的行格式是 Dynamic

Dynamic & Compressed 和 Compact 类似，不同之处在于处理行溢出（下文会介绍）时的策略，Dynamic 把所有变长数据保存在其他页中，记录中只保存数据页位置信息；Compressed 会压缩数据从而减少空间占用

Redundant

1. Redundant 格式比较古老，现在使用的已经比较少了
2. 偏移量列表会保存所有字段的偏移量，即使字段为 NULL。偏移量使用一个或者两个字节，偏移量最左侧位标识字段是否为 NULL
3. 使用 6 字节保存记录额外信息，最后两个字节保存下一条记录的相对位置
4. 与 Compact 格式一样，Redundant 也会插入一些额外的字段

行溢出

Innodb 默认情况下页大小是 16KB（16384 字节），且保证一页至少保存两条记录

Innodb 每页会保存 132 字节的额外信息，每条记录会使用额外的 27 字节。如果要保证每页至少保存 2 条记录，那么记录真实长度 n 要满足一定的要求：132 + 2×(27 + n) < 16384，如果行数据一页放不下就会造成行溢出

造成行溢出的因素有多种，比如数据库表定义了很多列（例如 1 万列 int 型数据），此时数据库的具体处理要看其实现方式，一般是拒绝创建过多列的；还有就是列元素保存了太多数据（比如长度超过 16KB 的 VARCHAR），此时 compact 行格式会尝试将 VARCHAR 列中的实际数据进行切割并保存在不同的页中

为减少行溢出的可能，可以使用 Dynamic 行格式，这样 VARCHAR 在记录中只会保存固定长度的地址信息；Compact 和 Redundant 行格式会将过长的 VARCHAR 数据分割保存在不同页中，真实的数据记录会保存一部分数据和下一页的地址，其他页使用链表的形式指向额外的页

InnoDB 页

页（Page）是 InnoDB 管理存储空间的基本单位，InnoDB 为了不同的目的而设计了许多种不同类型的页，比如存放表空间头部信息的页，存放 INODE 信息的页，存放 undo 日志信息的页等。索引（INDEX）页用于保存记录（record）数据和 B+ 树索引信息。下面将介绍一些 InnoDB 页的特性

InnoDB 页组成如下图所示

• File Header，页通用信息，比如页码，下/上一页的位置信息等等
  • InnoDB 存储引擎下每张表能存储的最大数据量是有限的（因为页码占用子节数是定长的），具体一张表最大可以保存多少数据可以参考官方文档 （16TB～256TB）
• Page Header，当前页有多少条记录、多少个槽等信息
• Infi+Supr，两个虚拟的最大最小记录，可类比于链表的首尾元素指针
• User Record，真实记录的保存位置，页内记录以单向链表的形式组织
• Free Space，页剩余可用空间
• Page Dir，为实现页内数据的快速查找而生成的二分查找信息
• File Trailer，页数据校验数据，前4字节保存校验和，后4字节保存日志序列位置（LSN）

数据页中的记录

以 compact 行格式为例，每页中的记录按照主键升序排列（没有设置主键就使用数据库自动插入的 ID），以单向链表的形式相互关联。为提高页内记录的查找速度，InnoDB 会对当前页内所有记录按升序进行分组并以数组的形式使用 Page Dir 保存相关信息，这样就可以利用二分法快速查找记录

保存原始数据的单向链表无法使用二分法，所以需要 Page Dir。默认索引只能使用主键（或者 ID，后续不再提示）进行快速查询，如果需要使用其他键进行快速查询，需要为对应的键建立索引。Page Dir 会保存每组最后一条记录的偏移量（存储于 Page Dir 中的每一个偏移量被称为一个 slot 槽），且每组最后一条记录的 n_owned 字段会保存当前组的记录数（MySQL 5.7 默认每组最多 8 条记录），所以使用 Page Dir 就可以快速的在不同组之间进行跳转

标记删除

数据库中记录的删除并不一定会触发记录的真实删除，即不会实时从磁盘中将对应的数据清理掉。InnoDB 会标记某一条记录是否被删除，下次插入新数据时可以重新使用这块空间，这样可以减少存储空间的分配次数

B+ 树与索引

InnoDB 使用 B+ 树保存数据库索引与记录（record）信息。InnoDB 在保存索引与记录时使用的页都是索引页，真实数据记录只会保存在叶子结点，非叶子结点只会保存索引信息。B 树和 B+ 树的区别可以参考其他资料【1】/ 【2】，两者主要区别是前者会在非叶子结点保存数据而后者不会

可以使用 record_type 实现页数据类型的判断（判断保存的是索引信息还是记录信息）。下图有两层索引层和最下面一层数据层，索引页一页可以保存很多子节点信息，假设个索引节点可以保存 100 条索引信息，那么 4 层索引可以保存 \(100^4\) 也就是 1 亿条数据的位置信息，进行 4 次页查询就可以搜索亿条数据，大大降低了内存和磁盘的交互次数

MyISAM 引擎的数据存储

MyISAM 和 InooDB 一样也使用树形结构保存索引，但 MyISAM 的记录数据是不分页的，所有数据都保存在相邻的数据块中，如下图所示

索引对性能的影响

InnoDB 默认的索引树（聚簇索引）其叶子结点会保存记录的真实数据，后续创建的索引（二级索引）其叶子节点只会保存记录的主键 ID，所以同一张表的所有索引之间强相关，数据的插入删除会强制修改所有索引

如上所述，给字段增加索引可以提高字段相关的查询速度，但同时会提高数据插入的复杂度，因为每次数据的插入所有索引都需要被更新（记录移位、页面分裂、页面回收等操作，这些操作有部分是B+树保存平衡性的操作）。所以索引需要按需创建且需要考虑键的属性（比如键的 DV Count）

MySQL 的索引适合如下任务：全值匹配、匹配左边的列、匹配范围值、精确匹配某一列并范围匹配另外一列、用于排序、用于分组

回表

非默认索引只会保存记录的主键，故在非默认索引中找到数据后需要拿着主键再去默认索引中查找对应的记录。这个过程被称为回表

回表机制的存在会影响索引的性能。如果非默认索引中查找到的数据对应默认索引而言太过分散，内存和硬盘之间页交换会非常频繁，从而影响整体性能

Buffer pools && LRU

MySQL 启动后会申请用于缓存 InnoBD 页的连续内存空间，默认是 128M（最小是 5MB）。为提高多线程处理速度，有大量可用空间时 MySQL 会使用多个 Buffer Pool，不同 Buffer Pool 处理不同的缓存页

为实现缓存页的管理，每个缓存页空间都有对应的控制块，控制块中有 free list ptr、flush list ptr、LRU list ptr 等信息，分别对应着未使用的缓存页、脏数据页，LRU 链表。注意这些链表所使用的指针都位于控制块内，修改控制块内的指针即可实现链表的修改。示例如下：

MySQL 使用链表保存 LRU 缓存页信息，**位于热点数据后部的页（比如所有热点数据块后 1/4 及以后）**在被使用时会被提升到 LRU 链表的头部，几乎没有使用的块，总是会保留在 LRU 链表的尾部。为减少预读对 LRU 链表的影响，MySQL 对 LRU 进行了分区，预读对数据一般使用冷数据块中的缓存页

Redo/Undo 日志

MySQL 直接操作的是内存中的数据页，而数据页与磁盘的同步不是实时的，如果内存数据页修改后突然断电，修改将无法同步到磁盘中。为解决这个问题，MySQL 引入了 Redo 日志的概念，每次执行真实操作前都将相应的修改写道 Redo 日志中，断电后系统将读取 Redo 日志与系统当前状态，修复数据未同步的问题

相比于内存数据页读写磁盘的随机性，Redo 日志是连续的存储空间且占用空间更小，所以速度上比数据页写磁盘要快。因 Redo 日志的特性，Redo 日志文件的数量和磁盘空间占用大小都是固定的

Redo 日志也有内存缓存区，在某些条件下日志会被强制同步到磁盘中，比如事务执行前、脏数据同步到磁盘、定时刷新任务等等

Undo 日志用于回滚（roll_pointer）操作

LSN（Log Sequence Number）

自系统开始运行，就不断的在修改页面，也就意味着会不断的生成redo日志。redo日志的量在不断的递增，InnoDB 设计了一个称之为Log Sequence Number的全局变量，翻译过来就是：日志序列号，简称lsn

索引与文件系统

MySQL 5.7 之前不同表的索引信息保存在操作系统角度的同一个文件中（系统表空间），MySQL 5.7 及之后的版本，每张表可以有其对应的独立的文件（独立表空间），配置文件中做如下配置可要求表使用独立的存储文件

[server]
innodb_file_per_table=1

与 InnoDB 不同，MyISAM 存储引擎默认不同表使用不同的存储文件

区 & 组

为方便管理，InnoDB 将页按照区和组进行进一步的组合，一般连续的 64 个页为一个区（1MB），连续的 256 个区为一组（256MB）

区的存在也是为了减少磁盘随机访问的可能，建立索引时以区为单位分配磁盘空间，尽量将相邻的页分配到连续的磁盘空间中

数据查询

MySQL 有查询优化器，SQL 语句经过查询优化器优化之后会选择合适的查询方式。数据查询可以分为如下两大类

1. 全表扫描，all 查询
2. 索引查询，只有为对应 key 创建索引且查询优化器认为索引有用才会使用二级索引
   1. 针对主键或唯一（unique 值）二级索引的等值查询，const 查询，速度最快
   2. 针对普通二级索引的等值查询，ref 查询。因为二级索引等值查询可能查到多个值，所以回表也可能有多个位置
   3. 针对索引列的范围查询，range 查询
   4. 直接扫描整个索引，index 查询。二级索引因为只存储了 ID ，所以扫描整个索引比扫描聚簇索引要快

MySQL 有多种方式创建二级索引，可以在创建表时指定需要创建索引的列，也可以在表创建之后再创建索引

为减少查询耗时，MySQL 会评估不同查询方式的成本，其评估过程大致如下：

1. 根据搜索条件，找出所有可能使用的索引
2. 计算全表扫描的代价
3. 计算使用不同索引执行查询的代价
4. 对比各种执行方案的代价，找出成本最低的那一个

查询优化器

一条查询语句在经过 MySQL 查询优化器的各种基于成本和规则的优化会后生成一个所谓的执行计划，这个执行计划展示了接下来具体执行查询的方式，比如多表连接的顺序是什么，对于每个表采用什么访问方法来具体执行查询等等。MySQL 提供了EXPLAIN语句来帮助我们查看某个查询语句的具体执行计划。如果我们想看看某个查询的执行计划的话，可以在具体的查询语句前边加一个EXPLAIN

如果想查看更详细的查询优化过程，可以使用 optimizer trace

锁

InnoDB 支持很多不同粒度的锁，比如表级锁行锁等等，本文不做叙述

PostgreSQL 简述

略

PostgreSQL 所使用的技术有不少和 InnoDB 类似，本文不再重复

FDW，外部数据包装器。使用 FDW，PSQL 可以访问 MySQL、HDFS、mongoDB 的数据库表文件