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

Question

根据多个来源，包括Wikipedia，实现二叉树的两种最常用方法是：

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

第二种方法在内存使用和局部性方面显然更优。但是，如果您想以可能使树不平衡的方式允许从树中进行插入和删除，则可能会导致问题。这是因为该设计的内存使用量是树深度的指数函数。

假设您想支持此类插入和删除。如何实现树，使得树遍历能够充分利用CPU缓存。

我在考虑为节点制作对象池，并将它们分配到一个数组中。这样，节点将靠在一起 -> 因此具有良好的局部性。

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

如果您的L1行大小为64字节，并且您访问std::vector<std::uint8_t>(64) 的第一个成员，则可能将向量的整个内容放入L1缓存中。这意味着您可以非常快地访问任何元素。但是，如果元素的大小与缓存行大小相同怎么办？由于对于L1、L2和L3缓存，缓存行很可能并没有太大的差异，因此似乎没有办法在这里利用引用局部性。我错了吗？还有什么其他办法吗？

- Martin Drozdik

---

第二个在几乎任何方面都明显优于第一个。除了缓存的问题，还有什么原因吗？ - user2100815

@NeilButterworth 那是我写的一件傻事。我尝试将其更加精确化。如果你有其他建议，请随意编辑。 - Martin Drozdik

也许使用std::deque而不是std::vector（或数组）更好。"典型的实现使用一系列单独分配的固定大小数组。"请参阅http://en.cppreference.com/w/cpp/container/deque，并且还要查看std::vector的性能（将尝试找到此参考资料）-使用std::vector与std::list进行随机插入/删除，当元素数量达到100,000个（左右）时，vector表现更佳。 - Richard Critten

从演示的大约46分钟处发现了《现代C++：你需要知道的一切-赫伯特·萨特》。 - Richard Critten

Answer 1

除非你正在研究如何改进二叉树以实现缓存访问模式，否则我认为这是一个XY问题 - 你试图解决的问题是什么？为什么你认为二叉树是最好的算法来解决你的问题？期望的工作集大小是多少？

如果你正在寻找通用的关联式存储，有多种缓存友好（其他关键字：“缓存高效”，“缓存无情”）的算法，例如Judy数组，其中有一个详细的说明PDF。

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

最终，要找出对你的用例最好的方法是尝试和测量不同的方法。

- Michal Kottman

Answer 2

使用块分配器。

您有一个或者多个连续的内存“池”，从中分配固定大小的块。它实现为链表。因此，分配就是

answer = head, 
head = head->next, 
return answer; 

释放其实很简单。

tofree->next = head;
head = tofree;

如果您允许使用多个池，那么您需要编写代码来确定池，这会增加一些复杂性，但并不多。它本质上是一个简单的内存分配系统。 由于所有池成员在内存中靠得很近，因此对于小树，您可以获得良好的缓存一致性。对于大树，您需要更聪明一些。

- Malcolm McLean