HenryKang's Docs

搜索

SearchSearch

MySQL索引

2023年1月01日19分钟阅读

Overview

主要讨论 InnoDB 引擎的 B+ 树索引。

一些基本概念

我们将索引的关键字称为 搜索码。

  • 两种基本的索引类型
    • 顺序索引：文件的记录按照搜索码顺序存放。
    • 散列索引：也叫哈希索引，通过一个哈希函数，将搜索码映射到不同的散列桶，文件的记录按照这个散列桶存放。
  • 按照其他标准分类：
    • 聚集索引：一个文件可以包含多个索引，分别基于不同的搜索码，若文件按照其某个搜索码指定的顺序排序存放，那么这个搜索码对应的索引，称为 聚集索引（clustered index），也称为 主索引（primary index）。
    • 非聚集索引：若文件没有按照某个搜索码的指定顺序存放，那这个搜索码对应的索引，称为该文件的 非聚集索引（nonclustered index），也称为 辅助索引（secondary index）。
    • 稠密索引（denxe index）：索引项包含搜索码值和指向具有该搜索码值的第一条记录的指针，其他具有相同搜索码值的记录顺序存储在第一条记录之后。这种情况称为稠密聚集索引，但如果是非聚集索引，即记录没有顺序存放，那么稠密索引就必须记录每一个具有相同搜索码值的记录的指针。
    • 稀疏索引（sparse index）：只为搜索码的某些值建立索引项，只有顺序存放才可以使用稀疏索引，即只有聚集索引才可以使用稀疏索引。查找时，找到最大的，小于等于查找关键字的搜索码值指向的记录，然后顺序查找。

**小结：**聚集索引有序，非聚集索引无序；聚集可以稠密可以稀疏，非聚集必须稠密。

由此，对于 B+ 树索引，MyISAM 的索引不论是主键索引还是非主键索引都是非聚集索引（叶节点保存指向数据的指针）；InnoDB 的主键索引包含所有的数据，是聚集索引，非主键索引保存主键索引的搜索码，是非聚集索引。

后面没有特别声明的都是在讲 InnoDB 的索引。

为什么使用 B+ 树

我么知道搜索效率最高的应该是二叉树，在普通二叉树上修改，有了二叉查找树（BST）确保二叉树有序，又给 BST 加上平衡条件形成了 AVL 树，确保了稳定性。若是所有数据都能保存在内存中，那 AVL 树可能就是最佳之选了。但我们不得不考虑的一个问题就是磁盘 IO 问题。数据量很大的时候，树越高树节点分布的越广，IO 就越频繁，最坏情况下 IO 次数等于树高，因此我们需要让树更加“矮胖”。

索引的作用不但是要实现对数据的快速查询，对于存在磁盘中的数据而言，索引还要对磁盘块进行编址寻址，即快速地找到数据所在的磁盘块。想要减少 IO 次数，就要让每一次 IO 调入的磁盘块上的可用信息越多，即每个磁盘块上包含的索引信息越多，这次 IO 的性价比就越高。

这时候就有了 平衡多路查找树：B- 树和 B+ 树。注意 B- 树 读作 “B 树”，因为英文 B-Tree。

上面提到的磁盘块对应到内存就是内存页，一般大小为 4KB，不能太大，否则会产生许多内碎片。InnoDB 索引页默认为 16KB，就会申请连续的四个磁盘块来使用。由于程序的局部性原理，InnoDB 每次读取不会只读一个内存页或一个索引页大小的磁盘块，而是会读若干个区，即包含多个磁盘块。

参考资料：
B-树　

B+树　

MySQL索引原理

B- 树

一个 m 阶的 B 树 具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都包含 k-1 个元素和 k 个孩子，其中 m/2 ⇐ k ⇐ m

3.每一个叶子节点都包含 k-1 个元素，其中 m/2 ⇐ k ⇐ m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。

B-树

1.2 B+ 树

一个 m 阶的 B+ 树 具有如下几个特征：

