多叉树定义为可以有多于两个子节点的树。如果多叉树最多可以有 m 个子节点，则此树称为 m 阶多叉树。与其他已研究的树一样，m 阶多叉树中的节点将由 m-1 个键字段和指向子节点的指针组成。5 阶多叉树为了简化 m 阶多叉树的处理，会在每个节点内的键上施加某种约束或顺序，从而形成 m 阶多叉查找树……阅读更多

基本概念多维二叉查找树（简称 k-d 树）定义为用于存储多键记录的数据结构。此结构已被实现以解决统计和数据分析中的一些“几何”问题。k-d 树（k 维树的缩写）定义为一种用于组织 k 维空间中点的空间划分数据结构。数据结构 k-d 树已应用于多种应用，例如涉及多维搜索键的搜索（例如范围搜索和最近邻搜索）。k-d 树被视为二叉空间划分树的特例。非正式描述k-d 树是一种二叉树……阅读更多

再平衡算法可以通过以下方式执行：Day-Stout-Warren 算法我们可以使用 Day-Stout-Warren 算法来实现实际的再平衡方法。它是节点数的线性函数。以下是伪代码中 Day-Stout-Warren 算法的基本表示。分配一个名为“伪根”的节点，并将树的实际根作为伪根的右子节点。调用 tree-to-vine 函数，使用伪根作为参数将其转换为排序链表。调用 vine-to-tree 函数，使用伪根和树的大小（元素数量）作为参数将其再次转换为树。树的实际……阅读更多

我们首先选择一个内存块。然后我们选择每个块内的局部布隆过滤器。这可能会导致内存块之间不平衡此过滤器效率很高，但假阳性率 (FPR) 很低。首先，分块布隆过滤器的 FPR（假阳性率）应与相同大小的标准布隆过滤器相同。分块布隆过滤器由一系列块 b 组成，这些块 b 比标准布隆过滤器（布隆过滤器块）小得多，每个块都适合一个缓存行。分块布隆过滤器方案与分区方案不同，在分区方案中，每个位都插入到不同的块中。分块布隆过滤器通过以下方式实现：位……阅读更多

计数器大小我们必须选择足够大的计数器以避免溢出。泊松近似建议大小为 4 位/计数器。实现 k = (ln 2)m/n 个计数器的平均负载为 ln 2。计数器负载至少为 16 的概率：≈e-ln2(ln 2)16/16！≈6.78E-17我们考虑 4 位/计数器进行比较。计数器溢出当计数器溢出时，它可能达到其最大值。这种情况以后只会导致假阴性，如果计数器最终下降到 0，而它应该保持为非零值。这种情况的预期时间非常长，但这是我们需要注意的任何不允许假……阅读更多

基本概念计数布隆过滤器定义为布隆过滤器的广义数据结构，用于测试在给定一系列元素时给定元素的计数是否小于给定阈值。作为布隆过滤器的广义形式，存在假阳性匹配的可能性，但没有假阴性的可能性——换句话说，查询返回“可能高于或等于阈值”或“肯定低于阈值”。算法描述计数布隆过滤器中使用的参数大部分与布隆过滤器相同，例如 n，……阅读更多

布隆过滤器有三个可以权衡的性能指标：计算或执行时间（对应于哈希函数的数量 k）、过滤器的大小（对应于位数 m）和错误概率（对应于假阳性率 f = (1 − p)k）布隆过滤器 (BF) 引入错误容限以增强查找性能和空间效率。布隆过滤器返回真或假。因此，布隆过滤器的结果属于以下类别之一：真阳性、假阳性、真阴性和假阴性。布隆……阅读更多

布隆过滤器定义为一种旨在快速有效地识别集合中元素是否存在的数据结构。布隆过滤器实现了一种名为概率数据结构的特定数据结构。此数据结构帮助我们识别元素是否存在于集合中。位向量实现为基本数据结构。这是一个我们用来解释的小例子123456789101112131415表中的每个空单元格指定一个位，下面的数字是其索引或位置。要将元素添加到布隆过滤器，我们只需哈希……阅读更多

多重选择哈希之所以得名，是因为它采用了多个哈希函数的实现。在高层次上，当有多个哈希函数时，每个项目都映射到多个桶，因此算法设计者可以自由选择项目所在的桶。事实证明，这种自由允许算法获得比使用单个哈希函数更均衡的分配。我们将介绍主要的算法思想和用于证明这些算法产生的分配范围的主要数学工具。我们将看到分析……阅读更多

定义动态完美哈希被定义为一种解决哈希表数据结构中冲突的编程方法。应用虽然比其哈希表对应物更占用内存，但此方法非常适合需要对大量元素执行快速查询、插入和删除的情况。实现Dietzfelbinger等人解释了一种动态字典算法，当将一组m个项目增量添加到字典中时，成员资格查询始终消耗恒定时间，因此最坏情况时间为O(1)，所需的总存储空间为O(m)（线性），并且预期摊销插入和删除时间为O(1)（摊销恒定时间）。在动态情况下，当…阅读更多