优化树形数据结构

本文关键字：数据结构 优化 | 更新日期: 2023-09-27 18:33:05

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

//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来存储整个树。第二个条件是快速删除、浏览和插入操作 - 它们不应该比我上面写的数据结构花费更多的时间。我不能制定更严格的标准

优化树形数据结构

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

如果这是一个搜索，并且如果这通常是第一个操作(即你找到一个有值的节点，然后你对它做了一些事情(，那么你可以考虑使用红/黑树。此结构需要 log n 时间来搜索、插入和删除。在插入和删除期间施加的规则使树针对搜索进行了优化。

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

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

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

自从我直接使用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可以非常强大和快速。

相关文章：