有百亿计的字符串 id ，需要快速批量检查某些给定的 id 是否在其中存在，有什么比较好的解决方案？

[stiekel]

现有数百亿的 id，长度全是 32 位。给定一组 id （比如 10000 个），找出已经存在的 id，已经存在的可能是 0 个，也可能是 10000 个。请问有什么比较好的方案吗？
目前已经否决的：
1、Elasticsearch，速度太慢
2、Redis，使用 hash 组织，太消耗内存

谢谢各位。

[stiekel]

@zealic 多谢你，朋友。这个我找时间试试，C++好久没用了，我用 Go 实现一下。
@tony601818 redis 都直接有布隆过滤了？我来看看。

[hugee]

这是要做特征库？

[tony601818]

@stiekel Redis 有官方支持的 ReBloom 模块： https://redislabs.com/redis-best-practices/bloom-filter-pattern/
当然你也可以自己在应用层写一个……

[sujin190]

trie 树存储呗，内存不够就序列化到磁盘，看你这个 32 位字符串都是 16 进制编码的吧，直接解码成 16 字节，查找磁盘最差也就 16 次，缓存开始几层，应该不慢

[stiekel]

@hugee 哈哈，的确类似特征库。

@tony601818 多谢。

@sujin190 是长度为 32 的字符串。append 中有示例。

[lujinang]

bloomfilter

[sujin190]

@stiekel #25 想了下，如果 500 亿的话，极限情况估计需要 6.2T 磁盘不小啊，前四到五层也许可以直接放到内存里，但是查询是稳定可靠的
排序后遍历 16 次就可以完成 trie 树构建，还是有点麻烦的，如果频繁查询也许还是不错，偶然用一下感觉还是 grep 来的更快更简洁吧
如果想读磁盘更少的话，可以每层保存两字节，8 次就可以，单每次读取量大大上涨了

[sujin190]

@zealic #19 内存使用量算错了吧，算法也不对吧，否则 mysql 索引应该早做成这样了，这么大数据量，想查询快，怎么也得几百 G 内存使用的吧

[stiekel]

@sujin190 如果单纯只存 id 得话，没 6 T 那么大。不过总体还是很吓人。