利用散列算法优化唯一索引性能(转www.pgsqldb.org/)

问题

我们通常需要对一些长文本字段建立唯一索引，比如，我们自己的应用里面，经常会有 URL 或者 URI 字段，里面保存类似：

这样的数据，并且要求唯一、不重复，常见的做法是创建一个唯一索引：

  create unique index on urls using btree (url);

这样处理是可以用的，但是如果只是做唯一的用途的话，会产生相当大的索引，比如我们有个表的索引就达到了 2.4G bytes 的大小，这个大小是非常惊人的，几乎令系统无法全部缓冲索引。因此造成了系统性能的明显下降。

如何解决这个问题呢？这里的主要核心在于如何减少IO，减少IO就意味着要减少数据的宽度，URL通常都会比较宽，上面两个URL一般都已经超过了30个字节，所以核心的思维在于减少这个URL的宽度，那么URL自身我们当然不能动，但是考虑到我们只是想保证唯一，以及检索是否存在这样的需求，那么我们完全还是有别的办法的，这里首先跳进脑海里的就是 MD5了。

解法

我们可以对URL做MD5运算，算出其散列值，只要散列值唯一，就基本可以保证URL是唯一的。（注意：我知道MD5是可能碰撞的，不过我们自己的数据量恐怕没那么容易碰撞，所以，先相信之）。于是，我可以创建这么一个索引：

  create unique index on urls using btree(md5(url));

似乎好了？看了看索引大小，从2.4G缩小到了900M多，貌似还可以，但是是不是就真的OK了？非也。

仔细看看 postgresql 里头 md5()函数的定义，它返回的是 text 类型，也就是用hex转码后的文本流，其宽度是 32 bytes，其实也不小！而我们只要二进制数据就可以了，所以，我们还要继续优化！

仔细查阅文档，可以发现 decode() 可以把 hex 转码的文本流反转成二进制类型（bytea），所以，我们这么干：

  create unique index on urls using btree(decode(md5(url), 'hex'));

就可以实现md5的二进制上头的唯一索引，现在看看大小：475M！老天，我们节约了 2G 的空间（内存）！

这个时候，我们需要用下面的方法查询URL或者URI是否存在：

  select * from urls where decode(md5(url), 'hex') = decode(md5({输入的URL串}), 'hex');

虽然麻烦些，但是效率很高，这就是典型的付出 CPU复杂度，换取 IO 复杂度降低的案例。

后记

二进制 16 字节的散列算法可能还是有些杀鸡用牛刀了，因为一般我们的数据也就几千万上亿行，所以64未（8字节）的散列算法就挺好的了，这个时候，我们可以考虑使用一些外部包，比如看看贡献包的digest函数，digest自身也支持md5，用法是：

 select digest(url, 'md5')

也支持sha等，担心MD5碰撞的朋友，可以使用这个贡献包的sha算法。

也可以找FNV算法来实现64位（8字节）的散列，这样前面475M的索引，在付出一定的碰撞概率增大的风险之后，有可能进一步缩小到290M左右！

总结

其实所有的优化归根结底都是IO的优化，说白了就是越小越好，IO小了，就会逐级映射到内存，缓存等等环节，最后导致惊人的质变。而IO优化则是从数据类型的宽度，数据的宽度开始，一点一滴，积少成多，聚流成河进化二来的。