如何实现缓存友好的动态二叉树？

Question

根据包括Wikipedia在内的一些资料，实现二叉树的两种最常用的方法是：

1. 每个节点明确拥有其子节点的节点和指针（或引用）。
2. 子节点的位置由其父节点的索引隐式给出的数组。

第二个显然在内存使用和引用的位置方面优越。但是，如果您希望以某种可能使树不平衡的方式从树中插入和移除，可能会导致问题。这是因为此设计的内存使用量是树深度的指数函数。

假设您要支持此类插入和删除。如何实现树，以便树遍历可以充分利用CPU缓存。

我正在考虑为节点创建对象池并将它们分配到数组中。这样，节点将彼此靠近->因此具有良好的参考位置。

但是，如果节点的大小与缓存行的大小相同，这有意义吗？

如果您的L1行大小为64字节，并且访问的第一个成员std::vector<std::uint8_t>(64)，则可能会在L1缓存中包含向量的全部内容。这意味着您可以非常快速地访问任何元素。但是，如果元素的大小与缓存行的大小相同怎么办？由于L1，L2和L3高速缓存的高速缓存行可能不会有很大差异，因此，似乎没有办法在此提供参考位置的帮助。我错了吗？还有什么可以做的？

Answer 1

除非您正在研究如何改进缓存访问模式的二叉树，否则我觉得这是一个XY 问题- 您要解决的问题是什么？为什么您认为二叉树是解决您问题的最佳算法？预期的工作集大小是多少？

如果您正在寻找一种通用的关联存储，则有多种缓存友好（其他关键字：“缓存高效”、“缓存遗忘”）算法，例如Judy arrays，对此有广泛的解释 PDF。

如果您的工作集大小足够小，并且您只需要有序的项目集，那么简单的有序数组可能就足够了，这可能会带来另一个性能优势 -分支预测。

最后，要找出最适合您的用例的方法是尝试衡量不同的方法。