MySQL探索：B-Tree索引底层结构及使用规则

了解MySQL索引有助于提高开发者优化使用MySQL数据库的能力。 MySQL索引有很多种类型，可以为不同的场景提供更好的性能。 B-Tree 索引是最常见的 MySQL 索引类型。一般来说，在谈论MySQL索引时，除非另有说明，都是指B-Tree索引。本文将详细讲解B-Tree指数的底层结构、使用原理和特点。为了节省时间，本文主要内容如下：

• B-Tree索引的底层结构
• B-Tree索引的使用规则
• 聚集索引 ❀InnoDB和InnoDB的区别MyISAM 引擎索引
• 已解析索引
• 覆盖索引

B-Tree 索引

B-Tree 索引使用 B-Tree 来存储数据。当然，不同的存储引擎有不同的实现。 B-Tree通常意味着所有值都按顺序存储并且每个叶边到根的距离相同。图 1 显示了 B-Tree 指数的抽象表示。从这里可以看出MySQL的B-Tree索引的大致工作机制。

B-Tree索引的底层数据结构一般是B+树。其具体的数据结构和好处这里不再详述。下图是B树索引的抽象表示，大致反映了MyISAM索引的工作原理。 InnoDB使用的结构是不同的。

MySQL可以在单列上添加B-Tree索引，也可以在多列数据上添加B-Tree索引。来自几列的数据按照索引语句添加的顺序组合起来并存储在B-Tree页面上。假设有以下数据表：

CREATE TABLE People (
      last_name    varchar(50)    not null,
      first_name   varchar(50)    not null,
      birthday     date           not null,
      gender       enum('m','f')  not null
      key(last_name, first_name, birthday)
);
复制代码

对于表中的每一行数据，索引包含姓氏、名字和生日列的值。下图展示了索引是如何组织数据存储的。

B-Tree索引使用B-Tree作为存储数据的数据结构，它使用的查询规则也由此决定。一般来说，B-Tree索引适合全键值、键值范围和键前缀搜索，其中键前缀搜索仅适合基于最左边前缀的搜索。 B-Tree索引支持的查询原理如下：

• 全值匹配：全值匹配是指匹配索引中的所有列，
• 匹配最左边的前缀：前面提到的索引可以用来查找所有姓 Allen 的人，即仅使用索引中的第一列。
• 匹配列前缀：您还可以仅匹配特定列的值的开头。例如，前面提到的索引可以用来查找所有姓氏以J开头的人。这里只使用索引的第一列。
• 匹配范围值：例如，前面提到的索引可用于查找姓氏在 Allen 和 Barrymore 之间的人。这里只使用索引的第一列。
• 精确匹配某一列，范围匹配另一列：前面提到的索引也可以用来查找所有姓氏为Allen、名字以字母K开头的人（如Kim、Karl等） 。即，第一列中的姓氏完全匹配，第二列中的名字的范围匹配。

因为索引树中的节点是有序的，所以索引除了可以按值搜索外，还可以用于查询中的ORDER BY操作（按顺序搜索），如果ORDER BY子句满足前面指定的查询type，这个索引也能满足相应的排序要求。

以下是有关 B-Tree 索引的一些限制：

• 如果未在索引的最左列开始搜索，则无法使用该索引。例如，上例中的索引无法找到名为 Bill 的人，也无法找到特定生日的日期，因为这两列都不是最左边的数据列。
• 如果查询中存在针对特定列的范围查询，则无法使用索引优化来查找该列右侧的所有列。

聚集索引

聚集索引不是一种单独的索引类型，而是一种数据存储方式。具体细节取决于其实现，但InnoDB的聚集索引实际上将B-Tree索引和数据行存储在相同的结构中。

当表有聚集索引时，它的数据行实际上存储在索引的叶子页上，也就是说数据行和相邻的键值紧凑地存储在一起。

下图显示了聚集索引中的条目是如何存储的。请注意，叶子页包含行中的所有数据行，但节点页仅包含索引列。

聚集索引可以帮助提高性能，但它们也可能导致严重的性能问题。集群数据具有一些重要的优势：

• 数据访问速度更快。聚集索引将索引和数据存储在同一个 B-Tree 中，因此从聚集索引检索数据通常比从非聚集索引检索数据要好。快点找到吧。
• 使用覆盖索引扫描的查询可以直接使用页面节点中的主键值。

如果在设计表和查询时能够充分利用上述优势，就可以显着提高性能。同时，聚集索引也有一些缺点：

