数据库底层 - 1

语句执行顺序

SQL语句的执行顺序如下

1. from字句，确定主表
2. join链接，确定列
3. where过滤，确定范围
4. group by进行分组，准备计算
5. having过滤聚合结果
6. select选择最终列
7. order by排序
8. limit返回行数

表结构

MySQL是以表的形式存储的，而表的结构则由段区页行组成

1. 行
   行是InnoDB中数据存储的最小逻辑单位，也就是一条记录。里面除了各个列的值，还有一些InnoDB为例管理为了管理而添加的一些字段，如行ID(DB_ROW_ID)、事务ID(DB_TRX_ID)、回滚指针(DB_ROLL_PTR)等。
2. 页
   页是InnoDB中磁盘管理的最小单位，也是内存和磁盘交互的基本单元。页默认有16kb大小，里面除了行，还有文件头、页头、最大最小记录等等。
3. 区
   区由64个连续的页组成，大小大约是1mb，用于顺序IO和管理效率
4. 段
   段是一个表或索引的存储容器，由一个或多个区组成。创建索引的时候会创建两个段，数据段和索引段，前者用来存储叶子节点的数据，后者用于存储非叶子节点的数据。

MySQL架构

MySQL的基础架构如下

• 连接器用于管理客户端链接、身份认证、权限获取
• 查询缓存层，查看是否有一条完全相同的sql语句
• 分析器，对sql语句进行词法分析和语法分析
• 优化器，在开始执行前，生成一个执行计划，决定sql语句应该如何高效执行
• 执行器，调用存储引擎接口开始执行
• 引擎层，一般是InnoDB，以前的版本是MyISAM

语句分析

在执行select语句时，需要进行以下操作

• 连接器建立链接，验证用户名、密码和主机权限
  一旦认证成功，连接器会获取你的全局权限，并在整个链接生命周期内进行缓存。这意味着即使管理员在连接期间修改了你的权限，已有的链接也不受影响。
• 在分析器进行词法分析和语法分析
• 在优化器进行查询优化，该步骤会做许多事情
  • 若有多个索引，优化器会选择使用成本最低的那个索引
  • 对于join表的查询，它会决定先读哪张表再读哪张表
  • 可能会把子查询转换为连接操作
  • 判断是否可以直接使用索引返回数据，而无需回表
• 最后进行执行查询，交给InnoDB处理

