压缩链表简介
压缩列表(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的类型大小
连锁更新
前面说过, 每个节点的 prevrawlen 属性都记录了前一个节点的长度:
- 如果前一节点的长度小于 254 字节, 那么 prevrawlen 属性需要用 1 字节长的空间来保存这个长度值。
- 如果前一节点的长度大于等于 254 字节, 那么 prevrawlen 属性需要用 5 字节长的空间来保存这个长度值。
因为连锁更新在最坏情况下需要对压缩列表执行 N
次空间重分配操作, 而每次空间重分配的最坏复杂度为 O(N)