共计 3660 个字符，预计需要花费 10 分钟才能阅读完成。
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。而倒序存储形式毕竟还是用的前缀索引的形式，也就是说还是会减少扫描行数。
05 总结
这篇文章聊了四种解决办法，每一种都有优缺点。没有方法判断哪一种最好，只有最合适的。在开发中，你也须要依据业务来抉择，总的方向就是：进步区分度 & 尽量 缩小占用空间。
- 间接创立残缺索引，这样可能比拟占用空间；
- 创立前缀索引，节俭空间，但会减少查问扫描次数，并且不能应用笼罩索引；
- 倒序存储，再创立前缀索引，用于绕过字符串自身前缀的区分度不够的问题；
- 创立 hash 字段索引，查问性能稳固，有额定的存储和计算耗费，跟第三种形式一样，都不反对范畴扫描。
06 参考
- time.geekbang.org/column/article/71492
- cnblogs.com/Mr-Echo/p/12730797.html
07 大厂面试题 & 电子书
如果看到这里，喜爱这篇文章的话，请帮点个 难看。
初次见面，也不晓得送你们啥。罗唆就送 几百本电子书 和2021 最新面试材料 吧。微信搜寻 JavaFish 回复 电子书 送你 1000+ 本编程电子书；回复 面试 送点面试题；回复 1024 送你一套残缺的 java 视频教程。
面试题都是有答案的，具体如下所示：有须要的就来拿吧，相对收费，无套路获取。