data-structures - T-trees 与 B+/-trees 相比有哪些优势？

Question

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

我不明白的是为什么 T 树甚至用于平面内存？

它们被宣传为 AVL 树的空间高效替代品。

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

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

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

Answer 1

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

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

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

查找

插入

删除

下一项

上一个

索引的最大大小未知

所以数据必须驻留在磁盘

每次获得支持的成本都很高

读取整个块的成本与读取一个字节的成本相同

B+-trees 让那台慢速的小 PC 真的在数据上飞起来了!

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