爲什麼在存儲分配器中使用循環鏈表而不是樹？

Question

存儲分配器如何使用循環鏈表來存儲分配/空閒地址而不是平衡樹？遍歷鏈表需要O（n）的複雜性順序，而平衡樹可以在O（logn）中遍歷，對嗎？背後有什麼優勢/推理？

Answer 1

前提（「存儲分配器用來存儲分配/釋放地址循環鏈表」）未必是真實的。對於某些分配器來說可能是這樣，但通常情況並非如此。

如果分配器使用鏈表狀結構來跟蹤內存塊，它通常嵌入在存儲塊本身的元數據 - 即。而不是作爲一個單獨的數據結構。

例如，存儲器的每個塊可以與狀態（空閒/分配），並且塊的尺寸開始。這種方法基本上實現了一個鏈表（使用大小，你可以很容易地確定下一個塊的起始地址），但是它還有鏈表不具有的其他屬性：你仍然可以找到一個特定的內存塊（節點）通過知道它的內存地址。

所以，你有一個O（1）訪問時間（因爲你，或者編譯器，知道的內存塊的內存地址）。合併相鄰的空閒塊也很簡單。如果需要運行某種去碎片或壓縮算法，可以使用類似鏈表的結構來完成。尋找一個足夠大小的空閒塊也可以使用類似鏈表的結構來完成（儘管有時第二個嵌入鏈表專門用於空閒塊，以最小化分配函數的開銷）。

當然，這只是解決問題的一種可能方法。但它表明，使用鏈表不一定是比其他數據結構更差的選擇。

Answer 2

嗯，分配器是經常特製的，非常認真，特別製作的，以他們預期的服務的特殊需求。

因此，有可能更復雜，在很多工業實力分配器發現少了規則的結構。

不過，假設你的問題的前提是準確的：

最壞的情況的複雜性是最相關的非常大的遍歷。大多數分配器的設計都是這樣，所需的遍歷通常很小，非常小，以至於維護平衡樹所需的額外開銷會使平均情況下的遍歷速度變慢。此外，工程師們更喜歡最簡單的解決方案，除非更復雜的解決方案明顯更好：循環鏈接列表只是簡單的。

Answer 3

遍歷鏈表需要複雜的O（n）的順序

是的，但存儲分配器的目的是提供一些分配的空間，而這並不一定需要「穿越」存儲以前分配的結構。例如，如果我們每次都在特定大小的塊中分配內存（所以我們在結構中保留了這種大小的塊），那麼我們只需要返回第一塊。一般來說，我們只需要找到一個足夠大的節點，所以我們看看，直到找到足夠大的節點（這通常會很快發生）。

而在O（logn）中可以遍歷一棵平衡樹，對不對？

，我們可以發現在O（LOGN）特定的元素，但在那個時候，我們不能「穿越」的樹，因爲根據定義的數據結構的「穿越」是指訪問每一個節點，且有是O（n）個節點。如果樹具有合適的搜索樹屬性，我們只能「在O（logn）中找到特定的元素，我們又想要哪個節點？這將使我們有效地找到，例如，足夠大的最小分配;但無論如何，這並不一定是我們想要回報的東西（因爲這種政策導致大量的小塊可能適用於或可能不適合未來分配，並且結構膨脹）See also。