索引组织表

在 InnoDB 存储引擎中，表都是根据主键顺序组织存放的，这种存储方式的表称为索引组织表（index organized table）。在 InnoDB 存储引擎表中，每张表都有一个主键（Primary Key），如果在创建表时没有显式地定义主键，则 InnoDB 存储引擎会按如下方式选择或创建主键：

• 首先判断表中是否有非空的唯一索引（Unique NOT NULL），如果有，则该列即为主键。
• 如果不符合上述条件，InnoDB 存储引擎会自动创建一个 6 字节大小的指针。

当表中有多个非空唯一索引时，InnoDB 存储引擎将选择建表时第一个定义的非空唯一索引为主键。这里需要非常注意的是，主键的选择依据的是定义索引的顺序，而不是建表时列的顺序。

以下是一个示例：

1
2
3
4
5
6
7
8
9
10
11
12
13

mysql> CREATE TABLE z (
  a INT NOT NULL,
  b INT NULL,
  c INT NOT NULL,
  d INT NOT NULL,
  UNIQUE KEY (b),
  UNIQUE KEY (d), UNIQUE KEY (c)
);
Query OK, 0 rows affected (0.02 sec)

mysql> INSERT INTO z SELECT 1,2,3,4;
Query OK, 1 row affected (0.00 sec)
Records: 1 Duplicates: 0 Warnings: 0

虽然 c、d 列都是非空唯一索引， 都可以作为主键的候选，但是在定义的过程中，由于 d 列首先定义为唯一索引，故 InnoDB 存储引擎将其视为主键。

逻辑存储结构

从 InnoDB 存储引擎的逻辑存储结构看，所有数据都被逻辑地存放在一个空间中，称之为表空间（tablespace）。表空间又由段（segment）、区（extent）、页（page）组成。页在一些文档中有时也称为块（block），InnoDB 存储引擎的逻辑存储结构大致如下：

表空间

表空间可以看做是 InnoDB 存储引擎逻辑结构的最⾼层，所有的数据都存放在表空间中。在默认情况下 InnoDB 存储引擎有一个共享表空间 ibdata1，即所有数据都存放在这个表空间内。如果用户启用了参数 innodb_file_per_table，则每张表内的数据可以单独放到一个表空间内。

如果启用了 innodb_file_per_table 的参数，需要注意的是每张表的表空间内存放的只是数据、索引和插入缓冲 Bitmap 页，其他类的数据，如回滚信息、插入缓冲索引页、系统事务信息、双写缓冲等还是存放在原来的共享表空间内。这同时也说明了另一个问题：即使在启用了参数 innodb_file_per_table 之后，共享表空间还是会不断地增加其大小。

以 Undo 日志为例：在事务提交之前，共享表空间的空间占用会不断增长。而且 InnoDB 存储引擎不会在执行 rollback 时去收缩这个表空间。虽然 InnoDB 不会回收这些空间，但是会自动判断这些 Undo 信息是否还需要，如果不需要，则会将这些空间标记为可用空间，供下次 Undo 使用。

段

表空间是由多个段组成的，常见的段有数据段、索引段、回滚段等。因为前面已经介绍过了 InnoDB 存储引擎表是索引组织的，因此数据即索引，索引即数据。那么数据段即为 B+ 树的叶子节点**，索引段即为 B+ 树的非索引节点。回滚段包含了事务执行过程中用于数据回滚的旧数据。

区

段由一个或多个区组成，区通常为 64 个连续的页，也就是总共 1MB 的数据。为了保证页的连续性，InnoDB 存储引擎会一次从磁盘申请 4 ~ 5 个区。连续的256个数据区为一个数据区组。使用区而非单独的页进行数据分配可优化磁盘操作，减少索引时磁盘寻道时间，特别是在大量数据进行读写时。

但是，这里还有这样一个问题：在用户启用了参数 innodb_file_per_table 后，创建的表默认大小是 96KB。区中是 64 个连续的页，创建的表的大小至少是 1MB 才对啊？

其实是因为有时我们可能只是创建一个很小的表，只插入一条或几条数据，此时 直接分配 1MB 区块是很浪费的，所以在每个段开始时，先最多用 32 个页大小的碎片页（fragment page） 来存放数据（也就是数据页）；在使用完这些页之后才是 64 个连续页的申请。

页

页是 InnoDB 存储数据的基本单元，标准大小为 16 KB，索引树上的一个节点就是一个页，也就意味着数据库每次读写都是以 16 KB 为单位的，即一次最少从磁盘中读取 16KB 的数据到内存，一次最少写入 16KB 的数据到磁盘。

在 InnoDB 存储引擎中，常见的页类型有：

• 数据页（B-tree Node）
• undo 页（Undo Log Page）
• 系统页（System Page）
• 事务数据页（Transaction System Page）
• 插入缓冲位图页（Insert Buffer Bitmap）
• 插入缓冲空闲列表页（Insert Buffer Free List）
• 未压缩的二进制大对象页（Uncompressed BLOB Page）
• 压缩的二进制大对象页（Compressed BLOB Page）

行

InnoDB 存储引擎是面向行（row-oriented）的，也就是说数据是按行进行存放的。每个页存放的行记录也是有硬性定义的，最多允许存放 16KB / 2 ~ 200 行的记录，即 7992 行记录。

这里提到了 row-oriented 的数据库，也就是说，存在有 column-oriented 的数据库。

InnoDB 行记录格式

行数据拥有多中记录格式，如 COMPACT、REDUNDANT、DYNAMIC 等。

COMPACT

Compact 行记录是在 MySQL 5.0 中引入的，其设计目标是高效地存储数据。一个页中存放的行数据越多，其性能就越高。下图是 Compact 行记录的格式：

Compact 行记录格式的前部是一个非 NULL 变长字段长度列表，并且其是按照列的顺序逆序放置的。其长度为：

• 若列的长度小于 255 字节，用 1 字节表示；
• 若大于 255 字节，用 2 字节表示。

变长字段的长度最大不可以超过 2 字节，这是因在 MySQL 数据库中 VARCHAR 类型的最大长度限制为 65535。变长字段之后的第二个部分是 NULL 标志位，该位指示了该字段中是否有 NULL 值，有则用 1 表示。该部分所占的字节数应为 1 字节。接下来的部分是记录头信息（record header），固定占用 5 字节（40 位），每位的含义如下：

最后的部分就是实际存储每个列的数据。需要特别注意的是，NULL 不占该部分任何空间，即 NULL 除了占有 NULL 标志位，实际存储不占有任何空间。

另外有一点需要注意的是，每行数据除了用户定义的列外，还有两个隐藏列，分别是：

• 事务 ID 列（6 字节）
• 回滚指针列（7 字节）

共计额外占用 13 字节。

若 InnoDB 表没有定义主键，每行还会增加一个 6 字节的 rowid 列。

接下来用一个具体示例来分析 Compact 行记录 的内部结构：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE mytest (
  t1 VARCHAR(10),
  t2 VARCHAR(10),
  t3 CHAR(10),
  t4 VARCHAR(10)
) ENGINE=INNODB CHARSET=LATIN1 ROW_FORMAT=COMPACT;
mysql> INSERT INTO mytest VALUES ('a','bb','bb','ccc');
mysql> INSERT INTO mytest VALUES ('d','ee','ee','fff');
mysql> INSERT INTO mytest VALUES ('d',NULL,NULL,'fff');

表 mytest 有 4 个字段：

• t1，t2，t4 是 VARCHAR（变长）
• t3 是 CHAR（定长）

插入三条记录后，查看表空间文件 mytest.ibd。

找到某记录存储起点 0x0000c078，解释如下：

1
2
3
4
5
6
7
8
9
10
11

03 02 01    -- 变长字段长度列表，逆序

00       -- NULL 标志位（第一行无 NULL）

00 00 10 00 2c   -- Record Header（5 字节）

00 00 00 2b 68 00 -- RowID（6 字节）

00 00 00 00 06 05  -- Transaction ID（6 字节）

80 00 00 00 32 01 10 -- Roll Pointer（7 字节）

接下来是列数据（按顺序）：

1
2
3
4
5
6
7

61       -- 'a'

62 62     -- 'bb'

62 62 20 20 20 20 20 20 20 20 -- CHAR 类型需补齐

63 63 63    -- 'ccc'

现在第一行数据就展现在用户眼前了。需要注意的是，变长字段长度列表是逆序存放的，因此变长字段长度列表为 03 02 01，而不是 01 02 03。此外还需要注意 InnoDB 每行有隐藏列 TransactionID 和 Roll Pointer。同时可以发现，固定长度 CHAR 字段在未能完全占用其长度空间时，会用 0x20 来进行填充。

接着再来分析下 Record Header 的最后两个字节，这两个字节代表 next_recorder，0x2c 代表下一个记录的偏移量，即当前记录的位置加上偏移量 0x2c 就是下条记录的起始位置。所以 InnoDB 存储引擎在页内部是通过一种链表的结构来串连各个行记录的。

第二行将不做整理，除了 RowID 不同外，它和第一行大同小异。现在来关注有 NULL 值的第三行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

03 01/* 变长字段长度列表，逆序 */

06  /* NULL 标志位，第三行有 NULL 值 */

00 00 20 ff 98/* Record Header */

00 00 00 2b 68 02/* RowID */

00 00 00 00 06 07/* TransactionID */

80 00 00 00 32 01 10/* Roll Pointer */

64/* 列1 数据 'd' */

66 66 66/* 列4 数据 'fff' */

第三行有 NULL 值，因此 NULL 标志位不再是 00 而是 06，转换成二进制为 00000110，为 1 的值代表第 2 列和第 3 列的数据为 NULL。在其后存储列数据的部分，用户会发现没有存储 NULL 列，而只存储了第 1 列和第 4 列非 NULL 的值。因此这个例子很好地说明了：不管是 CHAR 类型还是 VARCHAR 类型，在 Compact 格式下 NULL 值都不占用任何存储空间。

行溢出数据

我们将过大的字段数据存放到溢出页中，目的是让每个数据页能够存储更多的数据行，也就是减少数据页的膨胀和磁盘 I/O。

Compact 和 Redundant

InnoDB 存储引擎可以将一条记录中的某些数据存储在页外的数据页而非页内。一般认为 BLOB，TEXT 这类的大对象列类型的存储会把数据存放在数据页页外。但是，这个理解有点偏差，BLOB 可以不将数据放在溢出页面，而且即便是 VARCHAR 列数据类型，依然有可能被存放为行溢出数据。

首先对 VARCHAR 数据类型进行研究。MySQL 数据库的 VARCHAR 类型可以存放 65535 字节。但是，是真的吗？真的可以存放 65535 字节吗？

如果创建 VARCHAR 长度为 65535 的表，用户会得到下面的错误信息：

1
2
3
4
5

mysql> CREATE TABLE test (
  -> a VARCHAR(65535)
  -> ) CHARSET=latin1 ENGINE=InnoDB;

ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. You have to change some columns to TEXT or BLOBs

从错误消息可以看到 InnoDB 存储引擎并不支持 65535 长度的 VARCHAR。这是因为还有别的开销，通过实际测试发现，能存储 VARCHAR 类型的最大长度为 65532。以上长度的单位都是字节⚠️。

此外需要注意的是，MySQL 官方手册中定义的 65535 长度是指所有 VARCHAR 列的长度总和。如果列的长度总和超过这个长度，依然无法创建。

但是有没有想过，InnoDB 存储引擎的页为 16KB，即 16384 字节，怎么能存放 65532 字节呢？

因此，在一般情况下，InnoDB 存储引擎的数据都是存放在页类型为 B-tree node 中。但是当发生行溢出时，数据存放在页类型为 Uncompress BLOB 页中。

来看下面一个例子：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE t (
  -> a VARCHAR(65532)
  -> ) ENGINE=InnoDB CHARSET=latin1;
Query OK, 0 rows affected (0.15 sec)

mysql> INSERT INTO t
  -> SELECT REPEAT('a', 65532);
Query OK, 1 row affected (0.08 sec)
Records: 1 Duplicates: 0 Warnings: 0

在上述例子中，首先创建了一个列 a 长度为 65532 的 VARCHAR 类型表 t，然后插入了列 a 长度为 65532 的记录。我们可查看表文件，内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

page offset 00000000, page type <File Space Header> 

page offset 00000001, page type <Insert Buffer Bitmap> 

page offset 00000002, page type <File Segment inode> 

page offset 00000003, page type <B-tree Node>, page level <0000> 

page offset 00000004, page type <Uncompressed BLOB Page> 

page offset 00000005, page type <Uncompressed BLOB Page> 

page offset 00000006, page type <Uncompressed BLOB Page> 

page offset 00000007, page type <Uncompressed BLOB Page> 

Total number of page: 8 

Insert Buffer Bitmap: 1

Uncompressed BLOB Page: 4

File Space Header: 1

B-tree Node: 1

File Segment inode: 1

可以观察到表空间中有一个数据页节点 B-tree Node，另外有 4 个未压缩的二进制大对象页（Uncompressed BLOB Page）。在这些页中才真正存放了 65532 字节 的数据。

既然实际存放的数据都在 BLOB 页中，那数据页中又存放了些什么内容呢？

可以看到，从 0x0000c093 到 0x0000c392 数据页中其实只保存了 VARCHAR(65532) 的前 768 字节的前缀（prefix）数据（这里都是 'a'），之后是偏移量，指向行溢出页，也就是前面用户看到的 Uncompressed BLOB Page。因此，对于行溢出数据，其结构如下图：