而执行update语句的步骤就复杂得多。前面的步骤和select一致，而交由InnoDB`后

1. 读取
   先从缓冲池中查找对应的数据页。若数据页不在缓冲池中，则从磁盘的.ibd文件里加载到缓冲池。通过B+树定位到改行记录。
2. 加锁
   InnoDB会为这行记录仪加上排他锁X Lock。确保在事务提交前，其他事务无法读取或修改这行数据。若该行已经被其他事务加锁，则当前事务需要等待锁释放。
3. 记录Undo Log
   在修改数据之前，InnoDB会把这行数据的旧版本拷贝到Undo Log（回滚日志）中。一来可以用于事务回滚，二来实现MVCC，其他执行快照读的业务可以通过Undo Log链来读取这行数据的旧版本。
4. 执行更新操作
   执行器将新值传给InnoDB。InnoDB在缓存池中更新这行数据，此时缓存中的数据和磁盘中的数据页不再一致，该数据页被称为“脏页(Dirty Page)”。
5. 记录Redo Log
   在事务提交前，InnoDB把对数据页中做的物理修改（例如，在某个数据页的某个偏移处写了什么内容）记录到Redo Log Buffer中，以确保事务的持久性，即使数据库发生崩溃，重启后也能通过Redo Log重新应用这些修改。
6. 开始事务提交的准备阶段
   执行器通知InnoDB准备提交事务，InnoDB将Redo Log中的内容刷盘，写入到ib_logfile文件中，并在Redo Log中记录一个prepare标志。
7. 写Binlog
   Server层下的Binlog开始工作，将本次更新的逻辑语句写入到Binlog cache，然后将其刷盘到本地的binlog文件中，以用于主从复制或数据恢复。
8. 事务提交
   执行器通知InnoDB正式版提交事务，InnoDB在Redo Log中写入commit标记。此时，事务才算真正提交成功，随后会释放锁。
9. 后续工作
   告知客户端执行成功，并在后台异步将“脏页”刷回到磁盘的.idb文件中。因为有Redo Log保证了即使此时崩溃数据也不会丢失，因此MySQL不需要在事务提交时立即执行慢速的磁盘随机写。

• 在事务开始前记录的undo log主要用于事务回滚。
• 使用redo log可以实现事务功能
  • 判断redo log是否完整，若是完整的，就立即提交
  • 若redo log只是预提交但不是commit状态，这时候就去判断binlog是否完整，若完整就提交redo log，不完整就回滚事务。

存储引擎

MySQL的存储引擎是插件式架构，支持多种存储引擎。而且，存储引擎是基于表的，而不是数据库。

在MySQL5.5前，MyISAM引擎是MySQL的默认引擎，而在5.5后，InnoDB称为了默认存储引擎。两个引擎有以下区别

• MyISAM只支持表级锁，InnoDB支持行级锁。
• MyISAM不提供事务支持。
• MyISAM不支持外键，但可以没有主键；InnoDB支持外键，但必须有主键
• MyISAM不支持数据库崩溃后的异常修复
• MyISAM不支持MVCC(Multi-Version Concurrency Control，多版本并发控制)
• 二者都使用B+树作为索引结构，但MyISAM索引文件和数据文件是分离的，InnoDB的数据文件本身就是索引文件
• MyISAM使用键缓存，仅缓存索引页而不缓存数据页；InnoDB使用缓冲池缓存数据页和索引页

InnoDB

InnoDB的内存结构如下

整体分两块，buffer pool和log buffer，前者用于缓存数据页和索引页，提升读写性能；后者用于缓存redo log，提升写入性能。

数据页

其数据页由7部分构成，分别为文件头、页头、文件尾（这三者大小是固定的，用来标记该页的一些重要信息）、行记录、空闲空间、页目录、空闲空间。

每个数据页的文件头都有上一页和下一页的编号，所有的数据页会形成一个双向链表。

Buffer Pool

缓存池会将经常使用的数据页、索引页加载进内存，读的时候先查询缓存池即可。进行写操作时会先写入内存中的页，形成“脏页”。后台线程会定期将脏页刷新到磁盘中。

在1gb~4gbRAM的系统上，默认值为系统RAM的25%，在具有超过4gb的系统上，默认值为系统RAM的50%，但不超过4gb。一般为最小值128mb。

缓存池大小参数为innodb_buffer_pool_size

InnoDB的缓存对LRU进行了优化，目的是挡住一次性或顺序扫描带来的“缓存污染”，让真正的热点留在内存。

InnoDB将整个LRU链表通过midpoint指针切成两段：Young和Old。其中Young靠近链表头，占比63%，而Old占比接近37%。新页永远先查到Old的头部（即midpoint）。当页在Old里首次被访问后，若距离进入时间较短（默认小于1000ms），则不晋升，否则晋升到Young区的头部，于常见LRU保持一致。而需要淘汰时，从Old的尾部开始踢。

两个区比例的参数为innodb_old_blocks_pct
页的观察时间参数为innodb_old_blocks_time

日志

MySQL中日志种类很多，包括错误日志、查询日志、慢查询日志、事务日志、二进制日志几大类。其中较为重要的是MySQL自带的binlog和InnoDB引擎独有的redo log

binlog

binlog是一种逻辑日志，记录了语句的原始逻辑。不管使用什么存储引擎，只要发生了表数据更新，都会产生binlog日志。主要用于MySQL数据库的数据备份、主备、主主、主从等操作的同步数据。

binlog日志有三种格式：statement、row、mixed。

• 第一种会记录执行的sql语句，但诸如now()这种函数直接执行可能会导致不一致
• 第二种会记录sql语句和操作的具体数据。这是默认格式。但比较占用空间，影响恢复和同步的速度
• 第三种是前两者的结合。若某条sql语句可能会导致数据不一致，就用row格式，否则使用statement

binlog在事务提交和缓存满时都会写盘。具体怎么写盘取决于配置

binlog的部分配置参数如下

• logbin = mysql-bin 启用binlog
• max_binlog_size 设置每个binlog文件的大小
• expire_log_days 文件过期时间，到期删除
• binlog-do-db 指定的数据库的更新应该被记录
• binlog-ignore-db 指定忽略的数据库
• sync_binlog 指定写入几次后触发写盘
  • 0时只有在缓存满时才刷盘
  • 1时每次事务提交都刷盘
  • N时每提交N次刷盘

redo log

该日志让MySQL拥有了崩溃恢复能力。MySQL中的数据以页为单位，每查询一条记录，就会把磁盘中一页数据加载出来，放到缓存池里。更新表数据的时候，都是直接先在缓存池中更新，然后会把“在某个数据页上做了什么修改”记录到日志缓存(redo log buffer)中，接着在合适的时机刷盘到redo log文件中。

这个“合适的时机”，一般是

• 在事务提交的时候。至于事务提交几次看相关参数
• 当redo log已经占满了log buffer时
• 每秒的定期刷盘
• 触发CheckPoint时
• 正常关闭MySQL时

当MySQL崩溃重启时，会先检查redo log，对于未提交的事务，MySQL会通过undo log回滚这些修改。

MySQL的redo log采用环形结构在固定大小的文件组中循环写入。其机制依赖两个指针：write pos，指向当前的写入位置，和checkpoint，指向已被持久化的日志位置。这两个指针将环形空间分成两部分：空闲区域和未刷盘的数据脏页。

需要写入日志时，write pos向前推进，同时MySQL会定期执行checkpoint操作，将内存中的脏页定期刷盘，完成后即可将checkpoint指针向前推进，从而释放出旧日志占用的空间。

部分配置参数如下

• innodb_flush_log_at_trx_commit 设置刷盘策略
  • 0时，每次事务提交都不刷盘，性能最高但最不安全。因为崩溃时可能会丢失近1秒的事务
  • 1时，每次事务提交都刷盘，性能最低但最安全。默认值
  • 2时，每次事务提交时都只把log buffer里的redo log内容写入page cache。page cache是专门缓存文件，此处缓存redo log文件。性能和安全性介于两者之间（只有MySQL挂了就没事，但宕机了还是会丢失数据）
• innodb_redo_log_capacity 指定文件容量。日志文件组的文件数已固定为32
• innodb_log_file_size 每个redo log文件的大小
• innodb_log_files_in_group redo log文件个数
• innodb_log_buffer_size redo log buffer缓冲区大小
• innodb_max_dirty_pages_pct 脏页比例阈值

预写日志（WAL `Write-Ahead Logging）是InnoDB实现十五持久化的核心机制，它的思想是先写日志再刷硬盘。
在修改数据页前，先将修改记录写入redo log，这样的话，即使数据页尚未写入磁盘，系统崩溃时也能通过redo log恢复数据。

