雙端連結清單作為一種通用的資料結構在Redis 内部使用得非常多它既是Redis 清單結構的底
層實作之一還被大量Redis 子產品所使用用于建構Redis 的其他功能。
對清單類型的鍵進行操作——比如執行
RPUSH 、LPOP 或LLEN 等指令時程式在底層操作的可能就是雙端連結清單。
<a href="http://s3.51cto.com/wyfs02/M00/11/7F/wKiom1LSmVTieEL_AAD1MIhqxfA159.jpg" target="_blank"></a>
Note: Redis 清單使用兩種資料結構作為底層實作
1. 雙端連結清單
2. 壓縮清單
因為雙端連結清單占用的記憶體比壓縮清單要多是以當建立新的清單鍵時清單會優先考慮使用壓
縮清單作為底層實作并且在有需要的時候才從壓縮清單實作轉換到雙端連結清單實作。
除了實作清單類型以外雙端連結清單還被很多Redis 内部子產品所應用
. 事務子產品使用雙端連結清單來按順序儲存輸入的指令
. 伺服器子產品使用雙端連結清單來儲存多個用戶端
. 訂閱/發送子產品使用雙端連結清單來儲存訂閱模式的多個用戶端
. 事件子產品使用雙端連結清單來儲存時間事件time event
類似的應用還有很多在後續的章節中我們将看到雙端連結清單在Redis 中發揮着重要的作用。
雙端連結清單的實作由listNode 和list 兩個資料結構構成下圖展示了由這兩個結構組成的一
個雙端連結清單執行個體
<a href="http://s3.51cto.com/wyfs02/M01/11/7E/wKioL1LSmovClwQJAAB_unCATkw239.jpg" target="_blank"></a>
其中listNode 是雙端連結清單的節點
1
2
3
4
5
6
7
8
<code>typedef</code> <code>struct</code> <code>listNode {</code>
<code>// 前驅節點</code>
<code>struct</code> <code>listNode *prev;</code>
<code>// 後繼節點</code>
<code>struct</code> <code>listNode *next;</code>
<code>// 值</code>
<code>void</code> <code>*value;</code>
<code>} listNode;</code>
而list 則是雙端連結清單本身
9
10
11
12
13
14
<code>typedef</code> <code>struct</code> <code>list {</code>
<code>// 表頭指針</code>
<code>listNode *head;</code>
<code>// 表尾指針</code>
<code>listNode *tail;</code>
<code>// 節點數量</code>
<code>unsigned </code><code>long</code> <code>len;</code>
<code>// 複制函數</code>
<code>void</code> <code>*(*dup)(</code><code>void</code> <code>*ptr);</code>
<code>// 釋放函數</code>
<code>void</code> <code>(*</code><code>free</code><code>)(</code><code>void</code> <code>*ptr);</code>
<code>// 比對函數</code>
<code>int</code> <code>(*match)(</code><code>void</code> <code>*ptr, </code><code>void</code> <code>*key);</code>
<code>} list;</code>
注意listNode 的value 屬性的類型是void * 說明這個雙端連結清單對節點所儲存的值的類型
不做限制。
對于不同類型的值有時候需要不同的函數來處理這些值是以list 類型保留了三個函數指針——dup 、free 和match 分别用于處理值的複制、釋放和對比比對。在對節點的值進行處
理時如果有給定這些函數那麼它們就會被調用。
另外從這兩個資料結構的定義上也可以它們的一些行為和性能特征
1、 listNode 帶有prev 和next 兩個指針是以對連結清單的周遊可以在兩個方向上進行從
表頭到表尾或者從表尾到表頭。
2、list 儲存了head 和tail 兩個指針是以對連結清單的表頭和表尾進行插入的複雜度都為O(1) ——這是高效實作LPUSH 、RPOP 、RPOPLPUSH 等指令的關鍵。
3、list 帶有儲存節點數量的len 屬性是以計算連結清單長度的複雜度僅為O(1) 這也保證
了LLEN 指令不會成為性能瓶頸。
Redis 為雙端連結清單實作了一個疊代器這個疊代器可以從兩個方向對雙端連結清單進行疊代
1、沿着節點的next 指針前進從表頭向表尾疊代
2、沿着節點的prev 指針前進從表尾向表頭疊代
以下是疊代器的資料結構定義
<code>typedef</code> <code>struct</code> <code>listIter {</code>
<code>// 下一節點</code>
<code>listNode *next;</code>
<code>// 疊代方向</code>
<code>int</code> <code>direction;</code>
<code>} listIter;</code>
direction 記錄疊代應該從那裡開始
1、 如果值為adlist.h/AL_START_HEAD 那麼疊代器執行從表頭到表尾的疊代
2、 如果值為adlist.h/AL_START_TAIL 那麼疊代器執行從表尾到表頭的疊代
本文轉自shayang8851CTO部落格，原文連結：http://blog.51cto.com/janephp/1351054，如需轉載請自行聯系原作者
![redis筆記⑤——redis叢集[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)