信息的表示和查找是大多数计算机应用程序的核心。近年来,随着信息技术的发展,计算机网络已经成为人类社会重要的信息基础设施,并强力渗透到各个领域。资源的交互共享促进了更多数据和信息的产生,随着计算机的飞速发展,数据库、网络和其他应用中的数据集合规模呈几何增长。在信息集合变得越来越大,访问和表示越来越困难的情况下,如何表示大数据集合,完成大数据集合下的查询成为国内外学术界的挑战性课题。布鲁姆过滤器(Bloom Filter,BF)是一种能够简洁表示静态集合并支持集合成员从属查询的数据结构。它采用一个位串表示数据集,以可接受的误判率为代价支持元素的哈希查找。在数据库、网络和分布式系统中,布鲁姆过滤器已经得到广泛应用。然而,受限于布鲁姆过滤器的基本属性,实际应用中必须事先根据存储元素的数量和给定的误判率来估计所需过滤器的大小,如果达到过滤器最大容量后仍需额外存储元素,那么误判率就会增长,并且标准布鲁姆过滤器只支持静态集合的表示,并不支持元素的删除。因此,随着数据集的动态增长,并伴随元素的删除,传统布鲁姆过滤器将会遭遇到难以克服的困难。为此,本文设计了一种新型的可扩展的计数布鲁姆过滤器(Scalable Counting Bloom Filter,SCBF),通过添加额外的元数据来标识集合中的元素,增强元素和布鲁姆过滤器之间的关系,准确判断元素究竟属于哪一个布鲁姆过滤器,不仅支持新元素的插入,还支持已有元素的可靠删除。主要工作如下:1)实现动态扩展。在计数布鲁姆过滤器的基础上提出一种动态扩展方案,通过创建一个布鲁姆过滤器的列表,作为一个大的布鲁姆过滤器,每当过滤器满载后要更大的容量时,新建一个新的过滤器添加到列表中。同时,使用一个缩紧率r控制每个新添加过滤器的误判率,确保总体误判率可控。2)实现精确删除。整合布鲁姆过滤器的删除功能和可扩展性。在元素的插入和删除过程中,以单调递增的序列作为额外添加的标识,将元素归类。那么就可以通过元素的标识确定元素的归属,从而确保元素可以从正确的过滤器删除。3)系统优化。对SCBF的扩展规模进行了优化,并且通过引入内存序列和磁盘序列跟踪系统的操作,提供数据一致性保护。理论和实验表明,SCBF可以很好地实现动态扩展和动态删除,在功能的实现上明显优于其他布鲁姆过滤器。而且,经过大量的测试,本文找到了相关参数的最佳取值,确保系统的误判率始终收敛在可控范围,并且满载状态下空间开销仅比理想条件下的计数布鲁姆过滤器稍大。