likes
comments
collection
share

面试官:如何给 100 万个 Url 设计索引?

作者站长头像
站长
· 阅读数 433

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;

表数据:

面试官:如何给 100 万个 Url 设计索引?

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

alter table t add index index_url(url);

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

面试官:如何给 100 万个 Url 设计索引?

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

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

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

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

03 前缀索引

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

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

此时,index_url 的结构是这样的:

面试官:如何给 100 万个 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;

结果是这样的:

面试官:如何给 100 万个 Url 设计索引?

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

3.2 前缀索引的不足

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

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

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

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

04 其他方式

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

面试官:如何给 100 万个 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'))

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

面试官:如何给 100 万个 Url 设计索引?

不过有一点要注意,每次插入新记录时,都同时用 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 字段索引,查询性能稳定,有额外的存储和计算消耗,跟第三种方式一样,都不支持范围扫描。