leisurexi's Blog.

MySQL索引

MySQL
字数统计: 5.8k阅读时长: 21 min
2020/01/21 Share

本篇文章主要介绍 MySQL 中的索引。

前言

我们在平时工作中如果遇到查询慢的 SQL，第一反应是给对应的表建立索引。那么索引到底是什么呢？

MySQL索引原理

索引目的

索引 其实是一种数据结构，当表中的数据量越来越大时，索引对于性能的影响愈发重要。所以能够轻易将查询性能提升好几个数量级，总的来说就是可以明显提高查询效率。可以类比词典，如果要查 “mysql” 这个单词，我们肯定需要定位到 m 字母，然后从上往下找 y 字母，再找到剩下的 sql。如果没有索引，那么你可能就要把所有单词看一遍才能找到你想要的，如果我想找到 m 开头的单词呢？或者 ze 开头的单词呢？是不是觉得没有索引，这个事情根本无法完成？

索引原理

除了词典，生活中随处可见索引的例子，如火车站的车次表、图书的目录等。它们的原理都是一样的，通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。

数据库也是一样，但显然要复杂许多，还有范围查询 >、<、between、in、迷糊查询 like、并集查询 or等等。数据库应该选择怎么样的方式来应对所有的问题呢？我们回想词典的例子，能不能把数据分成段，然后分段查询呢？最简单的如果1000条数据，1到100分成第一段，101到200分成第二段，201到300分第三段······这样查第250条数据，只要找到第三段就可以了，一下子取出 90% 的无效数据。但如果是1千万的记录呢，分成几段比较好？稍有算法基础的同学会想到搜索树，其平均复杂度是 logn，具有不错的查询性能。但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的，数据库实现比较复杂，数据保存在磁盘上，而为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。

索引

索引的数据结构

二叉查找树

undefined

众所周知，二叉查找树是每个节点最多由两个子树的树结构，而其还有一个特点是，在任意一棵树种，根节点 的 左孩子 永远大于 小于 根节点，根节点 的 右孩子 永远 大于 根节点，用二叉查找树作为索引，确实可以提高效率，其可以使用二分查找将时间复杂度控制在 O(logn) ，但是二叉查找树有一个显而易见的 缺陷 ，当某种 特殊情况 (按照某个特定顺序插入树) 发生时，二叉查找树将变为上图右侧 (线形二叉树) 的抓概况。此时二叉查找树查找任意某个元素是，其查找顺序与逐行查找无异，查询时间复杂度有将回到 O(n) ，查询效率无法保持。

B-Tree

undefined

B-Tree，平衡多路查找树，如果每个节点最多有 N 个孩子，那么这样的树就叫 N 阶 B-Tree，每个节点主要包含 关键字 和 指向孩子的指针 ，最多能有几个孩子，取决与节点的容量和数据库的相关配置，通常情况下这个 N 是很大的。

B-Tree 作为一种数据结构，有如下特征：

  1. 根节点至少包含两个孩子。
  2. 树中每个节点 至多 含有 N 个孩子 (N>=2)。
  3. 除根节点和叶子节点外，其它每个节点至少有 ceil(N/2) 个孩子。(ceil 表示取上限，例如1.2的上限是2，1.1的上限也是2，非四舍五入)
  4. 所有叶子节点都位于同一层，即叶子节点的高度都是一样的。
  5. 假设每个 非终端 节点包含 N 个关键字信息 (P0，P1 ······ Pn，K1 ······ Kn)，那么
    • ki (i = 1 ······ n) 为关键字，且关键字按升序排序 K(i - 1) < Ki 。
    • 关键字的个数必须满足：[ceil(m / 2) - 1] <= n <= m - 1 。
    • 非叶子节点的指针：P[1]、P[2] ······ P[N]；其中 P[1] 指向关键字小于 K[1] 的子树，P[N] 指向关键字大于 K[N - 1] 的子树，其它 P[i] 指向关键字属于 (K[i - 1], K[i]) 的子树。

遵守上述规则，其目的就是尽量是每个索引块都尽可能多的存储数据，尽可能减少查找次数以提升效率。

假设我们要查询关键字为10的数据，则从根节点出发，10 < 17 ，于是通过 P1 进入其孩子节点，10 > 8 且 10 < 12 ，于是通过 P2 进入其孩子节点，最后寻找到10。如果不使用索引，而使用逐行扫描的方式进行查找，则从0开始至少扫描10次才能查找到10号数据，有了索引之后可以看到，查找次数从10变为3，大大提高了查找效率。

