PostgreSQL 布隆索引 与 a big bang therory

好吧我有点标题党，其实本期要说的是 bloom 过滤器的问题，但题目为什么是这样，一般来说我们如果要给一个大表来加索引，并且这个查询还要加挺多列的时候，是蛮头疼的问题，PostgreSQL 中有一种索引叫 BLOOM INDEX ，而这个索引有什么好处，我们来看看。

首先是什么BLOOM ，我看了一些网上的资料，写的挺好的，里面各种高大上的 X 个 值， K 个HASH ， 逼近极限，bula bula ，如果我现在也这样写，估计不少人就取关了。

所以我打算用通俗的话来说说这个事，可能说的不准确的，各位高手给纠正。

例如：我们有一个选秀比赛，里面都是 “小鲜肉”，“小仙女”，而这边又三个评委， 分别是 柯一敏， 金醒， 冯笑刚 ， 这边先进来一个，李于刚，

柯一敏说，好， 金醒说 好， 冯笑刚说 滚。

然后我们的评分表上就有了

1 1 0 这个数字

下面又进来一个 小仙女， 李与春， 柯一敏 说 滚， 金醒说 滚， 冯笑刚说 好

那么我们的评分表上就有了数字

0 0 1

以此类推，吴以凡 是 101 ， 史岩 是 100 等等， 我们就可以通过这样的数字来标识这个人，或者类似的这样的人。

但有的时候也不尽然，例如进来的是 周深 , 得分和 李于刚 一样，也是 110

那你说 110 就是 李于刚 就不大对了 （注，得分一样是因为，他们都嗓门高，唱出的声音你听不出是大老爷们）

OK 到此我们的脱离娱乐，回归到BLOOM 过滤了。某个值通过N 个 hash 计算后，在列表中产生的不同的值，一个值可以有多个HASH 的计算的值来标识，就是BLOOM过滤器的精髓，而通过这样的方法来查找值，不是 100% 的准确。但如果是用这样的方法来排除值，那绝对是 100% 的能排除不符合你要查找值的那些数据。

我们画一个图, 大致的意思我们有一堆值，通过多种HASH 算法，在我们下面的list中生成对应的HASH 值，下面的list 是记录这些值的地方VALUE1 通过三个 不同的HASH 算法后，得到的值是10000001000100100010000001

当然这里面的 位数为 1 的地方很可能，或者说有很大的可能有重复的情况，但遇到不同的HASH 算法或者后面的 VALUE2 也要在 已经有 1 的地方继续写1的时候，我们就忽略，最后依次将 VALUES 1 2 3 4 这几个值计算完毕后 10100101010100101010011101

那我们得到这个值有什么意义呢，意义就是我们在计算

value5 6 7 8 得到的值和 10100101010100101010011101 不一样的情况下，我们可以 100%的肯定，我们的 value 5 6 7 8 和 我们的 value 1 2 3 4 不一样， 但如果我们在计算 value 5 6 7 8 后，得到的值和 value 1 2 3 4 一样的情况下，我们是不能 100%的肯定我们的两次计算的值是相等的。这也就是我们耳熟能详的排除法，并且这样如果想 limit 逼近1 的情况那就可以无限的添加精度更高的 HASH 算法和 能保存值的的长度.

那么这个BLOOM 过滤器使用到使用到索引中，对比其他索引有什么好处？

使用bloom过滤器。当有一个包含太多列的表，并且查询在这样的表上使用了太多列的组合时，需要许多索引。维护这么多索引不仅对数据库来说很昂贵，而且在处理较大的数据集时也是性能杀手。

如果在所有这些列上创建一个bloom索引，则为每一列计算一个散列，并为每一行/记录合并到一个指定长度的索引条目中。这样就可以快速排出不匹配的记录,如果你查询的记录在大表中,占据的比例是很小或者是唯一的,则是一个好的选择。

我们下面就看看 PostgreSQL 中的 Bloom index 到底有多少斤两。

1 我们建立 postgresql的扩展

CREATE EXTENSION bloom;

2 建立一个测试的用表插入数据 10000000 行

3 给这个表建立一个复合索引，BTREE 的方式，耗时大约在 31秒

4 我们进行一些查询的测试，可以看到查询的速度还是蛮快的

5 我们删除索引，然后建立bloom 索引整体建立bloom 索引的时间，大约消耗8秒，对比 31秒 那是快了 四分之三

6 查询的速度也是比普通的 BTREE 索引要快的近 不到 10倍的样子

那么下面问题来了，你说这么快，那么快，没有缺点吗？

1 Bloom 过滤器适合 多个字段的索引建立

2 Bloom 适合等值运算