知识卡片
布隆过滤器省磁盘读
[[LSM树与预写日志]]有个性能陷阱:查找不存在的键最慢,要查完内存表和每一个磁盘段才能下结论。布隆过滤器是内存高效的近似集合结构,能快速回答“某键是否可能存在”。它可能误报存在,但绝不误报不存在:若它说不存在,就一定不存在,可以直接跳过该段的磁盘读取;说可能存在时再去查,偶尔白查一次也不影响正确性。这是用轻微、可控的误判率换取大量无谓磁盘 I/O 的经典权衡。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第三章:存储与检索 · 查看原书依据
例如,当查找数据库中不存在的键时,LSM树算法可能会很慢:您必须检查内存表,然后将这些段一直回到最老的(可能必须从磁盘读取每一个),然后才能确定键不存在。为了优化这种访问,存储引擎通常使用额外的Bloom过滤器【15】。 (布隆过滤器是用于近似集合内容的内存高效数据结构,它可以告诉您数据库中是否出现键,从而为不存在的键节省许多不必要的磁盘读取操作。)
参考来源
- 位置:《数据密集型应用系统设计》第三章《存储与检索》"性能优化"(源文件:_epub-src/ch3_split_002.html)
- 结论依据:原文说明LSM树算法查找不存在的键时必须检查内存表和一直回溯到最老的
段才能确定,性能较慢,为优化这种访问,存储引擎通常使用布隆过滤器——一种用于
近似集合内容的内存高效数据结构,能告诉数据库中是否出现某键,从而为不存在的键
节省许多不必要的磁盘读取操作,直接支撑本卡片结论。
- 原始内容:例如,当查找数据库中不存在的键时,LSM树算法可能会很慢:您必须检查内存表,然后将这些段一直回到最老的(可能必须从磁盘读取每一个),然后才能确定键不存在。为了优化这种访问,存储引擎通常使用额外的Bloom过滤器【15】。(布隆过滤器是用于近似集合内容的内存高效数据结构,它可以告诉您数据库中是否出现键,从而为不存在的键节省许多不必要的磁盘读取操作。)