面向稀疏位图集合语义查询的高性能数据结构选型咨询

我正在处理一类可从逻辑上视为稀疏位图的数据，形式为 d_k = (f_0, f_1, ..., f_n)，具备以下特性：

• f_i 为比特位，因此 d_k 实际是类似 010010001... 的序列；
• d_k 的长度（即 f_n 的最大索引 n）无法静态确定，运行时由用户输入，范围通常为 1000~10000；
• 所有 d_k 都是稀疏结构，每个 d_k 中的非零 f_i 数量最多不超过 1024，多数情况下少于 64，远小于其长度；
• d_k 中1比特位的位置完全随机，无连续等规律；
• d_k 由其比特位唯一确定，若 d_i 与 d_j 位图相同则视为同一对象。

需要支持的操作：

• 插入位图 (f_0, f_1, ...) 并返回整数 d_k 作为句柄；
• 通过句柄查询对应位图；
• 查询：给定位图 q = (f_q0, f_q1, ...)，找出所有满足“q中所有1比特位在 d_k 中均为1”（等价于 d_k & q == q）的 d_k；
• 查询：给定位图 q = (f_q0, f_q1, ...)，找出所有满足“q中所有1比特位在 d_k 中均为0”（等价于 d_k & q == 0）的 d_k；
• 查询（次要需求，允许较慢）：给定位图 q = (f_q0, f_q1, ...)，找出所有满足“q中任意1比特位在 d_k 中为1”（等价于 d_k & q > 0）的 d_k。

请问是否存在适配此类数据与查询场景的高性能数据结构？

针对这类稀疏位图的特性和查询需求，以下几种数据结构组合可以实现高性能：

1. 核心存储与去重：哈希表 + 稀疏位图表示 #

• 将每个稀疏位图用有序整数列表存储：只记录所有值为1的比特位索引（比如位图01001对应[1,4]），既节省空间，又便于后续运算。
• 用哈希表实现去重和句柄映射：把有序整数列表的哈希值（或序列化内容）作为键，映射到唯一整数句柄；同时维护句柄到稀疏位图的反向映射表，满足插入和句柄查询需求。

2. 子集查询（d_k & q == q）：倒排索引 + 交集运算 #

• 构建倒排索引：为每个比特位位置i维护一个列表，记录所有包含i的d_k句柄。
• 查询时，取出q中所有1比特位对应的倒排列表，计算这些列表的交集，结果即为满足条件的d_k。若q是全0位图，直接返回所有d_k。
• 优化：优先以长度最短的倒排列表为基准，再依次与其他列表求交集，减少计算量。

3. 无交集查询（d_k & q == 0）：全局集合 + 补集筛选 #

• 方式一：维护所有d_k的总集合，取出q中每个1比特位对应的倒排列表，合并去重得到“与q有交集的d_k”集合，用总集合减去该集合即为结果。
• 方式二：若q的1比特位数量极少（如少于10个），直接遍历总集合，逐个检查d_k的稀疏列表与q的稀疏列表是否无交集，这种场景下效率更高。
• 优化：预先维护总集合的句柄列表，合并倒排列表时用哈希集合加速去重。

4. 存在交集查询（d_k & q > 0）：倒排索引合并 #

• 取出q中所有1比特位对应的倒排列表，合并后去重，得到的就是满足条件的d_k。若q是全0位图，返回空集合。
• 优化：优先处理长度较短的倒排列表，若无需全量结果可提前终止合并。

5. 进阶优化：布隆过滤器与分层索引 #

• 若数据量极大，给每个d_k生成布隆过滤器，先通过布隆过滤器快速排除不符合条件的d_k，再做精确检查，减少遍历量。
• 按d_k中1比特位的数量分层维护索引，查询时先筛选对应分组，再执行后续运算，缩小候选范围。

内容的提问来源于stack exchange，提问作者xiang0x48