T 树或 B 树

Question

本文描述了T树算法 ，T*树是T树的改进，可以更好地利用查询操作，包括范围查询，并且包含T树的所有其他良好特性。
该算法在论文“T*-tree: A Main Memory Database Index Structure for Real-Time applications”中进行了描述。
根据这篇研究论文，当数据集适合内存时，T 树比 B 树/B+树更快。我按照这些论文中的描述实现了 T-Tree/T*Tree，并将性能与 B-tree/B+tree 进行了比较，但 B-tree/B+tree 在所有测试用例中都比 T-Tree/T*Tree 表现更好（插入、删除、搜索）。
我读到 T-Tree 是一种高效的内存数据库索引结构，Oracle TimesTen 使用它。但我的结果并没有表明这一点。
如果有人知道原因或对此有任何评论，很高兴收到她（或他）的来信。

Answer 1

T 树不是 AVL 树或 B 树那样的基本数据结构。它们只是平衡二叉树的破解版本，因此可能存在也可能不存在它们提供良好性能的利基应用程序。

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

将此与一般 B 树和特别是 B+ 树的出色访问局部性进行比较（更不用说显式设计时考虑到内存性能特征的缓存忽略和缓存感知版本）。

再平衡也存在类似的问题。在 B 树世界中，从 B+ 和 Blink 开始，已经开发和完善了许多变体，以便实现所需的摊销性能特征，包括并发（锁定/闩锁）或缺乏并发等方面。因此，大多数时候，您只需出去寻找适合您的性能配置文件的 B 树变体 - 或使用简单的经典 B+ 树并确保获得不错的结果。

T 树比类似的 B 树更复杂，并且考虑到具有单级内存“层次结构”的商品硬件的时代已经过去几十年了，它们似乎在一般性能方面没有提供任何帮助。不仅硬盘是新的内存，反之亦然，主内存现在也是新的硬盘。即，即使没有 NUMA，将数据从主内存带入缓存层次结构的成本也非常高，因此需要尽量减少页面传输 - 这正是 B 树及其变体所做的事情，而 T 树则不然。靠近处理器核心的是缓存行访问/传输的数量，但情况保持不变。

事实上，如果您采用二分搜索的想法（这被证明是最佳的）并考虑以与内存层次结构（缓存）良好配合的方式排列搜索键的方法，那么您最终总是会得到看起来不可思议的东西B树...

如果您针对性能进行编程，那么您会发现获胜者几乎总是位于排序数组、B 树和散列之间的三角形中的某个位置。即使是平衡二叉树，也只有在考虑其他因素时其相对较差的性能退居二线并且键数相当小（即不超过几百万）时才具有竞争力。