之前有介绍过redis相关知识：redis的三高架构设计实现分析，不过redis主要是内存数据库，所以redis的优化方向主要是内存数据结构，对于磁盘持久化部分而言，不管redis 采用RDB 还是 AOF方式，对于磁盘的写，都是以顺序写的方式，基本上不存在数据更新的随机写操作，因此很多写磁盘文件的常用设计方案都不会涉及。

因此，为了想了解文件操作的一些优化思路，顺便对我们日常开发中经常使用的数据库更深入一点的了解，本文将对基于InnoDB引擎的MySQL数据库做一个稍微深一点的介绍。

MySQL InnoDB 介绍主要分为两部分：

数据查询部分，主要是索引相关介绍；
MySQL InnoDB 关于 ACID部分的实现设计。

本文主要介绍 MySQL InnoDB关于数据查询部分的设计。本文主要的脉络，主要是：

首先介绍一个查询请求，从客户端到 MySQL Server 端的处理，以及被存储引擎的处理主流程；
然后在从InnoDB存储引擎的层面，探讨支持查询所采取的数据结构和处理流程；
接着，看MySQL Server 端对查询请求做的一些优化，来加快查询效率。

在开始深入了解MySQL查询设计之前，先整体了解下MySQL架构，以及常用的InnoDB存储引擎架构。

一、MySQL & InnoDB 总体架构

从MySQL官网给出的带有可插拔存储引擎的MySQL架构图，来看一个MySQL的整体结构。

整体看，MySQL架构图，主要包括两大部分：MySQL客户端和MySQL服务端。

MySQL客户端，一个是我们常在terminal控制台通过命令方式连接，到MySQL服务端操作数据库相关数据和配置的端口；一个是在不同应用程序中，代码连接数据库操作数据的语言工具包，例如Java常用的JDBC。

MySQL服务端，是整个MySQL架构的核心，其内部主要包括两大部分：一个是MySQL自身的通用处理功能；另一个就是可插拔的存储引擎，比如常用的InnoDB引擎。

MySQL Server 自身主要处理 SQL命令的请求，词法和语法的解析，然后对生成执行计划，对于查询选择适合的索引，接下来就是执行器将执行语句交给存储引擎，返回最终执行结果。

关于存储引擎，比较复杂，对于日常业务的使用，也是最重要的。需要了解对应的存储引擎细节，才能评估技术方案的可行性，同样，在业务出现数据库问题的时候，也能快速定位问题，找到解决思路。

1.1 可插拔存储引擎层

MySQL 可插拔存储引擎是 MySQL 数据库服务器中的组件，负责为数据库执行实际的数据 I/O 操作，以及启用和执行针对特定应用程序需求的某些功能集。采用插件模式组装到MySQL Server中，可支持InnoDB、MyISAM、NDB Cluster等等，这些存储引擎插件，都实现了同一套标准的管理接口和服务。

这带来了很多好处，首先就是，使用者可以基于不同的场景，使用不同的存储引擎。比如，InnoDB引擎可以很好地支持ACID和事务场景的诉求；MyISAM引擎如果业务没有事务的诉求，但是对全文检索有要求，可以尝试用这个引擎；如果你做一些简单的key查询，那么MEMORY引擎可以已内存模式通过hash索引来支持，等等。因为每个存储引擎只提供特定应用程序所需的功能，因此您在数据库中的系统开销更少，最终结果就是可以设计出更高效和更高性能的数据库。

另外一个好处，就是应用程序开发的统一性，基于不同场景的引擎，在开发接口层面上都可以用一套编码解决。

此外，当我们有全新的存储诉求，或者更优秀的引擎设计思路，可以基于MySQL提供的标准规范和接口，进行引擎组件的开发，成本非常低，开发效率最高。现在，互联网公司，在推行的中台，内部通过能力中心+业务流程编排来完成更多业务支撑，不同场景只是针对一些能力的替换即可完成新场景的开发上线。

