5分鐘了解Redis的内部實作跳躍表（skiplist）

跳躍表簡介

跳躍表（skiplist）是一個有序的資料結構，它通過在每個節點維護不同層次指向後續節點的指針，以達到快速通路指定節點的目的。跳躍表在查找指定節點時，平均時間複雜度為，最壞時間複雜度為O(N)。

Redis使用跳躍表（skiplist）作為有序集合（zset）的底層實作之一。當有序集合的元素個數大于等于

zset-max-ziplist-entries

（預設為128個），或者每個元素成員的長度大于等于

zset-max-ziplist-value

（預設為64位元組）的時候，使用跳躍表和哈希表作為有序集合的内部實作。

舉個例子，我們使用

zadd

指令建立一個以跳躍表為實作的有序集合：

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"
           

複制

跳躍表的實作

在Redis中的跳躍表是由

zskiplist

結構表示的，

zskiplist

結構包含由多個跳躍表節點組成的雙向連結清單，每一個跳躍表節點都儲存着元素成員和對應的分鐘。下面我們一個一個地詳細了解一下。

zskiplist結構

跳躍表是由

zskiplist

結構表示的，它包含以下幾個屬性：

• header

  屬性: 指向頭部跳躍表節點的指針。

• tail

  屬性：指向尾部跳躍表節點的指針。

• level

  屬性：表示跳躍表中層數最大的節點的層數，表頭節點的層數不計算在内。

• length

  屬性：表示跳躍表中的節點總數。

跳躍表節點的結構

跳躍表節點使用

zskiplistNode

結構表示，它包含以下幾個屬性：

• level

  屬性：表示層的數組，數組中每個項使用

  zskiplistLevel

  結構表示，它包含以下兩個屬性：

  • forward

    屬性：指向位于表尾方向其他節點的指針。

  • span

    屬性：目前節點到

    forward

    指向的節點跨越了多少個節點。

• backward

  屬性：指向目前節點的前一個節點的指針。

• obj

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

• score

  屬性：目前元素成員對應的分數。

圖解跳躍表

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

這就是一個跳躍表的内部結構，其中有4個元素，鍵分别是：萬、貓、學、社。

為什麼不使用平衡樹？

跳躍表以有序的方式在階層化的連結清單中儲存元素， 在大多數情況下，跳躍表的效率可以和平衡樹媲美，查找、删除、添加等操作都可以在對數期望時間下完成， 并且比起平衡樹來說， 跳躍表的實作要簡單直覺得多。是以在Redis中沒有使用平衡樹，而是使用了跳躍表。