文档章节

散列过滤器算法(HF)

断桥残雪断桥残雪
 断桥残雪断桥残雪
发布于 2015/07/29 10:46
字数 528
阅读 72
收藏 3

散列过滤器(有时称为 bloom 过滤器)是一种表示列或列集中值的分布的数据结构。散列过滤器可被视为(长)位字符串,其中 1 位指示存在某一特定行,而 0 位指示在此位的位置缺少任何行。通过将一组行中的值散列到过滤器的各个位的位置,数据库服务器可以确定是否存在与该值匹配的行(可能存在散列冲突)。

R<idx> *JH S<seq> JH* T<idx>


此处,将 R 连接到 S 和 T。数据库服务器先读取 R 的所有行,然后再从 T 读取任意行。如果散列过滤器是使用由索引扫描返回的 R 中的行构建的,则数据库服务器可以立即拒绝可能无法与 R 连接的 T 中的行。这将减少必须存储在第二个散列连接中的行数。

散列过滤器可以在同时满足以下条件的查询中使用:

  • 查询中的操作在向以后的操作返回行之前会读取它的整个输入。例如,某一列上两个表的散列连接需要从其中的一个输入读取所有相关行,以构成连接的散列表。

  • 查询访问计划中的后续操作会引用该操作结果中的行。例如,第一个连接所在列上的另一个连接只使用满足第一个连接的那些行。

在这种情况下,作为第一个连接的结果构建的散列过滤器可显著地提高第二个连接的性能。其实现方法是:在散列过滤器的位字符串中执行后备查询操作,以确定第一个连接是否先前已成功处理过某行—如果不存在这样的行,则可完全避免为第二个连接进行散列表探测,因为散列过滤器中不存在 1 位即表示探测将无法产生匹配项。



© 著作权归作者所有

断桥残雪断桥残雪
粉丝 53
博文 139
码字总数 94909
作品 0
广州
程序员
私信 提问
海量数据判重——布隆过滤器(Bloom filter)与Bitmap对比

前言 之前写过一篇Bitmap在海量整数排序中应用的博客,在看过布隆过滤器之后,感觉两个有些相似,但是又有区别,在查阅了很多资料之后,这里决定稍作总结。 关于布隆过滤器(Bloom filter)的...

tick_tock97
2017/12/01
0
0
哈希算法(go版)

哈稀函数按照定义可以实现一个伪随机数生成器(PRNG),从这个角度可以得到一个公认的结论:哈希函数之间性能的比较可以通过比较其在伪随机生成方面的比较来衡量。 一些常用的分析技术,例如泊...

徐学良
2016/01/19
761
0
bitmap 和布隆过滤器

如何解决排重问题: 对于大量的数据,有很多排重方案可以使用,典型的就是哈希表。哈希表实际上为每一个可能出现的数字提供了一个一一映射的关系,每个元素都相当于有了自己的独享的一份空间...

与你咫尺天涯
2018/03/03
32
0
布隆过滤器(Bloom Filter)

基本概念 如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合...

行者PHPer
2014/04/12
206
0
30分钟学会如何使用Shiro

一、架构 要学习如何使用Shiro必须先从它的架构谈起,作为一款安全框架Shiro的设计相当精妙。Shiro的应用不依赖任何容器,它也可以在JavaSE下使用。但是最常用的环境还是JavaEE。下面以用户登...

qq5923dd411b8fa
2017/05/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【1015】LNMP架构二

【1015】LNMP架构二 三、PHP安装 PHP安装和LAMP安装PHP方法有差别,需要开启php-fpm服务 1、下载PHP7至/usr/local/src/ 切换目录:cd /usr/local/src 2、解压缩 tar -jxvf php-7.3.0.tar.gz...

飞翔的竹蜻蜓
36分钟前
4
0
浅谈Visitor访问者模式

一、前言 什么叫访问,如果大家学过数据结构,对于这点就很清晰了,遍历就是访问的一般形式,单独读取一个元素进行相应的处理也叫作访问,读取到想要查看的内容+对其进行处理就叫作访问,那么...

青衣霓裳
55分钟前
6
0
JS内嵌多个页面,页面之间如何更快捷的查找相关联的页面

假设parent为P页面, P页面有两个子页面,分别为B页面和C页面; B页面和C页面分别内嵌一个iframe,分别为:D页面和E页面 现在通过B页面的内嵌页面D的方法refreshEpage(eUrl)来加载内嵌页面E的内容...

文文1
56分钟前
7
0
Hibernate 5 升级后 getProperties 错误

升级到 Hibernate 5 后,提示有错误: org.hibernate.engine.spi.SessionFactoryImplementor.getProperties()Ljava/util/Map; 完整的错误栈为: java.lang.NoSuchMethodError: org.hibernate......

honeymoose
57分钟前
6
0
mysql-connector-java升级到8.0后保存时间到数据库出现了时差

在一个新项目中用到了新版的mysql jdbc 驱动 <dependency>     <groupId>mysql</groupId>     <artifactId>mysql-connector-java</artifactId>     <version>8.0.18</version> ......

ValSong
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部