algorithm - T 树或 B 树

Question

T 树算法在 this paper 中有描述。T*-Tree 是 T-tree 的改进，可以更好地使用查询操作，包括范围查询，它包含 T-tree 的所有其他优点。
该算法在论文“T*-tree: A Main Memory Database Index Structure for Real-Time Applications”中有所描述。
根据这篇研究论文，当数据集适合内存时，T-Tree 比 B-tree/B+tree 更快。我按照这些论文中的描述实现了 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 树相同意义上的基本数据结构。它们只是平衡二叉树的黑客版本，因此可能存在也可能不存在它们提供良好性能的利基应用程序。

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

将其与一般 B 树和特别是 B+ 树的出色访问局部性进行比较(更不用说在设计时明确考虑了内存性能特征的无缓存和有缓存意识的版本)。

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

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

事实上，如果你采用二分搜索的想法——这已被证明是最优的——并考虑以一种与内存层次结构(缓存)很好地配合的方式排列搜索键的方式，那么你总是会得到看起来像这样的东西不可思议地像一棵 B 树......

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