了解融合树？
我偶然发现了他们的Wikipedia page：
Fusion tree
我阅读了链接在底部的课堂笔记pdf，但它对数据结构本身进行了手把手的介绍，并深入了解了许多关于sketch(x)函数的细节。我认为我的部分困惑是因为论文试图非常笼统，我想要一个具体的例子来可视化。
这种数据结构适合存储基于任意32位或64位整数键的数据吗？它与B树有什么不同？有一个部分说它基本上是一个带有分支因子B = (lg n)^(1/5)的B-树。对于一个具有32位密钥的完全填充的树，B应该是2。这会变成一个二叉树吗？这个数据结构是否打算使用更长的位串作为关键字？
我的谷歌搜索没有找到任何非常有用的东西，但我欢迎任何关于这个主题的好链接。这真的只是一个短暂的好奇心，所以我还不愿意为portal.acm.org上的PDF付费。
回答 3
Stack Overflow用户
发布于 2010-11-04 10:11:09
我读过(只是快速浏览一下)这篇开创性的论文，看起来很有趣。它还回答了您在第一页中的大多数问题。
你可以从here下载这篇论文
哈！
Stack Overflow用户
发布于 2010-11-10 02:51:53
我读过融合树的论文。这些想法相当巧妙，从O符号的角度来看，他可以为获胜做好准备。
我不清楚这在实践中是不是一场胜利。恒定因素很重要，芯片设计者非常努力地管理廉价的本地参考。
他必须在他的假B树中有B，对于真正的机器来说，B非常小( 32位的B=5，64位的可能是10 )。那么多的指针几乎可以放在一个缓存线中。在几百个周期的第一次缓存线接触(他无法避免)之后，您几乎可以在每个键的几个周期内对键进行线性搜索，这意味着仔细编码的B树传统实现看起来应该比融合树更快。(我已经构建了这样的B-tree代码来支持我们的程序转换系统)。
他声称有一份申请清单，但没有可比较的数字。
有人有确凿的证据吗？(实现和比较？)
Stack Overflow用户
发布于 2016-02-29 00:19:44
融合树背后的想法实际上相当简单。假设你有w位(比方说64位)的密钥，这个想法是将每一个连续的64个密钥压缩(即草图)到一个64元素的数组中。sketching函数确保了原始键和给定组的数组索引之间的恒定时间映射。则搜索密钥变成搜索包含密钥的组，该组为O(log(n/64))。正如您所看到的，主要的挑战是草图功能。
https://stackoverflow.com/questions/3878320
复制相似问题
腾讯云开发者
