本文所引用的源码全部来自redis2.8.2版本。
redis中ziplist数据结构与api相关文件是：ziplist.h, ziplist.c, t_zset.c。
一、ziplist的构成
是一个4字节无符号整数，用来存储整个ziplist占用的字节数；
是一个4字节无符号整数，用来存储ziplist最后一个节点的相对于ziplist首地址偏移量；
是一个2字节无符号整数，存储ziplist中节点的数目，最大值为(2^16 - 2)，当zllen大于最大值时，需要遍历整个ziplist才能获取ziplist节点的数目；
ziplist存储的节点，各个节点的字节数根据内容而定；
是一个1字节无符号整数，值为255(11111111)，作为ziplist的结尾符
二、ziplist宏模块
宏名称
作用
ziplist_bytes(zl)
获取zlbytes值
ziplist_tail_offset(zl)
获取zltail值
ziplist_length(zl)
获取zllen值
ziplist_header_size
获取ziplist header的长度，固定为10个字节
ziplist_entry_head(zl)
获取ziplist第一个entry的首地址
ziplist_entry_tail(zl)
获取ziplist最后一个entry的首地址
ziplist_entry_end(zl)
获取ziplist的末端，即zlend首地址
三、ziplist典型结构分布图
图中相关域以及宏的解析见上面的分析。
四、entry结构解析
prev_entry_bytes_length：
表示上个节点所占的字节数，即上个节点的长度，如果需要跳到上个节点，而已知道当前节点的首地址p,上个节点的首地址prev = p-prev_entry_bytes_length
根据编码方式的不同，prev_entry_bytes_length可能占1 bytes或5 bytes：
1 bytes：如果上个节点的长度小于254，那么就只需要1个字节；
5 bytes：如果上个节点的长度大于等于254，那么就将第一个字节设为254(1111 1110),然后接下来的4个字节保存实际的长度值；
encoding与length：
ziplist的编码类型分为字符串、整数
encoding的前两个比特位用来判断编码类型是字符串或整数：00, 01, 10表示contents中保存着字符串
11表示contents中保存着整数字符串的具体编码方式：(_:预留，a:实际的二进制数)
编码
编码长度
contents中的值
00aaaaaa
1 bytes
长度[0,63]个字节的字符串
01aaaaaa bbbbbbbb
2 bytes
长度[64,16383]个字节的字符串
01______ aaaaaaaa bbbbbbbb cccccccc dddddddd
5 bytes
长度[16384,2^32-1]个字节的字符串
11开头的整型编码方式：
编码
编码长度
contents中的值
1100 0000
1 bytes
int16_t类型整数
1101 0000
1 bytes
int32_t类型整数
1110 0000
1 bytes
int64_t类型整数
1111 0000
1 bytes
24 bit 有符号整数
1111 1110
1 bytes
8 bit 有符号整数
1111 xxxx
1 bytes
4 bit 无符号整数,[0,12]
解释一下1111 xxxx编码：1111 xxxx 首先最小值应该是0001（0000已经被占用），最大值应该是1101（1110与111 1均已经被占用），因此，可被编码的值实际上只能是 1 至 13，由于还需要减1，所以实际只能编码[0,12]，至于减1的理由，我的理解是方便编码0。
五、zlentry数据结构
typedef struct zlentry { //前一个节点长度的存储所占的字节数，上个节点占用的长度 unsigned int prevrawlensize, prevrawlen; //当前节点长度的存储所占的字节数，当前节点占用的长度 unsigned int lensize, len; unsigned int headersize;//当前节点的头部大小 unsigned char encoding;//当前链表结点长度（即字段len）使用的编码类型 unsigned char *p; //指向当前结点起始位置的指针} zlentry;
zlentry结构体就是用来存储当前节点的相关信息的，这些信息需要解析得到，解析的代码如下：
//判断是否为字符串编码#define zip_entry_encoding(ptr, encoding) do { \ (encoding) = (ptr[0]); \ if ((encoding) < zip_str_mask) (encoding) &= zip_str_mask; \} while(0)//返回 encoding 指定的整数编码方式所需的长度static unsigned int zipintsize(unsigned char encoding) { switch(encoding) { case zip_int_8b: return 1; case zip_int_16b: return 2; case zip_int_24b: return 3; case zip_int_32b: return 4; case zip_int_64b: return 8; default: return 0; /* 4 bit immediate */ } assert(null); return 0;}//从 ptr 指针中取出节点的编码、保存节点长度所需的字节数、以及节点的长度//节点保存的类型分字符串与整型#define zip_decode_length(ptr, encoding, lensize, len) do { \ zip_entry_encoding((ptr), (encoding)); \ if ((encoding) < zip_str_mask) {//字符串编码 \ if ((encoding) == zip_str_06b) { \ (lensize) = 1; \ (len) = (ptr)[0] & 0x3f; \ } else if ((encoding) == zip_str_14b) { \ (lensize) = 2; \ (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \ } else if (encoding == zip_str_32b) { \ (lensize) = 5; \ (len) = ((ptr)[1] << 24) | \ ((ptr)[2] << 16) | \ ((ptr)[3] << 8) | \ ((ptr)[4]); \ } else { \ assert(null); \ } \ } else { //整型编码 \ (lensize) = 1; \ (len) = zipintsize(encoding); \ } \} while(0);//从指针 ptr 中取出保存前一个节点的长度所需的字节数//小于254用1个字节，否则用5个字节#define zip_decode_prevlensize(ptr, prevlensize) do { \ if ((ptr)[0] < zip_biglen) { \ (prevlensize) = 1; \ } else { \ (prevlensize) = 5; \ } \} while(0);//从指针 ptr 中取出前一个节点的长度//如果保存前一个节点长度只需要1个字节，prevlensize = 1,那么直接得到前一个节点的长度值prevlen//否则prevlensize后四个字节表示前一个节点的长度#define zip_decode_prevlen(ptr, prevlensize, prevlen) do { \ zip_decode_prevlensize(ptr, prevlensize); \ if ((prevlensize) == 1) { \ (prevlen) = (ptr)[0]; \ } else if ((prevlensize) == 5) { \ assert(sizeof((prevlensize)) == 4); \ memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \ memrev32ifbe(&prevlen); \ } \} while(0);//从指针 p 中提取出节点的各个属性，并将属性保存到 zlentry 结构，然后返回static zlentry zipentry(unsigned char *p) { zlentry e; zip_decode_prevlen(p, e.prevrawlensize, e.prevrawlen); zip_decode_length(p + e.prevrawlensize, e.encoding, e.lensize, e.len); e.headersize = e.prevrawlensize + e.lensize; e.p = p; return e;}
六、ziplist的主要函数列表
函数名
作用
复杂度
ziplistnew
创建一个新的ziplist
o(1)
ziplistresize
重新调整ziplist的大小
o(1)
__ziplistcascadeupdate
级联更新ziplist中entry的大小
o(n*m)
__ziplistdelete
删除指定位置开始的n个节点
o(n*m)
__ziplistinsert
在指定位置之前插入一个节点
o(n*m)
ziplistindex
获取第n个节点的首地址
o(n)
ziplistnext
获取当前节点的下一个节点首地址
o(1)
ziplistprev
获取当前节点的前一个节点首地址
o(1)
ziplistget
获取给定节点的数据
o(1)
ziplistfind
找到ziplist中包含给定数据的节点
o(n)
ziplistlen
获取ziplist中节点的数目
o(n)
ziplistbloblen
以字节为单位，返回ziplist占用的内存大小
o(1)
七、另外三个简单而重要的函数
//p:当前节点首地址，len:上一个节点的长度值//如果p==null，则返回编码len需要多少个字节，否则将该len存储在当前节点的prev_entry_bytes_length区域static unsigned int zipprevencodelength(unsigned char *p, unsigned int len) { if (p == null) { return (len 新编码节点长度，返回 1 - 5 = -4 nextdiff = (p[0] != zip_end) ? zipprevlenbytediff(p,reqlen) : 0; /* store offset because a realloc may change the address of zl. */ offset = p-zl;//保存当前的偏移量，在这偏移量之前的数据不需要改变，只需要改变在此之后的数据 // 重分配空间，并更新长度属性和表尾 // 新空间长度 = 现有长度 + 新节点所需长度 + 编码新节点长度所需的长度差 zl = ziplistresize(zl,curlen+reqlen+nextdiff); p = zl+offset; /* apply memory move when necessary and update tail offset. */ if (p[0] != zip_end) { /* subtract one because of the zip_end bytes */ //将原有从p-nextdiff开始全部向后偏移，余留出reqlen保存即将insert的数据 /** nextdiff = -4:原来p有5个字节来存储上个节点的长度，而现在只需要1个， 因此只需要将p+4后面的字节偏移到p+reqlen即可，这样就 只保留1个字节保存reqlen的长度了 nextdiff = 4: 原来p只有1个字节来存储上个节点的长度，现在需要5个， 那就将p-4后面的字节偏移到p+reqlen，这样p原来有1个字节 加上多偏移来的4个字节就可以保存reqlen的长度了 nextdiff = 0: 不需要考虑 */ memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); /* encode this entry's raw length in the next entry. */ zipprevencodelength(p+reqlen,reqlen);//下个节点保存即将insert数据的所占字节数 /* update offset for tail */ ziplist_tail_offset(zl) = intrev32ifbe(intrev32ifbe(ziplist_tail_offset(zl))+reqlen); /* when the tail contains more than one entry, we need to take * nextdiff in account as well. otherwise, a change in the * size of prevlen doesn't have an effect on the *tail* offset. */ // 有需要的话，将 nextdiff 也加上到 zltail 上 tail = zipentry(p+reqlen); if (p[reqlen+tail.headersize+tail.len] != zip_end) { ziplist_tail_offset(zl) = intrev32ifbe(intrev32ifbe(ziplist_tail_offset(zl))+nextdiff); } } else { /* this element will be the new tail. */ // 更新 ziplist 的 zltail 属性，现在新添加节点为表尾节点 ziplist_tail_offset(zl) = intrev32ifbe(p-zl); } /* when nextdiff != 0, the raw length of the next entry has changed, so * we need to cascade the update throughout the ziplist */ /** 如果nextdiff不等于0，说明现在的p+reqlen节点的长度变了，需要级联更新下个节点能否保存 p+reqlen节点的长度值 */ if (nextdiff != 0) { offset = p-zl; zl = __ziplistcascadeupdate(zl,p+reqlen); p = zl+offset; } /* write the entry */ p += zipprevencodelength(p,prevlen);//填写保存上一个节点长度的字节数 p += zipencodelength(p,encoding,slen);//填写保存当前节点长度的字节数 if (zip_is_str(encoding)) {//保存当前节点的字符串 memcpy(p,s,slen); } else { zipsaveinteger(p,value,encoding);//整数 } ziplist_incr_length(zl,1);//length + 1 return zl;}
ziplist剩余的一些函数就不一一列举分析，理解上述三个函数，其余都很简单，关注这三个函数的重点是作者在realloc之后如何通过memmove保证后续节点的数据保持不变的，不得不说redis的作者对ziplist的实现很让人佩服。
另外，推荐redis黄健宏（huangz1990）的redis设计与实现一书中有关于ziplist插入与删除节点的简单模拟实现。
九、小结
ziplist的最大的好处就是相比skiplist节约大量内存，但是在插入、删除、查询等操作上的时间复杂度与skiplist都是无法比拟的，当保存的数据比较少时，操作的时间自然可以接受，内存就是关键因素。
ziplist在redis中主要用于hash table、list、sorted set数据类型小范围数据的存储，本文描述的ziplist的存储都是无序的，如何实现在sorted set中的有序存储待以后分析，无序变有序无疑又增加的时间复杂度。
总之，ziplist就是一种用时间换空间的策略。
最后感谢黄健宏（huangz1990）的redis设计与实现及其他对redis2.6源码的相关注释对我在研究redis2.8源码方面的帮助。
由于本文其他有关ziplist的函数没有分析，包括本文内容有问题欢迎评论，有些代码我也不是特别的明白，谢谢。