面试官：如何给字符串设计索引？

小咪咪 2022-10-05 09:48 142阅读 0赞

# 01 前言 #

哈喽，好久没更新啦。因为最近在面试。用了两周时间准备，在 3 天之内拿了 5 个 offer，最后选择了广州某互联网行业独角兽 offer，昨天刚入职。这几天刚好整理下在面试中被问到有意思的问题，也借此机会跟大家分享下。

这家企业的面试官有点意思，一面是个同龄小哥，一起聊了两个小时（聊到我嘴都干了）。二面是个从阿里出来的架构师，他问了个场景题：

> 数据库有个字符串类型的字段，存的是 URL 怎么设计索引？

当时我给出**拆分字段：url 的前半部分肯定区分度低，到了后半部分才高；我把区分度高和低的分别拆分为两个字段存储，并在区分度高的字段建立索引**的具体答案，并提出了**尽量提高区分度**的思路。

面试官也认可了我的方向，但是问我还有没其他方案。当时没答出来，回去之后我自己查了下资料，这里也给大家分享下具体的设计方案。

国际惯例，先上思维导图：

![503b71b154d6d39f526ae005779b2d9d.png][]

# 02 整个字段加索引 #

先亮出表设计：

CREATE TABLE IF NOT EXISTS `t`(
       `id` INT(11) NOT NULL AUTO_INCREMENT,
       `url` VARCHAR(100) NOT NULL,
       PRIMARY KEY ( `id` )
    )ENGINE=InnoDB DEFAULT CHARSET=utf8;

表数据：

![381e22f74f9312455ef7799578ffbdfc.png][]

其实这个问题 = **字符串怎么设计索引？**，你可能会说直接执行下面的语句不就得了？

alter table t add index index_url(url);

我随意画了张图，在 MySQL index\_url 的结构是这样的：

![91d3a7925b882b58bfd33a71e9f36721.png][]

确实，这样是可以的。执行下面的查询语句只需要**一次扫描**操作即可。

select id,url from t where url='javafish/nhjj/mybatis';

但它还有个问题就是**浪费存储空间**，这种情况\*\*只适合存储数据较短且区分度足够高（这点是必须的，要不然我们也不会在区分度很低的字段建索引）\*\*的情况。你想想整个字段这么长，肯定贼费空间了。

那有没有不那么费空间的方法呢？我们自然就想到了 MySQL 的**前缀索引**。

# 03 前缀索引 #

针对上面的表数据，加下前缀索引，没必要整个字段加索引，因此可以这样建索引：

alter table t add index index_url(url(8));

此时，index\_url 的结构是这样的：

![00b8c1f342553611c3819aaa08242a7f.png][]

select id,url from t where url='javafish/nhjj/mybatis';

执行同样的 sql 查询，它的流程是这样的：

*  从 index\_url 索引树找到满足索引值是 `javafish` 的记录，找到的第一个是 ID1；到主键上查到主键值是 ID1 的行，判断出 url 的值不是 `javafish/nhjj/mybatis`，这行记录丢弃；
 *  取刚刚查到的位置 ID1 的下一条记录，发现仍然是`javafish`，取出 ID2，再到 ID 索引上取整行然后判断，还是不对；
 *  重复上一步，直到在 index\_url 上取到的值不是 `javafish` 时，循环结束。在这个过程中，**要回主键索引取 6 次数据，也就是扫描了 6 行**。通过这个对比，你很容易就可以发现，使用前缀索引后，可能会**导致查询语句读数据的次数变多**。

当我们把 url 前缀索引的长度增加到 10 的时候。你会发现执行一样的查询语句，只需要**扫描1行**就可以获得目标数据。

## 3.1 前缀的长度选择 ##

看到这里，你可能也发现了。**使用前缀索引，定义好长度，可以做到既节省空间，又不用额外增加太多的查询成本。它的选择尤为关键**，数据少的时候我们可以肉眼就能判断前缀长度的选择，都是数据量很大我们应该怎么判断呢？

此时脑瓜子不断想，我们可以想到 MySQL 有 count distinct 去重计数这个操作，于是可以执行以下 sql 看选择多少前缀长度合适。

select count(distinct url) as L from t;

可以这样批量操作：

SELECT
    	count( DISTINCT LEFT ( url, 8 ) ) AS L8,
    	count( DISTINCT LEFT ( url, 9 ) ) AS L9,
    	count( DISTINCT LEFT ( url, 10 ) ) AS L10,
    	count( DISTINCT LEFT ( url, 11 ) ) AS L11 
    FROM
    	t;

结果是这样的：

![2184ce56be016ef6cebd739b9f123305.png][]

我们选择前缀长度的原则是：**区分度高 + 占用空间少**；考虑这二者的因素，我会选择 10 作为前缀索引的长度。

## 3.2 前缀索引的不足 ##

前缀索引虽好，但也有不足。比如我们上面说的长度选择不好就会导致**扫描行数增多**。

还有一点就是使用了前缀索引，当你优化 sql 时，就**不能使用索引覆盖**这个优化点了。不清楚索引覆盖的小伙伴建议看看这篇文章[《MySQL 索引原理》][MySQL]

举个栗子：即使你将 index\_url 的定义修改为 url (100) 的前缀索引，这时候虽然 index\_url 已经包含了所有的信息，但 InnoDB 还是要回到 id 索引再查一下，因为系统并不确定前缀索引的定义是否截断了完整信息。

这也是你是否选择前缀索引的一个考虑点。

# 04 其他方式 #

上面的 url 都比较短，还可以用前缀索引。假设 url 突然变长（别问为啥，就是能变长变粗），长成这个样子：