1.2 InnoDB 引擎架构

InnoDB引擎，主要包括两部分，一部分是InnoDB内存结构，另一部分就是InnoDB磁盘结构。

在内存结构里面，主要就是各种buffer缓冲区，这些缓冲区对于提升数据库性能上至关重要。

Buffer Pool，缓冲池。缓冲池允许直接从内存中处理经常使用的数据，从而加快了处理速度。在专用服务器上，通常将多达 80％的物理内存分配给缓冲池。
Change Buffer，更改缓冲区。这块缓冲区，是存放在Buffer Pool内部。更改缓冲区是一种特殊的数据结构，当这些页面不在Buffer Pool中时，该缓存可缓存对二级索引页的更改。可能由INSERT、UPDATE，或 DELETE操作(DML)导致的缓冲更改将在以后通过其他读取操作将页面加载到缓冲池中时合并。也就是说，其对应的数据不需要从磁盘加载到Buffer中，而是将变更存在在Change Buffer内，等待合适时机再merge 回去。
Log Buffer，日志缓冲区。主要用来存放redo log 数据。

在磁盘结构里面，就是各种类型的文件。所有的数据，最终都需要落到各种磁盘文件上来保证数据的持久性。核心的文件主要有：

表和索引文件。
double write buffer文件。
undo log 文件。
redo log 文件。

表空间、表、索引这些文件，是真正数据文件。double write buffer 是由于linux页大小4K，MySQL页大小16K，直接将MySQL页写到磁盘，可能导致部分成功、部分失败导致后期数据恢复存在问题，因为增加了double write buffer做数据恢复的时候使用。undo log事务回滚和MVCC时需要找到历史快照数据。redo log 则是保证数据的持久和原子性而存在的。

二、数据查询主流程

从MySQL整体架构图，可以大概看得出来，一个SQL命令请求到达MySQL服务后的内部操作的处理过程，为了更清晰，这里给了一个流程图（来自 MySQL实战 | 01-当执行一条 select 语句时，MySQL 到底做了啥？）：

当有一个select查询请求过来，执行流程如下：

建立client-server连接。TCP连接，通过三次握手协议建立。由于我们数据库都需要权限限制，因此，建立TCP连接请求之后，会进行权限验证，也就是确认用户名密码，验证完成之后，通过用户名，可以知道本次连接对应的用户权限，然后将用户权限信息缓存起来，后面的SQL操作的前置权限验证，就直接通过缓存来比较。额外说下，建立client-server连接，会提供给后面SQL复用，一般我们会对一个连接做超时时间限制，如果这个连接在指定的超时时间内没有请求过来，才会关闭连接。show processlist 可以看到连接的持续时间。
分析SQL请求。MySQL Server 会对SQL进行词法分析、语法分析，验证SQL的合法性，然后就有了一个分析后的 SQL语法树。
有了分析后的语法树，MySQL 会进行优化工作。例如，评估执行计划，选择合适的索引；通过提前计算，优化where子句等等；
经过优化器后，我们可以最终产生执行计划。在执行之前，做一次表操作权限的验证，然后调用具体的存储引擎来执行IO查询。

三、InnoDB引擎查询支持

从上面的主流程，可以看到核心的查询，最终是存储引擎 InnoDB来完成的。

3.1 InnoDB 存储结构

在InnoDB的引擎架构图中，可以发现，核心的数据库业务数据和索引，都是存在各种表空间中，以ibd格式文件存储。表空间，也就是 ibd文件的逻辑存储结构，如下图所示：

如上图，表空间由段segment、区 extent、页 page 、行row 四种结构组成。一个表空间由多个段组成，主要是数据段，索引段，回滚段等。数据段存储数据，也就是图中的叶子节点；索引段存储索引，也就是图中的非叶子节点；回滚段存储undo 日志。每个段，由多个区组成，MySQL中每个区大小是1M，每页的大小为16K，因此，每个区有64页。

