12

我已经探索了T-tree和 B-/B+ 树的定义。从网络上的论文中，我了解到 B 树在分层内存中表现更好，例如磁盘驱动器和缓存内存。

我无法理解的是为什么 T-trees 甚至被用于平面内存？

它们被宣传为 AVL 树的节省空间的替代品。

在最坏的情况下，T 树的所有叶节点只包含一个元素，所有内部节点都包含允许的最小数量，接近满。这意味着平均只使用了一半的分配空间。除非我弄错了，否则这与 B 树的最坏情况相同，即 B 树的节点是半满的。

假设两棵树都将键本地存储在节点中，但使用指针来引用记录，唯一的区别是 B 树必须为每个分支存储指针。这通常会导致高达 50% 或更少的开销（在 T-tree 上），具体取决于键的大小。事实上，这接近于 AVL 树中预期的开销，假设没有父指针、嵌入在节点中的记录、嵌入在记录中的键。这是阻止我们使用 B-trees 的预期效率增益吗？

T 树通常在 AVL 树之上实现。AVL 树比 B 树更平衡。这可以与T-trees的应用联系起来吗？

4

2 回答 2

3

我可以给你一个涵盖一半答案的个人故事，即为什么我在大约 18 年前编写了一些 Pascal 代码来编程B+ 树。

我的目标系统是一台带有两个磁盘驱动器的 PC，我必须在非易失性存储器上存储一个索引，我想更好地了解我在大学学习的内容。我对商业包的性能非常不满意，可能是 DBase III，或者某些 Fox 产品，我不记得了。

无论如何：我需要这些操作：

  • 抬头
  • 插入
  • 删除
  • 下一项

  • 上一项

  • 索引的最大大小未知

  • 所以数据必须驻留在磁盘上
  • 每次获得支持的成本都很高
  • 读取整个块的成本与读取一个字节相同

B+-trees 让那台速度慢的小 PC 真正飞过数据！

叶子有两个额外的指针，因此它们形成了一个双向链表，用于顺序搜索。

于 2011-02-11T22:49:37.887 回答
2

实际上，区别在于您使用的系统。正如我在大学的导师所评论的那样：如果您的问题在于内存不足，或者硬盘不足，将决定您将使用哪种树以及哪种实现。很可能它将是 B+ 树。

因为有数百种实现，例如使用 2direction 队列和 1 个方向队列，您需要循环思想元素，并且还有多种存储索引和检索索引的方法将确定任何实现的真正缺点和分钟。

于 2011-02-25T08:02:35.077 回答