如果这里是 二叉查找树 ，会出现极端情况，使得查找时间复杂度为 O(n) ，而如果是 B-Tree ，由于上述五个约束，可以让节点通过 合并、分裂、上移、下移登操作，使得树高度较二叉查找树较小，查找效率显然更高。

B+Tree

undefined

B+Tree 是 B-Tree 的一个变体，其定义基本与 B-Tree 相同，除了：

  1. 非叶子节点的子树指针与关键字个数相同，其表明 B+Tree 能存储更多的关键字。
  2. 非叶子节点的子树指针 P[i]，指向关键字值 [K[i], K[i + 1]]的子树。
  3. 非叶子节点仅用来做索引，数据保存在叶子节点中。(B+树 的所有检索都是从根部开始，知道搜索到叶子节点结束)
  4. 所有叶子节点均有一个链指针，指向下一个叶子节点。(方便直接在叶子节点直接做范围统计)

B+Tree 相较于 B-Tree 的优势：

  1. B+Tree 的磁盘读写代价更低。
  2. B+Tree 的查询效率更加稳定。
  3. B+Tree 更有利于对数据库的扫描。

B+Tree 索引使用的是 B+树 数据结构，我们大多数情况使用的是 InnoDB 存储引擎，默认是 B+Tree。如上图，浅蓝色的块我们称之位一个磁盘块，可以看到每个磁盘块包含几个数据项 (深蓝色所示) 和指针 (黄色所示)，如磁盘1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点，即3、5、9、10、13、15 ······ 非叶子节点只储存不真实的数据和指针搜索方向的数据项，如17和35并不真实存在于数据表中。

Hash索引

Hash索引 即哈希索引，哈希索引中储存的是 哈希值+数据行指针，索引大致结构如下图所示 (Slot 表示索引列根据 hash 函数计算出的值，Value 表示具体数据行的指针)：

undefined

Hash索引的限制

  • 由于索引仅包含 hash code 和记录指针，所以，MySQL 不能用过使用索引避免读取记录，即每次使用哈希索引查询到记录指针后都要 回读 元祖查取数据。
  • 不能使用哈希索引排序。
  • 哈希索引不支持键的部分匹配，因为是通过整个索引值来计算 hash 值的。
  • 哈希索引只支持等值比较，例如 =、IN、<=> 。对于 where orice > 100 并不能加速查询。
  • 访问哈希索引的速度非常快，除非有很多哈希冲突 (不同的索引列值却有相同的哈希值)。当出现哈希冲突时，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
  • 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。当从表中删除一行时，存储引擎要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。

InnoDB 引擎有一个特殊的功能叫作 自适应哈希索引 ，由 MySQL 自动管理，不需要人为干预。默认情况为开启，可以通过参数 innodb_adaptove_hash_index 来禁用此特性。

当 InnoDB 注意到某些索引值被使用得非常频繁时，它会在内存中基于缓冲池的 B+Tree 索引上再创建一个哈希索引，这样 B+Tree 索引也具有哈希索引的一些优点，比如快速的哈希查找。但是只能用于等值比较，例如 =、<=>、IN ，无法用于排序。

InnoDB 官方文档显示，启用自适应哈希索引后，读和写性能可以提高 2倍 ，对于辅助索引的连接操作，性能可以提高 5倍 。

全文 (Full-text) 索引

我们平时在模糊查询时用的比较多的是 like + % ，但这种方式值适合用于在文本比较少的情况下，对于大量的文本数据检索性能是很低的。全文索引 在大量的数据面前，能比 like + % 快 N 倍，速度不是一个数量级的，但是 全文索引 可能存在精度问题。

版本支持

  • MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引。
  • MySQL 5.6 及以后的版本，MyISAM 和 InnoDB 存储引擎均支持全文索引。
  • 只有字段的数据类型为 CHAR 、VARCHAR、TEXT 才可以建全文索引。
  • MySQL 的全文索引最开始仅支持英语，因为英语的词与词之间有空格，使用空格作为分词符时跟方便的。亚洲文字，比如汉语、日语、韩语等是没有空格的，这就造成了一定的限制。不过 MySQL 5.7.6 开始，引入了一个 ngram 全文分析器来解决这个问题，并且对 MyISAM 和 InnoDB 引擎都有效。

使用全文索引

和常用的模糊匹配使用 like + % 不同，全文索引 有自己的语法格式，使用 match 和 against 关键字，如下：