页，是InnoDB的最小存储单元。16K大小，一般linux页是4K，所以一个MySQL页相当于操作系统4个Page。每个页有文件头(File Header)、页头(Page Header)、页目录(Page Directory)等，在文件头字段中，有两个很重要的指针：FILE_PAGE_PREV 和 FILE_PAGE_NEXT，也就是InnoDB中叶子节点维护的连接是一个双向链表。此外，页目录中存放了记录的相对位置，但是多个记录按照顺序共享一个页目录内部的slot记录，方便利用二分搜索找到记录大概位置。

每个页里面有多个行记录，每页存储最多的行记录也是有硬性规定的最多16KB/2-200,即7992行。实际上，对我们的业务而言，这个数字并没有多大用处，一般我们采用utf8mb4编码，为了有业务含义，一行的平均大小不可能为2，所以这里只是讲讲而已。

上图列出了一行的数据结构：事务id，回滚指针，rowid等隐藏列，列数据列表。下面具体说下行记录结构。

变长字段长度列表。此字段表示列字段的长度，与列字段顺序相反存放。如果长度小于255，则一个字节表示；否则，使用两个字节表示，也就是65535。因此，MySQL InnoDB中的varchar字段最大长度为：65535。 但是，这里的65535是字节长度，如果使用utf8mb4编码，则显然会比这个小很多，一般utf8mb4至少占2字节。
NULL标志位。标识改列是否有空字段，有用1表示，否则为0。
记录头信息。主要的几个字段：deleted_flag，删除标识；record_type，记录类型，0是普通记录，1是B+树非叶子节点记录；next_record，下一个行记录。

以上，就是InnoDB 存储引擎的存储结构。因此，我们知道一个page的大小是16K，那么如果一行记录超过了一个page，数据怎么存储呢。在InnoDB中，有一种溢出页面类型，专门用来存储那边超长的列，这些页单独放在磁盘上。因此，我们在设计数据表的时候，尽量需要保证数据长度，否则在select *的时候，还需要单独去溢出页面所在的磁盘位置，获取具体列的数据，成本非常大。

3.2 InnoDB 索引数据结构

众所周知，MySQL InnoDB 使用 B+树结构存储数据和索引。数据本质上也是索引，称为聚集索引，索引键为主键id，然后将行记录的数据带上。非聚集索引，也就是常说的，辅助索引，索引键带的数据是id，查询的时候，先找到id，然后通过id，找到对应的行数据。

首先，给出B+树的数据结构图，然后我们再来说，使用B+树作为索引数据结构的优势。

以上就是B+树的数据结构图（来自维基百科）。B+树的特点，就是非叶子节点存索引数据，不存具体数据，就是图中的d1，d2等；另一个特点，就是各个叶子节点通过指针进行连接，因此可以从头部往后遍历。

3.2.1 B+树的优势

我们在做方案设计和技术选型的时候，最大的一点就是基于需求和场景思考，不存在一个万能的技术方案。因此，对于为啥InnoDB采用B+树数据结构作为最终的方案，需要首先来分析数据库的需求和场景。

数据库的最基础最核心的功能，就是数据的持久化和数据的查询。数据的持久化，就是数据需要存储在磁盘设备上；因此，数据的查询，就是需要从磁盘设备上将数据读取出来，进行数据过滤加工等处理后，返回给客户端。此外，数据持久化和查询的业务，一般都是在线业务，需要做到实时返回。

总结下来，对数据库的需求就是，需要支持实时响应客户端的数据磁盘存储，以及有条件的数据查询。那么，技术选型，就是在上面的需求背景下，如果选择一个可以提供更高性能的数据结构。

可以选的数据结构虽然很多，比如hash结构，各种二叉树结构，B树结构，B+树结构等等。B+树如何在种种数据结构中胜出？

