Red-Black与2-3-4树的真实性能，特别是考虑到缓存性能？

Question

2-3-4树的单个节点可以由8个指针构成:指向最多四个子节点的指针、指向最多3个包含关键字的实际记录的指针，这些关键字将匹配搜索关键字或将确定递归到4个子节点中的哪一个，以及父节点指针。

今天的普通硬件有8字节的指针，给出了一个64字节的节点。此外，现代CPU具有64字节的缓存线。如果节点与缓存线对齐，那么每个节点只需要一次缓存线命中:在引用七个指针中的第一个指针之后，所有其他指针都将在L1缓存中。

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

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

对此有什么共识或研究吗？

Answer 1

您的推理当然是正确的--对于冷查找，2-3-4树的性能会更好，因为它命中的缓存线更少。

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

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

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