低内存利用率的自平衡AVL树？

Question

一个自平衡的AVL树通常用一个列表来实现。每个节点包含：

pointer to parent (8 bytes on 64 bit apps)
pointer to left child (8 bytes on 64 bit apps)
pointer to right child (8 bytes on 64 bit apps)
balance (4 bytes)

pointer to the data struct (8 bytes on 64 bit apps)

由于数据是在内存中对齐的，所以每个项都需要40 bytes。

在我的应用程序中，我需要a)非常快的查找，b)非常快的插入和c)低内存使用率。

Q：是否有可能减少自平衡的AVL数据结构的内存使用量？

Answer 1

我有类似的项目，我做了类似的研究，你的。

我的回答是基于纯技术方面，不对AVL算法。

您可以尝试打包结构/类。不管大家怎么说，这不会影响x86机器上的性能。

编辑：

您肯定需要移除指向父级的指针。而不是顶级节点，而是将所有内容封装在一个主类中。

然后，您可能可以将余额打包成2个字节，但它将减少树的总体大小。

然后，您可能会发现标准(linux) malloc分配了大量额外的空间。这可以用jemalloc解决。但是，jemalloc性能比标准malloc慢。

如果你愿意，你可以试试谷歌的tcmalloc。其性能优于标准malloc，在标准malloc和andbjemalloc之间处于中间。然而，tcmalloc被认为是beta的或不稳定的。

我还会建议，如果可以的话，将数据直接存储在树节点中，例如不要使用指针。这将节省8个字节和一个额外的分配。

作为最后的节点，请检查std::map和std::set --这些是红色的黑树，工作得非常好。

请检查跳过列表。稍后，我将向我的实现添加评论。我的跳过列表具有类似于std::map的性能(稍微慢一点，我不能做很好的比较箱)，但是内存使用情况要好20-30%。