# 鏈表
鏈表提供了高效的節點重排能力, 以及順序性的節點訪問方式, 并且可以通過增刪節點來靈活地調整鏈表的長度。
作為一種常用數據結構, 鏈表內置在很多高級的編程語言里面, 因為 Redis 使用的 C 語言并沒有內置這種數據結構, 所以 Redis 構建了自己的鏈表實現。
鏈表在 Redis 中的應用非常廣泛, 比如列表鍵的底層實現之一就是鏈表: 當一個列表鍵包含了數量比較多的元素, 又或者列表中包含的元素都是比較長的字符串時, Redis 就會使用鏈表作為列表鍵的底層實現。
舉個例子, 以下展示的?`integers`?列表鍵包含了從?`1`?到?`1024`?共一千零二十四個整數:
~~~
redis> LLEN integers
(integer) 1024
redis> LRANGE integers 0 10
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"
9) "9"
10) "10"
11) "11"
~~~
`integers`?列表鍵的底層實現就是一個鏈表, 鏈表中的每個節點都保存了一個整數值。
除了鏈表鍵之外, 發布與訂閱、慢查詢、監視器等功能也用到了鏈表, Redis 服務器本身還使用鏈表來保存多個客戶端的狀態信息, 以及使用鏈表來構建客戶端輸出緩沖區(output buffer), 本書后續的章節將陸續對這些鏈表應用進行介紹。
本章接下來的內容將對 Redis 的鏈表實現進行介紹, 并列出相應的鏈表和鏈表節點 API 。
因為已經有很多優秀的算法書籍對鏈表的基本定義和相關算法進行了詳細的講解, 所以本章不會介紹這些內容, 如果不具備關于鏈表的基本知識的話, 可以參考《[算法:C 語言實現(第 1 ~ 4 部分)](http://book.douban.com/subject/4065258/)》一書的 3.3 至 3.5 節, 或者《[數據結構與算法分析:C 語言描述](http://book.douban.com/subject/1139426/)》一書的 3.2 節, 又或者《[算法導論(第三版)](http://book.douban.com/subject/20432061/)》一書的 10.2 節。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