undo log

每一个事务堆数据的修改都会被记录到undo log，当事务过程中出现错误或者需要执行回滚操作的话，MySQL可以利用undo log将数据恢复到事务开始前的状态。

两阶段提交

redo log让InnoDB拥有了崩溃恢复能力，binlog保证了MySQL集群架构的数据一致性。

当MySQL在预写redo log之后，写入binlog前崩溃，那么MySQL重启后InnoDB会回滚该事务，因为redo log不是提交状态。并且由于binlog中没有数据，所以库中也没有该事务的数据。

假如MySQL写入binlog后、redo提交前崩溃，那么MySQL重启后InnoDB会提交该事务，因为redo log时完整的prepare状态。并且由于binlog中有写入数据，所以库也会同步到该事务中的数据。

为了标识每一个事务提交，每一个事务提交都会生成一个独特的XID，提交时会写入一个XID_EVENT到binlog中，表示这个事务真正完成了。

Redo Log Buffer

redo log buffer一般是连续的内存空间，MySQL将其分为若干个连续的redo log block。为了提高写入效率，该buffer采用了顺序写入的方式，会先往前面的redo log block写入，当写满后再往后面的block写入。

MTR (Mini Transaction)是InnoDB内部用于操作数据页的原子操作单元。多个事务的redo log会议MTR为单位交替写入到redo log buffer中

