# 跳躍表 跳躍表（skiplist）是一種有序數據結構， 它通過在每個節點中維持多個指向其他節點的指針， 從而達到快速訪問節點的目的。 跳躍表支持平均??最壞??復雜度的節點查找， 還可以通過順序性操作來批量處理節點。 在大部分情況下， 跳躍表的效率可以和平衡樹相媲美， 并且因為跳躍表的實現比平衡樹要來得更為簡單， 所以有不少程序都使用跳躍表來代替平衡樹。 Redis 使用跳躍表作為有序集合鍵的底層實現之一： 如果一個有序集合包含的元素數量比較多， 又或者有序集合中元素的成員（member）是比較長的字符串時， Redis 就會使用跳躍表來作為有序集合鍵的底層實現。 舉個例子，?`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`?有序集合的所有數據都保存在一個跳躍表里面， 其中每個跳躍表節點（node）都保存了一款水果的價錢信息， 所有水果按價錢的高低從低到高在跳躍表里面排序： * 跳躍表的第一個元素的成員為?`"banana"`?， 它的分值為?`5`?； * 跳躍表的第二個元素的成員為?`"cherry"`?， 它的分值為?`6.5`?； * 跳躍表的第三個元素的成員為?`"apple"`?， 它的分值為?`8`?； 諸如此類。 和鏈表、字典等數據結構被廣泛地應用在 Redis 內部不同， Redis 只在兩個地方用到了跳躍表， 一個是實現有序集合鍵， 另一個是在集群節點中用作內部數據結構， 除此之外， 跳躍表在 Redis 里面沒有其他用途。 本章將對 Redis 中的跳躍表實現進行介紹， 并列出跳躍表的操作 API 。 本章不會對跳躍表的基本定義和基礎算法進行介紹， 如果有需要的話， 可以參考 William Pugh 關于跳躍表的論文 《[Skip Lists: A Probabilistic Alternative to Balanced Trees](ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf)》 ， 或者 《[算法：C 語言實現（第 1 ～ 4 部分）](http://book.douban.com/subject/4065258/)》 一書的 13.5 節。