为什么将树存储为连续的内存块？

Question

我刚刚发现有一些基于树的数据结构,当寻找高性能时,通常存储为连续的内存块,这在使用所谓的"基于策略的数据结构"时尤其流行.

问题是我无法理解为什么人们会这样做; 当您尝试"线性化"树以将其存储为向量/数组时,如何确保以有意义的方式重新排列分支和叶子以帮助提高性能？这只适用于完美平衡的树木吗？

换句话说,我无法想象用于访问跨越多个级别并具有多个叶子的线性数据结构的模式; 通常一棵树为每个节点/叶子添加1级间接,这为用户简化了很多事情,但是应该如何组织这样的"线性"树？

Answer 1

您可能会发现在短短的一篇文章在这里有趣

基本上,为这种结构使用连续内存块的原因是它在处理潜在的大型数据集时大大提高了查找和扫描时间.如果您的内存不连续,则可能必须使用昂贵的遍历算法从数据结构中检索数据.

希望这能满足您的兴趣.

以下是文章中描述这一概念的两个图像:

平衡的树

存储在连续内存中的树:

Answer 2

其实有很多这样的模式，它们有两个目的：节省内存和保持节点在一起，主要是为了分页性能。

一个非常简单的版本是简单地分配三个块，一个父节点和两个子节点，这个块有四个“子”块，每个子节点两个。这将您的分配减少了三分之一。这不是什么优化，直到你扩大它，7、15、31、63 的分配......如果你能得到它以便尽可能多的键适合单个内存系统页面，那么你最小化等待硬盘的时间。如果您的密钥每个是 32 字节，并且一页是 4K，那么您最多可以存储 125 个密钥，这意味着您只需从硬盘驱动器为树的每 7 行加载一页。此时，您加载“子”页面，然后再加载 7 行。一个普通的二叉树每页可能只有一个节点，这意味着你花在等待硬盘驱动器上的时间是迭代树的 7 倍。很慢。旋转有点棘手，因为您必须实际交换数据，而不是树实现中常见的指针。此外，当树变大时，使用大量空间也是一种浪费。

               ---------
               |   O   |
               |  / \  |
               | O   O |
              _---------_
           __/    \ /    \__
          /       | |       \
--------- --------- --------- ---------
|   O   | |   O   | |   O   | |   O   |
|  / \  | |  / \  | |  / \  | |  / \  |
| O   O | | O   O | | O   O | | O   O |
--------- --------- --------- ---------

另一种更复杂的“模式”是将树垂直切成两半，因此顶部是一个“子树”，它有许多子“子树”，并将每个“子树”线性存储。你递归地重复这个。这是一个非常奇怪的模式，但最终的工作方式与上述模式大致相似，除了它是“缓存遗忘”，这意味着它适用于任何页面大小或缓存层次结构。很酷，但它们很复杂，而且几乎所有东西都运行在三个众所周知的架构之一上，所以它们并不流行。它们也极难插入/移除

另一个非常简单的变体是将整个树放入一个通过 indecies 访问的数组中，这样可以节省总内存，但只有顶部是缓存友好的，较低级别的缓存比常规二叉树更糟糕。实际上，根在索引 i=0 处，左孩子在 ( n*2+1 = 1)，右孩子在 (n*2+2 = 2 ) 处。如果我们在索引 24 处的节点，它的父节点是 ((n-1)/2 = 12)，它的左孩子和右孩子分别是 49 和 50。这对于小树非常有效，因为它不需要任何指针开销，数据存储为连续的值数组，并且通过索引推断关系。此外，添加和删除子节点总是发生在右端附近，并且适用正常的二叉树插入/旋转/擦除。这些还有一个有趣的数学新颖性，如果将索引加一转换为二进制，则对应于树中的位置。如果我们考虑索引 24 处的节点，二进制中的 24+1 是 11001 -> 第一个 1 总是表示根，从那里每个 1 表示“向右走”，每个 0 表示“向左走”，这意味着要从根目录向右、向左、向左、向右移动，到达索引 24，然后就到了。此外，因为有 5 个二进制数字，所以你知道它在第五行。这些观察都不是特别有用，除了它们在某种程度上暗示根节点是右孩子，这有点有趣。（如果扩展到其他基，则根始终是最右边的子基）。话虽如此，如果您使用双向迭代器，将根实现为左节点通常仍然很有用。

     0
    / \
   /   \
  1     2
 / \   / \
3   4 5   6

[0][1][2][3][4][5][6]

Answer 3

在连续内存中存储数据结构是一种用于内存受限系统（例如嵌入式系统）的技术。该技术还可用于安全和性能关键系统。

桌面系统通常具有大量内存，并且其应用程序的生命周期很短。它们动态内存分配的过程是在内存池中找到下一个可用块并将其返回。如果没有可用内存（例如存在碎片），则分配失败。无法控制可以消耗多少内存。

通过采用连续分配方法，可以限制或限制创建的节点数量。这意味着在具有 32k 内存的系统中，树不会耗尽所有内存并留下漏洞。

使用连续系统，分配过程会更快。你知道区块在哪里。此外，可以存储索引值，而不是存储链接的指针。这还允许将树存储到文件中并轻松检索。

您可以通过创建节点数组或向量来对此进行建模。更改节点数据结构以使用数组索引而不是指针。

请记住，了解性能问题的唯一方法是进行分析。