知识卡片
位图用位与求集合交集
当桶内文档 ID 落在已知且可承受的整数范围,可用位图表示集合:某 ID 对应位为 1 表示它存在,两集合按位与即可得到交集。原书示例中,{1,3,5,7,8,9} 与 {2,3,4,5,6,7} 按位与后,只有第 3、5、7 位为 1,交集就是 {3,5,7}。
位运算便于批量处理,但空间消耗由 ID 范围决定;范围很大而元素稀疏时,直接位图可能浪费内存。分桶能缩小每张位图覆盖的范围。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《架构师之路》第54章《深入浅出搜索架构引擎、方案与细节(上)》(源文件:_epub-src/OEBPS/Text/54.html)
- 结论依据:原文在分桶之后用 16 位位图表示 [1,16] 的集合,并以按位与得出交集,同时指出连续空间开销。
- 原始内容:如果集合符合这个特点, 就可以使用bitmap来表示集合 : 如上图,假设set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的 所有元素都在桶值[1, 16]的范围之内