我已经探索了 T-trees 和 B-/B+ 树的定义。从网上的论文中我了解到 B 树在分层内存中表现更好，例如磁盘驱动器和缓存内存。
我不明白的是为什么 T 树甚至用于平面内存？
它们被宣传为 AVL 树的空间高效替代品。
在最坏的情况下，T 树的所有叶节点只包含一个元素，所有内部节点都包含允许的最小数量，接近满。这意味着平均只使用了一半的分配空间。除非我弄错了，这与 B 树的最坏情况相同，当 B 树的节点半满时。
假设两棵树都在节点本地存储键，但使用指针来引用记录，唯一的区别是 B 树必须存储每个分支的指针。这通常会导致高达 50% 或更少的开销(在 T 树上)，具体取决于键的大小。事实上，这接近于 AVL 树中预期的开销，假设没有父指针，节点中嵌入记录，记录中嵌入键。这是阻止我们使用 B 树的预期效率增益吗？
T 树通常在 AVL 树之上实现。 AVL 树比 B 树更平衡。这可以和T-trees的应用联系起来吗？
最佳答案
我可以给你一个个人故事，它涵盖了一半的答案，那就是，为什么我在 18 年前写了一些 Pascal 代码来编程 B+ trees。
我的目标系统是一台带有两个磁盘驱动器的 PC，我必须在非 volatile 内存上存储一个索引，我想更好地了解我在大学学习的内容。我对一个商业包的性能很不满意，可能是 DBase III，或者一些 Fox 产品，我不记得了。
无论如何:我需要这些操作:
B+-trees 让那台慢速的小 PC 真的在数据上飞起来了!
叶子有两个额外的指针，因此它们形成了一个双向链表，用于顺序搜索。
关于data-structures - T-trees 与 B+/-trees 相比有哪些优势？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4837460/