专利详情

专利名称	一种基于分层分配的多层数据库的布隆过滤器构造方法
申请号	CN201710078690.6	专利类型	发明专利
公开（公告）号	CN106874458A	公开（授权）日	2017.06.20
申请（专利权）人	中国科学技术大学	发明（设计）人	李永坤;张月明;张伟韬;吕敏;许胤龙
主分类号	G06F17/30(2006.01)I	IPC主分类号	G06F17/30(2006.01)I
专利有效期	一种基于分层分配的多层数据库的布隆过滤器构造方法至一种基于分层分配的多层数据库的布隆过滤器构造方法	法律状态	实质审查的生效
说明书摘要	本发明公开了一种基于分层分配的多层数据库的布隆过滤器构造方法，特征是包括设计建立存储结构、计算组合概率和、求解得分配给每层布隆过滤器的位数、维护存储结构；在进行合并操作时，使处于多层键值数据库(LevelDB)的高层的每个键分配到更多的布隆过滤器比特位数，低层的键分配到较少的布隆过滤器比特位数,其中布隆过滤器的误报率随着比特位数的增多而降低。与LevelDB传统的布隆过滤器构造方法相比，在保证内存开销与之前一致的情况下，本方法可以减少因布隆过滤器的误报带来的硬盘输入输出(I/O)操作，降低硬盘的I/O次数，减少LevelDB查询操作的平均延迟；也可以在保证查询时的期望硬盘I/O次数与传统方法基本相等的情况下，减少布隆过滤器带来的内存开销。