MySQL存储引擎分析锁和排序的原理

索引知识回顾

对于 MySQL 数据库而言,数据是存储在文件里的，而为了能够快速定位到某张表里的某条记录进行查询和修改,我们需要将这些数据以一定的数据结构进行存储，这个数据结构就是我们说的索引。回忆一下我们大学里学过的算法与数据结构，能够支持快速查找的数据结构有：顺序数组、哈希、搜索树。

数组要求 insert 的时候保证有序，这样查找的时候可以利用二分查找法达到 O(log(N)) 的时间复杂度，对范围查询支持也很好，但是 insert 的时候如果不是在数组尾部，就需要摞动后面所有的数据，时间复杂度为O(N)。所以有序数组只适合存储静态数据，例如几乎很少变动的配置数据，或者是历史数据。这里应该会有人有疑问：我用另外一种线性数据结构链表来替代数组不就可以解决数组因为要移动数据导致太慢的问题了么，要回答这个问题我们需要了解操作系统读取文件的流程，磁盘 IO 是一个相对很慢的操作，为了提高读取速度，我们应该尽量减少磁盘 IO 操作，而操作系统一般以 4kb 为一个数据页读取数据，而 MySQL 一般为 16kb 作为一个数据块，已经读取的数据块会在内存进行缓存，如果多次数据读取在同一个数据块，则只需要一次磁盘 IO ，而如果顺序一致的记录在文件中也是顺序存储的，就可以一次读取多个数据块，这样范围查询的速度也可以大大提升，显然链表没有这方面的优势。

类似于 jdk 中的 hashmap，哈希表通过一个特定的哈希函数将 key 值转换为一个固定的地址，然后将对应的 value 放到这个位置，如果发生哈希碰撞就在这个位置拉出一个链表，由于哈希函数的离散特性，所以经过哈希函数处理后的 key 将失去原有的顺序，所以哈希结构的索引无法满足范围查询，只适合等值查询的情况例如一些缓存的场景。

二叉树在极端情况下会变成线性结构，也就是每个节点都只有左子节点或者只有右子节点，这样就无法利用二分查找只能从第一个节点开始向后遍历了，所以为了维持 O(log(N)) 的时间复杂度，我们需要在插入节点的时候对节点进行调整以保证树的平衡，所以平衡二叉树插入的时间复杂度也是 O(log(N))，二叉树只有两个子节点，如果数据量很大则树就很高，树的每一层一般不在同一个数据块中存储，为了尽量的减少磁盘读写次数，我们用Ｎ叉树来代替二叉树，在 MySQL 中这个 N 一般为 1200，这样树高是 4 的话也可以存储亿级别的数据，而且树的前面两层一般都在内存中，MySQL 中用到的 B+ 树，一般用非叶子节点构建索引，而叶子节点用来存储具体的值。

在 InnoDB 中，有聚簇索引和普通索引之分，聚簇索引根据主键来构建，叶子节点存放的是该主键对应的这一行记录，而普通索引根据申明这个索引时候的列来构建，叶子节点存放的是这一行记录对应的主键的值，而普通索引中还有唯一索引和联合索引两个特例，唯一索引在插入和修改的时候会校验该索引对应的列的值是否已经存在，而联合索引将两个列的值按照申明时候的顺序进行拼接后在构建索引。

根据以上描述我们可以得到以下信息：

• 数据是以行为单位存储在聚簇索引里的，根据主键查询可以直接利用聚簇索引定位到所在记录，根据普通索引查询需要先在普通索引上找到对应的主键的值，然后根据主键值去聚簇索引上查找记录，俗称回表。
• 普通索引上存储的值是主键的值，如果主键是一个很长的字符串并且建了很多普通索引，将造成普通索引占有很大的物理空间，这也是为什么建议使用 自增ID 来替代订单号作为主键，另一个原因是 自增ID 在 insert 的时候可以保证相邻的两条记录可能在同一个数据块，而订单号的连续性在设计上可能没有自增ID好，导致连续插入可能在多个数据块，增加了磁盘读写次数。
• 如果我们查询一整行记录的话，一定要去聚簇索引上查找，而如果我们只需要根据普通索引查询主键的值，由于这些值在普通索引上已经存在，所以并不需要回表，这个称为索引覆盖，在一定程度上可以提高查询效率，由于联合索引上通过多个列构建索引，有时候我们可以将需要频繁查询的字段加到联合索引里面，例如如果经常需要根据 name 查找 age 我们可以建一个 name 和 age 的联合索引。
• 查询的时候如果在索引上用了函数，将导致无法用到根据之前列上的值构建的索引，索引遵循最左匹配原则，所以如果需要查询某个列的值中间是否包含某个字符串，将无法利用索引，如果有这种需求可以利用全文索引，而如果查询是否以某个字符串开头就可以，联合索引根据第一个列查询可以用到索引，仅仅根据第二个列将无法用到索引，查询的时候用 IN 的效率高于 NOT = 。另外建议将索引的列设置为非空，这个和 NULL 字段的存储有关，下文在分析。

