缓存感知树插入

Question

我有一棵树，每个节点都可能有0到N个子节点。

​

用例是以下查询：给出了指向两个节点的指针:这些节点是否在树的同一分支中？

示例

q(2,7) => true
q(5,4) => false

按书(慢)

直接实现是在每个节点存储指向父节点的指针和指向子节点列表的指针。但是这会导致糟糕的性能，因为树在内存中是支离破碎的，因此无法感知缓存。

问题

以紧凑的形式表示树的好方法是什么？整棵树大约有10万个节点。因此，应该有可能找到一种方法，使它完全适合CPU-缓存。

例如，二进制树通常是隐式表示为数组，因此非常适合完全存储在CPU-cache中(如果足够小的话)。

Answer 1

您可以预先分配一个连续的内存块，在其中连接所有节点的信息。

之后，每个节点只需要一种方法来检索其信息的开头以及该信息的长度。

在这种情况下，每个节点的信息可以由父节点表示，然后是子节点列表(假设在没有父节点(即根)的情况下使用-1 )。

例如，对于在问题中发布的树，节点1的信息应该是：-1 2 3 4，节点2的信息是：1 5，等等。

通过连接这些数组来获得连续数组，结果如下所示：

-1 2 3 4 1 5 1 9 10 1 11 12 13 14 2 3 5 5 5 3 3 4 4 4 15 4

每个节点将使用一些元数据来检索其相关信息。如前所述，这个元数据需要由一个startIndex和length组成。例如，对于节点3，我们有startIndex = 6，length = 3，它允许检索1 9 10子数组，这表明父节点是节点1，其子节点是节点9和10。

此外，元数据信息还可以在开始时存储在相邻内存块中。元数据对于每个节点都有固定的长度(两个值)，因此我们可以很容易地获得特定节点的元数据位置，给出它的索引。

这样，有关图形的所有信息都将存储在一个连续的、对缓存友好的内存块中。