大家好，我是水哥!

  今天给大家分享的是 MySQL 优化系列文章之如何给字符串增加索引。

  问题引入

  假设业务查询中，需要查询出 a、 b、 c 三个联合字段是否存在唯一记录值。

  其中，a、 b、 c 字段都为字符串。a 和 b 最大字符串长度为 5，c 最大字符串长度为 30。

  a、b、c 三个字段的组合值不允许重复。

  随着业务的增长，表数据的规模可能达到百万级和千万级。

  上述问题，在业务中会有如下查询语句:

mysql> select id from T where a="xxx" and b = "yyy" and c = "zzz";    

  由于是在大表上查询，如果不给这个查询增加索引，必然会引起 SQL 慢查询，导致查询性能问题，这样业务响应时间就会变得很慢，甚至可能引起系统故障。

  我们先来看一下不合理的索引设计方式。

  错误的索引设计

  基于上面的查询，我们通常会想到为上面三个字段增加一个联合索引：

mysql> alter table T add index idx_a_b_c(a,b,c);        

  显然，这是一个有效的索引设计，每次基于 a、 b、 c 的查询都会命中该索引。

  但我们不得不考虑一个现实问题，索引是以树为数据结构存储在磁盘上的，在查询时是从磁盘加载到内存中执行的。

  因此索引是通过空间来换取时间效率的一种设计。

  我们来简单计算一下上面索引的存储开销。

  在这个例子中，我们为该表指定的是 InnoDB 存储引擎，在 InnoDB 中，索引底层的数据结构使用的是 B+ 树。

  在 B+ 树中，每一层父节点的索引值都会出现在下层节点的索引值中，因此在叶子节点中，包含了所有索引值信息。

  为了简化计算，我们只计算叶子节点上索引值的存储开销，忽略非叶子节点的索引值存储开销。

  假设目前 a 和 b 字段可能有 10 种不同的值，c 字段可能有 10 万种不同值，那么 a、 b、 c 组合在一起不重复的值可能有: 10 10 10 万 = 1000 万种。

  如果这 1000 万种值被存入到表里面，那么 a、 b、 c 联合索引对应 B+ 树叶子节点的索引值也是会有 1000 万个。

  我们按 a、b、c 字段存储的都是英文字符并且以 a、b、c 最大存储长度来计算。

  那么 a 字段将占 5 个字节，b 字段也占 5 个字节，c 字段占 30 个字节，一个索引值将占 40 个字节的存储空间。

  备注: 在不同的编码中，英文字符通常都会占用 1 字节的存储空间。

  1000 万个索引值将占: 1000 万 * 40 字节 = 40000 万字节，40000 万字节大约是 382 兆的数据大小。

  如果 a 和 b 字段包含的值可能更多，c 字段值的量级也可能更大，那么索引占用的存储空间将成倍的，可能达到几 G 甚至及几十 G 的磁盘空间大小。

  如果一张表的单个索引就占用那么大的存储空间，这显然是不合理的。

  虽然这种索引设计方式能提高查询效率，但会占用过大的磁盘存储空间，随着数据的增长，必然会带来性能隐患，因此并不推荐这样的方式。

  合理的索引设计方式使用前缀索引

  在 MySQL 中，是允许给字符串一部分添加索引的，我们称为前缀索引。

  比如我们只给 c 字段的前 6 个字节添加索引:

mysql> alter table T add index idx_a_b_c6(a,b,c(6));        

  这样做有两个好处：

  节省索引值占用空间。由于只定义 c 字段的前 6 个字节做索引，而不是用全字符串作为索引，将极大的节省磁盘空间。

  如果定义的前缀区分度较高，将能很好的提高查询效率。

  怎么理解第 2 点呢?

  还是基于这个查询来举例。

mysql> select id from T where a="xxx" and b = "yyy" and c = "xxxxxx123";    

  如果 c 字段值前 6 个字符能很好的区分整个字符串，那么就不用对重复的前缀进行回表查询判断了，能减少往主键索引上查询的次数。

  备注: 这里还是假设 c 字段存储的都是英文字符，一个英文字符占据一个字节，前 6 个字节就代表前 6 个字符。

  比如当表记录中 c 字段值为以下值时，由于前 6 个字符没有重复，就不需要进行回表判断，提高查询效率。

xxxxxx123    yyyyyy456    zzzzzz789    

  当如果表中的记录为为以下值时，由于前 6 个字符 xxxxxx 并不能区分这三个值，因此需要回表判断才能确定查询的是哪条数据。

xxxxxx123    xxxxxx456    xxxxxx789    

  备注:

  因为是添加的是前缀索引，因此二级索引 idx_a_b_c6 对应 B+ 树的索引值并不包含 c 字段的全部字符值，只有在主键索引树上才包含。

  往主键索引树上查询 c 字段值的过程就称为回表查询。

  回表查询需要把主键索引树的节点从磁盘加载到内存中执行，因此会增加磁盘 IO 的次数，增加查询时间。

  因此设计出合理的前缀索引关键是要能有一个比较好的区分度。

  区分度越高，重复的索引键值越少，回表查询的次数也越少，查询的速度约越快。

  而前缀索引的长度是影响区分度的关键。

  那么如何确定前缀索引的长度呢?我们可以通过以下方式来确定。

  首先，我们可以用以下语句来确认 c 字段有多少不重复值。

mysql> select count(distinct c) as L  from T;        

  然后我们再来看一下前缀索引定义成不同长度时，有多少不重复值。

