跳躍表

跳躍表

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

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

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

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

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

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ù)都保存在一個(gè)跳躍表里面， 其中每個(gè)跳躍表節(jié)點(diǎn)（node）都保存了一款水果的價(jià)錢信息， 所有水果按價(jià)錢的高低從低到高在跳躍表里面排序：

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

諸如此類。

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

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

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