我最近一直在研究 B+ 树和 T-树。似乎有一种趋势，即 B+ 树用于磁盘索引，而 T 树用于内存。
我相信这是由于磁盘 I/O 造成的，但我找不到任何证实这一概念的东西。我的假设是否正确？
此外，如果 T-tree 的磁盘访问可以通过缓存限制为 log B，那么它们在 logB N 上的性能难道不能胜过 B+ 树吗？
问问题
468 次
1 回答
1
T-Tree本质上是一棵二叉树。因此，树深度类似于 T-Tree 的 log2(N/B) 与 B+Tree 的 logB(N) （N=#data 项，B=存储在每个节点中的键数=B 的分支因子+树）。这些是近似的，因为两棵树在每个节点中都没有固定数量的项目。无论如何，对于大 N，B+Tree 将在该指标上轻松获胜。在统一内存访问的假设下，该数字无关紧要，但在辅助存储上确实很重要，它大致是辅助存储访问的数量。它在具有分层内存的现代机器上也很重要（在 Vax 11/750 上测试的原始 T-Tree 论文）。
我对如何为各自的环境更新这两种结构做出了上述假设。我相信它们是对称和公平的。我主要假设数据和密钥通过引用存储在内存中并通过复制存储在辅助存储中。如果不以这种方式调整结构，对于将统一访问成本作为其设计核心的 T-tree 来说将是灾难性的，因为每个密钥比较都需要外部访问。对于非固定大小的数据，在这两种情况下（并在现实世界中使用）都需要进行一些其他的打包调整。
于 2013-02-18T18:32:00.613 回答