那么多长的 VARCHAR 是保存在单个数据页中的，从多长开始会保存在 BLOB 页呢？可以这样进行思考：InnoDB 存储引擎表是索引组织的，即 B+Tree 的结构，这样每个页中至少应该有两条记录（否则失去了 B+Tree 的意义，变成链表了）。因此，如果页中只能存放下一条记录，那么 InnoDB 存储引擎会自动将行数据存放到溢出页中。

考虑下面表的一种情况：

1
2
3
4
5
6
7
8
9
10
11
12

mysql> CREATE TABLE t (
  -> a VARCHAR(9000)
  -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.13 sec)

mysql> INSERT INTO t
  -> SELECT REPEAT('a', 9000);
Query OK, 1 row affected (0.04 sec)

mysql> INSERT INTO t
  -> SELECT REPEAT('a', 9000);
Query OK, 1 row affected (0.04 sec)

表 a 变长字段列的长度为 9000，故能存放在一个数据页中，但是这并不能保证两条长度为 9000 的记录都能存放在一个页中。此时查看磁盘文件，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

page offset 00000000, page type <File Space Header>

page offset 00000001, page type <Insert Buffer Bitmap>

page offset 00000002, page type <File Segment inode>

page offset 00000003, page type <B-tree Node>, page level <0000>

page offset 00000004, page type <Uncompressed BLOB Page>

page offset 00000005, page type <Uncompressed BLOB Page>

Total number of page: 6

Insert Buffer Bitmap: 1

Uncompressed BLOB Page: 2

File Space Header: 1

B-tree Node: 1

File Segment inode: 1

我们可知，确实行数据被存放到溢出页中。

但是，如果可以在一个页中至少放入两行数据，那 VARCHAR 类型的行数据就不会存放到 BLOB 页中去。经过多次试验测试，发现这个阈值的长度为 8098。

如用户建立一个列为 VARCHAR(8098) 的表，然后插入 2 条记录：

1
2
3
4
5
6
7
8
9
10

mysql> CREATE TABLE t (
  -> a VARCHAR(8098)
  -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.12 sec)

mysql> INSERT INTO t SELECT REPEAT('a', 8098);
Query OK, 1 row affected (0.04 sec)

mysql> INSERT INTO t SELECT REPEAT('a', 8098);
Query OK, 1 row affected (0.03 sec)

接着查看磁盘文件，可以发现此时的行记录都是存放在数据页中，而不是在 BLOB 页中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

page offset 00000000, page type <File Space Header>

page offset 00000001, page type <Insert Buffer Bitmap>

page offset 00000002, page type <File Segment inode>

page offset 00000003, page type <B-tree Node>, page level <0000>

page offset 00000004, page type <Freshly Allocated Page>

page offset 00000005, page type <Freshly Allocated Page>

Total number of page: 6

Freshly Allocated Page: 2

Insert Buffer Bitmap: 1

File Space Header: 1

B-tree Node: 1

File Segment inode: 1

另一个问题是，对于 TEXT 或 BLOB 的数据类型，用户总是以为它们是存放在 Uncompressed BLOB Page 中的，其实这也不准确。是否放在数据页中还是 BLOB 页中，和前面讨论的 VARCHAR 一样，至少保证一个页能存放两条记录。

当然既然用户使用了 BLOB 列类型，一般不可能存放长度这么小的数据。因此在大多数的情况下 BLOB 的行数据还是会发生行溢出，实际数据保存在 BLOB 页中，数据页只保存数据的前 768 字节。

Compressed 和 Dynamic

InnoDB 1.0.x 版本开始引入了新的文件格式（file format，用户可以理解为新的页格式），以前支持的 Compact 和 Redundant 格式称为 Antelope 文件格式，新的文件格式称为 Barracuda 文件格式。

Barracuda 文件格式下拥有两种新的行记录格式：Compressed 和 Dynamic。

新的两种记录格式对于存放在 BLOB 中的数据采用了完全的行溢出方式，如下图：

在数据页中只存放 20 个字节的指针，实际数据都存放在 Off Page 中，而之前的 Compact 和 Redundant 两种格式会存放 768 个前缀字节。

Compressed 行记录格式的另一个功能就是：存储在其中的行数据会以 zlib 的算法进行压缩，因此对于 BLOB、TEXT、VARCHAR 这类大长度类型的数据能进行非常有效的存储。

CHAR 的行结构存储

通常理解 VARCHAR 是存储变长度的字符类型，CHAR 是存储固定长度的字符类型。而在前面的内容中，我们可以发现每行的变长字段长度的列表都没有存储 CHAR 类型的长度。

然而，值得注意的是之前给出的两个例子中的字符集都是单字节的 latin1 格式。从 MySQL 4.1 版本开始，CHAR(N) 中的 N 指的是字符的长度，而不是之前版本的字节长度。

也就是说在不同的字符集中，CHAR 类型列内部存储的可能不是定长的数据。例如下面的这个示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

mysql> CREATE TABLE j (
  -> a CHAR(2)
  -> ) CHARSET=GBK ENGINE=InnoDB;
Query OK, 0 rows affected (0.11 sec)