首先看各种二叉树。首先从数据的查询而言，二叉树是2分支，B/B+树是N分支，显然B/B+树的查询效率，高于二叉树。对于B/B+树，每个节点块内部二分查找。
然后再来看hash结构。虽然说，hash结构的查询复杂度是O(1)，但是对于范围查询而言，就无法适用。但是range查询，在日常数据库查询中是非常常见的，所以通常场景下不会考虑hash结构。
最后看看B树结构。B树和B+树的区别，是B树的数据存储在各个节点中，而不仅仅只有叶子节点有；此外，B树的叶子节点间没有指针连接。叶子节点没有指针连接，范围查询非常不便，此外树上所有节点都有数据，会导致各种数据局部性很差。

基于以上，发现B+才是最适合通用业务场景下的数据结构选型。

3.2.2 聚集索引特别说明

从B+树的数据结构来设计 InnoDB 存储数据结构。InnoDB是操作磁盘，结合InnoDB存储结构，最终的InnoDB数据结构实现中，所有B+树的非叶子节点，使用索引页；而最下面的叶子节点，使用数据页。页大小为16K，数据页最后一个记录next_record指针，指向下一页的第一个记录。

B+树插入数据的过程中，会有一个现象称为分裂，因为B+树每个节点能存放的数据量是有限制的，超过了就需要分裂，小于某个值就需要合并。映射到InnoDB实现上，就称之为页分裂。由于我们说每个节点是存在数据量的大小范围的，因为分裂创建新节点之后，还需要copy一部分数据到新的节点，这种操作其实很消耗性能。

所以，这就是为什么我们说，在业务表设计中，没有特殊诉求下，尽量使用自增主键id作为聚集索引。由于id是自增的，后插入的肯定在先插入数据的后面，所以不会涉及页分裂，因此就不会有数据的copy操作，性能上会最优。

一颗聚集索引B+树可以放多少行数据？

这里我们先假设B+树高为2，即存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：根节点指针数 * 单个叶子节点记录行数。假设一行记录的数据大小为1k，那么单个叶子节点（页）中的记录数=16K/1K=16。

那么现在我们需要计算出非叶子节点能存放多少指针，我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共 14字节，我们一个页中能存放多少这样的索引单元，其实就代表有多少指针，即16kb/14b=1170。那么可以算出一棵高度为2的B+树，大概能存放1170 * 16=18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树大概可以存放：1170 * 1170 * 16=21902400行数据。所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次逻辑IO操作即可查找到数据。

3.3 InnoDB 存储引擎的查询流程

之前我们介绍过，MySQL Server内部的执行器在收到客户端的select 请求之后，是会调用存储引擎的接口，获取最终数据的。

我们说过，InnoDB内部使用的数B+树数据结构，并且B+树的叶子节点间保持一个双向链表。

首先，在MySQL Server中经过分析器、优化器之后，已经有了一份执行计划，这份执行计划会告知需要使用哪个索引进行数据查询。

接下来，从磁盘将对应索引的根节点Page读入内存中。然后按照标准的B+树查询方式进行数据查询。通过前面介绍知道，这里查询到的，只是数据所在的叶子节点的页表。

接着，我们获取到数据页到内存之后，一般而言，由于页中的记录，是通过指针进行关联的，只能通过遍历来查找。为此，上面介绍 InnoDB Page结构的时候，里面的页目录(Page Directory)就有了用场。通过对页目录使用二分查找就可以定位出记录的大概位置，然后通过这个位置一个个遍历过去。

最终，我们拿到了叶子节点的数据。此时，如果是聚集索引，就可以直接拿到最终记录数据返回；否则，则需要通过主键id，去聚集索引再回表查询一次。

一般的，很多时候我们查询的数据，并不是最终客户端需要的数据，因为 MySQL Server 提供的执行计划使用的某个索引只能过滤掉一部分数据，这个时候就会把剩余的全量数据返回，然后由 MySQL Server 在内存中按照查询条件进行再一次的过滤，最后才返回给客户端。

3.4 覆盖索引

