2

2-3-4 树的单个节点可以用 8 个指针构造：指向最多四个子节点的指针，指向最多 3 个实际记录的指针，这些记录包含与搜索键匹配或将确定 4 个子节点中的哪一个的键递归到，和一个父节点指针。

今天常见的硬件有 8 字节的指针，给出一个 64 字节的节点。此外，现代 CPU 具有 64 字节的高速缓存行。如果节点与缓存线对齐，那么每个节点只需要一个缓存线命中：在引用七个指针中的第一个之后，其余的都将在您的 L1 缓存中。

虽然红黑树实现起来要简单得多，而且小代码应该是快速代码，但树中的每一级下降都有 L1 缓存未命中的风险。对于 1023 个对象，2-3-4 树需要 5 个节点的最坏情况才能加载到缓存中。完美平衡的二叉树需要 10，但由于不平衡，红黑可能需要更多（不确定最坏的情况：20？）

简单地敲击一个数据结构的小型测试工具可能会将其全部保存在缓存中，因此可能会报告红黑树与 2-3-4 的性能相似。但我有一种感觉，一个复杂的现实世界的应用程序可能会看到更少的挂钟时间和更低的延迟与 2-3-4 树。

对此是否有任何共识或研究？

4

1 回答 1

0

您的推理当然是正确的——对于冷查找，2-3-4 树会表现得更好，因为它击中的缓存行更少。

但是，如果树的性能很重要，那通常意味着您经常使用它。

如果树经常被使用并且它并不是几乎全部在缓存中，那么它一定很大。当经常使用大树时，通常会缓存更高级别的节点，因为每个级别的平均命中率是低于级别的两倍。

因此，真正重要的性能改进仅限于树中最深的几个级别。您仍然可以看到使用 2-3-4 树的性能，但这不是失控，我认为您需要一个特殊的理由来判断它是否值得额外的代码复杂性（尤其是在搜索和迭代中）。

于 2019-06-01T12:56:29.777 回答