跳躍表簡介

　　跳躍表（skiplist）是一個有序的數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點維護不同層次指向后續(xù)節(jié)點的指針，以達到快速訪問指定節(jié)點的目的。跳躍表在查找指定節(jié)點時，平均時間復(fù)雜度為，最壞時間復(fù)雜度為O(N)。

　　Redis使用跳躍表（skiplist）作為有序集合（zset）的底層實現(xiàn)之一。當(dāng)有序集合的元素個數(shù)大于等于zset-max-ziplist-entries（默認(rèn)為128個），或者每個元素成員的長度大于等于zset-max-ziplist-value（默認(rèn)為64字節(jié)）的時候，使用跳躍表和哈希表作為有序集合的內(nèi)部實現(xiàn)。

　　舉個例子，我們使用zadd命令創(chuàng)建一個以跳躍表為實現(xiàn)的有序集合：

　　127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long

　　(integer) 1

　　127.0.0.1:6379> zrange one-more-zset 0 -1

　　1) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"

　　127.0.0.1:6379> object encoding one-more-zset

　　"skiplist"

　　跳躍表的實現(xiàn)

　　在Redis中的跳躍表是由zskiplist結(jié)構(gòu)表示的，zskiplist結(jié)構(gòu)包含由多個跳躍表節(jié)點組成的雙向鏈表，每一個跳躍表節(jié)點都保存著元素成員和對應(yīng)的分鐘。下面我們一個一個地詳細(xì)了解一下。

　　zskiplist結(jié)構(gòu)

　　跳躍表是由zskiplist結(jié)構(gòu)表示的，它包含以下幾個屬性：

　　header屬性: 指向頭部跳躍表節(jié)點的指針。

　　tail屬性：指向尾部跳躍表節(jié)點的指針。

　　level屬性：表示跳躍表中層數(shù)最大的節(jié)點的層數(shù)，表頭節(jié)點的層數(shù)不計算在內(nèi)。

　　length屬性：表示跳躍表中的節(jié)點總數(shù)。

　　跳躍表節(jié)點的結(jié)構(gòu)

　　跳躍表節(jié)點使用zskiplistNode結(jié)構(gòu)表示，它包含以下幾個屬性：

　　level屬性：表示層的數(shù)組，數(shù)組中每個項使用zskiplistLevel結(jié)構(gòu)表示，它包含以下兩個屬性：

　　forward屬性：指向位于表尾方向其他節(jié)點的指針。

　　span屬性：當(dāng)前節(jié)點到forward指向的節(jié)點跨越了多少個節(jié)點。

　　backward屬性：指向當(dāng)前節(jié)點的前一個節(jié)點的指針。

　　obj屬性：指向元素成員的指針。

　　score屬性：當(dāng)前元素成員對應(yīng)的分?jǐn)?shù)。

　　圖解跳躍表

　　說了這么多，都比較抽象不容易理解，我們來舉個例子：

　　這就是一個跳躍表的內(nèi)部結(jié)構(gòu)，其中有4個元素，鍵分別是：萬、貓、學(xué)、社。

　　為什么不使用平衡樹？

　　跳躍表以有序的方式在層次化的鏈表中保存元素， 在大多數(shù)情況下，跳躍表的效率可以和平衡樹媲美，查找、刪除、添加等操作都可以在對數(shù)期望時間下完成， 并且比起平衡樹來說， 跳躍表的實現(xiàn)要簡單直觀得多。所以在Redis中沒有使用平衡樹，而是使用了跳躍表。