了解数据库中的布隆过滤器原理

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: 【5月更文挑战第17天】本文介绍布隆过滤器是一种空间高效的的数据结构,用于判断一个元素是否可能在一个集合中。它包含一个位图和多个哈希函数。

1 简介

布隆过滤器是一种节省空间的方式,用来存储有关键列表的信息。
在其中,有一个位图和一个哈希函数。

计算存储在 SST 中的键的哈希值,并将结果用于将位图中的某些位设置为“1”。当您想知道列表中是否存在某个键时,您可以通过哈希函数运行它并检查位图中的相应位是“1”还是“0”。

如果其中一个位是“0”,您确定该密钥不在列表中。如果所有位均为“1”,则可能存在该值。误报的概率仅取决于几个因素:

位图的大小
列表中的键数
每个键值设置为“1”的位数

布隆过滤器是具有空间效率和概率性的独特属性的数据结构。我们将在博客后面详细介绍这两个属性。

2 两个概念

为了更好地了解布隆过滤器,让我们阅读布隆过滤器所依赖的 2 个概念。

  • 位数组

它是一种数组数据结构,其中仅存储布尔值。它用于将位数组中某个域的值与 {0, 1} 映射

    []  []  []  []  []
     1   2   3   4   5
  • 哈希函数
    哈希函数与任何其他函数一样,接受输入并应用一些算法将输入更改为称为哈希值的输出。

    输入 --> 哈希函数 SHA-1 ---> 哈希值

哈希值有多种应用,最常见的应用之一是将哈希值存储在哈希表中以加快检索速度。应用于转换输入的算法的一个示例是 SHA-1。

哈希函数的特性使其成为将其用于布隆过滤器的理想选择:

无论输入是什么,输出的长度都保持不变。
每次传递相同的输入时,它都会给出相同的输出。
您可以阅读有关哈希函数的更多信息这里打开一个新窗口.

3 它是如何工作的?

为了了解布隆过滤器的工作原理,让我们举一个用例,我们想在位数组中存储单词“Marvel”。

让我们将其工作分解为几个步骤。

初始化位数组。
将参数传递到一组哈希函数中。
收集每个哈希函数的输出。
应用一些数学逻辑来获取要更新的位,在我们的例子中,我们使用模运算。
使用值 1 更新上一步中获得的位。
让我们看一下图表,看看同样的过程在运行。

我们已经初始化了大小为 100 的位数组,默认值为 0。

[] [] [] ... []
 1  2  3     100

将参数传递给一组哈希函数。 函数进行一些输出

输入 --->  哈希函数  ---> 4456326
    --->  哈希函数   ---> 4456326
    ...

现在我们将模运算应用于哈希函数的每个输出,我们将通过位数组的大小对其进行调制。

这些是我们需要更新以将“Marvel”存储在位数组中的位。

[1] [0] [1] [1] [0] [0] [0] [0] [0] [0]
 1   2   3   4   5   6   7   8   9   10

4 小结

在布隆过滤器的哈希函数将键映射到位图的特定位置,设置为1。

查询时,通过同样哈希函数检查位图,全1则可能存在,有0则肯定不存在。

误报概率与位图大小、键数量和哈希位数相关。其工作流程包括初始化位数组、应用哈希函数、更新位数组。

布隆过滤器在存储和查找时利用位数组和哈希函数的特性,实现概率性查找。

现在,如果我们想在布隆过滤器中搜索任何单词,我们遵循相同的过程,除了不是用 1 更新位,而是在这些位中获取存储的值,如果所有值均为 1,则意味着该元素存在于集合中。

目录
相关文章
|
1天前
|
存储 SQL 人工智能
数据库技术:原理、实践与未来展望
一、引言 数据库技术是现代信息系统中的关键组成部分,它为我们提供了高效、可靠的数据存储、查询和管理手段
|
1天前
|
存储 SQL 人工智能
数据库技术:原理、应用与未来趋势
一、引言 数据库技术作为现代信息科技的重要组成部分,不仅为数据的存储、检索和管理提供了强大的支撑,还在推动数字化转型、大数据分析和人工智能等领域的发展中发挥着关键作用
|
1天前
|
SQL 存储 数据处理
数据库技术:核心原理、应用场景与未来趋势
一、引言 数据库技术作为现代信息科技的重要支柱,为企业和组织提供了稳定、高效的数据管理手段
|
2天前
|
存储 SQL NoSQL
深入了解数据库技术:核心原理、类型及行业应用
一、引言 数据库技术是信息技术领域的重要组成部分,它负责数据的存储、检索、管理和保护
|
2天前
|
存储 SQL 多模数据库
深入剖析数据库技术:从核心原理到未来趋势
一、引言 在当今信息化社会中,数据库技术作为数据存储、管理和分析的关键技术,已经成为各行各业不可或缺的一部分
|
2天前
|
存储 SQL NoSQL
深入探索数据库技术:从原理到应用
一、引言 数据库技术作为现代信息系统的重要组成部分,不仅承载着大量的数据信息,还为数据的存储、检索、处理和分析提供了强大的支持
|
2天前
|
SQL 存储 数据处理
深入探索数据库技术:原理、实践与未来展望
一、引言 在当今信息化快速发展的时代,数据库技术作为信息系统中不可或缺的一部分,承载着数据的存储、检索、处理和分析等重要功能
|
3天前
|
存储 监控 NoSQL
深入数据库世界:原理、前沿技术与应用场景
一、引言 数据库作为现代信息技术的核心组成部分,承载着各种关键数据,支持着各种复杂的业务操作
|
3天前
|
存储 SQL 人工智能
深入数据库技术的奥秘:探索其原理、应用与未来
一、引言 在信息化快速发展的今天,数据库技术作为信息存储、管理与处理的基石,已广泛应用于各行各业
|
3天前
|
SQL 存储 数据库
深入理解数据库技术:原理、应用与最佳实践
一、引言 数据库技术是信息技术领域的基石,它负责存储、管理和检索数据,为各种应用提供数据支持