MySQL 之 InnoDB Index 浅谈

MySQL 一直是 RDBMS 型数据库中用户最多，使用最广的数据库。主要是因为它开源、免费、文档丰富等。在 MySQL 查询优化中，提得最多、用得最广的就是 Index, 那我们就来慢慢的揭开它神秘的面纱吧。

Structure

InnoDB-physical-structure-overview.png

MySQL 是基于磁盘的数据库，所以 MySQL 的所有信息皆是以文件的形式存储于磁盘，我想这是借鉴了 Linux 的设计哲学 "Everything is a file" 吧。进入 MySQL 使用如下命令查看数据目录。

mysql> show variables where Variable_Name LIKE "%dir";
+---------------------------+----------------------------+
| Variable_name             | Value                      |
+---------------------------+----------------------------+
| basedir                   | /usr/                      |
| character_sets_dir        | /usr/share/mysql/charsets/ |
| datadir                   | /var/lib/mysql/            |
| innodb_data_home_dir      |                            |
| innodb_log_group_home_dir | ./                         |
| innodb_tmpdir             |                            |
| lc_messages_dir           | /usr/share/mysql/          |
| plugin_dir                | /usr/lib/mysql/plugin/     |
| slave_load_tmpdir         | /tmp                       |
| tmpdir                    | /tmp                       |
+---------------------------+----------------------------+
10 rows in set (0.00 sec)

Spaces

进入 datadir/database 目录, 文件分为 .frm 与 .ibd 两类文件，分别是表的结构文件与数据文件。以 var/lib/mysql 为数据目录，repldb 为 db_name, repl_tab1 作为表名，展示如下:

root@mysql-master:/var/lib/mysql/repldb# ls -l
-rw-r----- 1 mysql mysql    61 Apr 28  2019 db.opt
-rw-r----- 1 mysql mysql  8676 Apr 28  2019 repl_tb1.frm
-rw-r----- 1 mysql mysql 98304 Apr 28  2019 repl_tb1.ibd

以上是我们可以简单看到的物理文件，那在 MySQL 的逻辑当中，它又是如何的呢? InnoDB 的数据存储使用 "spaces" 进行存储，通常我们叫它 "tablespaces", 有时候 InnoDB 内部也叫它 "filespaces"。一个 space 可由 1 个或 n 个实际的文件组成(如: ibdata1,ibdata2 等, 多个文件时，它们带有特定的顺序和序号)，但不管它由多少个实际的文件进行存储，它只组成一个逻辑文件, 每个 space 文件在 InnoDB 中被赋于一个 32-bit Int 的 space_id 作为标识符。.idb 可以包含多个表文件，但是在 MySQL 的实现中，一个 .ibd 文件只包含一个表，所以把一个 .ibd 文件等价于一个表文件。

Pages

前面已经知道 MySQL 把每个表的数据存储在一个 data file 也就是 .ibd 文件中，又因为 MySQL 是基于磁盘的数据库系统，那是不是查询的时候把物理文件一次性加载到内存当中，然后再进行过滤查询呢？或者进一步的也文件流的形式载入内存，然后再过滤呢? 是的，MySQL 的查询确实需要把物理文件加载到内存才能进行处理，但是 MySQL 的操作都不是前面提到的两种方式。MySQL 采用 "分而治之" 的办法，把 .ibd 逻辑分割成小块，然后每次加载一个或几个块到内存再进行处理，这就是 MySQL 的查询处理方式，这些小块就是 MySQL 的数据处理最小单元。这些块在 MySQL 中称为一个Page, 有时也叫一个block, 每个Page同Space一样有一个32-bitInt 的标识符page_no, 每个page默认固定大小为16KB, 可通过参数 innodb_page_size 进行调整，如: 4K、8K、32K、64K 等。Page 由以下几部分组成详细:

Fil Header
Page Header
Infimun + Supermum Records
User Records
Free Space
Page Directory
Fil Trailer

Page 与 Page 之间是否是互不相关呢? 各 Page 之间的关系在 Page 的 Fil Header 中进行定义， Page 之间以 Doubly-Linked的方式进行关联，Page 的结构详细如下:

FIL_PAGE_SPACE //就是所谓的 `page_no`
FIL_PAGE_OFFSET
FIL_PAGE_PREV //指向前一个 Page
FIL_PAGE_NEXT //指向后一个 Page
FIL_PAGE_LSN  //LSN: log serial number
FIL_PAGE_TYPE
FIL_PAGE_FILE_FLUSH_LSN
FIL_PAGE_ARCH_LOG_NO

Records

经过前面的了解，我们已经知道真实的数据是分布在 space 空间的每个 page 内，那如何才能得得到每行数据记录呢？Page 的组成部分中有一项 User Records, 那就是真实数据存储位置。当然了，Record 有自己的结构，主要分为 Compact 和 Redundant 两种格式，但不管何种格式，它里一个指向下一条记录的数据 next_record, 通过这样的方式，各 Record 就以 Singly-Linked 的形式进行连接。

Index

