低內存使用率的自平衡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每個項目。

在我的應用程序需要一）極快的查找，B）非常快的插入和C）低內存佔用。

問題：是否有可能減少自平衡AVL樹數據結構的內存使用量？

Answer 1

我有類似的項目，我做了類似的aesearch給你。

我的答案是基於純技術方面的，不是AVL算法。

您可以嘗試打包結構/類。鄙視每個人都說的話，這不會損害x86機器的性能。

編輯：
你一定需要刪除父指針。而不是頂層節點，將所有東西都包裹在主類中。

然後你可能會收拾2個字節的餘額，但它會減少樹的整體大小。

然後在某些時候，您可能會發現標準（linux）malloc會分配很多額外的空間。這可以通過jemalloc修復。但是，jemalloc性能比標準malloc慢。

如果你願意，你可以試試谷歌的tcmalloc。它的性能比標準malloc高，而mem的使用在標準malloc和bjemalloc之間。但tcmalloc被認爲是beta或不穩定。

我也會建議如果可以，將數據直接存儲在樹節點中，例如不要使用指針。這將節省8個字節和一個額外的分配。

作爲最後一個節點，請檢查std :: map和std :: set - 那些是紅黑色的樹，工作得非常好。

請檢查跳過列表。我將在稍後爲我的實施添加評論。我的跳過列表的性能類似於std :: map（比較慢，我不能很好地比較），但內存使用率更好20-30％。