列表對象的編碼可以是?`ziplist`?或者?`linkedlist`?。
`ziplist`?編碼的列表對象使用壓縮列表作為底層實現, 每個壓縮列表節點(entry)保存了一個列表元素。
舉個例子, 如果我們執行以下?RPUSH?命令, 那么服務器將創建一個列表對象作為?`numbers`?鍵的值:
~~~
redis> RPUSH numbers 1 "three" 5
(integer) 3
~~~
如果?`numbers`?鍵的值對象使用的是?`ziplist`?編碼, 這個這個值對象將會是圖 8-5 所展示的樣子。

另一方面,?`linkedlist`?編碼的列表對象使用雙端鏈表作為底層實現, 每個雙端鏈表節點(node)都保存了一個字符串對象, 而每個字符串對象都保存了一個列表元素。
舉個例子, 如果前面所說的?`numbers`?鍵創建的列表對象使用的不是?`ziplist`?編碼, 而是?`linkedlist`?編碼, 那么?`numbers`?鍵的值對象將是圖 8-6 所示的樣子。

注意,?`linkedlist`?編碼的列表對象在底層的雙端鏈表結構中包含了多個字符串對象, 這種嵌套字符串對象的行為在稍后介紹的哈希對象、集合對象和有序集合對象中都會出現, 字符串對象是 Redis 五種類型的對象中唯一一種會被其他四種類型對象嵌套的對象。
注意
為了簡化字符串對象的表示, 我們在圖 8-6 使用了一個帶有?`StringObject`?字樣的格子來表示一個字符串對象, 而?`StringObject`?字樣下面的是字符串對象所保存的值。
比如說, 圖 8-7 代表的就是一個包含了字符串值?`"three"`?的字符串對象, 它是 8-8 的簡化表示。


本書接下來的內容將繼續沿用這一簡化表示。
## 編碼轉換
當列表對象可以同時滿足以下兩個條件時, 列表對象使用?`ziplist`?編碼:
1. 列表對象保存的所有字符串元素的長度都小于?`64`?字節;
2. 列表對象保存的元素數量小于?`512`?個;
不能滿足這兩個條件的列表對象需要使用?`linkedlist`?編碼。
注意
以上兩個條件的上限值是可以修改的, 具體請看配置文件中關于?`list-max-ziplist-value`?選項和?`list-max-ziplist-entries`?選項的說明。
對于使用?`ziplist`?編碼的列表對象來說, 當使用?`ziplist`?編碼所需的兩個條件的任意一個不能被滿足時, 對象的編碼轉換操作就會被執行: 原本保存在壓縮列表里的所有列表元素都會被轉移并保存到雙端鏈表里面, 對象的編碼也會從?`ziplist`?變為?`linkedlist`?。
以下代碼展示了列表對象因為保存了長度太大的元素而進行編碼轉換的情況:
~~~
# 所有元素的長度都小于 64 字節
redis> RPUSH blah "hello" "world" "again"
(integer) 3
redis> OBJECT ENCODING blah
"ziplist"
# 將一個 65 字節長的元素推入列表對象中
redis> RPUSH blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
(integer) 4
# 編碼已改變
redis> OBJECT ENCODING blah
"linkedlist"
~~~
除此之外, 以下代碼展示了列表對象因為保存的元素數量過多而進行編碼轉換的情況:
~~~
# 列表對象包含 512 個元素
redis> EVAL "for i=1,512 do redis.call('RPUSH', KEYS[1], i) end" 1 "integers"
(nil)
redis> LLEN integers
(integer) 512
redis> OBJECT ENCODING integers
"ziplist"
# 再向列表對象推入一個新元素,使得對象保存的元素數量達到 513 個
redis> RPUSH integers 513
(integer) 513
# 編碼已改變
redis> OBJECT ENCODING integers
"linkedlist"
~~~
## 列表命令的實現
因為列表鍵的值為列表對象, 所以用于列表鍵的所有命令都是針對列表對象來構建的, 表 8-8 列出了其中一部分列表鍵命令, 以及這些命令在不同編碼的列表對象下的實現方法。
* * *
表 8-8 列表命令的實現
| 命令 | `ziplist`?編碼的實現方法 | `linkedlist`?編碼的實現方法 |
| --- | --- | --- |
| LPUSH | 調用?`ziplistPush`?函數, 將新元素推入到壓縮列表的表頭。 | 調用?`listAddNodeHead`?函數, 將新元素推入到雙端鏈表的表頭。 |
| RPUSH | 調用?`ziplistPush`?函數, 將新元素推入到壓縮列表的表尾。 | 調用?`listAddNodeTail`?函數, 將新元素推入到雙端鏈表的表尾。 |
| LPOP | 調用?`ziplistIndex`?函數定位壓縮列表的表頭節點, 在向用戶返回節點所保存的元素之后, 調用`ziplistDelete`?函數刪除表頭節點。 | 調用?`listFirst`?函數定位雙端鏈表的表頭節點, 在向用戶返回節點所保存的元素之后, 調用?`listDelNode`?函數刪除表頭節點。 |
| RPOP | 調用?`ziplistIndex`?函數定位壓縮列表的表尾節點, 在向用戶返回節點所保存的元素之后, 調用`ziplistDelete`?函數刪除表尾節點。 | 調用?`listLast`?函數定位雙端鏈表的表尾節點, 在向用戶返回節點所保存的元素之后, 調用?`listDelNode`?函數刪除表尾節點。 |
| LINDEX | 調用?`ziplistIndex`?函數定位壓縮列表中的指定節點, 然后返回節點所保存的元素。 | 調用?`listIndex`?函數定位雙端鏈表中的指定節點, 然后返回節點所保存的元素。 |
| LLEN | 調用?`ziplistLen`?函數返回壓縮列表的長度。 | 調用?`listLength`?函數返回雙端鏈表的長度。 |
| LINSERT | 插入新節點到壓縮列表的表頭或者表尾時, 使用`ziplistPush`?函數; 插入新節點到壓縮列表的其他位置時, 使用?`ziplistInsert`?函數。 | 調用?`listInsertNode`?函數, 將新節點插入到雙端鏈表的指定位置。 |
| LREM | 遍歷壓縮列表節點, 并調用?`ziplistDelete`?函數刪除包含了給定元素的節點。 | 遍歷雙端鏈表節點, 并調用?`listDelNode`?函數刪除包含了給定元素的節點。 |
| LTRIM | 調用?`ziplistDeleteRange`?函數, 刪除壓縮列表中所有不在指定索引范圍內的節點。 | 遍歷雙端鏈表節點, 并調用?`listDelNode`?函數刪除鏈表中所有不在指定索引范圍內的節點。 |
| LSET | 調用?`ziplistDelete`?函數, 先刪除壓縮列表指定索引上的現有節點, 然后調用?`ziplistInsert`?函數, 將一個包含給定元素的新節點插入到相同索引上面。 | 調用?`listIndex`?函數, 定位到雙端鏈表指定索引上的節點, 然后通過賦值操作更新節點的值。 |
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