1 B+树的数据结构

1.1 数据结构

B+树是为磁盘或其他直接存取辅助设备设计的一种高扇出性的平衡查找树。

B+树的B指的是平衡（Balance）。

在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各个叶子节点指针进行连接。

根据叶子节点的大小和数量，会选取各个叶子节点的首个键值构造出上一层父节点。

同样，根据上一层父节点的大小和数量，也会选取各个父节点的首个键值继续构造出再上一层父节点。

如此反复，直至最上一层父节点的数量为1，此时称该父节点为根节点。

在InnoDB存储引擎中，每个节点都代表磁盘中的一个页，所以在B+树搜索过程中，每次查询节点都会做一个磁盘IO操作。

1.2 B+树的操作（分裂）

B+树的插入和删除操作必须要保证各个节点的顺序性和平衡性，可能会涉及到节点的拆分和合并（特别是在并发情况下）。

需要注意的是，B+树的节点表示磁盘中的页，对磁盘页的拆分和合并是十分消耗性能的。所以，我们不能将经常修改的字段设置成索引。

另外，只要是插入数据就需要对B+树进行维护，所以应该尽可能避免在同一张表中添加过多的索引。

2 B+树索引

2.1 聚簇索引

在InnoDB存储引擎中，表都是根据主键顺序组织存放的，这种存储方式的表称为索引组织表。

这种主键索引也称为聚簇索引。

在聚簇索引中，非叶子节点的数据页中会存储主键值和子节点指针，叶子节点的数据页中会存储该表的行记录数据。

在创建表时，都会创建主键，并根据主键构造B+树表数据：

如果显示指定主键，则使用该主键作为索引键。
如果没有显示指定主键，会使用第一个创建的非空唯一索引作为索引键。
如果没有非空唯一索引，会自动创建一个6字节的rowid作为索引键。

在查询聚簇索引B+树时，会按照主键从根节点开始搜索：

读取根节点磁盘页到内存，通过计算找到子节点所在磁盘页的指针。
读取子节点磁盘页到内存，通过计算找到下一个子节点所在磁盘页的指针。
……
读取叶子节点磁盘页到内存，通过计算找到所需要的行记录，返回数据。

2.2 辅助索引

辅助索引又称为非聚簇索引，它的非叶子节点的数据页中会存储索引值和子节点指针，叶子节点的数据页中会存储该表行记录的主键值。

在查询辅助索引B+树时，会按照辅助索引从B+树根节点开始搜索：

读取根节点磁盘页到内存，通过计算找到子节点所在磁盘页的指针。
读取子节点磁盘页到内存，通过计算找到下一个子节点所在磁盘页的指针。
……
读取叶子节点磁盘页到内存，通过计算找到所需要的主键值。

获取到主键值后，再去查询聚簇索引B+树时，按照主键从根节点开始搜索：

读取根节点磁盘页到内存，通过计算找到子节点所在磁盘页的指针。
读取子节点磁盘页到内存，通过计算找到下一个子节点所在磁盘页的指针。
……
读取叶子节点磁盘页到内存，通过计算找到所需要的行记录，返回数据。

所以，根据辅助索引查询数据往往需要再次查询聚簇索引。

只有在需要查询的数据在辅助索引B+树中就可以获取到时，可以不必重复查询聚簇索引，这种情况称为覆盖索引（或索引覆盖）。比如查询的字段就是辅助索引值或主键值、根据辅助索引统计数量等。

3 为什么使用B+树

MySQL的数据都是储存在磁盘中的，逻辑上称为表空间。

表空间又由段、区和页构成，它们之间存在父子包容关系：

表空间由多个段组成。
段由多个区组成。
区由多个连续的页组成。
页是InnoDB磁盘管理的最小单位。

段分为：数据段、索引段和回滚段等。在B+树索引中，非叶子节点就存在于索引段中，而叶子节点存在于数据段中。

区的大小固定为1M，它由多个连续的页组成。

页的默认大小是16KB，可以通过设置参数innodb_page_size修改为4K、8K或16K。

根据所处段逻辑的不同，每个页会存储不同含义的数据，例如存储索引和记录的数据页（B-tree Node）。

在页的内部，它会按行存储数据，行记录有特定的格式。由于页的大小是固定的，所以行数会随着行记录的大小而改变。

在B+树索引中，每个节点表示一个磁盘中的页。对于一个查询语句，MySQL会按照如下顺序进行操作：

读取根节点磁盘页到内存，通过计算找到子节点所在磁盘页的指针。
读取子节点磁盘页到内存，通过计算找到下一个子节点所在磁盘页的指针。
……
读取叶子节点磁盘页到内存，通过计算找到所需要的行记录，返回数据。

因此，每次读取节点都表示一次磁盘IO操作，所以树的高度可以代表查找数据的次数。

为了减小磁盘IO操作次数，需要减小树的高度，B+树只在叶子节点的行记录中保存完整数据，而在非叶子节点的行记录中只保存索引键值和子节点指针。由于页的大小是固定的，行记录变小了，每页能存储的行记录就变多了。这样一来，B+树每层的扇出就变大了，大大减小了树的高度，大大减小了磁盘IO操作的次数，大大提高了查询数据的效率。

此外，B+树的叶子节点之间通过指针进行连接。对于范围查询来说，如果数据分布在连续的多个页中，MySQL不必回表查询索引页，可以直接根据指针查询下一页的数据。