通过前面的介绍，我们已经知道了 MySQL InnoDB 引擎对于数据的处理方式和存储结构，当我们查询数据时，先定位 Table Space、再定位 Page、最后定位 Record，这是一个完整的数据查询过程。那 Index 能够帮助我们做什么呢？ Index 其实就是帮助我们快速定位记录，缩短 space --> page --> record 这个过程。

MySQL 是基于磁盘的数据库系统，有说过它的设计哲学和 Linux 的 "Everything is a file" 的设计哲学相符，那么 MySQL 的 Index 的设计哲学又是什么呢?

"Everything is an index in InnoDB".

Index 分为 Clustered Index 和 Secondary Indexes 两类, MySQL 中的索引的存储根据不同的数据表和引擎又采用不同的形式，一般情况通常采用 B-Tree 索引, 空间数据采用 R-Tree索引, 内存数据采用 Hash 索引，文档数据采用 Full Text 索引等。

Clustered Index

MySQL 中以 InnoDB 作为引擎时，每张表有且仅有一个 Clustered Index，而且每张表必须有一个 Clustered Index，下面详细了解一下 Clustered Index 的生成规则。

有主键时，InnoDB 使用它作为 Clustered Index;
无主键
- 有 unique 列且 not null 列, MySQL 用第一个符合该条件的列作为 Clustered Index;
- 且无合适的 unique 列, InnoDB 会内部生成一个名称为 GEN_CLUST_INDEX 的隐藏索引，该索引以隐藏的 6-byte 的 row_id 列作为索引列，该列以数据行插入的顺序进行排序;

Q: 那为什么一定要有一个Clustered Index呢?

A: 因为 MySQL 需要快速定位 Record, 所以必须要有一个索引，就像书的目录一样，通过索引就可以快速定位到记录对应的 Page。

Q: 那索引里面存储的是什么呢?

A: Clustered Index 里面包含了 索引列 和 page 的映射关系，而且直接指向了 page 中的行记录, 而这也是Clustered Index 之所以快的原因。

Secondary Indexes

MySQL 中有仅仅有一个 Clustered Index，但是对于 Secondary Indexes 则可以存在多个(这也是两个 Index 的写法分单数复数的原因)。在 InnoDB 中所有的 Secondary Indexes 都是基于 Clustered Index 的，每一个 Secondary Index 都包含 Primary Keys, 也就是 Clustered Index 中的索引列。

Q: Secondary Index 也是直接指向 page 中的记录吗？

A: Secondary Index 并不直接指向 page, 它先指向 Clustered Index 然后再指向 page 内数据 (这种情况也称为回表)。

Index-selective

Leftmost Prefix

当有多列索引(multiple-column，也叫联合索引) 时，索引形式如(c1, c2, c3), 查询条件如 (c1), (c1, c2) 以及 (c1, c2, c3) 均可利用到该索引。
Index-Extensions

InnoDB 自动把 Primary Key 附加到 Secondary Index 后面，如 PK(c1, c2), 同时也定义了 Secondary Index 其包含 (c3), InnoDB 内部优化器 (optimizer) 会把其扩展为 (c3, c1, c2) 的形式, 从而提高查询效率。该功能需要通过指令 SET optimizer_switch = 'use_index_extensions=off' 进行启动和停用，InnoDB 默认属于开启状态。
Index-Merge

所谓索引融合，就是对多个索引进行条件扫描，然后再把它们的结果合并。
Index-Cover

所谓索引覆盖，就是查询的列通过索引就能够取得，这种情况下不需要再定位到page去取数据。避免了磁盘读写、回表查询等操作，所以这种情况比一般的索引查询效率更高。

pros and cons

当了解了索引的功效之后，我们是不是为表建立越多的索引越好呢? 并不如此，索引也有它的适用范围，和代价，所以并不是索引越多越好。

Pros

减少数据量的扫描；
当索引列有排序操作时，可以避免服务端的排序与临时表的产生；
可以把随机的磁盘 I/O 变为顺序的 I/O;

Cons

当数据量少的时候建立索引其实并没有什么用，如果数据量还不足一个 page, 而 page 又是数据处理的最小单位，所以这个时候有没有索引都一样；那当数据量很大的时候呢，这个时候如果数据量非常大，那么索引文件相应的也变得很大，如果 MySQL 需要多次才能扫描完索引的内容，那么这时候索引也没有用了，因为索引的读取也得造成磁盘的 I/O, 且也不能短时间定位到对应的数据。而且索引的建立也是有一定的代价的，如每次插入数据时，相比于无索引情况需要另外的磁盘写操作，对应的也占用更多的磁盘空间，读取的时候相应的也占用更多的内存容量，数据更新随之而来的也是索引更新成本。

Summary

索引并不适用于所有的情况，只有当索引的成本小于它的代价时，才是有效的索引。所以建立索引时需要综合考虑实际的业务场景，再结合 MySQL 查询优化器以及索引选择原理才能够建立适合自己业务的索引。

Appendix

B+tree 为什么快 ?
查询到底什么了什么索引 ?
Page 详细结构 ?
Record 详细结构 ?

微信公众号