在本节中，我们解释了 (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 算法实现实际的再平衡方法。它在节点数量上是线性的。以下是伪代码中基本 DSW 算法的演示。分配一个名为“伪根”的节点，并将树的实际根作为伪根的右子节点。调用 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) 引入了错误容差以提高查找性能和空间效率。布隆过滤器要么返回真，要么返回假。因此，布隆过滤器的结果属于以下类别之一：真阳性、假阳性、真阴性和假阴性。布隆过滤器... 阅读更多