一个MTR包含一组redo log记录，是MySQL崩溃后恢复事务的最小执行单元。

redo log block由日志头、日志体和日志尾组成，其中日志头占12字节，日志尾占4字节，剩余496字节存储日志体，共512字节。机械硬盘的物理扇区大小通常就是512字节，这样设计可以让redo log lock的每次写入都是整数个扇区，减少对齐开销。

日志头包含以下字段

• LOG_BLOCK_HDR_NO 当前block的序号，相当于block在buffer这个数组中的下标
• LOG_BLOCK_HDR_DATA_LEN block已使用的字节数，包含日志头
• LOG_BLOCK_FIRST_REC_GROUP block中第一个MTR起始处的偏移量
• LOG_BLOCK_CHECKPOINT_NO block最后被写入时的checkpoint

LSN是一个不断递增的64位无符号整数，代表了InnoDB重做日志系统中的位置标记。主要用于崩溃恢复及数据一致性保证等。

该数字单调递增，存在于redo log、数据页头部和checkpoint中。

慢SQL优化

MySQL中有一个叫long_query_time的参数，原则上执行时间超过该值的SQL就是慢SQL，会被记录到慢查询日志中。

可以使用show processlist命令查看当前正在执行的SQL语句，找出执行时间长的SQL。

索引

使用索引可以使查询速度大大加快，但其创建和维护耗时较长，也会有额外的存储花销。

创建索引时，注意要选择合适的字段，比如频繁出现在where join order by group by中的字段，并优先选择区分度高的字段。并且要控制索引的数量，避免过度索引。不适合在频繁更新的列中创建索引。

在以下情况下，索引会失效

• 使用select语句时，查询范围过大
• in的取值范围较大
• 对索引列使用了函数
• 使用通配符开头（%等）进行like模糊查询
• 联合索引不满足最左前缀原则
• 使用or的时候链接非索引列条件

底层结构

除了哈希索引、BST索引、红黑树索引，目前大部分数据库和文件系统都采用B+树作为索引结构。

不用哈希或者BST的原因很好理解，但为什么不用平衡树呢？因为其每个节点最多只能有两个子节点，在数据较多时仍然需要时间。

B树与B+树的区别在于

• B树所有节点既存放键也存放数据，而B+树只有叶子节点存放键和数据，其他节点只存放key。这样非叶子节点就可以容纳更多的键值对。
• B+树的叶子节点有一条引用链，指向与它相邻的叶子节点
• B树的范围查询需要对B树进行中序遍历，而对B+树的范围查询只需要对链表进行遍历即可

因此B+树相比B树具有更少的IO次数，更稳定的效率和更适用于范围查询这些优势。

在InnoDB中，页的默认大小为16kb，当主键为bigint时，3层B+树通常可以存2000万条数据。

公式为

$最大记录数=分支因子^{树高度 - 1}\times 叶子节点容量$

B+树查询特定数据的时间复杂度为$O(\log_m N)$或$O(\log N)$

应用维度

主键索引

数据表的主键使用的就是主键索引。在创建主键时，MySQL会自动生成对应的唯一索引。

在MySQL的InnoDB表中，若没有指定表的主键时，InnoDB会自动检查表中是否有唯一索引且不允许有null值的字段，有则选择该字段为默认主键、否则InnoDB会自动创建一个6 byte的自增主键。

另外说明下自增主键的情况。

MyISAM将自增值保存在了文件中，而InnoDB在MySQL5.7前将自增值保存在了内存里，打开表的时候回去找自增值的最大值，以这个值加1作为当前表的自增值。

