跳躍表

跳躍表

跳躍表（skiplist）是一種有序數(shù)據(jù)結構， 它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針， 從而達到快速訪問節(jié)點的目的。

跳躍表支持平均 O(logN)、最壞 O(N) 復雜度的節(jié)點查找， 還可以通過順序性操作來批量處理節(jié)點。

在大部分情況下， 跳躍表的效率可以和平衡樹相媲美， 并且因為跳躍表的實現(xiàn)比平衡樹要來得更為簡單， 所以有不少程序都使用跳躍表來代替平衡樹。

Redis 使用跳躍表作為有序集合鍵的底層實現(xiàn)之一： 如果一個有序集合包含的元素數(shù)量比較多， 又或者有序集合中元素的成員（member）是比較長的字符串時， Redis 就會使用跳躍表來作為有序集合鍵的底層實現(xiàn)。

舉個例子， fruit-price 是一個有序集合鍵， 這個有序集合以水果名為成員， 水果價錢為分值， 保存了 130 款水果的價錢：

redis> ZRANGE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) "6.5"
5) "apple"
6) "8"

redis> ZCARD fruit-price
(integer) 130

fruit-price 有序集合的所有數(shù)據(jù)都保存在一個跳躍表里面， 其中每個跳躍表節(jié)點（node）都保存了一款水果的價錢信息， 所有水果按價錢的高低從低到高在跳躍表里面排序：

• 跳躍表的第一個元素的成員為 "banana" ， 它的分值為 5 ；
• 跳躍表的第二個元素的成員為 "cherry" ， 它的分值為 6.5 ；
• 跳躍表的第三個元素的成員為 "apple" ， 它的分值為 8 ；

諸如此類。

和鏈表、字典等數(shù)據(jù)結構被廣泛地應用在 Redis 內(nèi)部不同， Redis 只在兩個地方用到了跳躍表， 一個是實現(xiàn)有序集合鍵， 另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結構， 除此之外， 跳躍表在 Redis 里面沒有其他用途。

本章將對 Redis 中的跳躍表實現(xiàn)進行介紹， 并列出跳躍表的操作 API 。

本章不會對跳躍表的基本定義和基礎算法進行介紹， 如果有需要的話， 可以參考 William Pugh 關于跳躍表的論文 《Skip Lists: A Probabilistic Alternative to Balanced Trees》 ， 或者 《算法：C 語言實現(xiàn)（第 1 ～ 4 部分）》 一書的 13.5 節(jié)。