1
select * from test where match(content, tag) against('xx')

注意：match 函数中指定的列必须和 全文索引 中指定的列完全相同，否则就会报错，无法使用全文索引，这是因为全文索引不会记录关键字来自哪一列。如果想要对某一列使用全文索引，请单独为该列创建全文索引。

关于 全文索引 更详细的内容，可以查看 MySQL之全文索引 。

聚集索引、覆盖索引

聚集索引和非聚集索引

聚集索引 文件中的每个搜索码都对应一个索引值，非聚集索引 文件只为索引码的某些值建立索引项。

聚集索引 将数据存储与索引放到了一块，找到索引也就找到了数据，非聚集索引 将数据和索引分来存储，索引结构的叶子节点指向数据的对应行。

MyISAM 不论是 主键索引、唯一键索引、还是普通索引 ，都采用的是 非聚集索引 ，而 InnoDB 必须有且仅有一个 聚集索引 。

InnoDB 聚集索引规则：

  1. 若一个主键被定义，该主键则作为 聚集索引 。
  2. 若没有主键被定义，该表的第一个 唯一非空索引 则作为 聚集索引 。
  3. 若不满足以上条件，InnoDB 内部会生成一个隐藏主键 (聚集索引) 。
  4. 非主键索引存储相关键位和其对应的主键值，包含两次查找。

注：InnoDB 如果查询条件为 主键索引 ，则只需查询一次，但是 辅助索引 需要查询两次，先通过 辅助索引 查询到 主键索引， 再查询到数据。

undefined

从上图中可以看到，如果一个索引时 聚集索引 ， 则其叶子节点上存放的是数据本身，而如果一个索引是 非聚集索引 ，叶子节点存放的仅是地址，指向将要查询的数据。

覆盖索引

一般情况下，聚集索引 是比 非聚集索引 的查询速度要快，因为 聚集索引 的叶子节点直接就是我们要查询的整行数据了，而 非聚集索引 的叶子节点是 主键 的值，查到主键的值后，还需要通过主键 回表 再进行一次查询。但是有一种情况 可以通过 覆盖索引 也可以让 非聚集索引 只查询一次不需要 回表查询 。

覆盖索引 指一个查询语句的执行只用从索引中就能够取得，不必从数据表中读取。当一条查询语句符合 覆盖索引 条件时，MySQL 只需要通过索引就可以返回查询所需要的数据，这样避免了查到索引后再 回表 的操作，减少 I/O 提高效率。如，表 convering_index_sample 中有一个普通索引 inx_key1_key2(key1, key2) 。当我们通过 SQL 语句：select key2 from convering_index_sample where key1 = 'keytest' 的时候，就可以通过 覆盖索引 查询，无需 回表 。

为什么 InnoDB 只有一个聚集索引，而不将所有索引都使用聚集索引？

因为 聚集索引 是将索引和数据都存放在叶子节点中，如果所有的索引都用 聚集索引 ，则每一个索引都将保存一份数据，会造成数据的冗余，在数据量很大的情况下，这种数据冗余是很消耗资源的。

索引类型

普通索引

这是最基本的索引，它没有任何限制。普通索引 (由关键字 KEY 或 INDEX 定义的索引) 的唯一任务是加快对数据的访问速度。因此，应该只为那些最经常出现在查询条件 where column = ······ 或排序条件 order by column 中的数据列创建索引。

唯一索引

它与前面的 普通索引 类似，不同的就是：普通索引 允许被索引的数据列包含重复的值。而唯一索引列的值必须是唯一的，但允许有空值。如果是 联合索引 ，则列值得组合必须是唯一的。

主键索引

它是一种特殊的 唯一索引 ，不允许有空值。一个表只能有一个 主键 。

一般是在建表的时候同时创建主键索引，与之类似的是，外键索引 ：如果为某个外键字段定义了一个外键约束条件，MySQL 就会定义一个内部索引来帮助自己以最优效率的方式去管理和使用外键约束条件。

联合索引的最左前缀匹配

在 MySQL 中不仅可以对某一列建立索引，还可以对多列建立一个联合索引，而联合索引存在一个 最左前缀匹配 的概念。下面举个栗子：

首先创建一张表：

1
2
3
4
5
6
7
8
CREATE TABLE `user`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `age` int(5) NULL DEFAULT NULL,
  `height` int(5) NULL DEFAULT NULL,
  `weight` int(5) NULL DEFAULT NULL,
  `name` varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 1 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact;

