在本节中，我们将解释 (2,4) 树如何通过引入层级链接来支持高效的指针搜索。本节中解释的思想也适用于更通用的高度平衡树类，表示为 (a, b) 树，其中 b ≥ 2a。(2,4) 树定义为高度平衡搜索树，其中所有叶子节点具有相同的深度，并且所有内部节点的度数为 2、3 或 4。元素存储在叶子节点中，内部节点仅存储搜索键以引导搜索。由于每个内部节点的度数至少为 2，因此 (2,4) 树具有 ... 阅读更多

除了指针搜索之外，动态指针搜索数据结构还应执行在指针给定位置插入和删除元素的操作。指针搜索树定义为 B 树的变体，支持在 O(log d) 时间内进行指针搜索，并在 O(1) 时间内进行更新，假设仅维护 O(1) 个可移动指针。遍历指针 d 个位置需要 O(log d) 时间。指针搜索树（即 AVL 树、红黑树）的构建要么考虑固定数量的指针，要么仅支持摊销常数时间内的更新。支持任意数量的指针并在最坏情况下更新的构建 ... 阅读更多

数据结构上的指针搜索定义为任何搜索操作的扩展，该结构支持其中给出了数据结构中元素的引用（指针）以及查询。虽然元素的搜索时间最常表示为数据结构中元素数量的函数，但指针搜索时间被视为元素和指针之间距离的函数。在一组 m 个元素中，两个元素 a 和 b 之间的距离 d(a, b) 是它们在排序中的差值。如果元素 a 和 ... 阅读更多

多叉树定义为可以有多个子节点的树。如果多叉树最多可以有 m 个子节点，则此树称为 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 组成，该块比标准布隆过滤器（布隆过滤器块）小得多，每个块都适合一个缓存行。分块布隆过滤器方案不同于分区方案，在分区方案中，每个位都插入到不同的块中。分块布隆过滤器通过以下方式实现：位 ... 阅读更多

计数器大小我们必须选择足够大的计数器以避免溢出。泊松近似建议大小为 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) 引入了错误容忍度以提高查找性能和空间效率。布隆过滤器要么返回真，要么返回假。因此，布隆过滤器的结果属于以下类别之一：真肯定、错误肯定、真否定和错误否定。布隆过滤器中的最大数量 ... 阅读更多