# 跳躍表
跳躍表(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 節。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