1.有 k 个子树的中间节点包含有 k 个元素（B 树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树

  • 注意：
    • 在 B- 树中中间节点也包含数据，而在 B+ 树中，只有叶子节点包含数据，所以 B- 树的查询不够稳定。
    • B+ 树叶子节点用指针相连接形成一个链表（应该是一个双向循环链表，图中没有给出），非常适合范围查询，而 B- 树就需要中序遍历才可以。顺带一提为什么 InnoDB 不使用哈希索引，因为哈希索引只适合等值查询，范围查询就得全表扫描。
    • 一个三层的 B+ 树大约可以索引到 1600 万记录：设一条记录 1KB，一个索引页 16KB，根节点与中间节点的数据（Bigint）加指针（InnoDB 中为 6B，这里按 8B 计算）大约 16B，所以每个中间索引页可以索引 1 000 个下级索引页（16KB/16B），三层 B+ 树可以索引 1000*1000*（16K/1K）≈1600 万。

InnoDB 的索引

索引查询过程

一张表可以有多个索引，每一个索引对应一个 B+ 树，主键索引是聚集索引，非叶子节点存放搜索码和指针，叶子节点存放所有数据；非主键索引是非聚集索引，叶子节点存放的是自己的搜索码和主键索引的搜索码。若没有主键索引，InnoDB 会自动添加一个 6 字节的 rowId 作为主键索引。

查询辅助索引时，通常是找到相应叶子节点保存的主键值，再拿这个主键值去主键索引上寻找结果，这个过程称之为 回表，总共查询了两次索引。这是一个可以优化的地方，若我们使用辅助索引只查主键值，则因为辅助索引保存了主键值可以直接返回，而不用再回表，这个称之为 覆盖索引，后面还会记录。

查找数据时，无法直接找到需要的行，而是找到相应的页加载进内存，再在内存中采用二分法寻找数据。

为什么建议使用自增主键

需要从 时间 和 空间 这两个方面去考虑：

  1. 时间：主要是考虑 索引维护的开销，因为索引是有序的，所以如果插入的数据有序，则插入操作基本上不会影响数据页中原来的数据，只是顺序往后放，除非发生 页的分裂和合并。若插入的数据无序，则每次插入都要调整 B+ 树使其保持有序，浪费性能。
  2. 空间：自增索引通常是一个 int 或 bigint，也就是最多 8B，我们知道辅助索引的叶子节点要保存主键值，若主键采用 UUID 这种字符串，那辅助索引浪费的空间就比较大。

索引优化