mysql> select count(distinct left(c,4)) as L4,      count(distinct left(c,5)) as L5,    count(distinct left(c,6)) as L6,    count(distinct left(c,7)) as L7    from T;    

  理论上来说，统计出的 L 值越大，索引值的区分度越高，我们应该选择 L 值大的。

  但 L 值越大，索引值占用存储空间也将越大，我们可以用损失度来确认最终选择哪一个。

  比如我们允许损失 5%，那么就可以在 L4 ~ L7 之间找出一个不小于 L * 95% 的符合值。

  如果没有符合要求的值，我们可以增大损失的比例，或者找一个比较临近 L * 95% 的值。

  使用倒序存储

  如果字符串进行正序存储添加的前缀索引区分度不高，那么我们可以尝试使用倒序存储的方式。

  倒序存储指的是将需要添加前缀索引的字段值进行反转存储，在查找的时候也进行反转查询。

  这种方式有可能提高区分度，但也依然需要使用上面的损失度的方式来验证。

  比如对于文中的例子，进行反转查询的时候是这样的：

mysql> select id from T where a="xxx" and b = "yyy" and c = reverse("xxxxxx123");    

  倒序存储的方式只适合等值查询的场景，因为将字符串反转后将失去字符原有的组合规律，不再将适合范围查询。

  前缀索引带来的问题

  合理的前缀索引不仅能节省磁盘的存储空间，还能提高查询效率。

  但如果一个区分度不高的前缀索引将会增加回表查询的次数，引起查询性能的问题，这样的前缀索引就已经失去效果了。

  另外，前缀索引将会使覆盖索引的特性失效。

  比如对于以下查询:

mysql> select id,c from T where a="xxx" and b = "yyy" and c = "xxxxxx";    

  这里增加了一个 c 字段的额外查询，由于前缀索引不保存 c 字段的全部字符，因此需要往主键索引上进行查询才能获取。

  即使我们把前缀索引的长度增加到 c 字段的最大长度值，在查询的时候也依然不能利用覆盖索引的特性，还是需要往主键索引上查询。

  因为 MySQL 并不知道定义的前缀索引是否截断了完整信息。

  比如对于例子中的 c 字段，如果我们把前缀索引的长度定义为 6，MySQL 并不知道实际 c 字段的完整信息到底占用多大长度。

  虽然我们定义了 c 字段最大存储长度为 30，但如果 c 字段是 varchar 这种可变长类型，它实际存储的字符长度可能就是 1 - 30 之间的任何值。

  MySQL 并不清楚 6 这个长度是否就代表了字符的完整长度，因此需要往主键索引上查询才能确定，主键索引包含了 c 字段的完整信息值。

  使用 hash 字段

  上面介绍的使用损失度来确认定义的字符串前缀索引长度的方法，其实是属于「事后确认法」。

  也就是说只有等到业务表里面有一定的数据量后，我们需要给业务增加某个查询或者原有业务查询报出查询性能问题时，才考虑使用这种方式。

  但往往有时候，我们需要事先就定义好索引。

  比如在给业务开发一个新功能时，表需要单独再创建，并且在上线前就需要根据业务查询的特点设计好索引。

  这时候，如何给字符串字段增加索引，就变成需要考虑的一个问题。

  如果你对这个字符串字段组成规律比较了解，知道设计出多长的前缀能较好的进行区分，那么就可以为这个字符串字段增加前缀索引。

  如果无法事先确认前缀索引的长度，那还有其它方式来给字符串字段添加索引吗?

  答案是有的，我们可以给字符串添加 hash 字段。

  我们知道在数据结构中，哈希函数的思路是将字符串通过某种算法映射成一个唯一数字，用这个数字来代表这个字符串。

  在索引设计中，我们也可以在表里面添加一个额外的整数字段，用来存储字符串经过哈希之后的数字值。

  再用这个整数字段来代替字符串字段来创建索引，这样不仅能节省索引的占用磁盘空间，还能提高查询效率。

  我们还是以文中的例子，来看一下如何使用 hash 字段来添加索引。

  首先我们在表里面新增一个整数字段 c_crc:

mysql> alter table T add c_crc int unsigned;    

  然后我们给a、b、c_crc三个字段增加一个联合索引:

mysql> alter table T add index idx_a_b_cCrc(a,b,c_crc);        

  在业务记录插入时，我们可以使用 crc32() 这个哈希函数来生成字段 c 对应的整数值。

  查询时，我们可以使用以下语句就能使用到 idx_a_b_cCrc 这个索引:

mysql> select id from T where a="xxx" and b = "yyy" and c_crc=crc32("xxxxxx") and c = "xxxxxx";    

  为什么这里的查询条件还要加个 c = "xxxxxx"呢?

  因为经过哈希函数计算出来的数字可能是冲突的，也就是说多个字符串经过 crc32() 函数计算出的数字可能对应同一个值。

  如果不加上一个完整的字符串判断，那么系统查询出来的结果可能不是正确的。

  增加一个完整的字符串判断并不会使 idx_a_b_cCrc 这个索引失效，如果查询的时候有冲突，也只是增加回表次数而已。

  而且经过 crc32() 函数计算出来的数字冲突的概率是比较小的，但为了精确，在业务查询中我们还是需要增加一个完整的字符串判断。

  用 hash 字段给字符串字段增加索引的方式，也只适合等值查询的场景，不适合做范围查询，因此我们要根据实际业务查询特点按需使用。

  好了，今天的文章就分享到这边了，如果觉得水哥的文章对你有帮助，欢迎将文章分享给你身边的朋友。

  我们下次再见!