应用
- 压缩列表（ziplist）是由 一系列特殊编码的内存块构成的列表，其是Redis的列表建和哈希键的底层实现之一
- ziplist可以用来存放字符串或者整数，其存储数据的特点是：比较小的整数或比较短的字符串。Redis的列表建，哈希键，有序集合的底层实现都用到了ziplist
- 压缩列表是为了节约内存而开发的
- Ziplist 是为了尽可能地节约内存而设计的特殊编码双端链表
- Ziplist 允许在列表的两端进行 O(1) 复杂度的 push 和 pop 操作
数据结构
Redis的ziplist结构由三大部分组成，其分别是列表头（ziplist Header），数据节点（Entries）和列表尾（ziplist tail）,它们在内存上的布局如下：
- 头尾结构
ziplist的头部包含如下三个信息：
zlbytes：表示压缩列表占总内存的字节数
zltail：表示压缩列表头和尾之间的偏移量
zllen：表示压缩列表中节点的数量
ziplist尾部的zlend则表示压缩列表结束，其值固定为0xFF
Redis提供了一个宏定义来表示ziplist header的大小
// 总共10个字节
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
- 节点结构
数据节点部分由若干个节点紧密排列构成，每个节点也由三部分构成，分别是：
prev_entry_length：编码前置节点的长度，用于从后往前遍历
encoding：编码属性
contents：负责保存节点的值
prev_entry_length ： ziplist在编码前置节点长度的时候，采用以下规则：
如果前置节点的长度小于254字节，那么采用1个字节来保存这个长度值
如果前置节点的长度大于254字节，则采用5个字节来保存这个长度值，其中，第一个字节被设置为0xFE(254)，用于表示该长度大于254字节，后面四个字节则用来存储前置节点的长度值
encoding ： 记录节点的content 属性所保存数据类型以及长度
content : 负责保存节点的值，节点的值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定
- 保存 ziplist 节点信息的结构
typedef struct zlentry {
// prevrawlen ：前置节点的长度
// prevrawlensize ：编码 prevrawlen 所需的字节大小
unsigned int prevrawlensize, prevrawlen;
// len ：当前节点值的长度
// lensize ：编码 len 所需的字节大小
unsigned int lensize, len;
// 当前节点 header 的大小
// 等于 prevrawlensize + lensize
unsigned int headersize;
// 当前节点值所使用的编码类型
unsigned char encoding;
// 指向当前节点的指针
unsigned char *p;
} zlentry;
ziplist基本操作
1.创建空ziplist
unsigned char *ziplistNew(void) {
// ZIPLIST_HEADER_SIZE 是 ziplist 表头的大小
// 1 字节是表末端 ZIP_END 的大小
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
// 为表头和表末端分配空间
unsigned char *zl = zmalloc(bytes);
// 初始化表属性
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);/ 设定ziplist所占的字节数，如有必要进行大小端转换
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);// 设定尾节点相对头部的偏移量
ZIPLIST_LENGTH(zl) = 0;// 设定ziplist内的节点数
// 设置表末端
zl[bytes-1] = ZIP_END;
return zl;
}
2.插入节点
将长度为 slen 的字符串 s 推入到 zl 中
// ziplist插入节点只能往头或者尾部插入
// zl: 待插入的ziplist
// s，slen: 待插入节点和其长度
// where: 带插入的位置，0代表头部插入，1代表尾部插入
//值为 ZIPLIST_HEAD 时，将新值推入到表头。否则，将新值推入到表末端。 函数的返回值为添加新值后的 ziplist 。
// T = O(N^2)
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
unsigned char *p;
// 获取待插入位置的指针
p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
return __ziplistInsert(zl,p,s,slen);
}