在以下情况下，自增id可能会不连续

• 事务回滚，事务没有操作，但id增加了
• 插入失败，也是类似的状况
• 批量插入失败，同理
• 手动指定id值

稀疏索引

只在索引列中创建索引项，这意味着索引项的数量比数据行的数量少得多。对于存在大量重复值或大量空值的列，稀疏索引可以显著减少索引大小。

二级索引

二级索引的叶子节点存储的数据是主键的值，通过二级索引可以定位主键的位置。二级索引又可以称为辅助索引。

唯一索引、普通索引、前缀索引等都属于二级索引

唯一索引 unique index

主键索引= 唯一索引 + 非空。一个表中可以有多个唯一索引，也可以插入null值。

普通索引 index

普通索引仅用于加速查询，不限制其唯一性，适用于需要高频写入或范围查询的字段。

全文索引

在建表时，可以通过fulltext(title, body)来定义全文索引，通过match(col1, col2) against('keyword')进行检索，默认按照降序返回结果，支持布尔模式查询。在字符串前拼接特定符号可以表示不同含义

• + 必须包含
• - 表示排除
• * 表示通配符

注意，要处理中文分词的话，一定要记得加上with parser ngram，否则可能查不出来数据。

聚簇索引

聚簇索引即索引结构和数据结构一起存放的索引，在叶子节点存储了完整的数据行，InnoDB中的主键索引就属于聚簇索引。其优点在于查询速度快，及对排序查找和范围查找的优化好；缺点在于其依赖于有序的数据，即更新代价大。

非聚簇索引即索引结构和数据分开存放的索引，MyISAM引擎不论主键还是非主键，使用的都是非聚簇索引。

使用非聚簇索引进行查询时，MySQL需要先通过非聚簇索引找到主键值，然后再根据主键值回到聚簇索引中查找完整数据行，这个过程称为回表。

非聚簇索引不一定需要回表查询，当用户需要查询建立了索引的数据时，直接返回即可。

MRR是InnoDB为了解决回表带来的大量随机IO问题而引入的一种优化策略。它会首先把非聚簇索引查到的主键值列表进行排序再按顺序去主键索引中批量回表，从而把随机IO转换为批量IO。

覆盖索引

覆盖索引，即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了，不需要回表查询。

联合索引

使用表中的多个字段创建索引，就是联合索引。如

ALTER TABLE `cus_order` ADD INDEX id_score_name(score, name);

在使用联合索引时，MySQL会根据索引中的字段排序，从左到右依次匹配查询条件中的字段。若查询条件和索引中的最左侧字段匹配，那么MySQL就会使用索引来过滤数据。在进行范围查询时，索引只能应用于最左前缀的最后一列，范围查询之后的列无法使用索引。

存在最左前缀原则的原因在于，联合索引在B+树中是按照最左字段优先排序构建的，如果跳过最左字段，MySQL就无法判断查找范围从哪开始，自然无法使用索引。

像性别这种字段，区分度低，不适合作索引。但要是该字段经常用于查询条件，那也可以和区分度高的字段作为联合索引的一部分。

联合索引底层依然是B+树。然而，其每个节点会存储所有索引列的值，而不仅仅是第一列的值。

联合索引属于非聚簇索引，叶子节点存储的是联合索引各列的值和对应行的主键值，而不是完整的数据行。

在操作符左右两边的数据类型不一致时，就会发生隐式转换。在where查询时操作符左边为数值类型时若发生隐式转换还好，但左边为字符类型时就会导致索引失效。而将字符串转换为数值类型时，非数字开头的字符串会化为0，以数组开头的字符串会截取从第一个字符到第一个非数字内容为止的值作为转化结果。

索引下推

索引下推(ICP)是一项索引优化功能，它允许存储引擎在索引遍历的过程中，执行部分where字句的判断条件，直接过滤掉不满足条件的记录，从而减少回表次数。所谓的“下推”其实就是将部分server层负责的事情交给了存储引擎层去处理。