优化树形数据结构

本文关键字:数据结构 优化 | 更新日期: 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可以非常强大和快速。