爲什麼Redis SortedSet使用Skip List而不是平衡樹？

Question

Redis的文件如下所述：

ZSETs是使用兩個數據結構來保持相同的元件 爲了獲得有序集O（日誌（N））插入和移除操作成排序 數據結構。

將元素添加到散列表，將Redis對象映射到 得分。同時，這些元素被添加到跳過列表中 將分數映射到Redis對象（因此對象按 這個「視圖」中的分數排序）。

我不太明白，有人能給我詳細的解釋嗎？有人能給我一個詳細的解釋嗎？

Answer 1

首先，我想我瞭解了Redis文檔所說的內容。 Redis有序集通過用戶指定的元素分數維護元素的順序。但是當用戶使用一些redis Zset API時，它只會給出元素參數。例如：

ZREM key member [member ...] 
ZINCRBY key increment member 
... 

的Redis需要知道的是這個成員（元素）什麼樣的價值，因此它使用哈希表保持的映射，就像文件中稱：

的元素添加到一個將Redis對象映射到 得分的散列表。

當它接收到一個成員時，它通過散列表查找它的值，然後操縱跳過列表上的操作來維護set的順序。 redis使用兩種數據結構來保持雙映射以滿足不同api的需要。

我讀威廉·普格論文跳躍表：一個概率 替代平衡樹，發現跳躍列表是非常優雅，而且更容易比旋轉來實現。

另外我認爲一般的二進制平衡樹能夠以相同的時間成本完成這項工作。如果有什麼我錯過了，請指出。

Answer 2

Antirez說，看到https://news.ycombinator.com/item?id=1171423
有幾個方面的原因：
1）他們不是非常佔用大量內存。基本上取決於你。關於節點具有給定數量級別的可能性的參數改變將比b樹減少內存密集度。
2）排序後的集合通常是許多ZRANGE或ZREVRANGE操作的目標，即將跳過列表作爲鏈表進行遍歷。通過這個操作，跳過列表的緩存位置至少和其他類型的平衡樹一樣好。
3）它們更容易實現，調試等等。例如，由於跳過列表的簡單性，我收到了一個補丁（已經在Redis master中），其中增加了在O（log（N））中實現ZRANK的跳過列表。它只需要對代碼進行很少的更改。
關於只追加耐久性&速度，我認爲以更多的代碼和更復雜的代價優化Redis並不是一個好主意，對於一個用例來說，恕我直言對於Redis目標應該是罕見的（fsync（）命令）。即使使用ACID SQL數據庫，幾乎沒有人使用這個功能，因爲無論如何性能提示很大。
關於主題：我們的經驗表明，Redis主要是I/O綁定。我正在使用線程來從虛擬內存中提供服務。假設您的鏈接速度如此之快以至於您可以飽和單個內核，那麼利用所有內核的長期解決方案就是運行多個Redis實例（無鎖，幾乎完全可線性擴展內核數量），並使用「Redis集羣「我打算在未來發展的解決方案。