MySQL按位运算,布隆过滤器

Question

我想使用MySQL(其他建议的替代方案)实现bloom过滤器.

问题如下:

假设我有一个存储8位整数的表,具有以下值:

1: 10011010
2: 00110101
3: 10010100
4: 00100110
5: 00111011
6: 01101010

我想找到所有与此相关的结果:

00011000

结果应该是第1行和第5行.

但是,在我的问题中,它们不是8位整数,而是n位整数.我该如何存储,以及如何查询？速度是关键.

Answer 1

使用int列创建一个表(使用此链接选择正确的int大小).不要将数字存储为0和1的序列.

对于您的数据,它将如下所示:

number

154
53
148
38
59
106

你需要找到匹配24的所有条目.

然后你可以运行像这样的查询

SELECT * FROM test WHERE number & 24 = 24

如果你想避免在你的应用程序中转换成10个基数,你可以将它交给mysql:

INSERT INTO test SET number = b'00110101';

并像这样搜索

SELECT bin(number) FROM test WHERE number & b'00011000' = b'00011000'

Answer 2

考虑不要使用MySQL.

首先,可能没有超过64位表的内置方法.您必须使用用C编写的用户定义函数.

其次,每个查询都需要进行全表扫描,因为MySQL无法使用索引进行查询.所以,除非你的桌子很小,否则这不会很快.