首页 > 数据库 > MySQL

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

来源：SegmentFault

时间：2023-02-24 16:06:59 213浏览收藏

在数据库实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《面试官：如何给字符串设计索引？》，聊聊MySQL、字符串、索引、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 索引树找到满足索引值是
```
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。而倒序存储方式毕竟还是用的前缀索引的方式，也就是说还是会增加扫描行数。
05 总结
这篇文章聊了四种解决方法，每一种都有优缺点。没有办法判断哪一种最好，只有最合适的。在开发中，你也需要根据业务来选择，总的方向就是：提高区分度 &尽量减少占用空间。
- 直接创建完整索引，这样可能比较占用空间；
- 创建前缀索引，节省空间，但会增加查询扫描次数，并且不能使用覆盖索引；
- 倒序存储，再创建前缀索引，用于绕过字符串本身前缀的区分度不够的问题；
- 创建 hash 字段索引，查询性能稳定，有额外的存储和计算消耗，跟第三种方式一样，都不支持范围扫描。
06 参考
- time.geekbang.org/column/article/71492
- cnblogs.com/Mr-Echo/p/12730797.html
07 大厂面试题 & 电子书
如果看到这里，喜欢这篇文章的话，请帮点个好看。
初次见面，也不知道送你们啥。干脆就送几百本电子书和2021最新面试资料吧。微信搜索JavaFish回复电子书送你 1000+ 本编程电子书；回复面试送点面试题；回复1024送你一套完整的 java 视频教程。
面试题都是有答案的，详细如下所示：有需要的就来拿吧，绝对免费，无套路获取。
终于介绍完啦！小伙伴们，这篇关于《面试官：如何给字符串设计索引？》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布数据库相关知识，快来关注吧！