前面我们了解了InnoDB底层的存储结构，即：以B+树的方式组织数据页。另外了解了数据页中的数据行的存储方式。

而构建B+树索引的时候必须要选定一个或者多个字段作为索引的值，如果索引选择的是主键，那么我们就称为聚集索引，否则就是二级索引。

为什么MySQL使用B+树？

哈希表虽然可以提供O(1)的单行数据操作性能，但却不能很好的支持排序和范围查找，会导致全表扫描；

B树可以再非叶子节点存储数据，但是这可能会导致查询连续数据的时候增加更多的I/O操作；

而B+树数据都存放在叶子节点，叶子节点通过指针相互连接，可以减少顺序遍历时产生的额外随机I/O

更新详细解释: 为什么 MySQL 使用 B+ 树^[1]

了解到上面的底层逻辑存储结构之后，我们进一步来看看InnoDB是怎么通过B+树来组织存储数据的。

首先来介绍下聚集索引。

1、聚集索引

主键索引的InnoDB术语。

下面我们创建一张测试表，并插入数据，来构造一颗B+树：

CREATE TABLE t20 (
id int NOT NULL,
a int NOT NULL,
b int,
c int,
PRIMARY KEY (`id`)
) ENGINE=InnoDB;

insert into t20 values(20, 1, 2, 1);
insert into t20 values(40, 1, 2, 5);
insert into t20 values(30, 3, 2, 4);
insert into t20 values(50, 3, 6, 2);
insert into t20 values(10, 1, 1, 1);

可以看到，虽然我们是id乱序插入的，但是插入之后查出来的确是排序好的：

这个排序就是B+索引树构建的。

我们可以通过这个在线的动态演示工具来看看B+树的构造过程，最终结果如下：

实际存放在数据库中的模型因页面大小不一样而有所不同，这里为了简化模型，我们按照B+树的通用模型来解释数据的存储结构。

类似的，我们的数据也是这种组织形式的，该B+树中，我们以主键为索引进行构建，并且把完整的记录存到对应的页下面：

其中蓝色的是索引页，橙色的是数据页。

每个页的大小默认为16k，如果插入新的数据行，这个时候就要申请新的数据页了，然后挪动部分数据过去，重新调整B+树，这个过程称为页分裂，这个过程会影响性能。

相反的，如果InnoDB索引页的填充因子下降到之下MERGE_THRESHOLD，默认情况下为50％（如果未指定），则InnoDB尝试收缩索引树以释放页面。

自增主键的插入是递增顺序插入的，每次添加记录都是追加的，不涉及到记录的挪动，不会触发叶子节点的分裂，而一般业务字段做主键，往往都不是有序插入的，写成本比较高，所以我们更倾向于使用自增字段作为主键。

聚集索引注意事项

当在表上面定义了PRIMARY KEY之后，InnoDB会把它作为聚集索引。为此，为你的每个表定义一个PRIMARY KEY。如果没有唯一并且非空的字段或者一组列，那么请添加一个自增列；
如果您没有为表定义PRIMARY KEY，则MySQL会找到第一个不带null值的UNIQUE索引，并其用作聚集索引；
如果表没有PRIMARY KEY或没有合适的UNIQUE索引，则InnoDB 内部会生成一个隐藏的聚集索引GEN_CLUST_INDEX，作为行ID，行ID是一个6字节的字段，随着数据的插入而自增。

聚集索引查找

根据索引进行查找id=50的记录，如下图，沿着B+树一直往下寻找，最终找到第四页**，然后把该页加载到buffer pool中，在缓存中遍历对比查找**，由于里面的行记录是顺序组织的，所以很快就可以定位到记录了。

2、辅助索引

除了聚集索引之外的所有索引都称为辅助索引(二级索引)。在InnoDB中，辅助索引中每个记录都包含该行的主键列以及为辅助索引指定的列。

在辅助索引中查找到记录，可以得到记录的主键索引ID，然后可以通过这个主键索引ID去聚集索引中搜索具体的记录，这个过程称为回表操作。

如果主键较长，则辅助索引将使用更多空间，因此具有短的主键是有利的。

下面我们给刚刚的表添加一个组合联合索引

-- 添加多一个字段
alter table t20 add column d varchar(20) not null default '';
-- 添加一个联合索引
alter table t20 add index idx_abc(a, b, c);

添加之后组合索引B+树如下，其中索引key为abc三个字段的组合，索引存储的记录为主键ID：

覆盖索引(Using index)

InnoDB存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要回表去查询聚集索引中的记录，从而减少大量的IO操作。下面的查询既是用到了覆盖索引 idx_abc：

1	select a, b from t20 where a > 2;

执行结果如下：

可以发现，Extra这一列提示Using index，使用到了覆盖索引，扫描的行数为2。注意：这里的扫描行数指的是MySQL执行器从引擎取到两条记录，引擎内部可能会遍历到多条记录进行条件比较。

最左匹配原则

由于InnoDB索引式B+树构建的，因此可以利用索引的“最左前缀”来定位记录。

也就是说，不仅仅是用到索引的全部定义字段会走索引，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左n个字段。

索引条件下推(Using index condition)

索引条件下推 Index Condition Pushdown (ICP)，是针对MySQL使用索引从表中检索行的情况的一种优化。

为什么叫下推呢，就是在满足要求的情况下，把索引的条件丢给存储引擎去判断，而不是把完整的记录传回MySQL Server层去判断。

ICP支持range, ref, eq_ref, 和 ref_or_null类型的查找，支持MyISAM和InnoDB存储引擎。

不能将引用子查询的条件下推，触发条件不能下推。详细规则参考：Index Condition Pushdown

如果不使用ICP，则存储引擎将遍历索引以在聚集索引中定位行，并将结果返回给MySQL Server层，MySQL Server层继续根据WHERE条件进行筛选行。

启用ICP后，如果WHERE可以仅使用索引中的列来评估部分条件，则MySQL Server层会将这部分条件压入WHERE条件下降到存储引擎。然后，存储引擎通过使用索引条目来判断索引条件，在满足条件的情况下，才回表去查找记录返回给MySQL Server层。

ICP的目标是减少回表扫描的行数，从而减少I / O操作。对于InnoDB表，ICP仅用于二级索引。

使用索引下推的时候，执行计划中的Extra会提示：Using index condition，而不是Using index，因为必须回表查询整行数据。Using index代表使用到了覆盖索引。

References

为什么 MySQL 使用 B+ 树. draveness.me. (2019-12-11). Retrieved from https://draveness.me/whys-the-design-mysql-b-plus-tree/ ↩︎

MySQL

InnoDB执行引擎内幕：索引原理