然后用 name、age、telephone 建立一个 联合索引 。

1
alter table user add index index_obj(age asc, height asc, weight asc);

索引的数据结构是一棵 B+Tree ，B+Tree 优化查询效率的其中一个因素就是对数据进行了排序，那么在创建 index_obj 这个索引的时候，也就相当于创建了一棵 B+Tree 索引，而这个索引就是 依据联合索引的成员来进行排序 ，这里是 age、height、weight 。InnoDB 存储引擎主要主键被定义，那么主键就被作为一个 聚集索引 ，而其它索引都将被作为 非聚集索引 ，所以自然而然的，这个索引就会是一个 非聚集索引 。

所以根据这些我们可以得出结论：

  1. index_obj 这个索引会根据 age、height、weight 进行排序。
  2. index_obj 这个索引时一个 非聚集索引 ，查询时需要 回表 。

根据这两个结论，首先需要了解的就是，如何排序？

单列排序简单，比大小嘛，谁都会，但是 多列排序时基于什么原则的呢？

实际上在 MySQL 中，联合索引 的排序有这个一个原则，从左往右依次比较大小 ，就拿刚才建立的索引举栗子，它会先去比较 age 的大小，如果 age 的大小相同，那么比较 height 的大小，如果 height 特无法比较出大小，那么久比较 weight 的大小，最终对这个索引进行排序。

那么根据这个排序我们也可以画出一个 B+Tree ：

数据：

undefined

B+Tree：

undefined

注意：此时由于是 非聚集索引 ，所以叶子节点不在有数据，而是存了一个 主键索引 ，最终会通过 主键索引 来 回表 查询数据。

B+Tree 的结构有了，就可以通过这个来理解 最左前缀匹配原则 了。

我们先写一个查询语句。

1
select * from user where age = 1 and height = 2 and weight = 7

