May 2020
Beginner to intermediate
319 pages
7h 3m
Chinese
Content preview from 数据库系统内幕
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
132
｜
第
7
章
7.3.2
布隆过滤器
LSM 树中读放大的来源是，我们必须寻址多个磁盘驻留表，以便完成读取操作。这是因
为我们不一定能预先知道一个磁盘驻留表是否包含要搜索的键指向的数据记录。
防止表查询的方法之一是在元数据中存储其键的范围（存储给定表中的最小和最大键），
并检查要搜索的键是否在该表的范围之内。这一信息是不精确的，它只能告诉我们数据
记录是否
可能
会出现在表中。为了改进这种情况，包括 Apache Cassandra 和 RocksDB
在内的许多实现都使用一种称为
布隆过滤器
（Bloom Filter）的数据结构。
概率型数据结构通常比它对应的“常规”数据结构具有更高的空间效率。例
如，要检查集合成员身份、基数（找出集合中不同元素的数量）或频率（找出
某个元素出现的次数），我们必须储存所有集合元素，然后遍历整个数据集以
找到结果。而概率结构则允许我们储存近似信息并执行查询，从而产生带有不
确定因素的结果。关于这类数据结构的一些众所周知的例子有布隆过滤器（用
于集合成员判断）、HyperLogLog（用于估计基数）[FLAJOLET12] 和 Count-
Min Sketch（用于估计频率）[CORMODE12]。
布隆过滤器
是 Burton Howard Bloom 在 1970 年提出的 [BLOOM70]，它是一种空间效率
很高的概率型数据结构，可以用来测试元素是否是集合的成员。它可能产生假阳性匹配
（返回“元素在集合中”的结果，而实际上该元素却不在集合中），但不会出现假阴性匹
配（
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.