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

JavaFish

发布于 2021-07-05 19:08:27

6000

发布于 2021-07-05 19:08:27

文章被收录于专栏：狗哥的 Java 世界狗哥的 Java 世界

01 前言

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

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

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

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

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

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

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;

表数据：

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

alter table t add index index_url(url);

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

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

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

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

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

03 前缀索引

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

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

此时，index_url 的结构是这样的：

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;

结果是这样的：

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

3.2 前缀索引的不足

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

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

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

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

04 其他方式

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

由于前缀区分度实在不高，最起码长度 > 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'))

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

不过有一点要注意，每次插入新记录时，都同时用 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。而倒序存储方式毕竟还是用的前缀索引的方式，也就是说还是会增加扫描行数。