ziplist是用一個字符串來實現(xiàn)的雙向鏈表結(jié)構(gòu)，顧名思義，使用ziplist可以減少雙向鏈表的存儲空間，主要是節(jié)省了鏈表指針的存儲，如果存儲指向上一個鏈表結(jié)點(diǎn)和指向下一個鏈表結(jié)點(diǎn)的指針需要8個字節(jié)，而轉(zhuǎn)化成存儲上一個結(jié)點(diǎn)長度和當(dāng)前結(jié)點(diǎn)長度在大多數(shù)情況下可以節(jié)省很多空間(最好的情況下只需2個字節(jié))。但是每次向鏈表增加元素都需要重新分配內(nèi)存。

ziplist中的結(jié)構(gòu)體typedef struct zlentry {unsigned int prevrawlensize, prevrawlen;unsigned int lensize, len;unsigned int headersize;unsigned char encoding;unsigned char *p;} zlentry;Prevrawlen：上個鏈表結(jié)點(diǎn)占用的長度Prevrawlensize：上個鏈表結(jié)點(diǎn)長度的存儲占用的字節(jié)數(shù)Len：當(dāng)前鏈表結(jié)點(diǎn)占用的長度Lensize：當(dāng)前鏈表結(jié)點(diǎn)長度的存儲占用的字節(jié)數(shù)Headersize：當(dāng)前鏈表結(jié)點(diǎn)的頭部大小， headersize = prevrawlensize + lensizeEncoding：當(dāng)前鏈表結(jié)點(diǎn)長度(即字段len)使用的編碼類型P：指向當(dāng)前結(jié)點(diǎn)起始位置的指針Ziplist的存儲結(jié)構(gòu)鏈表存儲結(jié)構(gòu)Zlbytes：一個4字節(jié)的無符號整型，存儲的是整個ziplist占用的字節(jié)數(shù)，用于重分配內(nèi)存時使用。Zltail：一個4字節(jié)的無符號整型，存儲的是鏈表最后一個結(jié)點(diǎn)的偏移值，即鏈表開頭地址+zltail即為最后一個結(jié)點(diǎn)的起始地址Zllen：一個2字節(jié)的無符號整型，存儲的是鏈表中存儲的結(jié)點(diǎn)數(shù)，當(dāng)這個值存儲的是2字節(jié)無符號整型的最大值時，需要遍歷鏈表獲取鏈表的結(jié)點(diǎn)數(shù)Entry：鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)的存儲格式見結(jié)點(diǎn)存儲結(jié)構(gòu)Zlend：占用1字節(jié)的鏈表的結(jié)尾符，值為255相關(guān)的宏定義Ziplist.c: 89/* Utility macros */#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+ZIPLIST_TAIL_OFFSET(zl))#define ZIPLIST_ENTRY_END(zl) ((zl)+ZIPLIST_BYTES(zl)-1)結(jié)點(diǎn)存儲結(jié)構(gòu)<上一個鏈表結(jié)點(diǎn)占用的長度><當(dāng)前鏈表結(jié)點(diǎn)占用的長度><當(dāng)前結(jié)點(diǎn)數(shù)據(jù)>上一個鏈表結(jié)點(diǎn)占用的長度上一個鏈表結(jié)點(diǎn)占用的長度占用的字節(jié)數(shù)根據(jù)編碼類型而定當(dāng)長度數(shù)據(jù)小于254使用一個字節(jié)存儲，該字節(jié)存儲的數(shù)值就是該長度，當(dāng)長度數(shù)據(jù)大于等于254時，使用5個字節(jié)存儲，第一個字節(jié)的數(shù)值為254，表示接下來的4個字節(jié)才真正表示長度當(dāng)前鏈表結(jié)點(diǎn)用的長度存儲和數(shù)據(jù)存儲第一個字節(jié)的前兩位用于區(qū)分長度存儲編碼類型和數(shù)據(jù)編碼類型，具體如下字符串類型編碼|00pppppp|長度小于等于63(2^6-1)字節(jié)的字符串，后6位用于存儲字符串長度，長度與類型總共占用了1個字節(jié)|01pppppp|qqqqqqqq|長度小于等于16383(2^14-1)字節(jié)的字符串，后14位用于存儲字符串長度，長度與類型總共占用了2個字節(jié)|10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|長度大于等于16384字節(jié)的字符串，后4個字節(jié)用于存儲字符串長度，長度與類型總共占用了5個字節(jié)整型編碼|1100____|整型類型，后2個字節(jié)存儲的值就是該整數(shù)|1101____|整型類型，后4個字節(jié)存儲的值就是該整數(shù)|1110____|整型類型，后8個字節(jié)存儲的值就是該整數(shù)相關(guān)的宏定義Ziplist.c：77/* Different encoding/length possibilities */#define ZIP_STR_06B (0 << 6)#define ZIP_STR_14B (1 << 6)#define ZIP_STR_32B (2 << 6)#define ZIP_INT_16B (0xc0 | 0<<4)#define ZIP_INT_32B (0xc0 | 1<<4)#define ZIP_INT_64B (0xc0 | 2<<4)/* Macro's to determine type */#define ZIP_IS_STR(enc) (((enc) & 0xc0) < 0xc0)#define ZIP_IS_INT(enc) (!ZIP_IS_STR(enc) && ((enc) & 0x30) < 0x30)ziplist提供的接口unsigned char *ziplistNew(void);創(chuàng)建一個ziplist返回創(chuàng)建的ziplist的指針unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where);在ziplist的尾端或頭部添加一個結(jié)點(diǎn)zl是ziplist的指針s是待添加結(jié)點(diǎn)的值slen是待添加結(jié)點(diǎn)的值長度返回最新的ziplist的指針unsigned char *ziplistIndex(unsigned char *zl, int index);根據(jù)索引獲取ziplist的結(jié)點(diǎn)，封裝類似數(shù)組接口zl是ziplist的指針index是索引，從0開始，0即取鏈表的第一個結(jié)點(diǎn)，index可以是負(fù)數(shù)，負(fù)數(shù)表從后往前算，-1就是取鏈表的最后一個元素如果index處有結(jié)點(diǎn)，則返回指向改結(jié)點(diǎn)的指針，否則返回NULLunsigned char *ziplistNext(unsigned char *zl, unsigned char *p);獲取ziplist的下一個結(jié)點(diǎn)zl是無用參數(shù)p是當(dāng)前結(jié)點(diǎn)指針如果還有下一個結(jié)點(diǎn)，則返回下一個結(jié)點(diǎn)的指針，否則返回NULLunsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);獲取ziplist的上一個結(jié)點(diǎn)zl是ziplist的指針p是當(dāng)前結(jié)點(diǎn)指針如果還有上一個結(jié)點(diǎn)，則返回上一個結(jié)點(diǎn)的指針，否則返回NULLunsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);獲取p指向的當(dāng)前結(jié)點(diǎn)的值p是指向當(dāng)前結(jié)點(diǎn)的指針sval保存獲取到的當(dāng)前結(jié)點(diǎn)的值的指針slen是獲取到的當(dāng)前結(jié)點(diǎn)的值的長度lval是當(dāng)值是整型時保存返回的數(shù)值如果p指向的結(jié)點(diǎn)是合法結(jié)點(diǎn)返回1，否則返回0unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);在指針p指向的位置插入一個結(jié)點(diǎn)zl是ziplist的指針p是待插入結(jié)點(diǎn)的位置s是待插入結(jié)點(diǎn)的值slen是待插入結(jié)點(diǎn)的值的長度返回最新的ziplist的指針unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);刪掉*p指向的結(jié)點(diǎn)zl是ziplist的指針p是一個value-result參數(shù)，傳入需刪除的結(jié)點(diǎn)，返回被刪除結(jié)點(diǎn)下一個結(jié)點(diǎn)的指針返回最新的ziplist的指針unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num);刪除連續(xù)的一批結(jié)點(diǎn)zl是ziplist的指針index是開始刪除的索引num是刪除的個數(shù)返回最新的ziplist的指針unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);p指向的結(jié)點(diǎn)的值和s對應(yīng)的值做比較p是ziplist結(jié)點(diǎn)的指針s是呆比較的值slen是s的長度相等返回1，否則返回0unsigned int ziplistLen(unsigned char *zl);取ziplist鏈表中元素的個數(shù)zl是ziplist的指針返回ziplist鏈表中元素的個數(shù)size_t ziplistBlobLen(unsigned char *zl);取ziplist鏈表占用的字節(jié)數(shù)zl是ziplist的指針返回ziplist鏈表占用的字節(jié)數(shù)