本文所引用的源码全部来自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典型结构分布图

图中相关域以及宏的解析见上面的分析。

四、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:实际的二进制数)

11开头的整型编码方式：

解释一下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 < ZIP_BIGLEN)   1 : sizeof(len)+1;
    } else {
        if (len < ZIP_BIGLEN) {
            p[0] = len;
            return 1;
        } else {
            p[0] = ZIP_BIGLEN;
            memcpy(p+1,&len,sizeof(len));
            memrev32ifbe(p+1);
            return 1+sizeof(len);
        }
    }
}