4 B+树索引的使用和SQL优化

B+树索引主要应用在查询语句中。对于后端开发人员来说，对数据库的优化基本上就是指查询SQL的优化，而对查询SQL的优化基本上就是要让查询走索引，并且在走索引的过程中要尽量减少磁盘IO查询次数，即避免回表操作。

4.1 联合索引

联合索引本质上也是辅助索引，只不过它会对表上的多个列进行索引。

联合索引B+树的节点行记录中，会同时记录多个索引列，并且会按索引先后顺序分级别进行排序（类似于字符串的比较大小）。

例如，对于联合索引(a, b, c)：

在全局范围内，按a排序。
在a相等的范围内，按b排序。
在a和b都相等的范围内，按c排序。

举个数字作为例子：

(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 2, 2)
(3, 1, 1)
(3, 1, 2)

我们可以发现，在前一个索引列不相等时，后面的索引列的顺序时没办法保证的。

所以，我们在使用联合索引作为查询条件时，必须满足最左匹配原则，按联合索引从大范围进行逐步筛选。

此外，我们还可以发现，在前一个索引列（比如a）相等时，当前索引列（比如b）的值会按顺序排列。所以如果有这种特殊的按联合索引排序需求时，可以直接使用联合索引查询，减少一次内存的排序操作：

SELECT * FROM tb_test WHERE a = 1 ORDER BY b;

4.2 覆盖索引

覆盖索引并不是一种特殊的B+树，它时InnoDB存储引擎对辅助索引的一种优化操作。

如果查询条件满足某个辅助索引，并且查询数据可以根据辅助索引的叶子节点中的行记录获取，那么MySQL会直接从辅助索引中返回查询数据，避免了再次从聚簇索引中搜索的回表操作，大大减少了磁盘IO操作。

另一方面，由于辅助索引的叶子节点中存储的数据量小，每个叶子节点磁盘页能够存储更多行记录。相对于同一个表的聚簇索引而言，辅助索引所需要的叶子节点的数量更少，整体的非叶子节点数量和B+树的高度页随之变得更小。所以，在辅助索引中查询的磁盘IO操作往往会更少。

覆盖索引的典型应用有两个场景。

第一个场景是查询数据只需要辅助索引和主键值，此时可以直接从辅助索引的叶子节点中获取到。

第二个场景是按辅助索引进行统计，由于根据辅助索引就可以找到所有行记录的主键值，根据主键值就可以统计出数量，不必再次查询聚簇索引。

4.3 优化器

查询语句是否走索引，走哪个索引，由优化器决定。

比如，上面讲述的覆盖索引，就是优化器选择的结果。

4.3.1 优化器选择不走索引

在有些情况下，查询条件中带有索引条件，但是优化器却可能不会选择走索引。

这种情况多发生于范围查找、JOIN链接操作的情况下。

例如，我们根据辅助索引a查找：

SELECT * FROM tb_test WHERE a > 1;

由于查找的是所有数据，不会走覆盖索引，会按照先查找辅助索引，再查找聚簇索引的顺序执行。

虽然查询结果在辅助索引中按条件a是有序的，但是在聚簇索引中映射的主键可能是散列的。

由于顺序读操作要远远快于离散读操作，优化器会根据查询数据量的大小进行判断。如果查询数据量较小（<20%），优化器会选择走辅助索引。如果查询数据量较大（>20%），优化器就会选择直接走聚簇索引进行全表扫描。

JOIN链接操作本质上执行逻辑于上述情况相同，它会根据链接条件进行范围查找。

4.3.2 优化器选择索引开销更大

另外，需要注意的是，如果某个表的索引太多，优化器选择索引的开销可能会大于SQL语句本身。此时，可以考虑适当减少索引数量，或者使用force index命令强制使用某个索引。

4.3.3 MRR优化

MySQL5.6开始支持Multi-Range Read（MRR）优化，简单来说就是对多个范围查询的优化。

对于范围查询和JOIN查询操作，MRR的工作方式如下：

按辅助索引B+树进行范围查询，将查询得到聚簇索引键的集合存放到缓存。
将聚簇索引键的集合按rowid进行排序（MRR优化）。
根据排序后的rowid，对聚簇索引B+树进行范围查找。

通过MRR优化，可以将第二次的离散查找转变成顺序查找：

使得数据访问变得较为有序。
减少缓冲池中页被替换的次数。
批量处理对键值的查询操作。

4.3.4 ICP优化

MySQL5.6开始支持Index Condition Pushdown（ICP），简单来说就是支持在走索引时进行条件过滤。

例如，对于联合索引（a, b）和以下查询语句：

SELECT * FROM tb_test WHERE a LIKE '%AAA%' AND b LIKE '%BBB%';

如果不开启ICP功能，我们很容易就能想到，该语句不会走联合索引，而是会先全表扫描，然后在内存中对两个条件进行计算。

如果开启ICP功能，该语句会走联合索引，在走索引时对两个条件进行过滤，直接从索引中获取查询结果。

4.4 常用命令

4.4.1 explain

通过explain命令，可以分析优化器执行SQL的情况。

主要用来判断查询是否走索引，以及SQL执行情况：

type：查询类型，system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL。
key：使用的索引。
rows：优化器估计的查询结果行数。
extra：执行情况信息。