7

我刚刚发现有一些基于树的数据结构，在寻求高性能时，通常会存储为连续的内存块，这在使用所谓的“基于策略的数据结构”时特别受欢迎。

问题是我无法理解为什么要这样做。当您尝试“线性化”一棵树以将其存储为向量/数组时，如何确保以有意义的方式重新排列分支和叶子以提高性能？这仅适用于完美平衡的树木吗？

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

4

6 回答 6

7

您可能会发现这里的短文很有趣

基本上，为这种结构使用连续内存块的原因是，在处理潜在的大型数据集时，它极大地改善了查找和扫描时间。如果你的内存是不连续的，你可能不得不使用昂贵的遍历算法来从数据结构中检索数据。

希望这能解决您的兴趣。

以下是文章中的两张图片，它们说明了这个概念：

平衡的树

平衡的树

存储在连续内存中的树：

在此处输入图像描述

于 2014-06-13T17:48:59.577 回答
6

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

一个非常简单的版本是简单地分配三个块，一个父块和两个子块，这个块有四个“子”块，每个子块两个。这将您的分配减少了三分之一。这不是什么优化，直到你扩大它，分配 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]
于 2014-06-13T18:15:00.700 回答
4

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

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

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

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

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

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

于 2014-06-13T17:36:14.857 回答
2

您如何确保以有意义的方式重新排列树枝和树叶以提高性能？

如果您的程序已经在运行（使用不连续的树），您总是可以只检测您的程序以报告其实际节点访问模式通常是什么样的。一旦您对节点的访问方式有了很好的了解，您就可以自定义节点分配器，以相同的顺序在内存中分配节点。

于 2014-06-13T17:37:01.880 回答
1

区分树和AVL 树很重要。在您的问题中，您谈到了平衡树，所以您的问题可能是关于数组中的 AVL 树表示。

所有其他答案都是关于树而不是 AVL 树。据我所知，这种树可以用数组表示，但不能有效地更新，因为您必须重新排列数组的许多元素而不是使用内存指针。

这意味着只要输入元素已经排序，您就可以在数组中表示完美有序的平衡树。这棵树将比通常的内存树更快，但更新它会“更难”。

我的结论是：

  • 具有大量访问权限的只读树 => 在数组中
  • 具有大量更改的可更新树 => 在内存中
于 2014-06-13T19:20:15.910 回答
1

“ ...尝试将树“线性化”以将其存储为向量/数组，如何确保以有意义的方式重新排列分支和叶子以提高性能...”

我相信你想太多了。

在普通树中，您使用“new”请求创建节点的可用空间。

您使用 delete 将不再需要的空间返回到堆中。

然后使用指针连接节点。

对于“向量中的树”，您可以简单地重新实现 new 和 delete 以在向量中查找空间。

我认为您使用索引（指向父节点、左节点或右节点）而不是指针（指向父节点、左节点或右节点）。

我相信向量中第 n 个项目的索引（在重新分配增长之前和之后）没有变化。

另一个挑战是删除一个节点......但这可以像任何大于被删除节点的节点（或索引）减少 1 一样简单。

对于很少变化但必须尽快捕获的树，这些选择可能是公平的交易。

存储你的树真的需要向量块保存的性能吗？矢量块保存实际上是否比同一棵树的深度优先保存更快。你真的需要测量。

于 2014-06-13T18:08:11.563 回答