内存高效数据结构

介绍

内存最优解决方案

布隆过滤器

位图索引

概括

结束语

参考

介绍

RUM 系列的第一篇博文介绍了 RUM 猜想。它描述了在设计数据结构和访问方法时应该考虑的读取 (RO)、更新 (UO) 和内存 (MO) 开销之间的权衡。

在这篇文章中，我们将仔细研究两种为低空间开销而设计的数据结构：布隆过滤器和位图索引。

这篇博文是 RUM 系列的第四部分：

1. RUM 猜想——关于数据访问的推理
2. 读取高效数据结构
3. 更新高效的数据结构
4. 内存高效数据结构

本篇博文的结构如下。首先，我们将回顾上一篇博文中内存优化的解决方案，并阐述如何在牺牲结果正确性的情况下实现更佳的内存开销。下一节将介绍布隆过滤器，这是一种旨在降低且可调整内存开销的近似数据结构。之后，我们将讨论位图索引，它是一种以内存高效的方式对数据进行编码并支持快速多维查询的方法。接下来，我们将总结本文的主要思想。最后一节将结束 RUM 系列。

内存最优解决方案

实现恒定内存开销的最简单方法是不存储辅助数据。在我们的整数集示例中，内存优化实现将所有整数存储在一个大小恰好满足要求的数组中，并根据需要调整数组大小。我们推导出以下 RUM 开销：

• RO≤N
• 铀≤氮+2
• MO = 1

在这个实现中，我们可以在对整数进行排序时，用读取开销和更新开销来权衡。这允许二分查找，但需要在插入时保持顺序。另一种方法是使用压缩，这可以减少内存需求。然而，它可以应用于任何数据结构，详述这一点超出了本文的范围。

然而，由于存储在过去几十年中变得越来越便宜，我们通常对内存的要求并不严格。在大多数情况下，使用哈希表或其他读取效率高的数据结构都具有合理的内存开销。因此，在下一节中，我们将研究一种内存开销小于 1 的数据结构。

布隆过滤器

概念

布隆过滤器 [1] 是一种节省空间的近似数据结构。如果即使是加载良好的哈希表也无法完全装入内存，并且我们需要持续的读取访问，则可以使用它。然而，由于其近似的特性，必须注意可能存在误报，即成员资格请求可能返回 true，尽管该元素从未插入到集合中。

布隆过滤器背后的理念与哈希表类似。首先，我们分配的不是整数数组，而是m位数组。其次，我们使用了k 个独立的哈希函数，而不是一个。每个哈希函数都会从集合中取出一个（潜在）元素，并计算出它在位数组中的对应位置。

最初，所有位都设置为 0。为了将新值插入集合，我们使用k个哈希函数分别计算其哈希值。然后将相应位置的所有位设置为 1。

成员资格查询还会计算所有哈希值，并检查每个位置的位。如果所有位都设置为 1，则返回 true，且有一定的正确概率。如果至少有一个 0，则可以确定该元素不是集合的成员。

误报概率取决于哈希函数的数量k、位数组的大小m以及已插入布隆过滤器的元素数量n。假设所有位都独立设置，则误报率FP可以近似为

对于一个具有 100 万位、5 个哈希函数和已插入 10 万个元素的布隆过滤器，我们得到FP ≈ 1%。如果你想自己动手尝试一下这些变量，可以看看 Thomas Hurst 开发的这个很棒的布隆过滤器计算器。

除了可能存在误报之外，一个很大的缺点是不支持删除操作。我们不能简单地将要删除元素的所有位置都设置为 0，因为我们不知道在插入其他元素时是否发生了哈希冲突。我们甚至无法确定要删除的元素是否在布隆过滤器中，因为这可能是误报。

那么，布隆过滤器在实际应用中有何用途？一个用例是网络爬虫。为了避免重复工作，爬虫需要在跟踪链接之前确定自己是否已经访问过某个网站。布隆过滤器非常实用，因为将所有访问过的网站都存储在内存中几乎是不可能的。此外，如果得到误报，则意味着我们并没有访问某个网站，尽管它之前从未被访问过。如果爬虫的输出被用作搜索引擎的输入，我们并不介意，因为排名靠前的网站很可能不会只有一个链接，因此我们有机会再次看到它。

另一个用例是数据库。布隆过滤器与 LSM 树结合使用，这一点我们在上一篇博文中已经了解。执行读取操作时，我们可能需要检查日志的每一层。我们可以使用布隆过滤器来高效地检查我们查找的键是否存在于每个块中。如果布隆过滤器告诉我们键不存在，我们就可以确定，无需触碰该块。这对于通常存储在磁盘上的更高层级非常有用。