mysql> INSERT INTO j SELECT 'ab';
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> SET NAMES GBK;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO j SELECT '我们';
Query OK, 1 row affected (0.04 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> INSERT INTO j SELECT 'a';
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

在上述例子中，表 j 的字符集是 GBK。用户分别插入了两个字符的数据 ‘ab’ 和 ‘我们’，然后查看所占字节，可得如下结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

mysql> SELECT a,CHAR_LENGTH(a),LENGTH(a)
  -> FROM j\G;
*************************** 1. row ***************************
a: ab
CHAR_LENGTH(a): 2
LENGTH(a): 2
*************************** 2. row ***************************
a: 我们
CHAR_LENGTH(a): 2
LENGTH(a): 4
*************************** 3. row ***************************
a: a
CHAR_LENGTH(a): 1
LENGTH(a): 1
3 rows in set (0.00 sec)

通过不同的 CHAR_LENGTH 和 CHAR 函数可以观察到：前两个记录 ‘ab’ 和 ‘我们’ 字符串的长度都是 2。但是内部存储上 ‘ab’ 占用 2 字节，而 ‘我们’ 占用 4 字节。如果通过 HEX 函数查看内部十六进制的存储，可以看到：

1
2
3
4
5
6
7
8
9
10
11
12

mysql> SELECT a,HEX(a)
  -> FROM j\G;
*************************** 1. row ***************************
a: ab
HEX(a): 6162
*************************** 2. row ***************************
a: 我们
HEX(a): CED2C3C7
*************************** 3. row ***************************
a: a
HEX(a): 61
3 rows in set (0.00 sec)

因此对于多字节字符编码，如 GBK、UTF-8 等，的 CHAR 数据类型的存储，InnoDB 存储引擎在内部将其视为变长字符类型。这也就意味着在变长长度列表中会记录 CHAR 数据类型的长度。

我们可查看磁盘文件：

整理后可以得到如下结果：

第一行记录：

1
2
3
4
5
6
7
8
9
10
11
12
13

02     /* 变长字段长度 2，将 CHAR 视作变长类型 */

00     /* NULL 标志位 */

00 00 10 00 1c /* Recoder Header */

00 00 00 b6 2b 2b /* RowID */

00 00 00 51 52 da /* TransactionID */

80 00 00 00 2d 01 10 /* Roll Point */

61 62   /* 字符 'ab' */

第二行记录：

1
2
3
4
5
6
7
8
9
10
11
12
13

04     /* 变长字段长度 4，将 CHAR 视作变长类型 */

00     /* NULL 标志位 */

00 00 18 ff d5 /* Recoder Header */

00 00 00 b6 2b 2c /* RowID */

00 00 00 51 52 db /* TransactionID */

80 00 00 00 2d 01 10 /* Roll Point */

c3 d2 c3 c7     /* 字符 '我们' */

第三行记录：

1
2
3
4
5
6
7
8
9
10
11
12
13

02     /* 变长字段长度 2，将 CHAR 视作变长类型 */

00     /* NULL 标志位 */

00 00 20 ff b7 /* Recoder Header */

00 00 00 b6 2b 2d /* RowID */

00 00 00 51 53 17 /* TransactionID */

80 00 00 00 2d 01 10 /* Roll Point */

61 20   /* 字符 'a' */

上述例子清楚地显示了 InnoDB 存储引擎内部对 CHAR 类型在多字节字符集类型的存储。CHAR 类型被明确视为变长字符类型，对于未能占满长度的字符还是填充 0x20。InnoDB 存储引擎内部对字符的存储和我们用 HEX 函数看到的也是一致的。因此可以认为在多字节字符集的情况下，CHAR 和 VARCHAR 的实际行存储基本是没有区别的。

InnoDB 数据页结构

InnoDB 数据页由以下 7 个部分组成，如下图所示：

1. File Header（文件头）
2. Page Header（页头）
3. Infimum 和 Supremum Records
4. User Records（用户记录，即行记录）
5. Free Space（空闲空间）
6. Page Directory（页目录）
7. File Trailer（文件结尾信息）

其中 File Header、Page Header、File Trailer 的大小是固定的，分别为 38、56、8 字节，这些空间用于标记该页的一些信息，如 Checksum、数据页所在 B+ 树索引的层数等。User Records、Free Space、Page Directory 这些部分为实际的行记录存储空间，因此大小是动态的。

下图中具体分析了数据页中的各组成部分：

File Header

File Header 用来记录页的一些头信息，由下图中的 8 个部分组成，共占用 38 字节。

下图是 InnoDB 中页的类型：

Page Header

接着 File Header 部分的是 Page Header，该部分用来记录数据页的状态信息，由 14 个部分组成，共占用 56 字节，如下图所示。

需要注意的是，这里的堆结构指的是页内记录的排布方式，并不是数据结构中的堆 heap，也就是在 InnoDB 的一个数据页中，行记录是按照一定规则存储在一个称为“堆”的区域中。这个“堆”具有以下特征：

1. 数据页内的记录不是顺序排布，而是通过链表和 slot 引用来组织的；
2. 堆中的第一个 slot 是 Infimum（表示最小值），最后一个是 Supremum（最大值）；
3. 每个记录都包含一个 next record 指针，指向下一条记录；
4. PAGE_HEAP_TOP：表示当前堆的顶部，新的记录一般会存入这里。

其次，PAGE_DIRECTION：最后插入的方向，这个属性记录了最后一条插入记录的方向，主要用于优化后续插入操作的位置判断，避免每次都从头或尾查找插入位置。

示例：

假设你有一个数据页，用于存储用户年龄的索引，页中原来已有以下记录（已按顺序）：

[20] -> [30] -> [40] -> [50]

现在你要往页里插入新的值：

情况 1：插入 [45]

它的插入位置在 [40] 和 [50] 之间：

• InnoDB 在查找插入位置时，可能从 PAGE_LAST_INSERT 指向的上一个插入位置（比如 [30]）出发。
• 发现现在是往右边插入的，所以：
  • 设置 PAGE_DIRECTION = PAGE_RIGHT（0x02）；
  • 这样下次如果还要插入更大的记录，比如 [48]，就可以直接从 [45] 或 [50] 向右查找，加速插入位置的定位。

情况 2：插入 [25]

• 插入位置在 [20] 和 [30] 之间，InnoDB 会发现你是在“往左边插入”，
• 设置 PAGE_DIRECTION = PAGE_LEFT（0x01）；
• 如果下次你又插入 [22]，系统会直接从上次插入的 [25] 向左找，避免从 Supremum 重新查找。

情况 3：乱序插入

• 你现在插入一条 [42]，下一次又插入 [21]，再下一次插入 [51]，插入方向完全没有规律；
• InnoDB 会识别到你插入方向变化太频繁，就会设置：
  • PAGE_DIRECTION = PAGE_NO_DIRECTION（0x05）；

这时候优化机制关闭，下次插入位置会重新全页查找。

Infimum 和 Supremum Record

在 InnoDB 存储引擎中，每个数据页中有两个模拟的行记录，用来限定记录的边界。Infimum 记录是比该页中任何主键值都要小的值，Supremum 指比任何可能大的值还要大的值。这两个值在页创建时被建立，并且在任何情况下不会被删除。而且在 InnoDB 中，这两个伪行记录的类型是 Char(8)。下图显示了 Infimum 和 Supremum 记录。

User Record 和 Free Space

User Record 就是之前讨论过的部分，即实际存储行记录的内容。再次强调，InnoDB 存储引擎表总是 B+ 树索引组织的。

Free Space 很明显指的就是空闲空间，同样也是个链表数据结构。在一条记录被删除后，该空间会被加入到空闲链表中。

Page Directory

Page Directory 是 InnoDB 数据页中的一个结构，用于帮助快速定位页内记录的位置。它相当于是数据页内部的一个加速查找索引，而且是逆序存放的。

和很多人以为的不同，InnoDB 并不是每条记录都在 Page Directory 中有一个指针。

相反，它是稀疏的目录（sparse directory），即：

• 一个槽通常指向一组记录中最前面的那条；
• 这组记录一般有 4～8 条，由 n_owned 表示。

n_owned 是什么？

n_owned 表示：该槽负责的记录数量。

假设某页中实际有 12 条记录，按主键顺序如下：

a b c d e f g h i j k l

可能在 Page Directory 中只存了以下 3 个槽指针：

Slot 1 -> a

Slot 2 -> e

Slot 3 -> i

这表示：

Slot 1 覆盖记录 a、b、c、d；

Slot 2 覆盖 e、f、g、h；

Slot 3 覆盖 i、j、k、l。

为什么这样做？稀疏目录的好处是什么？

好处是节省空间 + 提高效率：

• 若每条记录都在 Page Directory 里有个槽，占用空间太大；
• 稀疏存储后，只需要少量槽位，通过二分查找就可以迅速定位到一个“接近位置”；
• 然后用链表（通过 next_record 指针）继续遍历几条记录，就能找到目标。

查询流程小结

当你需要在页中找一个记录（比如查主键 = f）时，流程如下：

1. 从 Page Directory 中进行二分查找，发现 f 应该在 e 开头的槽中；
2. 然后从 e 出发，用链表结构沿着 next_record 指针遍历；
3. 依次到 f，查找成功。

⚠️ Page Directory 只是个“粗索引”，最终还要依赖链表来完成精确定位。

File Trailer

为了检测页是否已经完整地写入磁盘（如可能发生的写入过程中磁盘损坏、机器关机等），InnoDB 存储引擎的页中设置了 File Trailer 部分。

File Trailer 只有一个 FIL_PAGE_END_LSN 部分，占用 8 字节。前 4 字节代表该页的 checksum 值，最后 4 字节和 File Header 中的 FIL_PAGE_LSN 相同。将这两个值与 File Header 中的 FIL_PAGE_SPACE_OR_CHKSUM 和 FIL_PAGE_LSN 值进行比较，看是否一致（checksum 的比较需要通过 InnoDB 的 checksum 函数来进行比较，不是简单的等值比较），以此来保证页的完整性（not corrupted）。

在默认配置下，InnoDB 存储引擎每次从磁盘读取一个页就会检测该页的完整性，判断页是否发生 Corrupt，这就是通过 File Trailer 部分进行检测，而该部分的检测会有一定的开销。

InnoDB 数据页结构实例分析

在 MySQL 技术内幕的这一节中，Record Header 中的最后 2 字节内容代表的是下一行中实际存储数据的部分的初始位置。

以 0000c107 对应的行为例，我们从 0000c100 开始看：因为表中只存在一个 Char(10) 类型的字段，而且字符集是 UTF8，因此 Char 字段会被视为可变字符，并会在行记录的开始记录其长度 0a。之后的 00 代表该行中没有为 NULL 的字段，而且该行中页确实没有 NULL 字段。接着是 5 字节的 Header。之后是主键 00 00 00 05，因为该表中我们指定了主键且主键类型为 INT，因为这里存储的是 4 字节的主键的内容，而不是 6 字节的 ROWID。再就是 6 字节的 Transaction ID 和 7 字节的 Roll Pointer。最后是 10 字节的 Char 字段的数据。一共 34 个字节，正好对应着下一条行数据的实际存储数据的起始位置。Perfecto！

Named File Formats 机制

随着 InnoDB 存储引擎的发展，新的页数据结构有时用来支持新的功能特性。例如前面提到的 InnoDB 1.0.x 版本提供了新的页数据结构来支持表压缩功能，完全的溢出（Off page）大变长字符串类型字段的存储。这些新的页数据结构和之前版本的页并不兼容，因此从 InnoDB 1.0.x 版本开始，InnoDB 存储引擎通过 Named File Formats 机制来解决不同版本下页结构兼容性的问题。

InnoDB 存储引擎 1.0.x 版本之前的文件格式（file format）定义为 Antelope，将这个版本支持的文件格式定义为 Barracuda。新的文件格式总是包含之前版本的页格式。图 4-8 显示了 Barracuda 文件格式和 Antelope 文件格式之间的关系，Antelope 文件格式有 Compact 和 Redundant 的行格式，Barracuda 文件格式既包括了 Antelope 所有的文件格式，另外新加入了之前已经提到过的 Compressed 和 Dynamic 行格式。

分区表

分区功能并不是在存储引擎层完成的，因此不是只有 InnoDB 存储引擎支持分区，常见的存储引擎 MyISAM、NDB 等都支持。但也并不是所有的存储引擎都支持，如 CSV、FEDERATED、MERGE 等就不支持。在使用分区功能前，应该对选择的存储引擎对分区的支持有所了解。

MySQL 数据库在 5.1 版本时添加了对分区的支持。分区的过程是将一个表或索引分解为多个更小、更可管理的部分。就访问数据库的应用而言，从逻辑上讲，只有一个表或一个索引，但是在物理上这个表或索引可能由数个小物理分区组组成。每个分区都是独立的对象，可以独自处理，也可以作为一个更大对象的一部分进行处理。

MySQL 数据库支持的分区类型为水平分区，并不支持垂直分区。此外，MySQL 数据库的分区是局部分区索引，一个分区中既存放了数据又存放了索引。而全局分区是指，数据存放在各个分区中，但是所有数据的索引放在一个对象中。目前，MySQL 数据还不支持全局分区。

大多数人会有这样一个误区：只要启用了分区，数据库就会运行得更快。这个结论是存在很多问题的。就我的经验来看，分区可能会给某些 SQL 语句性能带来提高，但是分区主要用于数据库高可用性和性能的管理。在 OLTP 应用中，对于分区的使用应该非常小心。总之，如果只是一味地使用分区，而不理解分区是如何工作的，也不清楚你的应用如何使用分区，那么分区极有可能会对性能产生负面的影响。

目前 MySQL 数据库支持以下几种类型的分区：

• RANGE 分区：行数据基于属于一个给定连续区间的列值被放入分区。
• LIST 分区：和 RANGE 分区类似，只是 LIST 区间内的是离散的值。
• HASH 分区：根据用户自己定义的表达式的返回值来进行分区，返回值不能为负数。
• KEY 分区：根据 MySQL 数据库提供的哈希函数来进行分区。

你不能创建不带索引的分区，如果表中存在主键或唯一索引时，分区列必须是唯一索引的一个组成部分，因此下面创建分区的 SQL 语句会因缺少索引而产生错误：

1
2
3

mysql> create table t1 (id int not null, val int not null, unique key (id)) partition by hash(val) partitions 4;

ERROR 1503 (HY000): A PRIMARY KEY must include all columns in the table's partitioning function (prefixed columns are not considered).

唯一索引可以是允许 NULL 值的，并且分区列只要是唯一索引的一个组成部分，不需要整个唯一索引列都是分区列。

如果建表时没有指定主键，唯一索引，可以指定任何一个列为分区列。

分区类型

RANGE 分区

第一种分区类型是 RANGE 分区，也是最常用的一种分区类型。下面的 CREATE TABLE 语句创建了一个 id 列的区间分区表。当 id 小于 10 时，数据插入 p0 分区；当 id 大于等于 10 小于 20 时，数据插入 p1 分区。

1
2
3
4
5
6

CREATE TABLE t(
  id INT
) ENGINE=INNODB
PARTITION BY RANGE (id)(
  PARTITION p0 VALUES LESS THAN (10),
  PARTITION p1 VALUES LESS THAN (20));

查看表在磁盘上的物理文件，启用分区之后，表不再由一个 ibd 文件组成了，而是由建立分区时的各个分区 ibd 文件组成，如下面的 t#P#p0.ibd、t#P#p1.ibd：

1
2
3
4
5
6
7
8
9

mysql> system ls -lh /usr/local/mysql/data/test2/t*

-rw-rw---- 1 mysql mysql 8.4K 7月 31 14:11 /usr/local/mysql/data/test2/t.frm

-rw-rw---- 1 mysql mysql  28 7月 31 14:11 /usr/local/mysql/data/test2/t.par

-rw-rw---- 1 mysql mysql  96K 7月 31 14:12 /usr/local/mysql/data/test2/t#P#p0.ibd

-rw-rw---- 1 mysql mysql  96K 7月 31 14:12 /usr/local/mysql/data/test2/t#P#p1.ibd

接着插入如下数据：

1
2
3
4
5
6
7
8
9
10
11

mysql> INSERT INTO t SELECT 9;
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> INSERT INTO t SELECT 10;
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> INSERT INTO t SELECT 15;
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

因为表 t 根据列 id 进行分区，所以数据是根据列 id 的值的范围存放在不同的物理文件中的。

由于我们定义了分区，因此对于插入的值应该严格遵守分区的定义，当插入一个不在分区中定义的值时，MySQL 数据库会抛出一个异常。

LIST 分区

LIST 分区和 RANGE 分区非常相似，只是分区列的值是离散的，而非连续的。如：

1
2
3
4
5
6
7
8

mysql> CREATE TABLE t (
  -> a INT,
  -> b INT) ENGINE=INNODB
  -> PARTITION BY LIST(b)(
    -> PARTITION p0 VALUES IN (1,3,5,7,9),
    -> PARTITION p1 VALUES IN (0,2,4,6,8)
    -> );
Query OK, 0 rows affected (0.26 sec)

不同于 RANGE 分区中定义的 VALUES LESS THAN 语句，LIST 分区使用 VALUES IN。因为每个分区的值是离散的，因此只能定义值。

在用 INSERT 插入多个行数据的过程中遇到分区未定义的值时，MyISAM 和 InnoDB 存储引擎的处理完全不同。MyISAM 引擎会将之前的行数据都插入，但之后的数据不会被插入。而 InnoDB 存储引擎将其视为一个事务，因此没有任何数据插入。

HASH 分区

HASH 分区的主要目的是将数据均匀地分配到预定义的各个分区中，以确保每个分区中的数据量大致相同。与 RANGE 和 LIST 分区需要显式指定某个列值或值集合应存储在哪个分区不同，HASH 分区的分配过程由 MySQL 自动完成。用户只需基于用于分区的列，指定一个返回整数的表达式，同时设置表应被划分的分区数量即可。

要使用 HASH 分区来分割一个表，要在 CREATE TABLE 语句上添加一个：PARTITION BY HASH(expr) 子句，其中 expr 是一个返回一个整数的表达式。它可以仅仅是字段类型为 MySQL 整型的列名。此外，用户很可能需要在后面再添加一个：PARTITIONS num 子句，其中 num 是一个非负的整数，它表示表将要被分割成分区的数量。如果没有包括一个 PARTITIONS 子句，那么分区的数量将默认为 1。

MySQL 数据库还支持一种称为 LINEAR HASH 的分区，它使用一个更加复杂的算法来确定新行插入到已经分区的表中的位置。它的语法和 HASH 分区的语法相似，只是将关键字 HASH 改为 LINEAR HASH。MySQL 数据库根据以下的方法来进行分区的判断：

• 取大于分区数量 4 的下一个 2 的幂值 V，V = POWER(2, CEILING(LOG(2, num))) = 4；
• 所在分区 N = YEAR('2010-04-01') & (V - 1) = 2。

LINEAR HASH 分区的优点在于，增加、删除、合并和拆分分区将变得更加快捷，这有利于处理含有大量数据的表。它的缺点在于，与使用 HASH 分区得到的数据分布相比，各个分区间数据的分布可能不太均衡。

KEY 分区

KEY 分区和 HASH 分区相似，不同之处在于 HASH 分区使用用户定义的函数进行分区，KEY 分区使用 MySQL 数据库提供的函数进行分区。对于 InnoDB 存储引擎，MySQL 数据库使用其内部的哈希函数，这些函数基于与 PASSWORD() 一样的运算法则。如：

1
2
3
4
5
6

mysql> CREATE TABLE t_key (
  -> a INT,
  -> b DATETIME) ENGINE=InnoDB
 -> PARTITION BY KEY (b)
 -> PARTITIONS 4;
Query OK, 0 rows affected (0.43 sec)

在 KEY 分区中使用关键字 LINEAR 和在 HASH 分区中使用具有同样的效果，分区的编号是通过 2 的幂算法得到的，而不是通过模数算法。

COLUMNS 分区

在前面介绍的 RANGE、LIST、HASH 和 KEY 这四种分区中，分区的条件是：数据必须是整型，如果不是整型，那么就需要通过函数将其转化为整型，如 YEAR()、TO_DAYS()、MONTH() 等函数。MySQL 5.5 版本开始支持 COLUMNS 分区，可视为 RANGE 分区和 LIST 分区的一种进化。COLUMNS 分区可以直接使用非整型的数据进行分区，分区根据类型直接比较而得，不需要转化为整型。此外，RANGE COLUMNS 分区可以对多个列的值进行分区。

COLUMNS 分区支持以下的数据类型：

• 所有的整型类型，如 INT、SMALLINT、TINYINT、BIGINT。FLOAT 和 DECIMAL 则不予支持。
• 日期类型，如 DATE 和 DATETIME。其余的日期类型不予支持。
• 字符串类型，如 CHAR、VARCHAR、BINARY 和 VARBINARY。BLOB 和 TEXT 类型不予支持。

对于日期类型的分区，我们不再需要 YEAR() 和 TO_DAYS() 函数了，而是可以直接使用 COLUMNS，如：

1
2
3
4
5
6
7
8

CREATE TABLE t_columns_range(
  a INT,
  b DATETIME
) ENGINE=INNODB
PARTITION BY RANGE COLUMNS (B)(
  PARTITION p0 VALUES LESS THAN ('2009-01-01'),
  PARTITION p1 VALUES LESS THAN ('2010-01-01')
);

同样可以直接使用字符串的分区：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

CREATE TABLE customers_1 (
  first_name VARCHAR(25),
  last_name VARCHAR(25),
  street_1 VARCHAR(30),
  street_2 VARCHAR(30),
  city VARCHAR(15),
  renewal DATE
)
PARTITION BY LIST COLUMNS(city) (
  PARTITION pRegion_1 VALUES IN('Oskarshamn', 'Högsby', 'Mönsterås'),
  PARTITION pRegion_2 VALUES IN('Vimmerby', 'Hultsfred', 'Västervik'),
  PARTITION pRegion_3 VALUES IN('Nässjö', 'Eksjö', 'Vetlanda'),
  PARTITION pRegion_4 VALUES IN('Uppvidinge', 'Alvesta', 'Växjo')
);

对于 RANGE COLUMNS 分区，可以使用多个列进行分区，如：

1
2
3
4
5
6
7
8
9
10
11
12

CREATE TABLE rcx (
  a INT,
  b INT,
  c CHAR(3),
  d INT
) Engine=InnoDB
PARTITION BY RANGE COLUMNS(a,d,c) (
  PARTITION p0 VALUES LESS THAN (5,10,'ggg'),
  PARTITION p1 VALUES LESS THAN (10,20,'mmmm'),
  PARTITION p2 VALUES LESS THAN (15,30,'sss'),
  PARTITION p3 VALUES LESS THAN (MAXVALUE,MAXVALUE,MAXVALUE)
);

MySQL 5.5 开始支持 COLUMNS 分区，对于之前的 RANGE 和 LIST 分区，用户可以用 RANGE COLUMNS 和 LIST COLUMNS 分区进行很好的代替。

子分区

子分区（subpartitioning）是在分区的基础上再进行分区，有时也称这种分区为复合分区（composite partitioning）。MySQL 数据库允许在 RANGE 和 LIST 的分区上再进行 HASH 或 KEY 的子分区，如：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE ts (a INT, b DATE) ENGINE=InnoDB
 -> PARTITION BY RANGE (YEAR(b))
 -> SUBPARTITION BY HASH (TO_DAYS(b))
 -> SUBPARTITIONS 2 (
   -> PARTITION p0 VALUES LESS THAN (1990),
   -> PARTITION p1 VALUES LESS THAN (2000),
   -> PARTITION p2 VALUES LESS THAN MAXVALUE
 );
Query OK, 0 rows affected (0.01 sec)

表 ts 被 范围分区成 p0、p1、p2；

每个主分区又被 子分区（HASH） 成两个子分区，比如 p0 变成：p0sp0、p0sp1；

最终形成了 3（主分区） × 2（子分区） = 6 个物理分区。

子分区的建立需要注意以下几个问题：

• 每个子分区的数量必须相同。
• 要在一个分区表的任何分区上使用 SUBPARTITION 来明确定义任何子分区，就必须定义所有的子分区。
• 每个 SUBPARTITION 子句必须包括子分区的一个名字。
• 子分区的名字必须是唯一的。

子分区可以用于特别大的表，在多个磁盘间分别分配数据和索引。MySQL 本身并不直接支持通过语法控制每个分区或子分区映射到哪个磁盘路径，但你可以通过以下方式间接实现这一点：

操作方法一：使用多个表空间 + DATA DIRECTORY 和 INDEX DIRECTORY

MyISAM 引擎可以使用如下方式手动指定每个分区/子分区存放的目录（通常每个目录挂载不同磁盘）：

1
2
3
4
5
6
7
8
9
10
11
12

CREATE TABLE big_table (
  id INT,
  name VARCHAR(100)
)
ENGINE = MyISAM
PARTITION BY HASH(id)
PARTITIONS 6 (
  PARTITION p0 DATA DIRECTORY = '/disk0/data' INDEX DIRECTORY = '/disk0/index',
  PARTITION p1 DATA DIRECTORY = '/disk1/data' INDEX DIRECTORY = '/disk1/index',
  ...
  PARTITION p5 DATA DIRECTORY = '/disk5/data' INDEX DIRECTORY = '/disk5/index'
);

⚠️ 仅支持 MyISAM，不支持 InnoDB。并且要求 innodb_file_per_table=OFF，否则无效。

操作方法二：使用 Linux 下的软链接（适用于 InnoDB）

虽然 InnoDB 不支持 DATA DIRECTORY 语法，但可以使用 软链接 将分区/子分区文件（.ibd）手动移动到不同磁盘，如：

步骤：

一、创建分区表（比如在 /var/lib/mysql 中）：

1
2
3
4
5
6
7
8

CREATE TABLE big_partition (
  id INT,
  dt DATE
) ENGINE=InnoDB
PARTITION BY RANGE (YEAR(dt)) (
  PARTITION p0 VALUES LESS THAN (2020),
  PARTITION p1 VALUES LESS THAN (2025)
);

二、关闭 MySQL 服务

移动分区数据文件到其他磁盘目录

1
2
3

mv /var/lib/mysql/db/big_partition#P#p0.ibd /disk0/big_partition#P#p0.ibd

ln -s /disk0/big_partition#P#p0.ibd /var/lib/mysql/db/big_partition#P#p0.ibd

三、重启 MySQL 服务

⚠️ 你必须启用 innodb_file_per_table=1 且使用独立表空间

操作方法三：使用 LVM 或 RAID 逻辑卷

将多个磁盘组合成一个逻辑卷，然后整个 MySQL 数据目录或表空间都部署在这个卷上，由底层逻辑卷管理器决定调度和负载均衡，对 MySQL 透明。

分区中的 NULL 值

MySQL 数据库允许对 NULL 值做分区，但是处理的方法与其他数据库可能完全不同。MySQL 数据库的分区是视 NULL 值小于任何一个非 NULL 值，这和 MySQL 数据库中处理 NULL 值的 ORDER BY 操作是一样的。因此对于不同的分区类型，MySQL 数据库对于 NULL 值的处理也是各不相同。

对于 RANGE 分区，如果向分区列插入了 NULL 值，则 MySQL 数据库会将该值放入最左边的分区。例如：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE t_range(
  a INT,
  b INT) ENGINE=InnoDB
  PARTITION BY RANGE(b)(
    PARTITION p0 VALUES LESS THAN (10),
    PARTITION p1 VALUES LESS THAN (20),
    PARTITION p2 VALUES LESS THAN MAXVALUE
  );
Query OK, 0 rows affected (0.01 sec)

接着向表中插入 (1,1)、(1,NULL) 两条数据，并观察每个分区中记录的数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

mysql> INSERT INTO t_range SELECT 1,1;
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO t_range SELECT 1,NULL;
Query OK, 1 row affected (0.00 sec)

mysql> SELECT * FROM t_range\G;
*************************** 1. row ***************************
a: 1
b: 1
*************************** 2. row ***************************
a: 1
b: NULL
2 rows in set (0.00 sec)

可以看到两条数据都放入了 p0 分区，也就是说在 RANGE 分区下，NULL 值会放入最左边的分区中。另外需要注意的是，如果删除 p0 这个分区，删除的将是小于 10 的记录，并且还有 NULL 值的记录，这点非常重要：

1
2
3
4
5
6

mysql> ALTER TABLE t_range DROP PARTITION p0;
Query OK, 0 rows affected (0.01 sec)
Records: 0 Duplicates: 0 Warnings: 0

mysql> SELECT * FROM t_range;
Empty set (0.00 sec)

在 LIST 分区下要使用 NULL 值，则必须显式地指出哪个分区中放入 NULL 值，否则会报错，如：

1
2
3
4
5
6
7
8
9
10
11

mysql> CREATE TABLE t_list(
  -> a INT,
  -> b INT) ENGINE=INNODB
 -> PARTITION BY LIST(b)(
   -> PARTITION p0 VALUES IN (1,3,5,7,9),
   -> PARTITION p1 VALUES IN (0,2,4,6,8)
 );
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO t_list SELECT 1, NULL;
ERROR 1526 (HY000): Table has no partition for value NULL

若 p0 分区允许 NULL 值，则插入不会报错：

1
2
3
4
5
6
7
8
9
10
11
12

mysql> CREATE TABLE t_list(
  -> a INT,
  -> b INT) ENGINE=INNODB
 -> PARTITION BY LIST(b)(
   -> PARTITION p0 VALUES IN (1,3,5,7,9,NULL),
   -> PARTITION p1 VALUES IN (0,2,4,6,8)
 );
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO t_list SELECT 1, NULL;
Query OK, 1 row affected (0.00 sec)
Records: 1 Duplicates: 0 Warnings: 0

HASH 和 KEY 分区对于 NULL 的处理方式和 RANGE 分区、LIST 分区不一样。任何分区函数都会将含有 NULL 值的记录返回值为 0。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

mysql> CREATE TABLE t_hash(
  -> a INT,
  -> b INT) ENGINE=InnoDB
 -> PARTITION BY HASH(b)
 -> PARTITIONS 4;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO t_hash SELECT 1,0;
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO t_hash SELECT 1,NULL;
Query OK, 1 row affected (0.01 sec)

mysql> SELECT table_name, partition_name, table_rows
  -> FROM information_schema.PARTITIONS
  -> WHERE table_schema=DATABASE() AND table_name='t_hash'\G;
*************************** 1. row ***************************
table_name: t_hash
partition_name: p0
table_rows: 2
*************************** 2. row ***************************
table_name: t_hash
partition_name: p1
table_rows: 0
*************************** 3. row ***************************
table_name: t_hash
partition_name: p2
table_rows: 0
*************************** 4. row ***************************
table_name: t_hash
partition_name: p3
table_rows: 0
4 rows in set (0.00 sec)

分区和性能

我们常听到开发人员说“对表做个分区”，然后数据库的查询就会快了。这是真的么？实际上可能根本感受不到查询速度的提升，甚至会发现查询速度会明显下降。因此，若要合理使用分区之前，必须了解分区的使用环境。

数据库的应用大致分为两类：一类是 OLTP（在线事务处理），如 Blog、电子商务、网络游戏等；另一类是 OLAP（在线分析处理），如数据仓库、数据挖掘。在一个实际的应用环境中，可能看上去属于 OLTP 的应用，也有 OLAP 的应用。例如游戏平台，玩家操作的数据游戏数据库应用属 OLTP 的，但游戏平台厂商可能需要对玩家产生的日志进行分析，通过分析得到的结果来更好地服务于游戏，预测玩家的行为等，而这却是 OLAP 的应用。

对于 OLAP 的应用，分区的确是可以很好地提高查询的性能，因为 OLAP 应用大多数查询需要频繁地扫描一张很大的表。假设有一张 1 亿行的表，其中有一个时间戳属性列，用户的查询需要从这张表中获取一年的数据。如果按照时间戳进行分区，则只需要扫描相应的区即可，这就是前面介绍的 Partition Pruning 技术。

但对于 OLTP 的应用，分区这时就会小心。在这种应用下，通常不可能会去获取一张大表中 10% 的数据，大家的查询是通过索引定位几条记录即回，而根据 B+ 树结构的原理可知，对于一张大表，一般的 B+ 树需要 2～3 次的磁盘 IO。因此 B+ 树可以很好地完成检索，不需要分区的帮助，并且设计不好的分区会带来严重的性能问题。

我发现很多开发团队会认为含有 1000W 行的表是一张非常巨大的表，所以他们往往会选择采用分区，如对主键做 10 个 HASH 的分区，这样每个分区就只有 100W 的数据；同时他们应该这样更快了，SELECT * FROM t WHERE pk=@pk。但他们没有考虑过这样一种情况：100W 和 1000W 行的数据本身构成的 B+ 树的层级是一样的，而查找都是 2 层。那么上述主键分区的索引并不会带来性能的提升。好吧，如果 1000W 的 B+ 树的高度是 3，100W 的 B+ 树的高度是 2，那么上述主键分区的索引可以避免 1 次 IO，从而提高查询的效率。这没问题，但是张表只有主键索引，没有任何其他的列需要建立查询的。如果还有这样的 SQL 语句：SELECT * FROM TABLE WHERE KEY=@key，这时对于 KEY 的查询要扫描所有的 10 个分区，即使每个分区的查询开销为 2 次 IO，则一共需要 20 次 IO。而对于原来单表的设计，对于 KEY 的整查询只需要 2～3 次 IO。

接着来看如下的表 Profile，根据主键 ID 进行了 HASH 分区，HASH 分区的数据为 10，表 Profile 有接近 1000W 的数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

mysql> CREATE TABLE `Profile` (
  -> `id` int(11) NOT NULL AUTO_INCREMENT,
  -> `nickname` varchar(20) NOT NULL DEFAULT '',
  -> `password` varchar(32) NOT NULL DEFAULT '',
  -> `sex` char(1) NOT NULL DEFAULT '',
  -> `rdate` date NOT NULL DEFAULT '0000-00-00',
  -> PRIMARY KEY (`id`),
  -> KEY `nickname` (`nickname`)
  -> ) ENGINE=InnoDB
 -> PARTITION BY HASH (id)
 -> PARTITIONS 10;
Query OK, 0 rows affected (1.29 sec)

mysql> SELECT COUNT(nickname) FROM Profile;
*************************** 1. row ***************************
count(1): 9999248
1 row in set (1 min 24.62 sec)

因为是根据 HASH 分区的，所以每个区分的记录数大致是相同的，即数据分布比较均匀：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

mysql> SELECT table_name, partition_name, table_rows
  -> FROM information_schema.PARTITIONS
  -> WHERE table_schema=DATABASE() AND table_name='Profile'\G;
*************************** 1. row ***************************
table_name: Profile
partition_name: p0
table_rows: 990703
*************************** 2. row ***************************
table_name: Profile
partition_name: p1
table_rows: 1086519
*************************** 3. row ***************************
table_name: Profile
partition_name: p2
table_rows: 976474
*************************** 4. row ***************************
table_name: Profile
partition_name: p3
table_rows: 986937
*************************** 5. row ***************************
table_name: Profile
partition_name: p4
table_rows: 993667
*************************** 6. row ***************************
table_name: Profile
partition_name: p5
table_rows: 978046
*************************** 7. row ***************************
table_name: Profile
partition_name: p6
table_rows: 990703
*************************** 8. row ***************************
table_name: Profile
partition_name: p7
table_rows: 978639
*************************** 9. row ***************************
table_name: Profile
partition_name: p8
table_rows: 1085334
*************************** 10. row ***************************
table_name: Profile
partition_name: p9
table_rows: 982788
10 rows in set (0.80 sec)

注意：即使是根据自增长主键进行的 HASH 分区，也不能保证分区数据的均匀。因为插入的自增长 ID 并非总是连续的，如果该主键值因为某种原因被回滚了，则该值将不会再次被自动使用。

如果进行主键的查询，可以发现分区的确是有意义的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

mysql> EXPLAIN PARTITIONS SELECT * FROM Profile WHERE id=1\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: Profile
partitions: p1
type: const
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: const
rows: 1
Extra:
1 row in set (0.00 sec)

可以发现只寻找了 p1 分区，但是对于表 Profile 中 nickname 列索引的查询，EXPLAIN PARTITIONS 则会得到如下的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

mysql> EXPLAIN PARTITIONS
  -> SELECT * FROM Profile WHERE nickname='david'\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: Profile
partitions: p0,p1,p2,p3,p4,p5,p6,p7,p8,p9
type: ref
possible_keys: nickname
key: nickname
key_len: 62
ref: const
rows: 10
Extra: Using where
1 row in set (0.00 sec)

可以看到，MySQL 数据库会搜索所有分区，因此查询速度上会慢很多。比较上述语句：

1
2
3
4
5
6
7
8

mysql> SELECT * FROM Profile WHERE nickname='david'\G;
*************************** 1. row ***************************
id: 5566
nickname: david
password: 3e35d1025659d07ae28e0069ec51ab92
sex: M
rdate: 2003-09-20
1 row in set (1.05 sec)

上述简单的索引查找语句竟然需要 1.05 秒，这是因为查询需要遍历所有分区的关系，实际上的 IO 执行了约 20～30 次。而在未分区的同样结构和大小的表上，执行上述同样的 SQL 语句只需要 0.26 秒。

因此对于使用 InnoDB 存储引擎作为 OLTP 应用的表在使用分区时应该十分小心，设计时确认数据的访问模式，否则在 OLTP 应用下分区可能不仅不会带来查询速度的提高，反而可能会使你的应用执行得更慢。

在表和分区间交换数据

MySQL 5.6 开始支持 ALTER TABLE … EXCHANGE PARTITION 语法。该语句允许分区或子分区中的数据与另一个非分区的表中的数据进行交换。如果非分区中的数据为空，那么相当于将分区中的数据移动到非分区表中；若分区表中的数据为空，则相当于将外部表中的数据导入到分区中。

要使用 ALTER TABLE … EXCHANGE PARTITION 语句，必须满足下面的条件：

• 要交换的表需和分区表有相同的表结构，但表不能包含分区；
• 在非分区表中的数据必须在交换的分区定义内；
• 被交换的表中不能有外键，或者其他的表含有对该表的外键引用；
• 用户除了需要 ALTER、INSERT 和 CREATE 权限外，还需要 DROP 的权限。

此外，有两个小细节也需要注意：

• ⚠️ 使用该语句时，不会触发交换表和被交换表上的触发器；
• ⚠️ AUTO_INCREMENT 列将被重置。

Greedy Dual Size (GDS) algorithm

Key Concepts:

1. Variable Size and Cost:
   • Unlike simple algorithms that treat all objects equally, GDS takes into account:
     • Size of the object (size(p)): Larger objects take up more space in memory.
     • Cost of the object (cost(p)): This can represent factors like time to retrieve the object, computational effort, or other resource usage.
2. Score H(p):
   • Each key-value pair ppp in the cache is assigned a score H(p). This score reflects the benefit of keeping the object in memory and is calculated using:
     • A global parameter L, which adjusts dynamically based on cache state.
     • The size(p) of the object.
     • The cost(p) associated with the object.
3. Eviction Strategy:
   • When the cache is full, and a new object needs to be added, GDS removes the object with the lowest score H(p). This process continues until there is enough space for the new object.

Proposition 1

L is non-decreasing over time.

• The global parameter L, which reflects the minimum priority H(p) among all key-value pairs in the KVS, will either stay the same or increase with each operation. This ensures stability and helps prioritize eviction decisions consistently.

For any key-value pair ppp in the KVS, the relationship holds:

L ≤ H(p) ≤ L + cost(p) / size(p)

• H(p), the priority of p, always lies between the global minimum L and L + cost(p) / size(p), ensuring H(p) reflects both its retrieval cost and size relative to other elements.

Intuition Behind Proposition 1:

• As L increases over time (reflecting the minimum H(p)), less recently used or less “valuable” pairs become increasingly likely to be evicted. This ensures that newer and higher-priority pairs stay in the KVS longer.

Key Insights from Proposition 1:

1. Delayed Eviction:
   • When p is requested again while in memory, its H(p) increases to L + cost(p) / size(p), delaying its eviction.
2. Impact of Cost-to-Size Ratio:
   • Pairs with higher cost(p) / size(p) stay longer in the KVS. For example, if one pair’s ratio is c times another’s, it will stay approximately c times longer.

Key Points in the Diagram

1. Cost-to-Size Ratios:
   1. Key-value pairs are grouped into queues according to their cost-to-size ratio.
   2. Each queue corresponds to a specific cost-to-size ratio.
2. Grouping by Ratio:
   1. Within each queue, key-value pairs are managed using the Least Recently Used (LRU) strategy.
3. Priority Management:
   1. The priority (H-value) of a key-value pair is based on: H(p) = L + cost(p) / size(p)
      1. L: The global non-decreasing variable.
      2. cost(p) / size(p): The cost-to-size ratio of the key-value pair.
4. Efficient Eviction:
   1. CAMP maintains a heap that points to the head of each queue, storing the minimum H(p) from every queue.
   2. To identify the next key-value pair for eviction:
      1. The algorithm checks the heap to find the queue with the smallest H(p).
      2. It then evicts the key-value pair at the front of that queue (i.e., the least recently used pair in that cost-to-size group).

Rounding in CAMP

1. Purpose: To improve performance, CAMP reduces the number of LRU queues by grouping key-value pairs with similar cost-to-size ratios into the same queue.
2. Key Idea: Preserve the most significant bits proportional to the value’s size.

Proposition 2: Explanation of Rounding and Distinct Values

Implications

1. Trade-Off Between Precision and Efficiency:

   • A higher p preserves more precision but increases the number of distinct values (and thus computational complexity).

   • Lower p reduces the number of distinct values, making CAMP more efficient but less precise.

2. Rounding Efficiency:

   • By limiting the number of distinct values, CAMP minimizes the number of LRU queues, reducing overhead while still approximating GDS closely.

Proposition 3: Competitive Ratio of CAMP

Practical Implications

1. Precision ppp:

   • The smaller the ϵ (higher ppp), the closer CAMP approximates GDS.

   • For sufficiently large p, CAMP performs nearly as well as GDS.

2. Trade-off:

   • Higher p increases precision but also increases the number of distinct cost-to-size ratios and computational overhead.

CAMP’s Improvement Over GDS:

1. Approximation: CAMP simplifies H(p) by rounding the cost-to-size ratio, reducing the precision but making the algorithm more efficient.
2. Grouping: Key-value pairs are grouped by similar cost-to-size ratios, reducing the number of queues and simplifying priority management.
3. Tie-Breaking: CAMP uses LRU within each group to determine the eviction order, making it computationally cheaper.

Figure 4: Heap Node Visits

This figure compares the number of heap node visits for GDS and CAMP as a function of cache size:

1. GDS:

   • Heap size equals the total number of key-value pairs in the cache.

   • Every heap update (insertion, deletion, or priority change) requires visiting O(log⁡n) nodes, where n is the number of cache entries.

   • As cache size increases, GDS’s overhead grows significantly.

2. CAMP:

   • Heap size equals the number of non-empty LRU queues, which is much smaller than the total number of cache entries.

   • Heap updates occur only when:

     • The priority of the head of an LRU queue changes.

     • A new LRU queue is created.

   • As cache size increases, the number of non-empty LRU queues remains relatively constant, resulting in fewer heap updates.

Evaluation

(a) Cost-Miss Ratio vs Precision

• 横轴：精度（Precision），从低到高。
• 纵轴：成本未命中比（Cost-Miss Ratio）。
• 结果：
  • 不同的缓存大小比（0.01、0.1 和 0.3）在较低精度下表现一致。
  • 提高精度后，成本未命中比没有显著变化。
  • 说明即使使用较低精度，CAMP 的成本未命中比也能接近 GDS（标准实现）。

(b) LRU Queues vs Precision

• 横轴：精度（Precision）。
• 纵轴：CAMP 维护的非空 LRU 队列数量。
• 结果：
  • 低精度（1-5）：CAMP 维持稳定的少量 LRU 队列（约 5 个）。
  • 高精度（>10）：队列数增加，尤其是在较大的缓存大小比（如 1.0）下。
  • 结论：
    • 在较低精度下，CAMP 能保持较低的计算开销，同时维持高效的队列管理。

(c) Cost-Miss Ratio vs Cache Size Ratio

• 横轴：缓存大小比（Cache Size Ratio），即缓存大小与 trace 文件中唯一键值对总大小的比值。
• 纵轴：成本未命中比（Cost-Miss Ratio）。
• 结果：
  • CAMP：
    • 在所有缓存大小下，成本未命中比最低。
    • 说明 CAMP 在高成本键值对管理上更具效率。
  • Pooled LRU：
    • 在较小缓存下表现稍差，但随着缓存增加，接近 CAMP。
  • LRU：
    • 成本未命中比始终最高。
  • 结论：
    • CAMP 优于 LRU 和 Pooled LRU，尤其是在小缓存下。

(d) Miss Rate vs Cache Size Ratio

• 横轴：缓存大小比（Cache Size Ratio）。
• 纵轴：未命中率（Miss Rate）。
• 结果：
  • CAMP：
    • 未命中率显著低于 LRU 和 Pooled LRU，尤其在小缓存下表现最优。
  • Pooled LRU：
    • 未命中率随着缓存增大而下降，但始终高于 CAMP。
    • 最低成本池（cheapest pool）未命中率接近 100%，次低成本池未命中率达到 65%。
  • LRU：
    • 始终高于 CAMP 和 Pooled LRU。
  • 结论：
    • CAMP 在多种缓存大小下都保持较低的未命中率，且比 Pooled LRU 更均衡。

CAMP 的适应能力：访问模式变化的分析

实验设置：

• 使用 10 个不同的 trace 文件，每个文件包含 400 万个键值对引用。
• 每个 trace 文件（如 TF1、TF2 等）中的请求在其结束后不会再被引用，模拟访问模式的突然变化。
• 访问模式具有倾斜分布（如 Zipf 分布），每个 trace 文件中的高成本对象可能在下一次访问中完全无效。

目标：

• 比较 CAMP、Pooled LRU 和 LRU 在不同缓存大小下对访问模式突变的适应能力。
• 评估三种算法在突然变化后清除旧的高成本键值对的效率，以及对总体性能（如成本未命中比和未命中率）的影响。

不同算法的行为分析

1. LRU：

   • 按最近使用排序，当新请求的总大小超过缓存大小时清除旧数据。

   • 当缓存大小比为 1 时，清除 TF1 数据的时间点对应于 TF3 开始请求的第一个键值对。

2. Pooled LRU：

   • 将键值对按成本分组，每组分配固定比例的缓存空间。

   • 高成本池占据 99% 的缓存空间，因此在每个新 trace 开始时会突然清除一批旧数据。

   • 对于缓存大小比 2/3 或更高的情况，直到 TF4（约 800 万请求后）才会清除所有 TF1 数据。

3. CAMP：

   • 对每个成本-大小比维护 LRU 队列，这些队列的大小可以动态调整。

   • 优先淘汰较低优先级的数据，但高成本数据即使来自旧 trace，也具有一定保留优先级。

   • 当新数据的总大小超过缓存时，旧 trace 的高成本数据才会被逐步清除。

图 6c：缓存比 0.25（小缓存）

1. LRU：

   • 清除最快，仅需 2.1 万次请求 即完全清除 Trace 1 的所有键值对。

   • 由于 LRU 优先淘汰最久未使用的数据，小缓存下表现最佳。

2. Pooled LRU：

   • 清除速度较慢，需要 13.1 万次请求。

   • 原因：Pooled LRU 按成本对键值对分组，高成本池占用较多缓存空间，导致清除滞后。

3. CAMP：

   • 初期清除速度比 Pooled LRU 更快，但最后完全清除所有键值对需到 TF3 结束（770 万次请求）。

   • 然而，这些未被清除的 Trace 1 数据仅占缓存的 2%，说明 CAMP 优先保留了高成本键值对。

图 6d：缓存比 0.75（大缓存）

1. LRU：

   • 同样清除最快，几乎在 Trace 2 开始时就清除掉大部分 Trace 1 的数据。

   • 说明即使缓存较大，LRU 仍然倾向淘汰旧数据。

2. Pooled LRU：

   • 清除延迟显著，需要 730 万次请求，接近 TF3 结束。

   • 原因：高成本池占用过多缓存空间，延迟清除低成本和无用数据。

3. CAMP：

   • 大部分 Trace 1 数据在较早阶段被淘汰，仅保留少量最昂贵的键值对（占缓存比小于 0.6%）。

   • 即使在 4000 万次请求后，这些高成本键值对仍在缓存中，但对整体缓存利用影响极小。

针对不同大小但成本相同的键值对，CAMP 优先保留较小的键值对，从而降低未命中率和成本未命中比。

针对相同大小但成本不同的键值对，CAMP 优先保留高成本键值对，在成本未命中比上显著优于其他算法。

与其他算法的对比：

• LRU：适用于简单场景，但无法处理成本差异。

• Pooled LRU：小缓存情况下表现不错，但静态分区策略限制了其大缓存场景的效率。

CAMP 的适应性：在处理多样化的成本分布时，通过动态调整和四舍五入策略，CAMP 在复杂负载下表现出更高的灵活性和效率。

Questions

What is the time complexity of LRU to select a victim?

O(1) because the least recently used item is always at the tail of the list.

What is the time complexity of CAMP to select a victim?

O(logk) CAMP identifies the key-value pair with the smallest priority from the heap, deletes it and then heapifies.

Why does CAMP do rounding using the high order bits?

• CAMP rounds cost-to-size ratios to reduce the number of distinct ratios (or LRU queues).
• High-order bits are retained because they represent the most significant portion of the value, ensuring that approximate prioritization is maintained.

How does BG generate social networking actions that are always valid?

Pre-Validation of Actions:

• Before generating an action, BG checks the current state of the database to ensure the action is valid. For instance:
  • A friend request is only generated if the two users are not already friends or in a “pending” relationship.
  • A comment can only be posted on a resource if the resource exists.

Avoiding Concurrent Modifications:

• BG prevents multiple threads from concurrently modifying the same user’s state.

How does BG scale to a large number of nodes?

BG employs a shared-nothing architecture with the following mechanisms to scale effectively:

1. Partitioning Members and Resources:

   • BGCoord partitions the database into logical fragments, each containing a unique subset of members, their resources, and relationships.

   • These fragments are assigned to individual BGClients.

2. Multiple BGClients:

   • Each BGClient operates independently, generating workloads for its assigned logical fragment.

   • By running multiple BGClients in parallel across different nodes, BG can scale horizontally to handle millions of requests.

3. D-Zipfian Distribution:

   • To ensure realistic and scalable workloads, BG uses a decentralized Zipfian distribution (D-Zipfian) that dynamically assigns requests to BGClients based on node performance.

   • Faster nodes receive a larger share of the logical fragments, ensuring even workload distribution.

4. Concurrency Control:

   • BG prevents simultaneous threads from issuing actions for the same user, maintaining the integrity of modeled user interactions and avoiding resource contention.

True or False: BG quantifies the amount of unpredictable data produced by a data store?

True.

This is achieved through:

• Validation Phase:
  • BG uses read and write log records to detect instances where a read operation observes a value outside the acceptable range, classifying it as “unpredictable data.”
• Metrics Collection:
  • The percentage of requests that observe unpredictable data (τ) is a key metric used to evaluate the data store’s consistency.

How is BG’s SoAR different than its Socialites rating?

SoAR (Social Action Rating): Represents the maximum throughput (actions per second) a data store can achieve while meeting a given SLA.

Socialites Rating: Represents the maximum number of concurrent threads (users) a data store can support while meeting the SLA.

Reference: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=d6f9678772a09ca29101f5efce583960ecf53745

索引是一种可以帮助 MySQL 高效获取数据的数据结构，也是有序结构。

优点

• 提高数据检索效率，降低数据库 I/O 成本。
• 通过索引列对数据进行排序，降低数据排序成本，降低 CPU 的消耗。

缺点

• 占用空间。
• 降低了更新表的效率，如 INSERT、UPDATE、DELETE。

因此，若索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能又会产生影响。要找到一个合适的平衡点，这对应用程序的性能至关重要。

索引结构

MySQL 索引是在引擎层实现的，不同的存储引擎支持不同的索引结构。

InnoDB 索引分类

根据索引存储形式，可分为以下两种：

InnoDB 支持以下索引：

• B+ 树索引
• 全文索引
• 自适应 Hash 索引

B+ 树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最为高效且被认为有效的索引。B+ 树索引的构造类似于二叉树，根据键值（Key Value）快速找到数据。B+ 树索引能找到的只是被查找数据所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。

整体流程：

B+ 树 Root => B+ 树索引节点 => B+ 树叶子节点 => Page Directory 中的一个 Slot => 目标行数据。

InnoDB 存储引擎支持的哈希索引是自适应的，InnoDB 存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。

InnoDB 的主键使用的是聚簇索引，而 MyISAM 中，不管是主键索引还是二级索引使用的都是非聚簇索引。

InnoDB 中的全表扫描会顺序读取聚集索引上的数据页（即叶子节点），等价于按主键顺序逐行扫描表中所有行。

全表扫描

在 InnoDB 中，一条简单的 SELECT * FROM A 在执行时会经过以下几层，才能把表 A 中的每一行读出来。下面分段结合关键源码，逐步说明一个典型的全表扫描流程。

一、Handler 接口：ha_rnd_next 循环读取

TableScanIterator::Read() 中：

1
2
3
4
5
6
7

while ((tmp = table()->file->ha_rnd_next(m_record))) {

  if (tmp == HA_ERR_RECORD_DELETED && !thd()->killed) continue;

  return HandleError(tmp);

}

• ha_rnd_next(m_record)：MySQL 存储引擎统一接口，每次调用读一行到 m_record。

• 跳过 DELETED：MyISAM 在并发删时会返回 HA_ERR_RECORD_DELETED，此处跳过。

• 返回码：0 表示成功取到一行；非 0 则调用 HandleError(tmp) 终止扫描。

对于 InnoDB，ha_rnd_next 内部实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13

int handler::ha_rnd_next(uchar *buf) {

  MYSQL_TABLE_IO_WAIT(..., { result = rnd_next(buf); })

    if (!result && m_update_generated_read_fields)

      update_generated_read_fields(buf, table);

  table->set_row_status_from_handler(result);

  return result;

}

二、InnoDB 读取流程：rnd_next → general_fetch → row_search_mvcc

rnd_next(buf) 中的核心调用如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

if (m_start_of_scan) {

  error = index_first(buf);

  m_start_of_scan = false;

} else {

  error = general_fetch(buf, ROW_SEL_NEXT, 0);

}

return error;

• 首次扫描 调用 index_first(buf) 定位到最左叶节点的第一条记录；
• 后续扫描 一律调用 general_fetch。

general_fetch(buf, ROW_SEL_NEXT, 0) 中的核心调用如下：

1
2
3
4
5
6
7

if (!intrinsic) // 普通表

  ret = row_search_mvcc(buf, PAGE_CUR_UNSUPP, m_prebuilt, 0, ROW_SEL_NEXT);

// ...

// 再把 dberr_t 转成 MySQL 错误码返回给 rnd_next

row_search_mvcc

row_search_mvcc 中的核心调用如下：

• 首次 (direction == 0)：构造或恢复一个 B-树游标 pcur，调用 pcur->open_no_init()（或 open_at_side）从根节点一路走到左最叶，定位第一条记录。
• 后续 (direction == ROW_SEL_NEXT)：直接在叶节点上调用 pcur->move_to_next(&mtr)，利用叶节点之间的双向链表遍历下一条记录，无需再从根节点重查。
• 循环过滤（rec_loop）：
  • 跳过 infimum/supremum 伪记录，检查页内偏移合法性；
  • MVCC 版本检查：如果当前版本不可见，调用 undo log 回溯到可见版本；
  • 删除标记：跳过 delete-marked；
  • 索引条件下推（此例没有 WHERE，相当于 match_mode == 0，所有行都通过）；
  • 转换格式：调用 row_sel_store_mysql_rec(buf, …) 将内部二进制行转成 MySQL 客户端格式；
  • 预取缓存：若启用缓存则放入队列，否则直接写入 buf 并 return DB_SUCCESS。
• 退出：当 move_to_next 返回 false（无更多记录），函数最终返回 DB_END_OF_INDEX 或 DB_RECORD_NOT_FOUND，上层映射为 HA_ERR_END_OF_FILE。

在 row_search_mvcc 的整个执行过程中，游标（pcur）的状态会在多处被保存和恢复，其核心目的有两个：

1. 跨页扫描时保持定位：当 B- 树叶节点遍历到一页的末尾，需要切换到下一页时，InnoDB 会提交当前 mini-transaction（mtr_commit(&mtr)）并重新开启一个新的 mini-transaction（mtr_start(&mtr)）。提交会释放当前页面的读锁（latch），以避免死锁或锁的过度持有。但一旦释放，就无法再在页内继续定位，于是必须在释放前存储当前位置，切换后再恢复，才能从下一个页的正确位置继续扫描。
2. 出现锁等待或错误时的回退：如果在给某条记录加锁过程中遇到锁等待（DB_LOCK_WAIT）或其他可重试的错误，函数会
   • 在释放 mini-transaction、让出 latch 之前存储游标位置，
   • 等待锁或错误解决后，再恢复游标，继续当前记录或下一条记录的扫描，保证最终不会漏读也不重复读。

完整调用链一览

1
2
3
4
5
6
7
8
9
10

mysql_select()
 └─ join_read_table() / read_table_rows()
   	└─ handler::ha_rnd_next(buf)
       └─ rnd_next(buf)
          ├─ index_first(buf)     // 第一次，从根到左叶
          └─ general_fetch(buf,…)  // 后续，调用 row_search_mvcc
         		 └─ row_search_mvcc(buf,…)
                ├─ pcur->open_no_init()   // 定位（首次）
                ├─ pcur->move_to_next()   // 遍历（后续）
                └─ row_sel_store_mysql_rec // 转换格式

此外，整个过程主要涉及两类锁：

元数据锁（MDL，Metadata Lock）

• MDL_SHARED_READ：在执行任何 SELECT 时，MySQL 都会在打开表的时候对表结构加一个元数据读锁，类型叫 MDL_SHARED_READ。
  • 作用：保证在查询进行时，表定义（DDL）不会被改动（比如 ALTER TABLE）。
  • 持续时间：从打开表到查询结束（close_tables()）为止。

InnoDB 内部的短期页锁（Latch）与 MVCC

• 页锁（Page Latch）：为了从缓冲池安全地读取 B+ 树节点和行记录，InnoDB 在内存页上会拿短期的读或写 latch（互斥锁），确保数据页在读取/解码时不被并发修改。
  • 这不是 SQL 层面的锁，你在 SHOW ENGINE INNODB STATUS 能看到它们，但在 SHOW OPEN TABLES 或 INFORMATION_SCHEMA.INNODB_TRX 中看不到。
• MVCC 版本控制：默认一致性读不会向行上加记录锁或间隙锁；它通过读视图加上 undo log 回溯来返回符合快照的行版本。
  • 不产生任何行锁，也不会阻塞并发的 UPDATE/DELETE。
  • 只有在遇到刚提交的、版本不可见的行时，InnoDB 会临时读取 undo log 中的旧版本，但这也是通过读取 undo 区块，不会在真正的索引上留下锁。

而且需要注意的是，整个流程中的数据是被一条条地读取并存储到 Record Buffer 中的，这就是 Valcano 风格的 pull-based Iteration Model 的体现。

并行化增强

我们可以对全表扫描进行并行化增强。因为 MySQL 在 InnoDB 层引入了并行扫描功能，用于加速需要全表扫描的操作，该功能自 8.0.14 版本开始支持，通过将 B+ 树划分为多个子树并由多个工作线程并行扫描来实现。要启用并行全表扫描，只需将会话级或全局变量 innodb_parallel_read_threads 设置为大于 1 的值，MySQL 会根据该值和实际子树数量来决定并行线程数。

配置参数 innodb_parallel_read_threads：

• 作用：控制 InnoDB 层并行扫描主键索引时的线程数，仅支持主键（聚簇索引）扫描，不支持二级索引扫描。
• 默认值：默认值为可用逻辑处理器数除以 8，至少 4；MySQL 8.4 之前始终为 4。
• 范围：1 至 256，总线程数上限为 256（跨所有会话）; 达到上限后会话会回退到单线程扫描。

动态修改：支持会话级和全局级动态设置，例如：

1
2

SET GLOBAL innodb_parallel_read_threads = 16;
SET SESSION innodb_parallel_read_threads = 8;

然后执行需要全表扫描的 SQL 即可利用并行扫描。

其他相关参数

• innodb_ddl_threads：控制并行创建二级索引或重建表时的排序和 B+ 树构建线程数。
• innodb_ddl_buffer_size：并行 DDL 操作的排序缓冲区总大小，应配合 innodb_parallel_read_threads 一同调优。

并行扫描原理

MySQL 并行查询实际上是对 B+ 树的并行扫描。核心流程如下：

1. 调用扫描接口：用户线程执行如 SELECT COUNT(*) 等语句后，进入 InnoDB 并行扫描逻辑，从 row_scan_index_for_mysql 接口开始分发任务。
2. 预分片（coarse-grained sharding）：用户线程先对整个聚簇索引做粗粒度分片，将每个子树（Range），由 [start, end) 两个游标标记，放入任务队列。其中分片的步骤如下：
   1. 用户线程在预分片期间对整个索引加 INDEX S 锁，并对根页加 ROOT PAGE S 锁，确保树在分片时不会发生页分裂或新增子树。
   2. 根页每条记录都包含一个指向子树的指针。用户线程依次读取这些指针，对应第 i 条指针即第 i 个子树。
   3. 对于每个指针，沿 B+ 树从该指针所在页向下定位到最左叶记录。
   4. 在遍历过程中，对每个经过的页加 S 锁，定位完成后创建一个 Iter，其中包含原始记录指针 m_rec 和持久化游标 m_pcur，用于后续线程快速定位。
3. 创建工作线程：根据 innodb_parallel_read_threads 值启动相应数量的工作线程，然后等待所有工作线程完成。
4. 工作线程取任务：每个工作线程从队列中取出一个 Range，如粒度过大（分片数 ＞ 线程数）则再基于该 RANGE 的键值范围按同样方式二次切分，然后依次扫描该范围内的记录，通过内部函数 row_search_mvcc 获取每条记录并执行回调（如计数或检查）。
5. 结果汇总：各线程扫描完毕后，用户线程收集各子树的统计结果或校验结果，并返回给 SERVER 层。

分片（Sharding）机制

并行扫描将 B+ 树划分为多个子树，每个子树对应一个 RANGE 结构体：

1
2
3
4

struct RANGE {
 Iter start; // 子树起始记录位置
 Iter end;  // 子树结束记录位置（右开区间）
};

其中 Iter 包含了记录指针和 B+ 树游标，用于定位扫描边界。工作线程可对粒度过大的 Range 再次细分，以提高负载均衡。

Iter 的结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/** Boundary of the range to scan. */
struct Iter {
 /** Destructor. */
 ~Iter();
 /** Heap used to allocate m_rec, m_tuple and m_pcur. */
 mem_heap_t *m_heap{};   // 分配迭代所需内存（记录副本、tuple、游标等）
 /** m_rec column offsets. */
 const ulint *m_offsets{}; // 原始记录中各列的偏移数组
 /** Start scanning from this key. Raw data of the row. */
 const rec_t *m_rec{};   // 指向边界记录的原始数据
 /**
  * Tuple representation inside m_rec,
  * for two Iter instances in a range m_tuple will be [first->m_tuple, second->m_tuple).
  */
 const dtuple_t *m_tuple{}; // m_rec 对应的解析后 tuple，方便按列访问
 /** Persistent cursor. */
 btr_pcur_t *m_pcur{};   // 用于快速定位 m_rec 所在页的 B+ 树游标
};

字段说明

1. m_heap：用于在堆上分配和管理该 Iter 所需的临时内存，包括存放记录副本、tuple 结构和游标状态等。
2. m_offsets：指向一组 ulint，用于记录 m_rec 中每列在页面上的偏移位置，以便快速定位列值。
3. m_rec：原始记录指针（raw record），标记分片边界的具体行数据。
4. m_tuple：m_rec 的逻辑封装（dtuple_t），两端 Iter 的 m_tuple 共同定义了扫描区间；扫描时常直接基于 m_tuple 进行比较和移动。
5. m_pcur：持久化游标（btr_pcur_t*），用于记录定位 m_rec 所在页面和行号，后续扫描可通过该游标快速恢复上次位置，而无需从根节点重定位。

支持的语句类型

目前，InnoDB 并行扫描支持以下全表操作场景：

• SELECT COUNT(*) FROM table1; 完整扫描主键索引并行计数。
• CHECK TABLE table1; 第二次扫描主键索引时可并行校验。
• CREATE INDEX … ON table1 / ALTER TABLE … ADD INDEX … 扫描和排序阶段支持并行，B+ 树构建阶段仍为单线程。
• ALTER TABLE … ENGINE=InnoDB / OPTIMIZE TABLE 重建表阶段扫描主键索引不并行，排序和索引构建支持并行。

限制与注意事项

• 并行扫描仅适用于主键索引，不支持二级索引扫描或包含虚拟列、全文索引、空间索引的表。
• 并行线程读取的数据页会被放到缓冲池 LRU 链表尾部，避免在扫描时占用过多热页。
• 当并行线程数超过子树数量时，实际使用的线程数取两者中的最小值。

B+ 树索引

B+ 树是为磁盘或其他直接存取辅助设备设计的一种自平衡的多路查找树。在 B+ 树中，所有记录节点都是按键值的大小顺序放在同一层的叶子节点上，由各叶子节点指针进行连接。

B+ 树的非叶子节点只存储键值，不存储数据，而叶子节点存储了所有的数据，并且构成了一个有序双向链表。因此，范围查询时就可以直接通过叶子节点间的指针顺序访问整个查询范围内的所有记录，而无需对树进行多次遍历。

在B+ 树的实现中，节点的大小往往被设计为与磁盘页大小相同（或者是其整数倍）。相比于 B 树（非叶子节点中存储指针和数据），B+ 树的非叶子节点能够存储更多的指针，提升索引查找的效率并且减少磁盘 I/O 次数，因为每次从磁盘中加载的节点携带了更多的指针信息。

以下是 B-Tree 的结构（绿色代表子节点的地址，黄色代表记录的主键，红色代表单条记录中除主键外的数据，之后的图也是如此）：

B-Tree可视化：B-Tree Visualization

以下是 B+ 树的结构：

B+ 树可视化：B+ Tree Visualization

也就是说，MySQL 索引数据结构在经典 B-Tree 的基础上，增加了一个指向相邻左右叶子节点的链表指针，形成了双向循环链表，这样可以方便范围查询和反向遍历。

如果需要在 B+树中从大值向小值进行范围查询，可以按以下步骤操作：

• 定位到最右侧节点：首先，找到包含最大值的叶子节点。这通常通过从根节点开始向右遍历树的方式实现。
• 反向遍历：一旦定位到了最右侧的叶子节点，可以利用叶节点间的双向链表向左遍历。

为什么Mongodb索引用B树，而MySQL用B+树?：在关系型数据库中，遍历操作比较常见，因此采用 B+ 树作为索引比较合适。而在非关系型数据库中，单一查询比较常见，因此采用 B 树作为索引比较合适。

B+ 树对于 B 树的优势：

1. 更高的查询效率： B+ 树叶子节点的双向链表使得范围查询时无需从根节点开始进行多次索引查询，只需顺序遍历双向链表即可。
2. 更高的空间利用率：B+ 树非叶子节点只存储指针，使得单个节点能够存储更多的指针只指向子节点，且单次磁盘 I/O 读取更多信息，减少 I/O 读取次数。
3. 更稳定的查询效率：B+ 树叶子节点深度相同，数据查询路径长度相同。

B+ 树对于二叉树的优势：

1. B+ 树的每个节点可以有 m 个子节点，而红黑树和二叉平衡树都只有 2 个。
2. 普通二叉树存在退化的情况，如果它退化成链表，就相当于全表扫描。
3. 读取数据的时候，是从磁盘先读到内存。平衡二叉树的每个节点只存储一个键值和数据，而 B+ 树可以存储更多的节点数据，树的高度也会降低，因此读取磁盘的次数就会下降，查询效率就快。

为什么 InnoDB 存储引擎选择使用 B+Tree 索引结构？

1. 相比于二叉树（顺序插入数据行的情况下会退化成链表），B+Tree 更平衡，层级更少，搜索效率高。
2. 就B-Tree（或 BST）而言，无论叶子节点还是非叶子节点都会保留数据，这样导致一页中存储的键减少，指针也减少了，要保存大量数据，只能增加树的高度，导致性能降低。
3. 相比于 Hash 索引，B+Tree 支持范围匹配及排序操作。

一棵 B+ 树能存储多少数据？

假如我们的主键 ID 是 bigint 类型，长度为 8 个字节。指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。所以非叶子节点(一页)可以存储 $16384/14=1170$ 个这样的单元(键值+指针)。

一个指针指向一个存放记录的页，一页可以放 16 条数据，树深度为 2 的时候，可以存放 $1170*16=18720$ 条数据。

同理，树深度为 3 的时候，可以存储的数据为 $1170117016=21902400$ 条记录。

理论上，在 InnoDB 存储引擎中，B+树的高度一般为 2-4 层，就可以满足千万级数据的存储。查找数据的时候，一次页的查找代表一次 IO，当我们通过主键索引查询的时候，最多只需要 2-4 次 IO 就可以了。

B+ 树的插入操作

B+ 树的插入必须保证插入后叶子节点中的记录依然排序，同时需要考虑插入到 B+ 树的三种情况，每种情况都可能会导致不同的插入算法。具体如下：

叶子节点未满，索引节点未满：直接将记录插入到目标叶子节点的合适位置（保持有序）。

叶子节点已满，索引节点未满：

• 拆分叶子节点为左右两个节点。
• 将中间键值提升为分隔键，插入到父级索引页。
• 原叶子节点中：
  • 小于中间键值的记录 → 左侧新页；
  • 大于等于中间键值的记录 → 右侧新页。

叶子节点和索引节点都已满：

• 拆分叶子节点（Leaf Page）：

  • 小于中间键值的记录 → 左页；
  • 大于等于中间键值的记录 → 右页；

• 将中间键值提升为分隔键，插入到父级索引页。

• 由于父级索引页也已满，继续处理其溢出：

  • 拆分 Index Page：
    • 小于中间索引值的记录 → 左侧索引页；
    • 大于中间索引值的记录 → 右侧索引页；
  • 将新的中间索引项继续提升到上一层索引页中。

• 若上一层索引页仍满，则继续递归，直到根节点；若根节点也满，最终会导致根节点分裂，树高度增加。

因此，不管怎么变化，B+ 树总是会保持平衡。但是为了保持平衡，对于新插入的键值可能需要做大量的拆分页操作。因为 B+ 树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应当在可能的情况下尽量减少页的拆分操作。因此，B+ 树同样提供了类似于平衡二叉树的旋转功能。

旋转发生在叶子页（Leaf Page）已经满，但其左右兄弟节点没有满的情况下。这时 B+ 树并不会急于做拆分页的操作，而是将记录移到所在页的兄弟节点上。在通常情况下，会首先检查左兄弟以执行旋转操作。在下面的例子中：若插入键值 70，B+ 树并不会立即拆分叶子节点，而是先做旋转操作。

我们可以看到，旋转操作使得 B+ 树减少了一次页的拆分操作，同时这棵 B+ 树的高度依然为 2。

B+ 树的删除操作

B+ 树使用填充因子（fill factor）来控制树的删除变化，50% 是填充因子可设的最小值。B+ 树的删除操作同样必须保证删除后叶子节点中的记录依然排序。与插入一样，B+ 树的删除操作同样需要考虑三种情况，根据填充因子的变化来衡量是否需要进行节点合并或旋转操作。

对于第一种情况的后半部分的解释：

在以下 B+ 树中（这里省去叶节点之间的指针），我们删除键值为 25 的记录，因为该值也是 Index Page 中的值，所以在删除之后，需要将 25 的右兄弟节点的 28 更新到 Index Page 中。

以下是删除之后的 B+ 树。

这时，如果删除 Leaf Page 中键值为 60 的记录，那么 Fill Factor 小于 50%，需要做合并操作；同样，在删除 Index Page 中相关记录后，需要做 Index Page 的合并操作。结果如下：

注意：页面合并时，首先尝试与左侧直接相邻的兄弟页合并；仅在左侧不符合条件时，才会检查右侧兄弟页。如果左右两侧都没有足够的空间容纳当前页的所有记录，合并操作将不会执行，页面将保持“半空”状态，直到后续操作（如父节点合并或树高度调整）触发新的重组逻辑。合并成功后，还需在父节点中删除对应的指针条目，并在必要时向上递归合并或降高。

聚集索引

数据库中的 B+ 树索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。但是无论是聚集索引还是辅助索引，其内部结构都是 B+ 树，即高度平衡的，且叶子节点存放所有的数据。聚集索引与辅助索引的不同之处在于：叶子节点存放的是否是一整行的信息。

之前已经介绍过，InnoDB 存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一棵 B+ 树，同时叶子子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同 B+ 树数据结构一样，每个数据页都通过一个双向链表来进行链接。

由于实际的数据页只能按照一棵 B+ 树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在 B+ 树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快速地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

例如：

1
2
3
4
5
6
7
8
9
10
11
12

CREATE TABLE t (
 a INT NOT NULL,
 b VARCHAR(8000),
 c INT NOT NULL,
 PRIMARY KEY (a),
 KEY idx_c (c)
) ENGINE=InnoDB;

INSERT INTO t SELECT 1, REPEAT('a', 7000), -1;
INSERT INTO t SELECT 2, REPEAT('a', 7000), -2;
INSERT INTO t SELECT 3, REPEAT('a', 7000), -3;
INSERT INTO t SELECT 4, REPEAT('a', 7000), -4;

我们可以发现数据页上存放的是完整的每行记录，而在非数据页的索引页中，存放的仅仅是键值及指向数据页的偏移量，而不是一个完整的行记录。具体结构如下：

许多资料会说：聚集索引按照顺序物理地存储数据。但是试想一下，如果聚集索引必须按照特定顺序存放物理记录，则维护成本显得非常之高。所以，聚集索引的存储并不是物理上连续的，而是逻辑上连续的。这其中有两点：

1. 前面说过的页通过双向链表链接，页按照主键的顺序排列；
2. 每个页中的记录也是通过双向链表进行维护的，物理存储上可以不按主键存放。

说白了，就是在物理存储时，不同页和页内记录的数据块可以散布在数据文件各处，通过上述链表结构保证逻辑遍历顺序，从而大幅降低维护开销。

聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。

还有就是范围查询（range query），即如果要查找主键某一范围内的数据，通过叶子节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可。

此外，聚集索引存在如下选取规则：

• 如果存在主键，主键索引就是聚集索引。
• 如果不存在主键，将使用第一个遇到的唯一索引作为聚集索引。
• 如果既没有主键也没有合适的唯一索引，则自动生成一个以单调递增的 row ID 作为键的隐藏聚集索引。

辅助索引

对于辅助索引（Secondary Index，也称非聚集索引），叶子节点并不包含行记录的全部数据。也就是说，叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签。该书签用来告诉 InnoDB 存储引擎哪里可以找到与该索引行对应的行数据。由于 InnoDB 存储引擎表是索引组织表，因此辅助索引的书签就是相应行数据在聚集索引中的聚集索引键。

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。当通过辅助索引来寻找数据时，InnoDB 存储引擎会：

1. 遍历辅助索引树，到达叶子节点后获得对应行的聚集索引键；
2. 再通过聚集索引树查找该主键，定位到完整的行记录所在的数据页。

举例来说，如果辅助索引树的高度为 3，则需要 3 次查找才能找到指定的主键；若聚集索引树的高度也为 3，则还需要额外 3 次查找才能在聚集索引中定位到完整行的数据页。因此，总共需要 6 次逻辑 I/O 访问，才能得到最终的数据页。

示例：

在之前的表 t 上新增一列 c，并对列 c 创建聚集索引：

1
2
3
4
5
6
7
8
9
10
11
12

mysql> ALTER TABLE t
  -> ADD c INT NOT NULL;
Query OK, 4 rows affected (0.24 sec)
Records: 4 Duplicates: 0 Warnings: 0

mysql> UPDATE t SET c = 0 - a;
Query OK, 4 rows affected (0.04 sec)
Rows matched: 4 Changed: 4 Warnings: 0

mysql> ALTER TABLE t ADD KEY idx_c (c);
Query OK, 4 rows affected (0.28 sec)
Records: 4 Duplicates: 0 Warnings: 0

更改之后的索引结构如下：

上图显示了表 t 中辅助索引 idx_c 和聚集索引的关系。可以看到辅助索引的叶子节点中包含了列 c 的值和主键的值。因为这里的键值为负值，所以会发现以 7f ff ff ff 的方式进行内部存储。7（0111）最高位为 0，代表负值，实际的值应该取反后加 1，即得 -1。

B+ 树索引的分裂

之前介绍的 B+ 树分裂是最为简单的一种情况，这和数据库中 B+ 树索引的实际情况可能略有不同，因为并未涉及并发，而这才是 B+ 树索引实现中最为困难的部分。

B+ 树索引页的分裂并不总是从页的中间记录开始，这样可能会导致页空间的浪费。例如下面的记录：

1

1, 2, 3, 4, 5, 6, 7, 8, 9

插入是根据自增顺序进行的，若此时插入第 10 条记录后需要进行页的分裂操作，那么根据之前介绍的分裂方法，会将记录 5 作为分裂点记录，分裂后得到下面两个页：

Page 1: 1, 2, 3, 4；

Page 2: 5, 6, 7, 8, 9, 10。

由于插入是顺序的，P1 这个页将不会再有新记录被插入，从而导致空间浪费；而 P2 又会再次进行分裂。

InnoDB 存储引擎的 Page Header 中有以下几个部分用来保存在页中记录插入的顺序信息：

• PAGE_LAST_INSERT
• PAGE_DIRECTION
• PAGE_N_DIRECTION

通过这些信息，InnoDB 存储引擎可以决定是向左还是向右进行分裂，同时决定将分裂点记录为哪一个。若插入是随机的，则取页中的中间记录作为分裂点记录，这和之前介绍的相同。若往同一方向进行插入的记录数量为 5，并且目前已定位（cursor）到的记录（该记录为待插入记录的前一条记录）之后还有 3 条记录，则分裂点记录为定位到的记录后的第三条记录；否则，分裂点记录就是待插入的记录。

示例：

下面来看一个向右分裂的例子，并且定位到的记录之后还有 3 条记录，则分裂点记录如下：

分裂后的结果如下：

接着是分裂点就为插入记录本身：

B+ 树的管理

索引管理

索引的创建和删除可以通过两种方法，一种是 ALTER TABLE，另一种是 CREATE/DROP INDEX。通过 ALTER TABLE 创建索引的语法为：

1
2
3
4
5
6

ALTER TABLE tbl_name
ADD [INDEX|KEY] [index_name]
[index_type] (index_col_name, ...) [index_option] ...

ALTER TABLE tbl_name
DROP PRIMARY KEY | DROP {INDEX|KEY} index_name

CREATE/DROP INDEX 的语法同样很简单：

1
2
3
4

CREATE [UNIQUE] INDEX index_name
[index_type] ON tbl_name (index_col_name, ...)

DROP INDEX index_name ON tbl_name

用户可以设置对整个列的数据进行索引，也可以只索引一列的开头部分数据，如前面创建的表 t，列 b 为 varchar(8000)，但是用户可以只索引前 100 个字段，如：

1
2
3
4

mysql> ALTER TABLE t
  -> ADD KEY idx_b (b(100));
Query OK, 4 rows affected (0.32 sec)
Records: 4 Duplicates: 0 Warnings: 0

若用户想要查看表中索引的信息，可以使用命令 SHOW INDEX。我们以主键列为例，结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

mysql> SHOW INDEX FROM t\G;
*************************** 1. row ***************************
    Table: t
    Non_unique: 0
    Key_name: PRIMARY
    Seq_in_index: 1
    Column_name: a
    Collation: A
    Cardinality: 2
    Sub_part: NULL
    Packed: NULL
    Null: 
    Index_type: BTREE
    Comment: 
…

以上结果中每列的含义如下：

Table：索引所在的表名。

Non_unique：非唯一的索引，可以看到 primary key 是 0，因为必须是唯一的。

Key_name：索引的名字，用户可以通过这个名字来执行 DROP INDEX。

Seq_in_index：索引中该列的位置，如果看联合索引 idx_a_c 就比较直观了。

Column_name：索引列的名称。

Collation：列以什么方式存储在索引中。可以是 A 或 NULL。B+ 树索引总是 A，即排序的。如果使用了 Heap 存储引擎，并且建立了 Hash 索引，这里就会显示 NULL 了。因为 Hash 根据 Hash 桶存放索引数据，而不是对数据进行排序。

Cardinality：非常关键的值，表示索引中唯一值的数目的估计值。Cardinality 表的行数应尽可能接近 1，如果非常小，那么用户需要考虑是否可以删除此索引。

Sub_part：是否是列的部分被索引。如果看到 idx_b 这个索引，这里显示 100，表示只对 b 列的前 100 字符进行索引。如果索引整个列，则该字段为 NULL。

Packed：关键字如何被压缩。如果没有被压缩，则为 NULL。

Null：是否索引的列含有 NULL 值。可以看到 idx_b 这里为 Yes，因为定义的列 b 允许 NULL 值。

Index_type：索引的类型。InnoDB 存储引擎只支持 B+ 树索引，所以这里显示的都是 BTREE。

Comment：注释。

Cardinality 值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的，即并非每次索引的更新都会更新该值，因为这样代价太大了。因此这个值是不太准确的，只是一个大概的值。上面显示的结果主键的 Cardinality 为 2，但是很显然我们表中有 4 条记录，这个值应该是 4。如果需要更新索引 Cardinality 的信息，可以使用 ANALYZE TABLE 命令。

另一个问题是 MySQL 数据库对于 Cardinality 计数的问题，在运行一段时间后，可能会看到下面的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

mysql> show index from Profile\G;
*************************** 1. row ***************************
    Table: Profile
    Non_unique: 0
    Key_name: UserName
    Seq_in_index: 1
    Column_name: username
    Collation: A
    Cardinality: NULL
    Sub_part: NULL
    Packed: NULL
    Null: 
    Index_type: BTREE
    Comment: 

Cardinality 为 NULL，在某些情况下可能会发生索引建立了却没有用到的情况。或者对两条基本一样的语句执行 EXPLAIN，但是最终出来的结果不一样：一个使用索引，另外一个使用全表扫描。

这时最好的解决办法就是做一次 ANALYZE TABLE 的操作。因此建议在一个非高峰时间，对应用程序下的几张核心表做 ANALYZE TABLE 操作，这能使优化器和索引更好地为你工作。

Fast Index Creation

MySQL 5.5 版本之前（不包括 5.5）存在的一个普遍被人诟病的问题是 MySQL 数据库对于索引的添加或者删除的这类 DDL 操作，MySQL 数据库的操作过程是：

• 首先创建一张新的临时表，表结构为通过命令 ALTER TABLE 新定义的结构。
• 然后把原表中数据导入到临时表。
• 接着删除原表。
• 最后把临时表重名为原来的表名。

可以发现，若用户对一张大表进行索引的添加和删除操作，那么会花费很长的时间。更关键的是，若有大量事务需要访问正在被修改的表，这意味着数据库服务不可用。

InnoDB 存储引擎从 InnoDB 1.0.x 版本开始支持一种称为 Fast Index Creation（快速索引创建） 的索引创建方式——简称 FIC。

对于辅助索引的创建，InnoDB 存储引擎会对创建索引的表加上一个 S 锁。在创建的过程中，不需要重建表，因此速度较之前提高很多，并且数据库的可用性也得到了提高。
删除辅助索引操作就更简单了，InnoDB 存储引擎只需更新内部视图，并将辅助索引的空间标记为可用，同时触发 MySQL 数据库内部视图上对该索引定义即可以。

这里需要特别注意的是，临时表的创建路径是通过参数 tmpdir 进行设置的。用户必须保证 tmpdir 有足够的空间可以存放临时表，否则会导致创建索引失败。

由于 FIC 在索引的创建中对表加上了 S 锁，因此在创建的过程中只能对该表进行 读操作，若有大量的事务需要对目标表进行写操作，那么数据库的服务同样不可用。此外，FIC 方法只限用于 辅助索引，对于主键的创建和删除同样需要重建一张表。

Online Schema Change

Online Schema Change（OSC）是一种用于 在线执行 MySQL DDL 操作 的技术，最早由 Facebook 推出并开源，旨在解决传统 DDL 操作期间数据库不可用的问题。通过 OSC，用户可以在 不中断业务访问的前提下 对表结构进行修改，如添加索引、修改字段等。

其核心思想是通过复制原表结构创建一张临时表，并在数据迁移和结构变更过程中，借助触发器记录原表的变更操作（DML）。在数据导入和变更同步完成后，再将原表与新表进行原子性换名操作，从而实现无缝切换。

Online DDL

虽然 FIC 可以让 InnoDB 存储引擎避免创建临时表，从而提高索引创建的效率，但正如前面章节所说的，索引创建时会阻塞表上的 DML 操作。OSC 虽然解决了上述的部分问题，但还是有很大的局限性。

MySQL 从 5.6 版本开始支持 Online DDL（在线数据定义） 操作，其允许在辅助索引创建的同时，还允许其他诸如 INSERT、UPDATE、DELETE 这类 DML 操作，这极大地提高了 MySQL 数据库在生产环境中的可用性。

此外，不仅是辅助索引，以下几类 DDL 操作都可以通过“在线”的方式进行操作：

• 辅助索引的创建与删除

• 改变自增长值

• 添加或删除外键约束

• 列的重命名

通过新的 ALTER TABLE 语法，用户可以选择索引的创建方式：

1
2
3
4
5

ALTER TABLE tbl_name
ADD [INDEX|KEY] [index_name]
[index_type] (index_col_name,...) [index_option] ...
ALGORITHM [=] {DEFAULT|INPLACE|COPY}
LOCK [=] {DEFAULT|NONE|SHARED|EXCLUSIVE}

ALGORITHM 指定了创建或删除索引的算法：

• COPY 表示按 MySQL 5.1 版本之前的工作模式，即创建临时表的方式。
• INPLACE 表示索引创建或删除操作不需要创建临时表。
• DEFAULT 表示根据参数 old_alter_table 判断是否使用 INPLACE 或 COPY 算法，默认值为 OFF，即采用 INPLACE 方式。

LOCK 部分表示在创建或删除索引时对表加锁的情况，可选值包括：

1. **NONE：**执行索引创建或删除操作时，对目标表不添加任何锁，即事务仍然可以进行读写操作，不会受到阻塞。因此该模式可以获得最大的并发度。
2. **SHARE：**与 FIC 类似，执行索引创建或删除操作时，对目标表加上一个 S 锁。对于读操作不影响，但会阻塞写操作。
3. **EXCLUSIVE：**执行索引创建或删除操作时，对目标表加上一个 X 锁。此时所有事务都不能进行，等同于 COPY 方式运行时的状态，但不需要创建临时表。
4. **DEFAULT：**默认模式下，系统会判断当前操作是否可以使用 NONE 模式，若不能，则判断是否可以使用 SHARE，最后才判断是否可以使用 EXCLUSIVE 模式。DEFAULT 会根据当前事务的最大并发性来自动选择 DDL 执行的锁定模式。

InnoDB 存储引擎在执行 Online DDL 的过程中，会将 INSERT、UPDATE、DELETE 等 DML 操作的日志写入一个缓冲区，待索引创建完成后再将这些日志应用到表上，以此保证数据一致性。

这个缓冲区的大小由参数 innodb_online_alter_log_max_size 控制，默认值为128MB。若在创建过程中遇到大量写事务，而缓冲区不够，会报错：

1
2
3

Error: 1799 SQLSTATE: HY000 (ER_INNODB_ONLINE_LOG_TOO_BIG)

Message: Creating index 'idx_aaa' required more than 'innodb_online_alter_log_max_size' bytes of modification log. Please try again.

为避免该错误，可通过调整 innodb_online_alter_log_max_size 获取更大的日志缓冲空间。此外，也可以设置 ALTER TABLE 的 LOCK = SHARE 模式，以避免记录过多的 DML 日志。

需要特别注意的是，在 Online DDL 结束后，MySQL 会通过重放日志达到数据最终一致性。因此在索引创建过程中，SQL 优化器不会选择正在创建的索引。