在上面介绍辅助索引查询完成之后，还需要回聚集索引表再查下一次数据，这个成本也是非常高昂的，这个时候，就需要考虑看能不能进行一些优化。

于是，基于一些特定查询场景，就有了优化方案：覆盖索引。

覆盖索引是指在普通索引树中可以得到查询的结果，不需要在回到主键索引树中再次搜索。

覆盖索引，日常使用最多的时候，可能就是count(id)的时候，where命中索引，count 记录数，完全不需要回标。在业务过程中，一般不追求更极致性能情况下，很多时候，还是使用select 全量字段返回，便于sql复用。

3.5 索引下推ICP

在介绍ICP之前，先说一下InnoDB索引中众所周知的最左前缀匹配。所谓最左前缀，就是说我们查询数据的时候，where条件，和联合索引的字段顺序，需要满足从左到右的顺序，也就是如果第一个字段没有where限制，而只有第二个字段有，则是不满足最左前缀，不能通过索引优化查询效率；此外，对于当个字段的字符串，如果使用like查询，也是按照最左前缀原则进行。

此外，按照最左前缀，如果第一个字段使用的是范围查询，那么第二个字段无法使用上索引的过滤，按照MySQL 以往的规则，需要在Server中进行过滤。

但是，如果使用了索引下推技术，则可以避免这些数据，回到Server中，进行内存过滤，尤其是当数据量大的时候，则会严重损害性能，并且占用内存。

此外，需要说明ICP只适合，命中联合索引的范围查询，非唯一的等值查询等。

一般，我们通过explain查看执行计划的时候，可以看到extra中Using index condition信息，这个就是执行了索引下推。但是，并不代表最终执行了索引下推动作，比如，索引下推，这个点你肯定不知道中介绍的一个表两个索引下，由于查询不可能同时走两个索引，所以也就不可能会有 ICP的出现，但是在explain的时候，还是发现了Using index condition。

四、MySQL Server查询优化支持

4.1 索引合并优化

索引合并优化，其实蛮少见的，虽然其在MySQL 5.0就已经提供了。当我们只想explain查询执行计划的时候，type类型为index_merge时，就表明本次查询使用了索引合并优化。

所谓的索引合并优化，通常是将多个索引字段的范围扫描合并为一个。包括单表中多个索引的交集，并集以及交集之间的并集，但不包括跨多张表和全文索引。

该优化特性主要应用于以下三种场景：

对 OR 语句求并集，例如，查询 SELECT * FROM TB1 WHERE c1="xxx" OR c2=""xxx"时，如果c1和c2列上分别有索引，可以按照c1和c2条件进行查询，再将查询结果合并union操作，得到最终结果。
对 AND 语句求交集，例如，查询SELECT * FROM TB1 WHERE c1="xxx" AND c2=""xxx"时，如果c1和c2列上分别有索引，可以按照c1和c2条件进行查询，再将查询结果取交集join操作，得到最终结果。
对 AND 和 OR 组合语句求结果。

该优化不一定会发生，MySQL会根据优化后的效率是否更优来决定优化器是否进行优化。同样，由于MySQL统计信息和预测效果并不好，导致优化后的效率非常差，最终导致严重的线上故障，因此，很多公司直接把这个优化给关闭。

关于索引合并优化，可以参考：索引合并优化(Index merge optimization)

五、结尾

本文主要介绍基于InnoDB存储引擎的MySQL查询工作原理。在实际工作中，数据库查询在业务开发过程中处于一个非常重要的地位，因此，对于数据库的查询底层工作原理的了解，可以有助于我们更好的设计查询方案，利用InnoDB索引的特点和优化，来得到最高效率的查询响应。

由于，MySQL 处理查询SQL的时候，优化器的分析和最终索引选择，会直接导致查询效率，因此，在实际开发中，当出现和预期不一致的查询效率问题时，需要使用explain工具来协助定位。

没有期望的分布

MySQL InnoDB 查询部分核心设计和原理