-- 参考自MySQL实战45讲
-- 用户表
CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`,`name`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB
覆盖索引

前面提到了若是通过辅助索引查询主键值的话，可以直接返回，是因为辅助索引的叶子节点存放了主键值，避免了 回表。那么我们是不是可以让辅助索引的叶子节点，除了保存主键值外，再保存一些额外的信息，这就是 覆盖索引。

如业务中有大量的操作要根据身份证号查找人名，我们就可以在身份证号和人名上建立联合索引。当根据身份证号查询人名的时候，会发现叶子节点保存了人名，则可以直接返回。当然覆盖索引需要考虑空间因素，数据的冗余是否值得。

最左前缀匹配原则

当我们执行查询条件 where name like ‘张%’ 时，InnoDB 不会判断索引中的全部内容，而是只匹配最左的一个字符，达到性能的提升，这就是最左前缀匹配原则。

对于这个特性，我们需要的是考虑 如何安排联合索引中字段的顺序，以达到最好的效果。例如联合索引顺序（name，age）就可以快速查找到某姓名用户，而反过来（age，name）就不行了。这时候想走 name 索引，只能再建立一个索引（name），无疑是浪费了性能。

索引下推

MySQL 5.6 引入了索引下推优化，当查询 where name = ‘张三’ and age = 10 时，使用联合索引（name，age）。5.6 之前查到第一个张三，会拿着主键值去回表，在主键索引中查找出数据再判断 age 是否符合要求；而在 5.6 之后，会直接判断联合索引中的 age 是否符合条件，直接进行过滤，不需要回表。

普通索引 VS 唯一索引

主键索引方然是唯一索引，所以这里讨论的普通索引和唯一索引都是 针对辅助索引 而言的，需要从查询和更新两个角度考虑。

  • 更新：

    • 当数据页在缓存中时：找到位置后普通索引直接更新，唯一索引需要判断是否冲突再更新。
    • 当数据页不在缓存中时：普通索引更新可以使用 change buffer，而唯一索引因为要判断是否唯一而需要调入其他数据页，不能使用 change buffer。

  • 查询：

    等值查询时，唯一索引查到后可以直接返回，而普通索引需要查询到下一条记录才能知道不满足条件。

综上所述，写多读少时可以使用普通索引，读多写少时可以使用唯一索引。因为读多写少时可能会触发 change buffer 的频繁 merge，有一些维护代价，不如直接插入来的直接。

如何给字符串字段加索引

直接加当然可以，但是要考虑到空间的浪费。我们可以想到截取字符串的前几个字符作为 前缀索引，以节省空间，但不要忘了索引还需要良好的区分度，否则会导致频繁的回表，在辅助索引和主键索引中“反复横跳”。

有两个方法可以考虑，保证区分度和节省空间：

  1. 倒序存储 + 前缀索引：像身份证号这样的字符串，直接截取额前几位那同一个省市区的人前几位都一样，区分度太小，倒序存储后取前几位那就有了一定的区分度。
  2. 新增一个散列字段：InnoDB 不支持 hash 索引，但是我们可以通过新增一个散列字段，给这个散列字段加上索引来模拟 hash 索引。

索引失效

优化器选错索引

优化器会根据 扫描行数、是否回表、是否使用临时表、是否排序 等等因素综合判断选取什么样的执行计划。在一些大范围查询、join 查询的情况下，优化器可能会觉得全表扫描比走辅助索引来得快。

判断 扫描行数 显然不可能直接扫描出每一行来计数，InnoDB 每隔一段时间会对索引的 基数 进行 采样统计。基数指 一个索引上不同值得个数，反映了索引中不重复记录数量的估计值，指示了索引的区分度。具体做法是：随机选择 N 个数据页，统计上面不同值的个数，得到平均值再乘以索引所使用的数据页的总数，就得到了该索引的基数。

对于 非主键索引，Innodb 会使用基数来估计扫描行数，有可能造成不准确的预估扫描行数，选错索引。

Innodb 的 count(*) 会找一个小的唯一索引，进行遍历，没有其他唯一索引，就是主键索引。由于有 MVCC 的原因，需要逐行判断当前事务能否可见，所以非常的耗时。

注：count 的参数不是 null，计数才会 +1。

show table status 中的 table_rows 不能作为表中数据行数的依据，因为它也是采样统计。只不过是在唯一索引上采样统计，因为是唯一的，所以基数能够一定程度上反应行数。

使用函数导致索引失效

  • 显示调用函数：

  • 对某索引字段进行函数操作，有可能破坏索引的顺序性，所以优化器会放弃走该索引。

  • 隐式的类型转换：

    • 字符串和数字运算时，MySQL 会将字符串转换为数字。当索引的字段是字符串，而查询条件是数字（没加引号）时，就会隐式的将索引字段的字符串转化为数字，就会导致索引失效。
    • 多表查询时，若关联条件在不同表的字符集不一样，则也会隐式的调用转换函数，导致索引失效。

  • 其他索引失效：

    • 使用 or、!=、<> 会导致索引失效；

      select * from xxx where index1 = xxx or index2 = xxx;
select * from xxx where index1 != xxx;

    • 索引顺序问题；

      select * from xxx where index1 = xxx and indxe3 = xxx;

    • 范围条件的右侧索引列会失效；

      -- index2 使用了范围条件，index3就会失效，下面这条语句就不会走索引
select * from xxx where index1 = xxx and index2 < xxx and index3 = xxx;

关系图谱

反向链接