Redis 压缩列表

压缩链表简介

压缩列表(ziplist)是List类型和Hash类型的底层编码实现之一。比如List底层的编码有两种：ziplist和linkedlist，hash类型也有两种：ziplist和hashtable。这两种Redis的基本类型都用到了ziplist编码。

为什么List和Hash都用到了ziplist去做底层实现呢？因为ziplist对空间的利用节省到了极致，先来看下ziplist的数据结构，在源码ziplist.c文件中注释中可以看到，但是我并没有找到相关结构体的定义，只找到了entry节点的结构体定义。ziplist是个连续的entry节点组成的列表。

压缩列表数据结构

ziplist结构：

<zlbytes><zltail><zllen><entry><entry><zlend>

zlbytes：记录着ziplist总大小(byte)
zltail：ziplist表尾的entry节点距ziplist起始位置有多少个字节，用zltail通过计算可以很快得出ziplist表尾的位置
zllen：压缩列表中entry节点的个数
entry：节点，在ziplist中连续排列
zlend：用于标记ziplist的结束位置，相当于字符串用'\0'来标记结束位置

entry结构：

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;	// prevrawlen前一个entry的长度
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;	// p的实际类型
    unsigned char *p;	// 节点的值
} zlentry;

p：节点内容，节点可以是个字节数组或者整数，它的类型和长度由encoding属性决定
prevrawlen：前一个entry的长度，如果前一节点的长度小于 254 字节，那么 prevrawlen 属性的长度为 1 字节，如果前一节点的长度大于等于 254 字节，那么prevrawlen属性的长度为 5 字节
encoding：p属性的实际类型，这个是ziplist节省空间的关键，如果可以动态调整p的类型大小