• 插入的顺序很大程度上取决于插入的顺序。按主键顺序插入是将数据插入 InnoDB 表的最快方法。需要避免主键值随机（不连续且值分布范围非常大）的聚集索引。例如，如果您使用 UUID 作为主键，请使用 AUTO_INCRMENT 之类的内容。自动增量列。
• 更新聚集索引列的成本很高，因为它迫使 InnoDB 将每个更新的行移动到新位置。
• 基于聚集索引的表在插入新行或更新主键并需要移动行时可能会面临“页面分裂”问题。当某行的主键值要求将该行插入到整个页中时，存储引擎会将该页拆分为两个页来容纳该行。这是一个页面分割操作。页拆分会导致表占用更多磁盘空间
• 二级索引可能比想象的要大，因为二级索引中的叶子节点包含引用行中的主键列
• 二级索引访问需要两个 Index查找而不是查找。

InnoDB 和 MyISAM 的索引区别

聚集索引和非聚集索引之间的数据分布存在差异，以及对应的主键索引和辅助索引之间的数据分布存在差异，这通常使得人们感到困惑和惊讶。下图展示了MyISAM和InnoDB的不同索引和数据存储方式。

MyISAM的数据分布非常简单。它按照数据插入的顺序存储在磁盘上。主键索引和辅助索引的叶子节点存储了指向对应数据行的指针。

在InnoDB中，聚集索引“就是”一张表，因此它不需要像MyISAM那样独立的行存储。聚集索引的每个叶节点包含主键值和所有剩余列（本例中为 col2）。

InnoDB的二级索引和聚集索引有很大的不同。 InnoDB二级索引的叶子节点中存储的不是“行指针”，而是主键值，作为指向行的“指针”。

松散索引扫描

MySQL不支持松散索引扫描，即不能以不连续的方式扫描索引。通常情况下，MySQL的索引扫描首先要定义一个起点和一个终点。即使需要的数据只是该索引中的一小部分，MySQL仍然需要扫描该索引中的每一条记录。

下面我们通过一个例子来说明这一点。假设我们有如下索引(a,b)和如下查询：

mysql>SELECT * FROM tb1 WHERE b BETWEEN 2 AND 3;
复制代码

因为索引中的前导字段是a列，但查询中只指定了b字段，MySQL无法使用该索引，所以只能通过全表扫描找到匹配的行，如下图所示。

如果您了解索引的物理结构，就不难发现有一种更快的方法来执行上述查询。索引的物理结构（不是存储引擎的API）是可以先扫描a列第一个值对应的b列范围，然后跳转到第二个不同值对应的b列范围要扫描的 a 列。下图展示了如果 MySQL 实现这个过程会发生什么。

注意，此时不需要使用WHERE子句过滤器，因为松散索引扫描已经跳过了所有不必要的记录。

MySQL 5.0之后的版本在一些特殊场景下可以使用松散索引扫描。例如，在组查询中查找组最大值和最小值：

mysql> EXPLAIN SELECT actor_id, MAX(film_id)
        -> FROM sakila.film.film_actor
        -> GROUP BY actor_id;
********************************************* 1. row ***********************************
id: 1
select_type: SIMPLE
table: film_actor
type: range
possible_keys: NULL
key: PRIMARY
key_len: 2
ref: NULL
rows: 396
Extra: Using index for group-by
复制代码

EXPLANATION 中的额外字段出现“Using index for group-by”，表明这里将使用松散索引扫描。

覆盖索引

索引除了是查找数据的有效方式之外，也是获取列数据的直接方式。 MySQL可以使用索引直接检索列数据，因此不需要读取数据行。如果一个索引包含了所有要查询的字段的值，我们称之为“覆盖索引”。覆盖索引是非常有用的工具，可以极大地提高性能。 SQL查询只需要扫描索引而不返回表，这会带来很多好处：

• 索引条目的数量和大小通常远小于条目和数据行的大小，所以如果只需要索引进行读取时，MySQL 的数据访问量得到大大减少。
• 由于索引按列顺序存储，I/O 密集型范围搜索所需的 I/O 比从磁盘随机读取每行数据要少得多。
• 由于 InnoDB 的聚集索引，覆盖索引对于 InnoDB 表特别有用。 InnoDB 的二级索引将行的主键存储在叶节点中。如果次主键可以覆盖查询，则该索引就避免了对主键索引的另一次查询。

当您使用覆盖索引启动查询（也称为索引覆盖查询）时，您可以在 EXPLAIN 的 Extras 列中看到“索引使用情况”信息。例如，sakila.inventory 表具有多列索引（store_id、movie_id）。如果MySQL只需要访问这两列，可以使用该索引作为覆盖索引，如下所示：

mysql> EXPLAIN SELECT store_id, film_id FROM sakila.inventory
*********************************1.row***************************************
id:1
select_type:SIMPLE
table:inventory
type:index
possible_keys:NULL
key:idx_store_id_film_id
key_len:3
ref:NULL
rows:4673
Extra:Using Index

作者：ztwindy
链接：https://juejin.im/post/5b5c2096f265da0f65239483 来源：You Kim
版权归作者所有。商业转载请联系作者获取授权。非商业转载请注明出处。