type
status
date
slug
summary
tags
category
icon
password
AI summary
Last edited time
Jul 14, 2025 07:24 AM
问题描述
有以下用户订阅关系表
先给定一个 CSV 文件 和一个 template_id，只包含 userId, 数量预计在百万级别，要求判断 有多少 userId 在
template_subscribe 表中存在纯数据库方案
分批次，通过 sql 从数据库中查询,比如每次 1000 个
100W数据 需要 1000次循环，假设每次查询需要 1s，一共需要 1000 秒，该方案耗费时间太长不可接受，也会对数据库造成压力
bloom filter方案
基于数据库中的 template_id 做分组，通过定时任务生成每个分组的 bloom filter 数据结构，判断时，循环遍历csv文件中每个userId，判断是否在 bloom filter 中存在。每个id判断时间查找复杂度大概在 O(k) k为hash函数数量，100W约为 100W * k次，但是会有误判率（数据比真实数量大）。
bitmap 方案
基于数据库中的 template_id 做分组，通过定时任务生成每个分组的 bitmap 数据结构 A1，判断时，通过循环遍历csv文件中每个userId，生成一个 bitmap A2，通过对 A1、A2 取交集原算得到 A3, 直接判断A3 中的数据量即可得到人数
roaringbitmap 方案
bitmap 方案的升级版本，解决了内存消耗过大的问题
对比总结
特性 | bloom filter | bitmap | roaringbitmap |
类型 | 概率型数据结构 | 精确数据结构 | 精确数据结构 |
准确性 | 有误判率 | 准确 | 准确 |
空间效率 | 固定空间消耗 | 与最大值线性相关 | 自适应压缩存储 |
查询复杂度 | O(k) | O(1) | O(1) |
支持数据类型 | 任意可hash的对象 | 整数 | 整数 |
内存消耗 | 中等可控 | 稀疏时存在浪费 | 高 |
写入性能 | 快 | 快 | 中等 |
支持集合运算 | 否 | 是 | 是 |
删除操作 | 不支持 | 支持 | 支持 |