RUM 开销

布隆过滤器的 RUM 开销与哈希表的 RUM 开销相似。读取和更新开销与未采用冲突解决机制的哈希表相同。然而，由于我们使用了k 个哈希函数，因此计算哈希函数的开销要高出k倍。

内存开销取决于元素大小，即存储的元素越大，影响越大，同时也取决于过滤器的负载因子。对于存储在 1 MB 布隆过滤器中的 10 万个 32 位整数值，内存开销约为 0.33。

位图索引

概念

位图索引 [2] 是数据库索引中常用的数据结构。与布隆过滤器类似，位图索引基于位数组（也称为位图）。

从概念上讲，位图索引是一组位数组，它们将数据库列的值编码为一个逻辑位向量。对于每个可能的值，我们存储一个与列大小相同的位数组。我们来看一个布尔值列的示例。表中的第一列表示原始值。第二列和第三列是每个可能值的位数组。如果值未设置，我们只需将所有位保留为 0。

这意味着我们将 表示True为[1, 0]，False表示为[0, 1]，并将Null表示为[0, 0]。我们也可以将此过程推广到基数更高的列。

我们从中得到了什么？位图索引背后的主要动机是能够通过使用按位逻辑运算来高效地响应多维查询。如果我们想了解所有居住在德国并拥有高级合同的客户，我们只需使用成对的方式将Germany和premium位数组组合起来and即可。此外，位图索引的空间开销比 B 树索引或类似的数据结构要小得多。

一个缺点是，低内存开销效果仅在基数相当低的情况下才有效。此外，原始列的更新需要更新所有位图。因此，当应用于只读数据（例如数据仓库应用程序）时，性能最佳。

RUM 开销

使用位图索引来实现整数集合并非好主意。如果基数过高，则需要先进行分箱操作。因此，为了便于论述，我们暂时先考虑字符串集合。

由于位图只是对原始数据进行编码的另一种方式，因此读取开销与列中元素的数量成正比。如果我们要查找一个特定的值，比如说Frank，我们必须扫描整个Frank位数组来查找 1。更新开销同样很高，而且插入元素需要调整位数组的大小。

就内存开销而言，我们将基数为c 的n 个值表示为一个n×c的位矩阵。内存开销不仅取决于基数，还取决于原始值的大小。

假设我们想要表示一组美国州。如果我们将它们存储为一个包含 256 个 ASCII 字符的字符串数组，这意味着每个州现在占用 50 位而不是 256 字节。这种表示方式的额外内存开销为50 / (256 ⋅ 8) ≈ 0.02，这得益于高效的多维查询。这个计算方法可能有点不准确，因为有人可能会认为，计算基础数据的内存消耗时应该考虑最高效的编码方式。不过，我希望你能理解我的意思。

概括

在这篇博文中，我们介绍了布隆过滤器，它通过牺牲一些正确性来提升内存开销，使其超越最佳性能。位图索引是一个很好的例子，它展示了如何在不增加太多内存开销的情况下，获得索引带来的一些好处。

您是否在项目中使用过布隆过滤器或其他类似数据结构/扩展？您是如何确定哈希函数的数量和过滤器的大小的？您是否在运行时监控了误报率？

结束语

在 RUM 系列中，我想阐明在设计或推理数据结构和访问模式时面临的各种权衡。在比较不同的实现时，考虑读取、更新和内存开销，有助于更好地理解差异，甚至选择最适合您工作的实现。我还想概述现有的不同数据结构，尤其是在 RUM 猜想的背景下。

我在撰写这些文章的过程中学到了很多东西。我之前对一些数据结构的内部细节不太熟悉。阅读论文很有趣，也很享受迄今为止在现场和评论区进行的讨论，并期待着未来的讨论。感谢大家的反馈，敬请期待我们即将发布的博客文章。

参考

• [1] Bloom, BH, 1970. 具有允许误差的哈希编码中的空间/时间权衡。《ACM通讯》，13(7)，第 422-426 页。
• [2] Spiegler, Israel 和 Rafi Maayan。“二进制数据库的存储和检索考虑因素。”《信息处理与管理》21.3 (1985): 233-254。
• 封面图片：Par LPLT — 劳务人员，CC BY-SA 3.0，https://commons.wikimedia.org/w/index.php? curid=26568662

如果您喜欢这篇文章，您可以在 ko-fi 上支持我。