存储格式

有了以上的索引知识我们在来分析数据是怎么存储的，InnoDB 存储引擎的逻辑存储结构从大到小依次可以分为：表空间、段、区、页、行。

表空间作为存储结构的最高层，所有数据都存放在表空间中，默认情况下用一个共享表空间 ibdata1 ，如果开启了 innodb_file_per_table 则每张表的数据将存储在单独的表空间中，也就是每张表都会有一个文件，

表空间由各个段构成，InnoDB存储引擎由索引组织的，而索引中的叶子节点用来记录数据，存储在数据段，而非叶子节点用来构建索引，存储在索引段，而回滚段我们在后面分析锁的时候在聊。

区是由连续的页组成，任何情况下一个区都是 1MB ，

一个区中可以有多个页，每个页默认为 16KB ，所以默认情况下一个区中可以包含64个连续的页，页的大小是可以通过 innodb_page_size 设置，页中存储的是具体的行记录。一行记录最终以二进制的方式存储在文件里，我们要能够解析出一行记录中每个列的值，存储的时候就需要有固定的格式，至少需要知道每个列占多少空间，而 MySQL 中定义了一些固定长度的数据类型，例如 int、tinyint、bigint、char数组、float、double、date、datetime、timestamp 等，这些字段我们只需要读取对应长度的字节，然后根据类型进行解析即可，对于变长字段，例如 varchar、varbinary 等，需要有一个位置来单独存储字段实际用到的长度，当然还需要头信息来存储元数据，例如记录类型，下一条记录的位置等。下面我们以 Compact 行格式分析一行数据在 InnoDB 中是怎么存储的。

• 变长字段长度列表，该位置用来存储所申明的变长字段中非空字段实际占有的长度列表，例如有3个非空字段，其中第一个字段长度为3，第二个字段为空，第三个字段长度为1，则将用 01 03 表示，为空字段将在下一个位置进行标记。变长字段长度不能超过 2 个字节，所以 varchar 的长度最大为 65535。
• NULL 标志位，占 1 个字节，如果对应的列为空则在对应的位上置为 1 ，否则为 0 ，由于该标志位占一个字节，所以列的数量不能超过 255。如果某字段为空，在后面具体的列数据中将不会在记录。这种方式也导致了在处理索引字段为空的时候需要进行额外的操作。
• 记录头信息，固定占 5 字节，包含下一条记录的位置，该行记录总长度，记录类型，是否被删除，对应的 slot 信息等
• 列数据 包含具体的列对应的值，加上两个隐藏列，事务 ID 列和回滚指针列。如果没有申明主键，还会增加一列记录内部 ID。
• 数据页头（ Page Header）固定 56 个字节 包含slot数目，可重用空间起始地址，第一个记录地址，记录数，最大事务ID等
• 虚拟的最大最小记录 （Infimum + Supremum Record）
• 用户记录 （User Records） 包含已经删除的记录以链表的形式构成可重用空间
• 待分配空间 （Free spaces） 未分配的空间
• 页目录 （Page Directory） slot 信息，下面单独介绍
• 文件尾 （File Trailer） 固定8个字节,用来保证页的完整性
• 1 表示事务每次提交都需要调用 fsync 进行刷盘，以防止数据库宕机导致数据丢失。
• 2 表示事务提交的时候会写入文件但是只保证写入操作系统缓存，不进行 fsync 操作。 redolog 文件只会顺序写，所以磁盘操作性能不会太慢，
• 不可重复读
• 丢失更新
• 死锁和热点
• order_no 是普通索引，并且是唯一索引 将会对 普通索引上对应的一套记录加排他锁，对主键索引上对应的记录加排他锁
• order_no 是普通索引，并且不是唯一索引 将会对 普通索引上 order_no = '201912102322' 一条或者多条记录加锁，并且对这些记录对应的主键索引上的记录加锁。这里除了加上行锁外，还会加上间隙锁，防止其他事物插入 order_no = '201912102322' 的记录，然而如果是唯一索引就不需要间隙锁，行锁就可以。
• 一致性 ：保证磁盘和缓存的数据一致，binlog 数据和 主库中的数据一致。
• 隔离性 ： 默认为可重复读，采用 undolog 来实现。
• 持久性 ： 事务一旦提交，其结果就是永久的，redolog 需要在事务提交前进行刷盘，磁盘采用 RAID 等。