首页 > itarticle > MySQL系列（11）—索引索引索引总结索引应用

MySQL系列（11）—索引索引索引总结索引应用

admin 12月 09, 2021 0

索引

参考：

MySQL 索引

索引 就是为了提高数据查询的效率，就像书的目录一样，我们可以借助目录快速找到某个知识点所在的页。同样，对于数据库的表而言，索引其实就是表数据的“目录”。

索引 是在 MySQL 存储引擎层中实现的，所以每一种存储引擎支持的索引不一定相同，即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。下面这张表格展示了不同的存储引擎所支持的索引类型。

索引类型 InnoDB 引擎 MyISAM 引擎 Memory 引擎
B+Tree 索引 Y Y Y
Hash 索引 N N Y
R-Tree 索引 N Y N
Full-Text 索引 N Y N

B+Tree索引和Hash索引是比较常用的两个索引数据存储结构：

  • B+Tree索引是通过B+树实现的，是有序排列存储，所以在排序和范围查找方面都比较有优势。

  • Hash索引适合 key-value 键值对查询，无论表数据多大，查询数据的复杂度都是O(1)，且直接通过 Hash 索引查询的性能比其它索引都要高。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度很慢。所以，哈希表结构适用于只有等值查询的场景。

B+Tree 索引

数据页

B+Tree 索引是通过 B+ 树实现的，可以通过 平衡二叉树、B树、B+树、B*树 这篇文章了解 B+ 树的数据结构原理。

InnoDB 磁盘管理的最小单位是页，B+Tree 索引中的每个节点就是一个数据页。在研究 B+Tree 索引前，先回顾下前面学过的一些关于页的知识。

页结构的 File Header 部分记录的信息如下表所示：

这里记住如下几个比较重要的信息：

  • FIL_PAGE_OFFSET：当前页的页号，每个页都有一个唯一编号
  • FIL_PAGE_PREV：双向链表中指向当前页的上一个页
  • FIL_PAGE_NEXT：双向链表中指向当前页的下一个页
  • FIL_PAGE_TYPE：页的类型，索引和数据都是存放在 FIL_PAGE_INDEX（0x45BF）这种类型的页中，就是数据页。

数据页中存放的就是一行行记录，如常使用的 Compact 行记录格式如下图所示：

其中记录头部分记录的信息如下表所示：

这里记住两个比较重要的信息：

  • record_type：记录的类型：
    • 0：普通的用户记录
    • 1：目录项记录
    • 2：最小记录
    • 3：最大记录
  • next_record：指向页中下一条记录

有了上面这些信息，就可以形成一个简单的双向链表来存储数据，页与页之间就通过 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 连成双向链表。页中存放的就是一行行记录，每行记录通过 next_record 连接起来形成一个单项链表，每个页中都会有一个最小记录（Infimum，record_type=2），以及最大记录（Supremum，record_type=3），然后就是普通的用户记录（record_type=0）。

image.png

B+Tree 索引的形成过程

还是以前面测试使用的 account 表为例，我们先以为 id 列创建主键索引为例来说明。

