概述 在 redis 中，list 有两种存储方式：双链表（linkedlist）和压缩双链表（ziplist）。双链表即普通数据结构中遇到的，在 adlist.h 和 adlist.c 中实现。压缩双链表以连续的内存空间来表示双链表，压缩双链表节省前驱和后驱指针的空间（8b），这在小的 li
概述在 redis 中，list 有两种存储方式：双链表（linkedlist）和压缩双链表（ziplist）。双链表即普通数据结构中遇到的，在 adlist.h 和 adlist.c 中实现。压缩双链表以连续的内存空间来表示双链表，压缩双链表节省前驱和后驱指针的空间（8b），这在小的 list 上，压缩效率是非常明显的；压缩双链表在 ziplist.h 和 ziplist.c 中实现。
这篇主要详述压缩双链表，普通双链表可以参看其他资料。
压缩双链表的具体实现在压缩双链表中，节省了前驱和后驱指针的空间，共 8个字节，这让数据在内存中更为紧凑。只要清晰的描述每个数据项的边界，就可以轻易得到后驱数据项的位置；只要描述前驱数据项的大小，就可以定位前驱数据项的位置，redis 就是这么做的。
ziplist 的格式可以表示为：
...
zlbytes 是 ziplist 占用的空间；zltail 是最后一个数据项的偏移位置，这方便逆向遍历链表，也是双链表的特性；zllen 是数据项 entry 的个数；zlend 就是 255，占 1b.详细展开 entry 的结构。
entry 的格式即为典型的 type-lenght-value，即 tlv，表述如下：
|>||---1----------------2--------------3---|
域 1）是前驱数据项的大小。因为不用描述前驱的数据类型，描述较为简单。
域 2） 是此数据项的的类型和数据大小。为了节省空间，redis 预设定了多种长度的字符串和整数。
3种长度的字符串#define zip_str_06b (0 域 3）为真正的数据。
透过 ziplist 查找函数 ziplistfind()，熟悉 ziplist entry 对数据格式：
// 在 ziplist 中查找数据项/* find pointer to the entry equal to the specified entry. skip 'skip' entries* between every comparison. returns null when the field could not be found. */unsigned char *ziplistfind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) { int skipcnt = 0; unsigned char vencoding = 0; long long vll = 0; while (p[0] != zip_end) { unsigned int prevlensize, encoding, lensize, len; unsigned char *q; zip_decode_prevlensize(p, prevlensize); // 跳过前驱数据项大小，解析数据项大小 // len 为 data 大小 // lensize 为 len 所占内存大小 zip_decode_length(p + prevlensize, encoding, lensize, len); // q 指向 data q = p + prevlensize + lensize; if (skipcnt == 0) { /* compare current entry with specified entry */ if (zip_is_str(encoding)) { // 字符串比较 if (len == vlen && memcmp(q, vstr, vlen) == 0) { return p; } } else { // 整数比较 /* find out if the searched field can be encoded. note that * we do it only the first time, once done vencoding is set * to non-zero and vll is set to the integer value. */ if (vencoding == 0) { // 尝试将 vstr 解析为整数 if (!ziptryencoding(vstr, vlen, &vll, &vencoding)) { /* if the entry can't be encoded we set it to * uchar_max so that we don't retry again the next * time. */ // 不能编码为数字！！！会导致当前查找的数据项被跳过 vencoding = uchar_max; } /* must be non-zero by now */ assert(vencoding); } /* compare current entry with specified entry, do it only * if vencoding != uchar_max because if there is no encoding * possible for the field it can't be a valid integer. */ if (vencoding != uchar_max) { // 读取整数 long long ll = ziploadinteger(q, encoding); if (ll == vll) { return p; } } } /* reset skip count */ skipcnt = skip; } else { /* skip entry */ skipcnt--; } // 移动到 ziplist 的下一个数据项 /* move to next entry */ p = q + len; } // 没有找到 return null;}
注意，ziplist 每次插入新的数据都要 realloc。
为什么要用 ziplistredis hset 命令官网的描述是：
sets field in the hash stored at key to value. if key does not exist, a new key holding a hash is created. if field already exists in the hash, it is overwritten.
实际上，hset 底层所使用的数据结构正是上面所说的 ziplist，而不是平时所说的 hashtable。
那为什么要使用 ziplist，反对的理由是查找来说，（ziplist o(n)）vs（hashtable o(1)）？redis 可是为内存节省想破了头。首先 ziplist 比 hashtable 更节省内存，再者，redis 考虑到如果数据紧凑的 ziplist 能够放入 cpu 缓存（hashtable 很难，因为它是非线性的），那么查找算法甚至会比 hashtable 要快！。ziplist 由此有性能和内存空间的有事。
捣乱 2014-6-20
http://daoluan.net
原文地址：深入剖析 redis 数据结构 ziplist, 感谢原作者分享。