MYSQL存储引擎InnoDB（二十三）：排序索引构建

InnoDB在创建或重建索引时执行批量加载，而不是一次插入一个索引记录。这种索引创建方法也称为排序索引构建。空间索引不支持排序索引构建。

索引构建分为三个阶段。在第一阶段， 扫描聚集索引，生成索引条目并添加到排序缓冲区。当排序缓冲区变满时，条目将被排序并写入临时中间文件。此过程也称为 “运行”。在第二阶段，将一个或多个运行写入临时中间文件，对文件中的所有条目执行合并排序。在第三个也是最后一个阶段，排序后的条目被插入到 B-tree中。

在引入排序索引构建之前，使用插入 API 将索引条目一次插入 B 树中的一条记录。此方法涉及打开 B 树 游标以查找插入位置，然后使用 乐观插入将条目插入 B 树页面。如果由于页面已满而导致插入失败， 则将执行悲观插入，这涉及打开 B-tree 游标并根据需要拆分和合并 B-tree 节点以找到条目空间。这种“自上而下”的弊端建立索引的方法是搜索插入位置的成本以及 B 树节点的不断拆分和合并。

排序索引构建使用“自下而上”建立索引的方法。使用这种方法，对最右侧叶页的引用保存在 B 树的所有级别。分配必要 B 树深度的最右侧叶页，并根据其排序顺序插入条目。一旦叶页已满，就会将节点指针附加到父页，并为下一次插入分配一个兄弟叶页。这个过程一直持续到所有条目都被插入，这可能导致插入到根级别。分配同级页时，释放对先前固定叶页的引用，新分配的叶页成为最右边的叶页和新的默认插入位置。

要为将来的索引增长留出空间，您可以使用innodb_fill_factor变量来保留一定百分比的 B 树页面空间。例如，设置 innodb_fill_factor为 80 会在排序索引构建期间保留 B 树页面中 20% 的空间。此设置适用于 B 树的叶子页面和非叶子页面。它不适用于用于 TEXT或 BLOB条目的外部页面。保留的空间量可能与配置不完全相同，因为innodb_fill_factor值被解释为提示而不是硬限制。

全文索引支持排序索引构建 。以前，SQL 用于将条目插入全文索引。

对于压缩表，以前的索引创建方法将条目附加到压缩页和未压缩页。当修改日志（表示压缩页面上的可用空间）变满时，将重新压缩压缩页面。如果由于空间不足而导致压缩失败，则页面将被拆分。使用排序索引构建，条目仅附加到未压缩的页面。当一个未压缩的页面变满时，它就会被压缩。自适应填充用于确保在大多数情况下压缩成功，但如果压缩失败，则会拆分页面并再次尝试压缩。这个过程一直持续到压缩成功。

在排序索引构建期间禁用重做日志记录。相反，有一个 检查点来确保索引构建可以承受意外退出或失败。检查点强制将所有脏页写入磁盘。在排序索引构建期间，页面清理线程会定期收到信号以刷新 脏页，以确保可以快速处理检查点 *** 作。通常，当干净页面的数量低于设置的阈值时，页面清理线程会刷新脏页面。对于排序索引构建，脏页会被及时刷新以减少检查点开销并行化 I/O 和 CPU 活动。

排序索引构建可能会导致 优化器统计信息与以前的索引创建方法生成的统计信息不同。统计数据差异是由于用于填充索引的算法不同造成的。

创建表

该表的记录如下：

添加两个索引：

通过 explain 来查看：

会命中两条索引，但实际只用了 idx_v1，即使实际查询用联合索引更好，也依然只用了 idx_v1。

之前的测试，发现用的是第一个，我们删除索引，把之前的索引语句顺序换一下：

发现用的是第一个。

MYSQL官方文档介绍索引是一种方便快速查询数据的数据结构。用我们生活中的例子来讲，索引就好比书的目录，如果没有目录，每次你想要查找某些内容，你必须从头开始查找，这样的效率极其低下。

索引一般比较大，所以大部分情况下索引是存在磁盘的索引文件上，也有可能是存在数据文件上。

索引的种类有很多：主键索引（这是最常见的一种索引，主键不能为空且必须唯一）、唯一索引（相对于主键索引，它的值可以为空）、全文索引（在char、varchar、text类型可以使用）、普通索引、前缀索引。按照列数来区分：单一索引、组合索引（多字段组成）

2.MYSQL索引的数据结构

在讲解MYSQL索引的数据结构之前，我们先看看了解一下其他的数据结构，看看他们的优缺点进行对比。

2.1 二叉树

二叉树简单来说就是左节点大于右节点，在理想的情况下，他的查找速度就接近与二分法的性能O(log2n)。因为在内存排序的时间是非常快的，可以忽略不计，所以总的消耗时间就取决于IO的 *** 作次数。二叉树查找速度取决树高,每次查询接口都是一次IO *** 作，也是性能的瓶颈所在。

但是也会有这种一种情况,同样也是二叉树，但是他的树非常高，导致查询一次需要多次IO *** 作，效率及其低下

2.2 平衡二叉树

平衡二叉树可以解决二叉树不稳定导致查询效率低下的缺点。平衡二叉树的特点：树的左右节点层级最高相差一层。在插入或者删除的情况下，通过左旋转或右旋转使得整个二叉树平衡，不会出现层级相差很多的情况。平衡二叉树的性能接近二分法查找O(log2n)。

平衡二叉树查找id为8的记录，只需要IO *** 作2次即可。但是仔细想一下，如果数据量很多呢？假设数据表有100W的数据，根据O(log2n)计算，大约需要20次IO *** 作。磁盘寻道大概需要10ms，总的查询时间为20 * 10 = 0.2，效率也比较低下。

还有就是平衡二叉树不支持范围查询，范围查询每次都需要从根节点遍历，效率及其低下。

2.3 B-树(改造二叉树成多叉树)

之前的几种树形结构适合与小数据量的内存查找，也叫做内查找。在1970年，R.Bayer和E.Mccreight提出了一种适合于外查找的平衡多叉树B-树。MYSQL数据文件是存在磁盘的，每次都是按照一页大小（一般而16K）读取内存。像二叉树、平衡二叉树，每次读取节点都要进行一次IO *** 作，所以树越高IO *** 作次数越多。想要提高

---