xsc*_*ott 17 data-structures fusion-tree
我偶然发现了维基百科页面:
我读到了底部链接的课堂笔记pdf,但它对数据结构本身有了一些手感,并详细介绍了该sketch(x)功能.我认为我的一些困惑是文章试图非常笼统,我想要一个可视化的具体例子.
此数据结构是否适合存储基于任意32或64位整数键的数据？它与B树有何不同？有一节说它基本上是一个带有分支因子的B树B = (lg n)^(1/5).对于具有32位密钥的完全填充的树,B将为2.这是否只是一个二叉树？这个数据结构是否打算使用更长的位串作为键？
我的谷歌搜索没有发现任何非常有用的东西,但我欢迎任何有关该主题的良好链接.这真的只是一种好奇心,所以我还不愿意为PDF付费portal.acm.org.
tem*_*def 12
你在这里问了很多很好的问题：
我想依次回答这些问题。
您的第一个问题是关于融合树设计用于存储什么。融合树数据结构专门用于存储适合单个机器字的整数。因此，在 32 位机器上，您将使用融合树来存储最多 32 位的整数，而在 64 位机器上，您将使用融合树来存储最多 64 位的整数。
融合树不是为处理任意长的位串而设计的。融合树的设计（我们将在稍后介绍）基于一种称为字级并行性的技术，其中对机器字（乘法、移位、减法等）执行单独的操作以隐式操作在并行的大量数字上。为了使这些技术正常工作，存储的数字需要适合单个机器字。（不过，在技术上可以调整这里的技术来处理适合固定数量机器字的数字。）
但在我们继续之前，我需要包括一个主要的警告：融合树仅具有理论意义。尽管面值的融合树似乎具有出色的运行时保证（O(log wn) 每次操作的时间，其中 w 是机器字的大小），实际的实现细节使得隐藏的常数因素是巨大的，并且是实际采用的主要障碍。关于融合树的原始论文主要是为了证明可以通过使用字级并行性而不考虑挂钟运行时间成本来超越 BST 操作的 ?(log n) 下限。因此，从这个意义上说，如果您理解融合树的目标是在实践中使用一种，我建议您停在此处并搜索另一种数据结构。另一方面，如果您有兴趣了解在不起眼的机器词中有多少潜在的力量，那么请继续阅读！
在高层次上，您可以将融合树视为常规 B 树，其中加入了一些额外的魔法以加快搜索速度。
提醒一下，b 阶 B 树是一种多路搜索树，直观上，每个节点存储（大致）b 个键。B 树是一种多路搜索树，这意味着每个节点中的键按排序顺序存储，子树存储相对于这些键排序的元素。例如，考虑这个 B 树节点：
+-----+-----+-----+-----+
| 103 | 161 | 166 | 261 |
+-----+-----+-----+-----+
/ | | | \
/ | | | \
A B C D E
这里，A、B、C、D 和 E 是根节点的子树。子树 A 由严格小于 103 的键组成，因为它位于 103 的左侧。子树 B 由介于 103 和 161 之间的键组成，因为子树 B 夹在 103 和 161 之间。类似地，子树 C 由介于 161 和 166 之间的键组成，子树 D 由 166 到 261 之间的键组成，子树 E 由大于 261 的键组成。
要在 B 树中执行搜索，您从根节点开始并反复询问您需要下降到哪个子树以继续搜索。例如，如果我想在上面的树中查找 137，我需要以某种方式确定 137 驻留在子树 B 中。我们可以通过两种“自然”的方式进行搜索：
因为 B 树中的每个节点都有 b 或更大的分支因子，所以 b 阶 B 树的高度是 O(log b n)。因此，如果我们使用第一种策略（线性搜索）来查找要下降到的树，那么搜索所需的最坏情况工作是 O(b log b n)，因为我们在 O 的每个级别上执行 O(b) 工作(log b n) 级。有趣的事实：当 b = e 时，数量 b log b n 被最小化，并且随着我们增加 b 超过此限制而逐渐恶化。
另一方面，如果我们使用二分搜索来查找要下降到的树，则运行时间最终为 O(log b · log b n)。使用对数基公式的变化，注意
log b · log b n = log b · (log n / log b) = log n，
所以以这种方式进行查找的运行时间是 O(log n)，与 b 无关。这与搜索常规平衡 BST 的时间范围相匹配。
融合树的神奇之处在于找到一种方法来确定在 O(1) 时间内下降到哪个子树。让我们先了解一下——我们可以在 B 树中的每个节点有多个子节点，按排序顺序存储，但我们可以在 O(1) 时间内找到我们的元素位于哪两个键之间！这样做绝对是不平凡的，并且是融合树的主要魔力。但是现在，假设我们可以这样做，请注意搜索融合树的运行时间将为 O(log b n)，因为我们在树中执行 O(1) 工作时间 O(log b层)！
现在的问题是如何做到这一点。
出于技术原因（稍后会变得更清楚），融合树的工作原理是选择值 b = w 1/5作为 B 树的分支参数，其中 w 是机器字大小。在 32 位机器上，这意味着我们会选择
b = w 1/5 = (2 5 ) 1/5 = 2,
在 64 位机器上我们会选择
b = w 1/5 = (2 6 ) 1/5 = 2 6/5 ? 2.29,
我们可能会四舍五入到 2。那么这是否意味着融合树只是一个二叉树？
答案是“不完全”。在 B 树中，每个节点存储 b - 1 到 2b - 1 个总键。b = 2，这意味着每个节点总共存储 1 到 3 个键。（换句话说，如果您熟悉那个可爱的数据结构，我们的 B 树将是一棵 2-3-4 树）。这意味着我们将比常规的二叉搜索树分支更多一点，但不会更多。
回到我们之前的观点，融合树主要具有理论意义。我们会在真实机器上选择 b = 2 并且几乎没有比常规二叉搜索树做得更好的事实是出现这种情况的众多原因之一。
另一方面，如果我们正在研究一台字长为 32,768 位的机器（我一生中看到其中一个都不会屏住呼吸），那么我们将得到一个分支因子 b = 8，我们实际上可能会开始看到一些击败常规 BST 的东西。
如上所述，融合树的“秘诀”是能够用一些辅助信息来扩充 B 树中的每个节点，从而可以有效地（在时间 O(1) 内）确定 B-树的哪个子树下降到的树。一旦你有能力让这一步工作，数据结构的其余部分基本上只是一个普通的 B 树。因此，广泛地（专门地？）关注此步骤的工作方式是有意义的。
到目前为止，这也是整个过程中最复杂的步骤。使这一步工作需要开发几个非常重要的子程序，这些子程序共同提供整体行为。
我们需要的第一种技术是并行排序操作。让我们回到关于 B 树搜索的关键问题：我们如何确定下降到哪个子树？让我们回顾一下我们的 B 树节点，如下所示：
+-----+-----+-----+-----+
| 103 | 161 | 166 | 261 |
+-----+-----+-----+-----+
/ | | | \
/ | | | \
T0 T1 T2 T3 T4
这是与之前相同的图，但我没有标记子树 A、B、C、D 和 E，而是将它们标记为 T0、T1、T2、T3 和 T4。
假设我想搜索 162。那应该把我放到子树 T2 中。看到这一点的一种方法是 162 大于 161 且小于 166。但我们可以从另一个角度来看：我们想要搜索 T2，因为 162 大于 103 和 161，这两个键位于它之前。有趣 - 我们想要树索引 2，并且我们大于节点中的两个键。嗯。
现在，搜索 196。这将我们置于树 T3 中，而 196 恰好大于 103、161 和 166，总共三个键。有趣的。17 呢？那将在树 T0 中，并且 17 大于零的键。
这暗示了我们将用来使融合树工作的关键策略：
为了确定要下降到哪个子树，我们需要计算我们的搜索关键字大于多少个关键字。（这个数字称为搜索关键字的排名。）
融合树的关键是如何在 O(1) 时间内做到这一点。
在开始绘制草图之前，让我们构建一个我们稍后需要的关键基元。这个想法是这样的：假设你有一个小整数的集合，这里，“小”的意思是“小到很多可以打包成一个机器字”。通过一些非常巧妙的技巧，如果可以将多个小整数打包成一个机器字，就可以在O(1)时间内解决以下问题：
Parallel rank：给定一个键 k，它是一个小整数，和一个固定的小整数集合 x 1 , ..., x b，确定有多少 x i小于或等于 k。
例如，我们可能有一堆 6 位数字，例如 31、41、59、26 和 53，然后我们可以执行诸如“这些数字中有多少小于或等于 37？”之类的查询。
为了简要了解该技术的工作原理，其想法是将所有小整数打包成一个机器字，由零位分隔。该数字可能如下所示：
00111110101001011101100110100110101
0 31 0 41 0 59 0 26 0 53
现在，假设我们想查看这些数字中有多少小于或等于 37。为此，我们首先形成一个整数，该整数由数字 37 的多个复制副本组成，每个副本前面都有一个 1 位. 那看起来像这样：
11001011100101110010111001011100101
1 37 1 37 1 37 1 37 1 37
如果我们从第二个数字中减去第一个数字，就会发生非常酷的事情。看这个：
11001011100101110010111001011100101 1 37 1 37 1 37 1 37 1 37
- 00111110101001011101100110100110101 - 0 31 0 41 0 59 0 26 0 53
----------------------------------- ---------------------------------
10001100111100010101010010110110000 1 6 0 -4 0 -12 1 9 0 -16
^ ^ ^ ^ ^ ^ ^ ^ ^ ^
我在此处突出显示的位是我们添加到每个数字前面的额外位
要了解为什么会这样，如果顶部数字大于或等于底部数字，那么当我们执行减法时，我们将永远不需要从我们放在顶部数字前面的额外 1 位“借用”，因此该位将保持为 1。否则，顶部的数字较小，因此要进行减法运算，我们必须借用该 1 位，将其标记为 0。换句话说，这个单一的减法运算可以被认为是在原始密钥和每个小数字之间进行并行比较。我们正在做一次减法，但从逻辑上讲，这是五次比较！
如果我们可以数出有多少标记位是 1，那么我们就有了我们想要的答案。事实证明，这需要一些额外的创造力才能在 O(1) 时间内工作，但这确实是可能的。
这个并行排序操作表明，如果我们有很多非常小的键——小到我们可以将它们打包成一个机器词——我们确实可以在 O(1) 时间内计算我们的搜索键的排序，这将告诉我们需要下降到哪个子树。然而，有一个问题——这个策略假设我们的密钥真的很小，但总的来说，我们没有理由假设这一点。如果我们将完整的 32 位或 64 位机器字存储为密钥，我们就不能将大量的机器字打包成一个机器字。我们可以将一个键放入一个机器字中！
为了解决这个问题，融合树使用了另一种见解。假设我们选择 B 树的分支因子与机器字中的位数相比非常小（例如， b = w 1/5）。如果您有少量机器字，您需要的主要见解是这些机器字中只有少数位实际上与确定 ordering 相关。例如，假设我有以下 32 位数字：
A: 00110101000101000101000100000101
B: 11001000010000001000000000000000
C: 11011100101110111100010011010101
D: 11110100100001000000001000000000
现在，想象一下我想对这些数字进行排序。为此，我只需要查看其中的几个部分。例如，一些数字的第一位不同（顶部的数字 A 为 0，其余数字为 1）。所以我会写下我需要查看数字的第一位。这些数字的第二位实际上并没有帮助排序——任何在第二位不同的东西已经在第一位不同（你明白为什么吗？）。数字的第三位同样帮助我们对它们进行排名，因为数字 B、C 和 D 具有相同的第一位，在第三位发散为组 (B, C) 和 D。我还需要看第四位，它将 (B, C) 分成 B 和 C。
换句话说，要将这些数字相互比较，我们只需要存储这些标记位。如果我们按顺序处理这些位，我们就不需要查看任何其他位：
A: 00110101000101000101000100000101
B: 11001000010000001000000000000000
C: 11011100101110111100010011010101
D: 11110100100001000000001000000000
^ ^^
这是素描，你在你的问题中提到的步骤，并且在使用它采取小数量的大数字，把它们变成一个小数目的小数目。一旦我们有了少量的小数，我们就可以使用我们之前的并行排序步骤在时间 O(1) 中进行排序操作，这就是我们需要做的。
当然，我在这里跳过了很多步骤。您如何确定哪些位是我们需要查看的“有趣”位？你如何从数字中提取这些位？如果给您一个不在组中的数字，考虑到它在其他位位置上可能不同，您如何确定它与组中的数字相比如何？这些不是要回答的微不足道的问题，它们是导致融合树的大部分复杂性的原因。
是的，也不是。我会说“是”，因为那里有资源可以显示不同步骤的工作方式。但是，我会说“不”，因为我不相信您可以看到任何一张图片会导致整个数据结构突然聚焦。
我教授一门高级数据结构课程，并花了两节 80 分钟的讲座，使用字级并行技术来构建融合树。此处的讨论基于这些讲座，其中对每个步骤进行了更深入的讨论，并包括不同子步骤的可视化（如何在恒定时间内计算排名、草图步骤的工作原理等），并且这些步骤中的每一个都可能让您更好地了解整个结构的工作原理。这些材料链接在这里：
第一部分讨论字级并行性、在 O(1) 时间内计算排名、构建适用于非常小的整数的融合树的变体，以及在 O(1) 时间内计算最高有效位。
第二部分探讨了融合树的完整版本，介绍了草图步骤背后的基础知识（根据与 Patricia 树的联系，我将其称为“Patricia 代码”）。
总之：
融合树是对 B 树的修改。除了每个节点都有一些辅助信息以加快搜索速度外，基本结构与常规 B 树相同。
融合树在这一点上纯粹是理论上的兴趣。隐藏常数因子太高，分支因子太低，无法与二叉搜索树进行有意义的竞争。
融合树使用字级并行来加速搜索，通常是通过将多个数字打包到一个机器字中并使用单独的操作来模拟并行处理。
草图步骤用于将输入数字中的位数减少到可以与机器字并行处理的程度。
有讲座幻灯片更深入地详细说明了这一点。
希望这可以帮助！
| 归档时间： |
|
| 查看次数： |
4664 次 |
| 最近记录： |