CREATE TABLE `account` (
  `id` bigint(11) NOT NULL AUTO_INCREMENT COMMENT '主键',
  `card` varchar(60) NOT NULL COMMENT '卡号',
  `name` varchar(60) DEFAULT NULL COMMENT '姓名',
  `balance` int(11) NOT NULL DEFAULT '0' COMMENT '余额',
  PRIMARY KEY (`id`),
  UNIQUE KEY `account_u1` (`card`) USING BTREE,
  KEY `account_n1` (`name`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='账户表';
复制代码

每当为某个表创建一个 B+Tree 索引的时候，都会为这个索引创建一个根节点页面，这个根节点页面创建后便不会再移动。这个根节点的页号会被记录起来，然后在访问这个表需要用这个索引的时候，就会取出这个根节点页面，从而来访问这个索引。

例如创建主键索引时，创建了一个页号为30的根节点页面，插入数据时，首先会插入到根节点页面中。

需要注意的是，一行记录不只包含用户记录，还包含隐藏的事务ID（trx_id）、回滚指针（roll_pointer）等，这些就没有展示在图中了。

image.png

假设一个页最多存储 3 条记录就满了。

这时再插入一条 id=4 的记录，根节点页面已满，就会新分配一个页（页35），然后将根节点中的所有记录复制到这个新分配的页中。由于页 35 已满，所以会再分配一个新的页（页38），然后将新的记录插入页 38 中。

image.png

但这里是有点问题的，索引上的记录是顺序排列的，而且要求 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。页 35 中最大的记录是 id=5，如果插入一条 id > 5 的记录，插入到页 38 中就没有问题，而这里插入的是 id=4 这条记录。所以插入 id=4 这条记录时还伴随着 页分裂，就是把 id=5 这条记录移动到页 38 中，然后再把 id=4 这条记录插入到页 35 中。

image.png

这个过程表明了在对页中的记录进行增删改操作的过程中，会通过一些诸如记录移动的操作来保证下一个数据页中记录的主键值始终大于上一个页中记录的主键值，这个过程也可以称为页分裂。

存储用户记录的页在物理存储上可能并不挨着（把这种页称为用户记录页），所以如果想从这么多页中根据主键值快速定位某些记录所在的页，就需要给它们做个目录。

这时候根节点页就会变成目录页，里面的记录的类型为record_type=1，也就是目录项记录。目录项记录跟普通记录的结构类似，只不过它的数据部分只存储了主键值和页号，每个用户记录页都会对应一个目录项记录，这个目录项记录的主键值就是这个用户记录页中主键值最小的记录。

这时，跟节点页中就会有两条目录项记录，第一条记录的页号为 35，id=1；第二条记录的页号为 38，id=5。

image.png

随着用户记录不断插入，用户记录页越来越多，目录页中的记录也满了，这时要再插入一个目录项记录就放不下了。例如下面最后一条记录。

image.png

其实跟前面是类似的，也会伴随着页分裂的操作。根节点页始终不动，它会把所有记录复制到一个新分配的页中。这时可以看到目录页就有两层了。

image.png

上面这幅图现在看起来就像一个倒过来的树，这其实就是 B+树，B+ 树就是一种用来组织数据的数据结构。

不论是存放用户记录的数据页，还是存放目录项记录的数据页，都把它们存放到 B+ 树这个数据结构中了。从图中可以看出来，用户记录页都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中B+树最上边的那个节点就称为根节点。

在索引中查找记录

上面已经形成一个 B+ 数索引了，假设现在要查找 id=11 这条记录，这时就会按如下步骤来查找：

  • 首先IO读取索引的根节点页（页30）到内存中，然后在内存中遍历根节点页中的记录项，这些记录可以根据主键划分几个区间：(Infimum, 1)，[1, 15)，[15，Supremum)。id=11 落在 [1, 15) 这个区间，所以定位到 id=1 这条记录，对应的页号是 52。

  • 接着IO读取页 52 到内存中，同样的遍历页中的记录，这时 id=11 落在 [10, Supremum) 这个区间，因此定位到 id=10 这条记录，对应的页号是 45。

  • 接着IO读取页 45 到内存中，再遍历页中的记录，就可以定位到 id=11 这条用户记录了。

需要注意的是，不管是目录页还是用户记录页，页中都会有一个 Page Directory，就是页目录，通过页目录就可以通过二分法快速定位到页中的一条记录，而不是从左往右一条条遍历。关于 Page Directory 请参考：MySQL系列（4）— InnoDB数据页结构。

image.png

注意B+树索引并不能找到一个给定键值的具体行，能找到的只是被查找数据行所在的页。然后数据库把页读入到内存，再在内存中进行查找，最后得到要查找的数据。所以上面的步骤中会有IO操作。

从上面查找记录的过程可以看出，磁盘IO的次数等于 B+ 树的高度，也就是说IO的次数将取决于 B+ 树的高度，而磁盘 IO 往往是数据库性能的瓶颈。B+Tree 索引最高会有多少层呢？

前面我们只是假设每个页最多存放3条记录，其实一个 16KB 的页存放的记录数量是非常大的。假设存放用户记录的叶子节点数据页可以存放100条用户记录，而存放目录项记录的内节点数据页可以存放1000条目录项记录：

  • 如果 B+Tree 有1层，也就是只有1个用于存放用户记录的节点，最多能存放 100 条记录。

  • 如果 B+Tree 有2层，最多能存放 1000×100=10万 条记录。

  • 如果 B+Tree 有3层，最多能存放 1000×1000×100=1亿 条记录。

  • 如果 B+Tree 有4层，最多能存放 1000×1000×1000×100=1000亿 条记录。

一张表一般来说很少会超过1亿条记录，更不用说 1000亿 了。所以一般情况下，B+Tree 都不会超过4层。

我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有 Page Directory（页目录），所以在页面内又可以通过二分法实现快速定位记录。

所以有了索引之后，根据索引查找数据是非常快的。而没有索引，就只能全表扫描，读取每个页到内存中遍历，就会有很多次的磁盘IO，这个性能就非常低下了。

聚簇索引

上面介绍创建的ID主键索引其实就是一种聚簇索引，最主要的特征便是 B+树的叶子节点存储的是完整的用户记录，也就是存储了一行记录中所有列的值（包括隐藏列）。

除此之外，聚簇索引使用记录主键值的大小进行记录和页的排序，主要表现在以下几个方面：

  • 页内的记录是按照主键的大小顺序排成一个单向链表。
  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

InnoDB 存储引擎表都会有主键，如果我们没有为某个表显式的定义主键，并且表中也没有定义唯一索引，那么InnoDB会自动为表添加一个 row_id 的隐藏列作为主键。因此，InnoDB 始终会自动创建聚簇索引，在 InnoDB 中，聚簇索引就是数据的存储方式，所有的数据都是存储在这颗 B+树的叶子节点上，这也就是 索引即数据，数据即索引。

辅助索引

InnoDB 在创建表时，默认会创建一个主键的聚簇索引，而除此之外的其它索引都属于辅助索引，也被称为二级索引或非聚簇索引。

聚簇索引只能在搜索条件是主键值时才能发挥作用，因为目录页中存储的都是主键，B+树中的数据都是按照主键进行排序的。如果我们要根据其它的非主键列来查询，比如前面 account 表中的 name 列，这时就可以再建一个 name 列的辅助索引。

辅助索引与聚簇索引最大的区别在于叶子节点存储的就不再是完整的用户记录了，而是索引列+主键值，目录页中存储的也是索引列的值，同时，辅助索引使用索引列的大小进行记录和页的排序。

例如下面就是为 name 列创建的一个辅助索引。可以看到最底层的叶子节点就只包含 name + id 列的数据，同时数据是按照 name 列的大小排序的，目录页中存储的也是 name 列的值。

image.png

这时，再根据 name 列查找数据时，就会用上这个辅助索引了，查找过程跟聚簇索引的查找过程是类似的。最主要的区别在于利用辅助索引查找到的数据不是完整的用户记录，所以找到叶子节点上的记录后，还会根据对应的主键值回到主键索引上再根据主键值找到对应的完整记录，这个过程也称为回表。

例如查找 name=H 的记录，就会定位到页69，name=H 对应的主键 id=11，然后就会回表在聚簇索引上查找 id=11 这条完整记录。

利用辅助索引查找的时候，也并非一定需要回表，如果我们查找的数据在辅助索引上都已经存在了，就不会回表了。例如SQL select name, id where name='H' 只查询 name、id 的值，就不会回表了，因为这个辅助索引上已经包含了要查找的所有列，只有索引上不包含要查找的列时，才会回表再查一遍。

联合索引

我们也可以同时以多个列的大小作为排序规则，同时为多个列建立索引，多个列建立的索引称为联合索引，其本质上也是一个辅助索引或二级索引。

多个列建立的联合索引，叶子节点中存储的就是这几个索引列+主键值，例如为 name、balance 列建立索引，那叶子节点上存储的就是 name、balance、id 这几列，目录页存储的就是 name、balance + 页号。

联合索引会先根据第一列排序，第一列相同的再根据第二列排序，以此类推。例如 name、balance 的联合索引，会先以 name 列排序存储，name 列值相同的再按 balance 列排序。

MyISAM 中的索引

InnoDB 引擎表中聚簇索引既包含了索引目录又包含了完整数据，索引和数据是一起存在一颗B+树上的。

MyISAM 引擎表则是将索引和数据分开存储：

  • 用户数据按照记录的插入顺序单独存储在一个文件中，称之为数据文件，也就是 .MYD 为后缀的文件。这个文件并不划分数据页，所有记录都按照插入顺序插入就行了，然后通过每行数据的物理地址来快速访问到一条记录。

  • 索引信息则另外存储到一个单独的索引文件中，就是 .MYI 为后缀的文件。MyISAM 会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 物理地址的组合。也就是先通过索引找到行对应的物理地址，再通过物理地址去找对应的记录。

也就是说，MyISAM 引擎中建立的索引相当于全部都是二级索引，无论是为主键还是其它列创建的索引，都需要根据物理地址 回表，到数据文件中查找完整的用户记录。

image.png

索引总结

索引规则

根据前面的学习，我们先总结熟悉下 InnoDB 引擎的 B+ 树索引规则。

  • 每个索引都对应一棵 B+树，B+ 树一般最多不超过4层，最底层的是叶子节点，其余的是内节点。所有用户记录都存储在B+树的叶子节点，所有目录项记录都存储在内节点。

  • InnoDB 存储引擎会自动为主键建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录。

  • 可以根据实际需求创建 二级索引，二级索引的叶子节点仅包含索引列 + 主键，所以如果想通过二级索引来查找完整的用户记录，会有 回表 操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。

  • B+树索引中，每层数据页节点都是按照索引列值从小到大的顺序排序而组成了双向链表，每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列值从小到大的顺序而形成了一个单向链表。

  • 联合索引 的页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序。

  • 通过索引查找记录是从B+树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了 Page Directory，所以在这些页面中的查找也非常快。

记住索引列的顺序性是非常重要的，索引本身的特征以及很多查询的性能优化和限制都和索引的顺序有关系。

索引优点

索引主要就是为了提升数据库的查询性能，总结下来主要有如下几个优点：

  • 索引大大减少了服务器需要扫描的数据量，通过索引可以快速定位到一条记录。而且因为索引列存储了实际的值，所以有些查询只使用索引就能够完成全部查询，而无需回表。

  • 索引可以帮助服务器避免排序和临时表，因为索引是按照索引列排序的，数据已经排好序了，所以对于范围查询、排序 ORDER BY、分组 GROUP BY 是非常有用的。

  • 索引可以将随机 I/O 变为顺序 I/O，因为数据就是按索引列排序的。

索引代价

首先要明确，索引并不是越多越好，索引的使用是有一定代价的。

  • 空间上的代价

每创建一个索引都要为它建立一棵 B+树，每一棵 B+树 的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间。一张表数据越多，这颗 B+树就会越大，占用的空间就会越多。

  • 时间上的代价

每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引。B+树 每层节点都是按照索引列的值从小到大排序连成的双向链表，节点中的记录也是按照索引列的值从小到大排序而形成的一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收等操作来维护好节点和记录的排序。所以索引建的越多，每次增、删、改操作索引所耗费的时间就会越多。

所以，一个表上索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。只有正确使用和创建索引，才能整体提升性能，否则只会适得其反。

只有当索引对查找到记录带来的好处大于其带来的额外工作时，索引才是有效的。对于非常小的表，大部分情况下简单的全表扫描更高效。对于中到大型的表，索引就非常有效。

索引应用

全值匹配

全值匹配就是查询条件中的列和索引中的列一致。

例如为 (card, name, balance) 创建的一个联合索引 idx_cnb，假设一个查询语句把这三列都用上了：

SELECT * FROM account WHERE card = 'A' AND name = 'A' and balance = 0;
复制代码

首先要知道 idx_cnb 这个索引是一个联合索引，这个索引首先按照 card 列排序，card 列相同的再按照 name 列排序，name 列相同的再按照 balance 列排序。

所以这个查询语句会先查找 card = 'A' 的记录，再从这些记录中快速找出 name='A' 的记录，如果 card 和 name 都相同，还会用上 balance 列。

WHERE 子句中的几个搜索条件的顺序对查询结果是没有什么影响的，MySQL查询优化器会自动优化SQL语句，然后根据要使用的索引，来决定先使用哪个查询条件，后使用哪个查询条件。

匹配最左前缀

对于联合索引，可以只使用左边的部分列，可以不用包含全部联合索引中的列，但只能是左边连续的列。

例如下面的查询语句就会使用 idx_cnb 这个联合索引，但只使用了索引中的前两个列。

SELECT * FROM account WHERE card = 'A' AND name = 'A';
复制代码

如果只使用了中间的列，则用不上这个联合索引。例如下面的SQL根据 name 查询，因为 idx_cnb 索引是先安装 card 列排序的，在 card 列相同的情况下才会使用 name 列排序。所以无法跳过 card 列直接根据 name 列查找数据。

SELECT * FROM account WHERE name = 'A';
复制代码

再比如下面的SQL，则只会使用到 idx_cnb 索引的第一列，因为 balance 是先根据 name 列排序后再排序的，所以对于 card=A 的数据，balance 可能并不是有序的。所以要将所有 card=A 的数据查询到内存后再筛选出 balance=0 的数据 。

SELECT * FROM account WHERE card = 'A' AND balance = 0;
复制代码

匹配列前缀

匹配列前缀就是只匹配某一列的值的开头部分。

例如下面的查询，只匹配 card 为 A 开头的记录，也可以用 idx_cnb 索引来快速定位记录。

SELECT * FROM account WHERE card LIKE 'A%';
复制代码

但如果只给出后缀或者中间的某个字符串，则无法使用索引。例如下面的查询，查找 card 为 A 结尾的记录，因为并不知道 A 结尾之前的顺序，所以就没办法使用索引。

SELECT * FROM account WHERE card LIKE '%A';
复制代码

匹配范围值

匹配范围值就是利用索引的有序性，可以非常方便的查找在某个范围内的记录。

例如下面的SQL语句，根据 card 列进行范围查找，就可以使用上 idx_cnb 索引。

SELECT * FROM account WHERE card > 'A' AND card < 'H';
复制代码

但需要注意的是，如果对联合索引多个列同时进行范围查找的话，只有对索引最左边的那个列进行范围查找的时候才能用上索引。因为第一列使用范围查询后，第二列并不是有序的，要知道是在第一列值相同的情况下，才用第二列排序。

例如下面的查询，先查询了 card 在 (A，B) 之间的记录，此时可能会有多条 card 不同的记录，所以这些记录中的 name 并不是有序的。所以需要先找到 card 在 (A, B) 之间的记录，再一条条过滤出 name > A 的记录。所以这个查询只用到了 idx_cnb 索引的 card 列，没用到 name 列。

SELECT * FROM account WHERE card > 'A' AND card < 'H' AND name > 'A';
复制代码

精确匹配某一列并范围匹配另外一列

上一小节说的是如果第一列是范围查询，第二列也是范围查询时，第二列不会走索引。

但如果左边的列是精确匹配的，后面的列是范围查询则可以用上索引，因为左边的列精确匹配后，后边的列就是排好序的。

例如下面的查询，card 列是精确匹配，之后对 name 列进行范围查找，这个查询会用上 idx_cnb 索引的 card、name 两列。

SELECT * FROM account WHERE card = 'A' AND name > 'A';
复制代码

排序和分组

我们经常会使用 ORDER BY 子句来对记录排序，一般情况下，数据库只能把记录都加载到内存中，再用一些排序算法在内存中对这些记录进行排序。有的时候可能查询的结果集太大以至于不能在内存中进行排序的话，还可能要使用磁盘空间来存放中间结果，排序操作完成后再把排好序的结果集返回到客户端。在MySQL中，把这种在内存中或者磁盘上进行排序的方式统称为文件排序（filesort），文件排序的性能一般就比较低了。

但是如果 ORDER BY 子句里使用到了索引列，就有可能省去在内存或文件中排序的步骤。

例如下面的查询就会使用到 idx_cnb 索引，因为 card，name 已经排好序了，这个查询就可以直接从 idx_cnb 索引中提取数据，然后回表查询。（当然了，idx_cnb 索引已经包含了整张表的数据，所以不会有回表这一步了）

SELECT * FROM account ORDER BY card, name;
复制代码

同样的，ORDER BY 也可以只使用部分的B+树索引列，当联合索引左边列的值为精确匹配时，也可以使用后边的列进行排序。例如下面的查询：

SELECT * FROM account ORDER BY card, balance;

SELECT * FROM account WHERE card='A' ORDER BY name;
复制代码

需要注意的是，ORDER BY 子句后边的列的顺序必须按照索引列的顺序来，否则也是用不了索引的。例如下面的查询：

SELECT * FROM account ORDER BY name, card;
复制代码

使用联合索引进行排序时，要求各个排序列的排序顺序是一致的，要么各个列都是ASC升序，要么都是DESC降序。

因为如果一个按 ASC 升序，一个按 DESC 降序，这与索引中的顺序始终都是反的，而且如果加上 LIMIT 之类的限制条件，只能排好序之后才能确定具体的记录。所以 MySQL 认为这种情况还不如文件排序来的快，就不会使用索引。

例如下面的查询语句：

SELECT * FROM account ORDER BY name ASC, card DESC;
复制代码

如果用来排序的多个列不是一个索引里的，这种情况也不能使用索引进行排序，原因跟上面的是类似的。假设 acount 表还有其它列，例如下面的查询，country 列不属于 idx_cnb ，所以这个查询排序也用不上 idx_cnb 这个索引。

SELECT * FROM account ORDER BY name, country;
复制代码

分组和排序在使用索引的方式上是类似的，就不在赘述了。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能