毋庸置疑，这条语句一点会走 index_obj 这个索引，我们可以通过 explain 命令来验证一下。

}{LIUTCQ`}6XA%YZQ}R1GDR.png

可以看到 key 列显示的是索引 index_obj ，代表实际使用了 index_obj 这个索引。

那么我们再看一个语句。

1
select * from user where height = 2 and weight = 7

思考一下，这条语句会走索引吗？

image-20200120134041633.png

答案是否定的，如上图 type 为 ALL，代表全表扫描，那么我们分析的方向就是，为什么这条语句不会走索引 。

组合索引 的排序规则是从左到右进行比较然后排序的，而我们的 index_obj 这个索引从左到右依次是 age、height、weight ，所以当我们使用 height 和 weight 来作为查询条件时，由于 age 的缺失，那么就无法从 age 来进行比较了。看到这里可能有小伙伴会有疑问，那 如果直接用 height 和 weight 来进行比较不可以吗？ 显然是不可以的，可以举个栗子，我们把缺失的这一列写作一个 问号 ，那么这条语句的查询条件就变成了 ?27 ，那么我们从这棵 B+Tree 的根节点开始，根节点上有127和365，那么以 height 和 weight 来进行比较的话，走的一定是127这一边，但是如果缺失的列数据是大于3的呢？比如427、527、627，那么如果走索引来查询数据，将会丢失数据，错误查询 。所以这种情况下绝对 不会走索引进行查询 。这就是 最左前缀匹配的原则的原因 。

  • 最左前缀匹配原则，MySQL 会一直向右匹配直到遇到范围查询 >、<、between、like 就停止匹配，比如 a=3 and b=4 and c>5 and d=6 ，如果建立 (a,b,c,d) 顺序的索引，d 是无法使用索引的，如果建立 a,b,d,c 的索引则都可以使用到，a、b、d 的顺序可以任意调整。
  • = 和 in 可以乱序，比如 a=1 and b=2 and c=3 建立 (a,b,c) 索引可以任意顺序，MySQL 的查询优化器会帮你优化成索引可以识别的形式。

根据我们了解的可以得出结论：只要无法进行排序比较大小的，就无法走联合索引 。

可以再看几个语句：

1
select * from user where age = 1 and height = 2

如上图，这条语句是可以走 index_obj 索引的，因为它可以通过比较 12? < 365 。

1
select * from user where age = 1 and weight = 7

image-20200120143716713.png

如上图，这条语句也是可以走 index_obj 索引的，因为它也可以通过比较 1?7 < 365 ，走左子树，但是实际上 weight 并没有用到索引，因为根据 最左匹配原则，如果有两页的 age 都等于1，那么会去比较 height ，但是 height 在这里并不作为查询条件，所以 MySQL 会将这两页全都加载到内存中进行最后的 weight 字段的比较，进行扫描查询。

1
select * from user where age > 1

这条语句不会走索引，但是可以走索引。这句话是什么意思呢？这条 SQL 很特殊，由于其存在可以比较的索引，所以它走索引也可以查询出结果，但是由于这种情况是范围查询并且是全字段查询，如果走索引，还需要进行回表，MySQL 查询优化器就会认为走索引的效率比全表扫描还要低，所以 MySQL 回去优化它，让它直接进行全表扫描。

1
select * from user where age = 1 and height > 2 and weight = 7

image-20200120145731421.png

如上图，这条语句是可以走索引的，因为它可以通过 age 进行比较，但是 weight 不会用到索引，因为 height 是范围查找，与第二条语句类似，如果有两页的 height 都大于2，那么 MySQL 会将两页的数据都加载进内存，然后再来通过 weight 匹配正确的数据。

参考

https://dev.mysql.com/doc/refman/5.7/en/innodb-fulltext-index.html](https://dev.mysql.com/doc/refman/5.7/en/innodb-fulltext-index.html)

https://www.javazhiyin.com/40232.html

https://blog.objectspace.cn/2019/12/10/%E6%B8%85%E7%A9%BA%E8%AE%A4%E7%9F%A5%EF%BC%8C%E7%84%B6%E5%90%8E%E9%87%8D%E6%96%B0%E7%90%86%E8%A7%A3MySQL%E7%B4%A2%E5%BC%95%E7%BB%93%E6%9E%84/

https://juejin.im/post/5d23ef4ce51d45572c0600bc

https://zhuanlan.zhihu.com/p/29118331

https://tech.meituan.com/2014/06/30/mysql-index.html

https://blog.objectspace.cn/2019/09/04/%E3%80%90%E4%BB%8E%E5%85%A5%E9%97%A8%E5%88%B0%E5%85%A5%E5%9C%9F%E3%80%91%E4%BB%A4%E4%BA%BA%E8%84%B1%E5%8F%91%E7%9A%84%E6%95%B0%E6%8D%AE%E5%BA%93%E5%BA%95%E5%B1%82%E8%AE%BE%E8%AE%A1/#%E5%AF%86%E9%9B%86%E7%B4%A2%E5%BC%95%E5%92%8C%E7%A8%80%E7%96%8F%E7%B4%A2%E5%BC%95%E7%9A%84%E5%8C%BA%E5%88%AB

原文作者：leisurexi

原文链接：https://github.com/leisurexi/category/2020/01/21/MySQL/MySQL索引.html

发表日期：January 21st 2020, 9:30:00 pm

更新日期：January 22nd 2020, 9:33:17 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 前言
  2. 2. MySQL索引原理
    1. 2.1. 索引目的
    2. 2.2. 索引原理
  3. 3. 索引
    1. 3.1. 索引的数据结构
      1. 3.1.1. 二叉查找树
      2. 3.1.2. B-Tree
      3. 3.1.3. B+Tree
      4. 3.1.4. Hash索引
        1. 3.1.4.1. Hash索引的限制
      5. 3.1.5. 全文 (Full-text) 索引
        1. 3.1.5.1. 版本支持
        2. 3.1.5.2. 使用全文索引
    2. 3.2. 聚集索引、覆盖索引
      1. 3.2.0.1. 聚集索引和非聚集索引
      2. 3.2.0.2. 覆盖索引
      3. 3.2.0.3. 为什么 InnoDB 只有一个聚集索引，而不将所有索引都使用聚集索引？
  4. 3.3. 索引类型
    1. 3.3.1. 普通索引
    2. 3.3.2. 唯一索引
    3. 3.3.3. 主键索引
    4. 3.3.4. 联合索引的最左前缀匹配
  • 4. 参考
    • Total : 26
    2020
    2019
    CentOS 7 JVM 设计模式 Zookeeper Kafka MySQL RabbitMQ 并发 Nacos Spring IoC 集合 ELK Redis
    CentOS-7 JVM 设计模式 CentOS-7/Zookeeper MySQL RabbitMQ 并发 CentOS-7/Zookeeper/Kafka CentOS-7/MySQL Spring-IoC CentOS-7/MySQL/Nacos 集合 ELK Redis