数据库底层 - 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. 段
   段是一个表或索引的存储容器, 也就是一个逻辑空间分配单位, 由一个或多个区组成。每个索引会使两个段来管理，数据段(叶子段)和索引段(非叶子段).

其中，数据页由7部分构成，分别为文件头、页头、文件尾（这三者大小是固定的，用来标记该页的一些重要信息）、行记录、空闲空间、页目录、空闲空间。每个数据页的文件头都有上一页和下一页的编号，所有的数据页会形成一个双向链表。

MySQL架构

字节跳动, 中国交易与广告 - 实习, 一面

MySQL的基础架构如下

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

语句分析

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

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

腾讯混元 - 实习, 一面.

OPPO 后端工程师 - 实习, 二面

而执行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. 后续工作
   告知客户端执行成功，并在后台异步将“脏页”刷回到磁盘的.ibd文件中。因为有Redo Log保证了即使此时崩溃数据也不会丢失，因此MySQL不需要在事务提交时立即执行慢速的磁盘随机写。

InnoDB

InnoDB的内存结构如下

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

Buffer Pool

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

在内存在 1GB~4GB RAM 的系统上，默认值为系统 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中日志种类很多，包括错误日志、查询日志、慢查询日志、事务日志、二进制日志几大类。其中较为重要的是 Server 层通用的 binlog 和 InnoDB 引擎独有的 redo log

binlog

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

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

• 第一种会记录执行的sql语句，但诸如 now() rand() 这种函数直接执行可能会导致主从不一致
• 第二种会记录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文件中。

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

• 在事务提交的时候。至于事务提交几次看相关参数
• 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。性能和安全性介于两者之间（只有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恢复数据。

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

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

undo log

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

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 block的每次写入都是整数个扇区，减少对齐开销。

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的原因很好理解，但为什么不用平衡树呢？因为其每个节点最多只能有两个子节点，在数据较多时树太高，磁盘 IO 次数多，仍然需要时间。而 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字节的自增主键。

InnoDB在MySQL5.7前将自增值保存在了内存里, 现在则是再每次变更后都写入 redo log 中, 并定期持久化道数据字典(mysql.ibd)里.在以下情况下，自增id可能会不连续:

• 事务回滚，事务没有操作，但id增加了. 因为自增值在插入语句执行初期就预分配了, 属于语句级, 非事务级分配.
• 插入失败，也是类似的状况
• 批量插入失败，同理
• 手动指定id值

稀疏索引

仅为索引列的部分值创建索引项，索引项的数量远少于数据行数。对于存在大量重复值或大量空值的列，稀疏索引可以显著减少索引大小。

如在 gender 列只有 M/F/U 三种, 稀疏索引只需要三条索引即可. 然而, InnoDB 本身没有这种索引. 这种索引形式常见于搜索引擎(如 ES 等).

与这个概念相对的是稠密索引, 一般用的就是这种索引.

二级索引

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

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

唯一索引 unique index

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

普通索引 index

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

全文索引

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

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

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

聚簇索引与非聚簇索引

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

非聚簇索引即索引结构和数据分开存放的索引. 使用非聚簇索引进行查询时，MySQL需要先通过非聚簇索引找到主键值，然后再根据主键值回到聚簇索引中查找完整数据行，这个过程称为回表。非聚簇索引也不一定需要回表查询，当查询所需字段全部都在索引中时，直接返回即可。

MRR (Multi-Range Read) 是 InnoDB 为了解决回表带来的大量随机 IO 的策略。它会首先把非聚簇索引查到的主键值列表进行排序, 再按顺序去主键索引中批量回表，从而把随机 IO 转换为顺序 IO。

除此之外, MySQL 还会进行索引下推(ICP), 即允许存储引擎在索引遍历的过程中，执行部分 where 条件，直接过滤掉不满足条件的记录，从而减少回表次数。所谓的“下推”其实就是将部分 server 层负责的事情交给了存储引擎层提前处理。

覆盖索引

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

联合索引

腾讯微信支付 - 实习, 一面.

美团后台开发 - 暑期实习, 一面.

OPPO 后端工程师 - 实习, 一面

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

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

使用时需要注意：

1. 最左前缀原则：B+ 树按最左字段优先排序，查询需匹配最左字段才能触发索引；范围查询后的字段无法使用索引；
2. 底层结构：仍为 B+ 树，节点存储所有索引列的值，叶子节点存 “联合索引列值 + 主键值”；
3. 适用场景：区分度低的字段（如性别）可与高区分度字段组合成联合索引。

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