爲什麼跳過列表內存局部性很差，但平衡樹很好？

Question

一個傢伙一次挑戰antirez（Redis的作者）爲什麼Redis的使用跳躍列表的實施已排序集合在ycombinator：

我昨天看的Redis和注意到了這一點。是否有任何 你選擇跳過列表而不是btrees的特殊原因，除了 簡單？跳過列表在指針中消耗更多內存，並且由於內存不足導致 通常比btrees慢因此 遍歷它們意味着很多緩存未命中。我還建議了一種 提高吞吐量，當你能保證每個命令的耐久性（在 wiki頁面的結尾）： http://code.google.com/p/redis/wiki/AppendOnlyFileHowto此外，有你 思考收納只讀流量的附加線程 的方式來利用至少有兩個核心高效共享同一個內存？

然後antirez回答：

有幾個方面的原因：1）他們不是非常佔用大量內存。它基本上是 。有關 節點具有給定數量級別的概率的參數更改會使內存數量比b樹數量少 。 2）有序集合通常是許多ZRANGE 或ZREVRANGE操作的目標，即將跳過列表作爲鏈接的 列表進行遍歷。通過此操作，跳過列表的緩存位置至少爲 ，與其他類型的平衡樹一樣好。 3）它們更容易實現，調試等等。例如，由於跳過列表 簡單，我收到一個補丁（已在Redis主控中），並在O（log（N））中增加了實現ZRANK的跳過列表 。它需要對代碼進行很少的更改 。關於僅添加耐久性&速度，我不認爲 這是一個好主意，以更多代碼和更多 優化Redis爲一個用例，恕我直言對於Redis 目標（fsync（）at每個命令）。即使在ACID SQL數據庫中，幾乎沒有人使用此功能 ，因爲無論如何，性能提示都很大。 關於主題：我們的經驗表明，Redis主要是I/O綁定。 我正在使用線程來從虛擬內存提供服務。假設你的鏈路如此之快以至於你可以使一個核心飽和，運行Redis的多個實例（無鎖，幾乎完全可線性地隨着核的數量而線性地運行），並且使用 長期的 解決方案來利用所有的核，並且使用 我計劃在未來發展的「Redis集羣」解決方案。

我仔細閱讀，但我不明白爲什麼跳過列表與內存不佳的地方？爲什麼平衡樹會導致良好的記憶地區？

---

在我看來，內存的地方就是將數據存儲在一個連續的內存中。我認爲當讀取地址爲x的數據時，CPU會將地址x+1中的數據加載到緩存中（基於幾年前C的一些實驗）。所以遍歷一個數組會導致高可能性緩存命中，我們可以說數組具有良好的內存局部性。

但是當涉及到跳過列表和平衡樹時，它們都不是數組，也不會連續存儲數據。所以我認爲他們的記憶區域都很差。那麼有誰能爲我解釋一下嗎？

Answer 1

也許這個傢伙意味着只有一個在跳躍列表鍵值節點（在默認情況下實現的情況下），並在B樹N鍵節點線性佈局。所以我們可以從節點加載一堆b-tree密鑰到緩存中。

你說：

都是不陣列和不連續存儲數據

，但我們做的。我們將數據連續存儲在b-tree 節點中。