T-树或B-树

Question

T-树或B-树

algorithmdata-structurestreeb-treein-memory-database

5

T-Tree算法在这篇论文中有描述。而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也使用了它。但我的结果并未显示出这一点。
如果有人知道原因或对此有任何评论，很高兴能听到他/她的意见。

- Ahmad 阿德

2

展示你的结果和测试方法。 - Filburt

或许这种老式的T-Tree并不高效。根据旧版T-Tree论文，我们无法百分之百确定T-Tree的效率。对于所有对我的问题持消极态度的人，我只是尽力按照论文中描述的方式实现T-Tree，并将其与B-Tree进行比较，发现了这些结果。我也亲自实现了B-Tree，因此我为T-Tree和B-Tree做出了同样的努力。 - Ahmad 阿德

2

三十年前的研究所使用的硬件具有非常不同的内存层次结构特征和CPU（当时没有多核心，更不用说不均匀的了），这些CPU很难饱和内存接口。 - greybeard

@greybeard，谢谢你的回答。 - Ahmad 阿德

Oracle Timesten现在默认使用B树，以防你还对此有疑问。 - Aru

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DarthGizka · Accepted Answer

T-Trees并不像AVL树或B树那样是基本的数据结构。它们只是平衡二叉树的一个修改版本，因此可能会在某些特定应用场景中提供良好的性能表现。

但是，在当今时代，由于其局部性差，T-Trees很可能会遭受严重的性能问题，无论是在期望的块/页传输次数方面还是在缓存局部性方面。后者很明显，因为在搜索中除了最后一个节点访问之外，只有边界值会与搜索键进行比较 - 其余所有内容都被分页或缓存却未被使用。

相比之下，B-Trees通常具有出色的访问局部性，尤其是B+Trees（更不用说专门针对内存性能特征设计的缓存无关和缓存感知版本）。

类似的问题也存在于重新平衡上。在B-Tree领域中，已经开发和完善了许多变体，从B+到Blink，以实现所需的摊销性能特征，包括并发性（锁定/挂起）或其缺失。因此，大多数情况下，您可以简单地找到适合您性能配置文件的B-Tree变体，或使用简单的经典B+Tree并确保获得良好的结果。

总体而言，与可比较的B-Tree相比，T-Trees更复杂，并且似乎没有什么可以提供的性能表现。因为单层内存“层次结构”的商用硬件时代已经过去了几十年。硬盘是新的内存，反之亦然，主内存现在是新的硬盘。即使没有NUMA，从主内存将数据带入缓存层次结构的成本也很高，因此有必要将页面传输最小化 - 这正是B-Tree及其变体所做的，而T-Tree则不行。接近处理器核心时，缓存线访问/传输的数量很重要，但情况仍然如此。

实际上，如果您采用二分查找的思想 - 这是可以证明的最优方法 - 并考虑如何安排搜索键以与内存层次结构（缓存）协调，则您将不可避免地得到一个看起来非常像B-Tree的东西...

如果您为性能编写程序，那么您会发现获胜者几乎总是位于排序数组、B-Tree和哈希之间的某个三角形区域。即使平衡的二叉树只有在其他考虑因素占据主导地位并且键计数相对较小，即不超过几百万时才具有竞争力。