![8a7bccc15f4f7e048fc7932d98893f73.png][]

由于前缀区分度实在不高，最起码长度 > 20 时，区分度才比较理想。**索引选取的越长，占用的磁盘空间就越大，相同的数据页能放下的索引值就越少，搜索的效率也就会越低。**

那还有别的方法既能保证区分度又能不占用那么多空间吗？

有的，比如：**倒序存储以及加哈希字段**

## 4.1 倒序存储 ##

先说第一种，在存储 url 时，倒序存。这时候前缀的区分度就很高啦，利用倒序建立前缀索引。查询的时候可以利用 reverse 函数查：

select url from t where url = reverse('输入的 url 字符串');

## 4.2 哈希字段 ##

**在数据表里面加一个整形字段，用作 url 的校验码，同时在这上面建立索引**。

alter table t add url_crc int unsigned, add index(url_crc);

插入的时候可以这样做：调用 MySQL 的 crc32 函数计算出一个校验码，并保存入库。

INSERT INTO t VALUE( 00000000007, 'wwww.javafish.top/article/erwt/spring', CRC32('wwww.javafish.top/article/erwt/spring'))

然后执行完之后就插入这么个结果啦。

![20f5bc7e56e62671aa7ab80c3bb01816.png][]

不过有一点要注意，每次插入新记录时，都同时用 crc32 () 函数得到校验码填到这个新字段，可能存在冲突。

也就是说两个不同的 url 通过 crc32 () 函数得到的结果可能是相同的，所以查询语句 where 部分还要判断 url 的值是否相同：

select url from t where url_crc = crc32('输入的 url 字符串') and url = '输入的 url 字符串'

如此一来，就相当于把 url 的索引长度降低到 4 个字节，缩短存储空间的同时提高了查询效率。

## 4.3 二者对比 ##

相同点：都不支持**范围查询**。

倒序存储的字段上创建的索引是按照倒序字符串的方式排序的，没有办法利用索引方式进行范围查询了。同样地，hash 字段的方式也只能支持等值查询。

它们的区别，主要体现在以下三个方面：

*  从**占用的额外空间**来看，倒序存储方式在主键索引上，不会消耗额外的存储空间，而 hash 字段方法需要增加一个字段。当然，倒序存储方式使用 4 个字节的前缀长度应该是不够的，如果再长一点，这个消耗跟额外这个 hash 字段也差不多抵消了。
 *  在 **CPU 消耗**方面，倒序方式每次写和读的时候，都需要额外调用一次 reverse 函数，而 hash 字段的方式需要额外调用一次 crc32 () 函数。如果只从这两个函数的计算复杂度来看的话，reverse 函数额外消耗的 CPU 资源会更小些。
 *  从**查询效率**上看，使用 hash 字段方式的查询性能相对更稳定一些。因为 crc32 算出来的值虽然有冲突的概率，但是概率非常小，可以认为每次查询的平均扫描行数接近 1。而倒序存储方式毕竟还是用的前缀索引的方式，也就是说还是会增加扫描行数。

# 05 总结 #

这篇文章聊了四种解决方法，每一种都有优缺点。没有办法判断哪一种最好，只有最合适的。在开发中，你也需要根据业务来选择，总的方向就是：提高区分度 &尽量 减少占用空间。

*  直接创建完整索引，这样可能比较占用空间；
 *  创建前缀索引，节省空间，但会增加查询扫描次数，并且不能使用覆盖索引；
 *  倒序存储，再创建前缀索引，用于绕过字符串本身前缀的区分度不够的问题；
 *  创建 hash 字段索引，查询性能稳定，有额外的存储和计算消耗，跟第三种方式一样，都不支持范围扫描。

# 06 参考 #

*  time.geekbang.org/column/article/71492
 *  cnblogs.com/Mr-Echo/p/12730797.html

# 07 大厂面试题 & 电子书 #

如果看到这里，喜欢这篇文章的话，请帮点个**好看**。

初次见面，也不知道送你们啥。干脆就送**几百本电子书**和**2021最新面试资料**吧。微信搜索**JavaFish**回复**电子书**送你 1000+ 本编程电子书；回复**面试**送点面试题；回复**1024**送你一套完整的 java 视频教程。

面试题都是有答案的，详细如下所示：有需要的就来拿吧，**绝对免费，无套路获取**。

![面试题][f7fb80ac3cce1e9520824533308f57b3.png]

[503b71b154d6d39f526ae005779b2d9d.png]: /images/20221005/742c295b95674cb9a8c0c89cca33cbe0.png
[381e22f74f9312455ef7799578ffbdfc.png]: /images/20221005/e0c68e2edc2b443bbb9b41aa25e4c4a5.png
[91d3a7925b882b58bfd33a71e9f36721.png]: /images/20221005/c3a2d95b59ce40f7956db1214119f495.png
[00b8c1f342553611c3819aaa08242a7f.png]: /images/20221005/e0ecc7662b164f0aa1d787662e9f4148.png
[2184ce56be016ef6cebd739b9f123305.png]: /images/20221005/1c93a81426e34c6392f3d0b2abd247a3.png
[MySQL]: https://mp.weixin.qq.com/s/ZDM_ttWCstw0mUwGtUEciw
[8a7bccc15f4f7e048fc7932d98893f73.png]: /images/20221005/1ab0643826244657b023b030dd4add52.png
[20f5bc7e56e62671aa7ab80c3bb01816.png]: /images/20221005/3074af1f696b411687bc9692db670f36.png
[f7fb80ac3cce1e9520824533308f57b3.png]: /images/20221005/8c575929621245a59b5a79b5fa2cc3c2.png