跳躍表簡介
跳躍表（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中沒有使用平衡樹，而是使用了跳躍表，
最后，謝謝你這么帥，還給我點贊和關注，
微信公眾號：萬貓學社
微信掃描二維碼
關注后回復「電子書」
獲取12本Java必讀技術書籍
作者：萬貓學社
出處：http://www.cnblogs.com/heihaozi/
著作權宣告：本文遵循 CC 4.0 BY-NC-SA 著作權協議，轉載請附上原文出處鏈接和本宣告，
微信掃描二維碼，關注萬貓學社，回復「電子書」，免費獲取12本Java必讀技術書籍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/448059.html
標籤：Java