0

我有一棵树，它有很多节点（数百万+），需要加载到内存中。因此，我需要最有效的方式将节点及其关系存储在内存中。最好的数据结构是什么？到目前为止，我有两个选择：

//more obvious but the less efficient
class TreeNode
{
 Node parent;
 TreeNode[] children;

 //additional fields
 byte X;
 byte Y;
 byte marker;
 string comment;
}

//more efficient
class TreeNode
{
 TreeNode next; //reference to the next child of parent node,
                //if isLast=true - reference to parent node

 TreeNode firstChild; //reference to the first child of this node

 bool isLast; //true, if this node is the last parents child

 //additional fields
 byte X;
 byte Y;
 byte marker;
 string comment;
}

请注意，我需要在这棵树上执行诸如浏览、删除和插入之类的操作，并且我需要这些操作足够快。

编辑：这种情况下的最佳选择是使用更少的 RAM 来存储整个树。第二个标准是快速删除、浏览和插入操作——它们不应该比我在上面写的数据结构中花费更多的时间。我不能更严格地制定这个标准

4

2 回答 2

0

听起来您有一组变异的内存数据。如果是这样，那么了解哪些操作是常见的将非常重要。例如，当您提到“浏览”时，它是搜索，还是从您当前正在查看的节点到父节点或子节点的简单遍历？

如果是搜索，并且这通常是第一个操作（即您找到一个具有值的节点，然后对它执行某些操作），那么您可能会考虑使用Red/Black Tree。此结构需要 log n 时间进行搜索、插入和删除。在插入和删除期间施加的规则使树为搜索而优化。

如果搜索速度不重要，那么您可以使用更简单的树结构来加快插入和删除速度。

就您的空间而言，红/黑树，就像几乎所有其他树结构一样，占用 n 个空间。这与您可以为结构本身做的一样好。不过，请振作起来，因为您可以采取创造性的措施。

例如，您在每个节点中存储 3 个字节和一个字符串。您是否可以仅将这些数据的一个子集存储在内存中，并根据需要从持久存储（例如数据库）中查找其余数据？对于标准的树操作来说，它必须是不必要的数据，但也许它是可行的。或者，是否可以在内存中压缩字符串数据？

于 2013-09-28T19:18:57.427 回答
0

自从我直接使用 C++ 类型的结构以来已经有一段时间了，但是当我这样做时，我正在使用btree结构。前提是相似的，但是在单个节点上，您可以说...每个级别有 8 个（或更多）键。但是，如果您要处理数百万个条目，可能需要研究一下吗？

前提是在顶级节点你有 8 个键......并且为了简单地理解一棵 90k 条目的树，顶级节点是 10k、20k、30k...80k。因此，如果您要查找的数字小于 10k，则它会下降... 少于 20k 会下降它的腿，等等。因此，通过在单个节点级别测试一些可用的元素，您基本上可以扔掉其他80k。

因此，例如，您正在寻找 26,895。它从顶部节点开始并获得您想要的 30k（小于 30k，但大于 20k）。现在加载下一个节点。但是这个节点跨越 20,001 到 29,999。对于咧嘴笑，它的关键休息时间是 21250、22500、23750、2500、26250、27500、28750、29999。（每个休息时间为 1250）。所以现在你达到了你低于的 27500 点，它又进了一层。这个水平现在跨越了你的 26250 到 27499 的差距，你只是第二个水平。

您显然需要一本书或更强大的参考才能完成，但 btree 可以非常强大和快速。

于 2013-09-28T19:46:49.390 回答