前言
在上一章中我們介紹了 String 的一些內(nèi)部原理,在這一章中我們再來討論在五種數(shù)據(jù)結(jié)構(gòu)中 List 的基本使用和一些內(nèi)部實(shí)現(xiàn).
基本介紹
Redis的List 呢相當(dāng)于 Java 中的 LinkedList,也是雙向鏈表.具有一些和 LinkedList 同樣的特征,比如插入和刪除一條很快,時(shí)間復(fù)雜度為 O(1),獲取頭結(jié)點(diǎn)和尾節(jié)點(diǎn)也很快,時(shí)間復(fù)雜度也為 O(1),隨機(jī)讀取則相對較慢時(shí)間復(fù)雜度為 O(n).常用作消息隊(duì)列.
當(dāng)做隊(duì)列使用時(shí),遵循先進(jìn)先出原則:
> rpush books python java golang
(integer) 3
> lpop books
"python"
> lpop books
"java"
當(dāng)做棧使用時(shí),遵循先進(jìn)后出原則:
> rpush books python java golang
(integer) 3
> rpop books
"golang"
> rpop books
"java"
同時(shí)還可以通過 get(index)的方法獲取:
> rpush books python java golang
(integer) 3
> lindex books 0
"python"
> lindex books -1
"golang"
index從 0 開始,可以為負(fù)數(shù) -1 代表倒數(shù)第一個(gè)元素
內(nèi)部實(shí)現(xiàn)
上述部分我們把 Redis 中的 List當(dāng)做 Java 中的 LinkedList 操作,因?yàn)橛泻芏嘞嗤牟糠?但實(shí)際上在 Redis 中鏈表的內(nèi)部實(shí)現(xiàn)可不是一個(gè)簡單的雙向鏈表.在數(shù)據(jù)量較少的時(shí)候它的底層存儲結(jié)構(gòu)為一塊連續(xù)內(nèi)存,稱之為ziplist(壓縮列表).當(dāng)數(shù)據(jù)量較多的時(shí)候?qū)兂涉湵淼慕Y(jié)構(gòu).后來因?yàn)殒湵硇枰?prev 和 next 兩個(gè)指針占用內(nèi)存很多,改用 ziplist+鏈表的混合結(jié)構(gòu),稱之為 quicklist(快速鏈表).在新的版本中 Redis 鏈表統(tǒng)一使用 quicklist來存儲.下面我們就來詳細(xì)介紹這種數(shù)據(jù)結(jié)構(gòu).
ziplist 壓縮列表
先來看看 ziplist 的數(shù)據(jù)結(jié)構(gòu):
struct ziplist<T>{
int32 zlbytes; //壓縮列表占用字節(jié)數(shù)
int32 zltail_offset; //最后一個(gè)元素距離起始位置的偏移量,用于快速定位到最后一個(gè)節(jié)點(diǎn)
int16 zllength; //元素個(gè)數(shù)
T[] entries; //元素內(nèi)容
int8 zlend; //結(jié)束位 0xFF
}
如圖所示:
有了 ztail_offset 就可以快速的定位到最后一個(gè)節(jié)點(diǎn),這樣就可以倒序遍歷了.也就是說 ziplist支持雙向遍歷.
下面再來看下 entry 的內(nèi)部實(shí)現(xiàn):
struct entry{
int<var> prevlen; //前一個(gè) entry 的長度
int<var> encoding; //元素類型編碼
optional byte[] content; //元素內(nèi)容
}
當(dāng) ziplist 倒序遍歷的時(shí)候,就是通過這個(gè)pervlen定位到前一個(gè)元素位置的.
encoding 保存了 content 的編碼類型.
content 則是保存的元素內(nèi)容,它是optional 類型表示是這個(gè)字段是可選的.當(dāng)content 是很小的整數(shù)時(shí),他會內(nèi)聯(lián)到 encoding 字段的尾部.
quicklist 快速列表
quicklist 是 ziplist 和鏈表的混合體.下面是 quicklist和 node 的部分?jǐn)?shù)據(jù)結(jié)構(gòu):
struct quicklist{
quicklistNode* head; //指向頭結(jié)點(diǎn)
quicklistNode* tail; //指向尾節(jié)點(diǎn)
long count; //元素總數(shù)
int nodes; //quicklistNode節(jié)點(diǎn)的個(gè)數(shù)
int compressDepth; //壓縮算法深度
...
}
為了節(jié)約空間 Redis 還會對 ziplist 使用 LZF 算法進(jìn)行壓縮,可以選擇壓縮深度.我們待會在說.
如上圖所示,quicklist含有兩個(gè) quicklistNode 代表頭結(jié)點(diǎn)和尾節(jié)點(diǎn),其中每個(gè)head 和 tail 之間是雙向鏈表.每個(gè)quicklistNode指向一個(gè) ziplist.
struct quicklistNode{
quicklistNode* prev; //前一個(gè)節(jié)點(diǎn)
quicklistNode* next; //后一個(gè)節(jié)點(diǎn)
ziplist* zl; //壓縮列表
int32 size; //ziplist大小
int16 count; //ziplist 中元素?cái)?shù)量
int2 encoding; //編碼形式 存儲 ziplist 還是進(jìn)行 LZF 壓縮儲存
...
}
在 quicklist 中每個(gè) ziplist 默認(rèn)大小是 8kb,超出這個(gè)字節(jié)就會增加一個(gè) ziplist.這個(gè)默認(rèn)大小是可配置的,由list-max-ziplist-size決定.
上面說到 ziplist 可以使用 LZF 算法壓縮,通過list-compress-depth配置.默認(rèn)情況下quicklist 的壓縮深度是 0,也就是不壓縮.配置為 1 的話代表從頭/尾開始第 1 個(gè)ziplsit 進(jìn)行壓縮.
下章預(yù)告,Redis 數(shù)據(jù)結(jié)構(gòu)之 Hash
