← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 2280.j.4

布隆过滤器省磁盘读

理解等级:未标注

[[LSM树与预写日志]]有个性能陷阱:查找不存在的键最慢,要查完内存表和每一个磁盘段才能下结论。布隆过滤器是内存高效的近似集合结构,能快速回答“某键是否可能存在”。它可能误报存在,但绝不误报不存在:若它说不存在,就一定不存在,可以直接跳过该段的磁盘读取;说可能存在时再去查,偶尔白查一次也不影响正确性。这是用轻微、可控的误判率换取大量无谓磁盘 I/O 的经典权衡。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第三章:存储与检索 · 查看原书依据

      例如,当查找数据库中不存在的键时,LSM树算法可能会很慢:您必须检查内存表,然后将这些段一直回到最老的(可能必须从磁盘读取每一个),然后才能确定键不存在。为了优化这种访问,存储引擎通常使用额外的Bloom过滤器【15】。 (布隆过滤器是用于近似集合内容的内存高效数据结构,它可以告诉您数据库中是否出现键,从而为不存在的键节省许多不必要的磁盘读取操作。)

    参考来源

    - 位置:《数据密集型应用系统设计》第三章《存储与检索》"性能优化"(源文件:_epub-src/ch3_split_002.html) - 结论依据:原文说明LSM树算法查找不存在的键时必须检查内存表和一直回溯到最老的 段才能确定,性能较慢,为优化这种访问,存储引擎通常使用布隆过滤器——一种用于 近似集合内容的内存高效数据结构,能告诉数据库中是否出现某键,从而为不存在的键 节省许多不必要的磁盘读取操作,直接支撑本卡片结论。 - 原始内容:例如,当查找数据库中不存在的键时,LSM树算法可能会很慢:您必须检查内存表,然后将这些段一直回到最老的(可能必须从磁盘读取每一个),然后才能确定键不存在。为了优化这种访问,存储引擎通常使用额外的Bloom过滤器【15】。(布隆过滤器是用于近似集合内容的内存高效数据结构,它可以告诉您数据库中是否出现键,从而为不存在的键节省许多不必要的磁盘读取操作。)