问T树或B树

EN

与AVL树或B树不同，t树不是基本的数据结构.他们只是平衡二叉树的一个黑客版本，因此，可能有或不可能有利基应用程序，他们提供体面的性能。

在这个时代，无论是在预期的块/页传输计数意义上，还是在缓存局部性意义上，它们都会因为其糟糕的位置而遭受严重的损失。后者是显而易见的，因为在搜索的所有节点访问中，除了最后一个节点访问之外，只有边界值将根据搜索键进行检查--其余的将被分页或缓存为0。

将其与一般的B树，特别是B+trees的出色访问局部性进行比较(更别提那些显式地使用内存性能特性设计的缓存遗忘和缓存意识版本)。

再平衡也存在类似的问题。在B树世界中，许多变体--从B+和Blink开始--已经被开发和完善，以实现期望的分期性能特性，包括并发性(锁/锁)或不存在这些特性。因此，大多数情况下，您可以简单地出去寻找适合您的性能配置文件的B树变体，或者使用简单的经典B+tree，并确保结果不错。

T树比类似的B树复杂得多，考虑到具有单一内存“层次”的商品硬件时代已经过去了几十年，它们似乎在性能方面没有什么可提供的。不仅硬盘是新内存，相反也是正确的，主存现在是新硬盘。也就是说，即使没有NUMA，将数据从主内存带到缓存层次结构中的成本也非常高，因此尽可能减少页面传输(这正是B-树及其变体所做的)和T-树的代价是非常高的。更接近处理器核心的是缓存线访问/传输的数量，但图片保持不变。

事实上，如果你接受二进制搜索的想法--这是最优的--并考虑如何以一种很好的方式来安排搜索键，那么你总会得到一些看起来像B树的奇怪的东西.

如果你为性能而编程，你会发现优胜者几乎总是位于排序数组、B树和散列之间的三角形中。即使是平衡的二叉树，也只有在其相对较差的性能在其他考虑因素面前处于次要地位，并且密钥计数相当小，即不超过几百万的情况下，才具有竞争力。