Posted on 2013-04-05 18:05
鑫龍 閱讀(518)
評論(0) 編輯 收藏 引用 所屬分類:
redis
轉(zhuǎn)自：http://www.redisbook.com
雙端鏈表
鏈表作為數(shù)組之外的一種常用序列抽象， 是大多數(shù)高級語言的基本數(shù)據(jù)類型， 因為 C 語言本身不支持鏈表類型， 大部分 C 程序都會自己實現(xiàn)一種鏈表類型， Redis 也不例外 —— 它實現(xiàn)了一個雙端鏈表結(jié)構(gòu)。
雙端鏈表作為一種常見的數(shù)據(jù)結(jié)構(gòu)， 在大部分的數(shù)據(jù)結(jié)構(gòu)或者算法書里都有講解， 因此， 這一章關(guān)注的是 Redis 雙端鏈表的具體實現(xiàn)， 以及該實現(xiàn)的 API ， 而對于雙端鏈表本身， 以及雙端鏈表所對應(yīng)的算法， 則不做任何解釋。
讀者如果有需要的話，可以參考維基百科的雙端鏈表詞條，里面提供了關(guān)于雙端鏈表的一些基本信息。
另外，一些書籍，比如《算法：C 語言實現(xiàn)》和《數(shù)據(jù)結(jié)構(gòu)與算法分析》則提供了關(guān)于雙端鏈表的更詳細(xì)的信息。
雙端鏈表的應(yīng)用
雙端鏈表作為一種通用的數(shù)據(jù)結(jié)構(gòu)， 在 Redis 內(nèi)部使用得非常多： 它既是 Redis 列表結(jié)構(gòu)的底層實現(xiàn)之一， 還被大量 Redis 模塊所使用， 用于構(gòu)建 Redis 的其他功能。
實現(xiàn) Redis 的列表類型
雙端鏈表還是 Redis 列表類型的底層實現(xiàn)之一， 當(dāng)對列表類型的鍵進(jìn)行操作 —— 比如執(zhí)行 RPUSH 、 LPOP 或 LLEN 等命令時， 程序在底層操作的可能就是雙端鏈表。
redis> RPUSH brands Apple Microsoft Google
(integer) 3
redis> LPOP brands
"Apple"
redis> LLEN brands
(integer) 2
redis> LRANGE brands 0 -1
1) "Microsoft"
2) "Google"
Redis 列表使用兩種數(shù)據(jù)結(jié)構(gòu)作為底層實現(xiàn)：
- 雙端鏈表
- 壓縮列表
因為雙端鏈表占用的內(nèi)存比壓縮列表要多， 所以當(dāng)創(chuàng)建新的列表鍵時， 列表會優(yōu)先考慮使用壓縮列表作為底層實現(xiàn)， 并且在有需要的時候， 才從壓縮列表實現(xiàn)轉(zhuǎn)換到雙端鏈表實現(xiàn)。
后續(xù)章節(jié)會對壓縮鏈表和 Redis 類型做更進(jìn)一步的介紹。
Redis 自身功能的構(gòu)建
除了實現(xiàn)列表類型以外， 雙端鏈表還被很多 Redis 內(nèi)部模塊所應(yīng)用：
- 事務(wù)模塊使用雙端鏈表來按順序保存輸入的命令；
- 服務(wù)器模塊使用雙端鏈表來保存多個客戶端；
- 訂閱/發(fā)送模塊使用雙端鏈表來保存訂閱模式的多個客戶端；
- 事件模塊使用雙端鏈表來保存時間事件（time event）；
類似的應(yīng)用還有很多， 在后續(xù)的章節(jié)中我們將看到， 雙端鏈表在 Redis 中發(fā)揮著重要的作用。
雙端鏈表的實現(xiàn)
雙端鏈表的實現(xiàn)由 listNode 和 list 兩個數(shù)據(jù)結(jié)構(gòu)構(gòu)成， 下圖展示了由這兩個結(jié)構(gòu)組成的一個雙端鏈表實例：
其中， listNode 是雙端鏈表的節(jié)點：typedef struct listNode {
// 前驅(qū)節(jié)點
struct listNode *prev;
// 后繼節(jié)點
struct listNode *next;
// 值
void *value;
} listNode;
而 list 則是雙端鏈表本身：typedef struct list {
// 表頭指針
listNode *head;
// 表尾指針
listNode *tail;
// 節(jié)點數(shù)量
unsigned long len;
// 復(fù)制函數(shù)
void *(*dup)(void *ptr);
// 釋放函數(shù)
void (*free)(void *ptr);
// 比對函數(shù)
int (*match)(void *ptr, void *key);
} list;
注意， listNode 的 value 屬性的類型是 void * ，說明這個雙端鏈表對節(jié)點所保存的值的類型不做限制。
對于不同類型的值，有時候需要不同的函數(shù)來處理這些值，因此， list 類型保留了三個函數(shù)指針 —— dup 、 free 和 match ，分別用于處理值的復(fù)制、釋放和對比匹配。在對節(jié)點的值進(jìn)行處理時，如果有給定這些函數(shù)，那么它們就會被調(diào)用。
舉個例子：當(dāng)刪除一個 listNode 時，如果包含這個節(jié)點的 list 的 list->free 函數(shù)不為空，那么刪除函數(shù)就會先調(diào)用 list->free(listNode->value) 清空節(jié)點的值，再執(zhí)行余下的刪除操作（比如說，釋放節(jié)點）。
另外，從這兩個數(shù)據(jù)結(jié)構(gòu)的定義上，也可以它們的一些行為和性能特征：
- listNode 帶有 prev 和 next 兩個指針，因此，對鏈表的遍歷可以在兩個方向上進(jìn)行：從表頭到表尾，或者從表尾到表頭。
- list 保存了 head 和 tail 兩個指針，因此，對鏈表的表頭和表尾進(jìn)行插入的復(fù)雜度都為 θ(1) —— 這是高效實現(xiàn) LPUSH 、 RPOP 、RPOPLPUSH 等命令的關(guān)鍵。
- list 帶有保存節(jié)點數(shù)量的 len 屬性，所以計算鏈表長度的復(fù)雜度僅為 θ(1) ，這也保證了 LLEN 命令不會成為性能瓶頸。
以下是用于操作雙端鏈表的 API ，它們的作用以及算法復(fù)雜度：
| 函數(shù) | 作用 | 算法復(fù)雜度 |
|---|
| listCreate | 創(chuàng)建一個新鏈表 | O(1) |
| listRelease | 釋放一個鏈表，以及該鏈表所包含的節(jié)點 | O(N) |
| listDup | 創(chuàng)建一個給定鏈表的副本 | O(N) |
| listRotate | 取出鏈表的表尾節(jié)點，將它插入到表頭 | O(1) |
| listAddNodeHead | 將一個包含給定值的節(jié)點添加到鏈表的表頭 | O(1) |
| listAddNodeTail | 將一個包含給定值的節(jié)點添加到鏈表的表尾 | O(1) |
| listInsertNode | 將一個包含給定值的節(jié)點添加到某個節(jié)點的之前或之后 | O(1) |
| listDelNode | 刪除給定節(jié)點 | O(1) |
| listSearchKey | 在鏈表中查找和給定 key 匹配的節(jié)點 | O(N) |
| listIndex | 給據(jù)給定索引，返回列表中相應(yīng)的節(jié)點 | O(N) |
| listLength | 返回給定鏈表的節(jié)點數(shù)量 | O(1) |
| listFirst | 返回鏈表的表頭節(jié)點 | O(1) |
| listLast | 返回鏈表的表尾節(jié)點 | O(1) |
| listPrevNode | 返回給定節(jié)點的前一個節(jié)點 | O(1) |
| listNextNode | 返回給定節(jié)點的后一個節(jié)點 | O(1) |
| listNodeValue | 返回給定節(jié)點的值 | O(1) |
迭代器
Redis 為雙端鏈表實現(xiàn)了一個迭代器 ， 這個迭代器可以從兩個方向?qū)﹄p端鏈表進(jìn)行迭代：
- 沿著節(jié)點的 next 指針前進(jìn)，從表頭向表尾迭代；
- 沿著節(jié)點的 prev 指針前進(jìn)，從表尾向表頭迭代；
以下是迭代器的數(shù)據(jù)結(jié)構(gòu)定義：
typedef struct listIter {
// 下一節(jié)點
listNode *next;
// 迭代方向
int direction;
} listIter;
direction 記錄迭代應(yīng)該從那里開始：
- 如果值為 adlist.h/AL_START_HEAD ，那么迭代器執(zhí)行從表頭到表尾的迭代；
- 如果值為 adlist.h/AL_START_TAIL ，那么迭代器執(zhí)行從表尾到表頭的迭代；
以下是迭代器的操作 API ，它們的作用以及算法復(fù)雜度：
| 函數(shù) | 作用 | 算法復(fù)雜度 |
|---|
| listGetIterator | 創(chuàng)建一個列表迭代器 | O(1) |
| listReleaseIterator | 釋放迭代器 | O(1) |
| listRewind | 將迭代器的指針指向表頭 | O(1) |
| listRewindTail | 將迭代器的指針指向表尾 | O(1) |
| listNext | 取出迭代器當(dāng)前指向的節(jié)點 | O(1) |
小結(jié)
- Redis 實現(xiàn)了自己的雙端鏈表結(jié)構(gòu)。
- 雙端鏈表主要有兩個作用：
- 作為 Redis 列表類型的底層實現(xiàn)之一；
- 作為通用數(shù)據(jù)結(jié)構(gòu)，被其他功能模塊所使用；
- 雙端鏈表及其節(jié)點的性能特性如下：
- 節(jié)點帶有前驅(qū)和后繼指針，訪問前驅(qū)節(jié)點和后繼節(jié)點的復(fù)雜度為 O(1) ，并且對鏈表的迭代可以在從表頭到表尾和從表尾到表頭兩個方向進(jìn)行；
- 鏈表帶有指向表頭和表尾的指針，因此對表頭和表尾進(jìn)行處理的復(fù)雜度為 O(1) ；
- 鏈表帶有記錄節(jié)點數(shù)量的屬性，所以可以在 O(1) 復(fù)雜度內(nèi)返回鏈表的節(jié)點數(shù)量（長度）；