redis 压缩链表
概述
压缩链表是相对于普通链表而言的
当普通链表的数据越来越多, 链表查询性能会低效
当存储的数据较少时, 使用链表存储会浪费空间
压缩链表本质上是一个字符串
压缩链表内存储的数据只能是 整型, 字符串
压缩链表结构
<zlbytes> <zltail> <zllen> <entry1> <entry2> .. <entryN> <zlend>
| 属性 | 用途 | 说明 | 长度 | 备注 |
|---|---|---|---|---|
| zlbytes | 压缩链表占用的内存总字节数 | 可以直接对内存大小进行调整, 无需遍历整个链表获取大小 | 32 位 | #define ZIPLIST_BYTES(zl) (*((uint32_t *)(zl))) |
| zltail | 压缩链表尾节点的偏移量 | 长度 1 字节, 0xFF; pop 操作无需遍历整个链表 | 32 位 | #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t *)((zl)+sizeof(uint32_t)))) |
| zllen | 压缩链表存储的节点总数 | zllen 大于 2^16 - 2 时, 需要遍历整个链表来获取长度 | 16 位 | #define ZIPLIST_LENGTH(zl) (*((uint16_t *)((zl)+sizeof(uint32_t) * 2))) |
| entryN | 节点 | |||
| zlend | 压缩链表结束符 | 0xFF | 8 位 | #define ZIP_END 255 |
-
entryN
-
header 头部
-
前置节点编码规则 (前置节点的长度, 从后向前遍历时用)
如果前置节点长度小于 ZIP_BEGIN 字节(254), 则使用 1 个字节表示长度
如果前置节点大于等于 ZIP_BEGIN 字节(254), 则使用 5 个字节表示长度
a) 第 1 个字节为 ZIP_BEGIN, 表示这是一个 5 字节长度
b) 之后的 4 个字节表示长度 -
当前节点编码规则 (当前节点的长度)
整数前 2 位为 1
编码长度为 1 字节
表示 说明 备注 1100 0000 表示 2 字节长度 0xc0 位或 0<<4 1101 0000 表示 4 字节长度 0xc0 位或 1<<4 1110 0000 表示 8 字节长度 0xc0 位或 2<<4 1111 0000 表示 3 字节长度 0xc0 位或 3<<4 1111 1110 表示 1 字节长度 0xfe 1111 xxxx (除去 0000, 1111) 表示 (xxxx - 1) 位长度 1111 1111 压缩链表结束符 字符串前 2 位不是 11
前 2 位用来表示字符串所占用的字节
编码长度为 1字节, 2字节, 5字节
表示 说明 备注 00pp pppp 1字节, 表示字符串长度小于等于 2^6 -1 前 2 位不用来表示长度 01pp pppp qqqq qqqq 2字节, 表示字符串长度小于等于 2^14 - 1 前 2 位不用来表示长度 10pp pppp qqqq qqqq ... 5字节, 表示字符串长度大于等于 2^14 前 2 位不用来表示长度
-
-
body 数据部分
// 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 对于长度的存储编码, 当要使用长度的时候对长度进行解码, 放于 entry 实体的 prevrawlen 与 len 均为实际的长度值, prevrawlensize 与 lensize 为对实际长度进行编码所占的字节数
-
ziplist 宏定义 (src/ziplist.c)
| 宏名称 | 作用 | 备注 |
|---|---|---|
| ZIP_END | 压缩链表尾部标识 | #define ZIP_END 255 |
| ZIP_BEGIN | 前置节点使用 5 字节表示长度的标识符 | #define ZIP_BIGLEN 254 |
| ZIP_STR_MASK | 字符串类型的掩码 | #define ZIP_STR_MASK 0xc0 |
| ZIP_INT_MASK | 整数类型的掩码 | #define ZIP_INT_MASK 0x30 |
| ZIP_STR_06B | 字符串编码类型 | #define ZIP_STR_06B (0 << 6) |
| ZIP_STR_14B | 字符串编码类型 | #define ZIP_STR_14B (1 << 6) |
| ZIP_STR_32B | 字符串编码类型 | #define ZIP_STR_32B (2 << 6) |
| ZIP_INT_16B | 整数编码类型 (2字节) | #define ZIP_INT_16B (0xc0 位或 0<<4) |
| ZIP_INT_32B | 整数编码类型 (4字节) | #define ZIP_INT_32B (0xc0 位或 1<<4) |
| ZIP_INT_64B | 整数编码类型 (8字节) | #define ZIP_INT_64B (0xc0 位或 2<<4) |
| ZIP_INT_24B | 整数编码类型 (3字节) | #define ZIP_INT_24B (0xc0 位或 3<<4) |
| ZIP_INT_8B | 整数编码类型 (1字节) | #define ZIP_INT_8B 0xfe |
| ZIP_INI_IMM_MASK | 对于 1111 xxxx 后4位表示编码类型的整数掩码 | #define ZIP_INT_IMM_MASK 0x0f |
| ZIP_INI_IMM_MIN | 4位整数编码的最小值 | #define ZIP_INT_IMM_MIN 0xf1 |
| ZIP_INI_IMM_MAX | 4位整数编码的最大值 | #define ZIP_INT_IMM_MAX 0xfd |
| ZIP_INI_IMM_VAL | 计算4位整数编码 | #define ZIP_INT_IMM_VAL(v) (v & ZIP_INT_IMM_MASK) |
| INT24_MAX | 24位整数编码的最大值 | #define INT24_MAX 0x7fffff |
| INT24_MIN | 24位整数编码的最小值 | #define INT24_MIN (-INT24_MAX - 1) |
| ZIP_IS_STR | 查看指定编码是否是字符串编码 | #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK) |
| ZIPLIST_BYTES | 获取压缩链表的 zlbytes 值 | #define ZIPLIST_BYTES(zl) (*((uint32_t *)(zl))) |
| ZIPLIST_TAIL_OFFSET | 获取压缩链表的 zltail 值 | #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t *)((zl)+sizeof(uint32_t)))) |
| ZIPLIST_LENGTH | 获取压缩链表的 zllen 值 | #define ZIPLIST_LENGTH(zl) (*((uint16_t *)((zl)+sizeof(uint32_t) * 2))) |
| ZIPLIST_HEADER_SIZE | 压缩链表表头的大小 | #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) |
| ZIPLIST_ENTRY_HEAD | 压缩链表头节点指针 | #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) |
| ZIPLIST_ENTRY_TAIL | 压缩链表尾节点指针 | #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) |
| ZIPLIST_ENTRY_END | 压缩链表末端 zlend 的指针 | #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1) |
| ZIPLIST_INCR_LENGTH | 增加压缩链表的 zlen 的值, 增加幅度为 incr | #define ZIPLIST_INCR_LENGTH(zl,incr) |
| ZIP_ENTRY_ENCODING | 从 ptr 中获取编码类型, 并将其存入 encoding | #define ZIP_ENTRY_ENCODING(ptr, encoding) |
| ZIP_DECODE_LENGTH | 从 ptr 中获取 encoding, lensize, len | #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) |
| ZIP_DECODE_PREVLENSIZE | 解码 ptr, 设置 prevlensize 的值 | #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) |
| ZIP_DECODE_PREVLEN | 解码 ptr, 设置 prevlensize, prevlen | #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) |
ziplist api (src/ziplist.c)
| 函数 | 作用 | 备注 |
|---|---|---|
| zipIntSize | 保存 encoding 所需的字节数 (仅针对整数编码类型) | static unsigned int zipIntSize(unsigned char encoding) |
| zipEncodeLength | 将长度 rawlen 按照 encoding 进行编码, 并存到指针 p 中 | static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) |
| zipPrevEncodeLength | 编码前置节点 len, 存入节点指针 p | static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) |
| zipPrevEncodeLengthForceLarge | 编码前置节点 len 用 5 个字节存储, 存入节点指针 p | static void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len) |
| zipPrevLenByteDiff | 计算编码 len 所需的字节数, 与原 p 中存储的 prevlensize 进行减法 | static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) |
| zipRawEntryLength | 返回节点所占用的字节数 | static unsigned int zipRawEntryLength(unsigned char *p) |
| zipTryEncoding | 尝试将字符串转换为整数, 若转换成功, 存储到 v, 并将编码方式存储到 encoding | static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) |
| zipSaveInteger | 以 encoding 指定的编码方式, 将整数值 value 写入到 p | static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) |
| zipLoadInteger | 以 encoding 指定的编码方式, 读取并返回 p 中的整数值 | static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) |
| zipEntry | 获取指定指针 p 的节点 | static zlentry zipEntry(unsigned char *p) |
| ziplistNew | 创建并返回一个新的 ziplist | unsigned char *ziplistNew(void) |
| ziplistResize | 调整 ziplist 到指定的 len 长度 | static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) |
| __ziplistCascadeUpdate | 当一个节点添加到某个节点之前时, 有可能相应节点的 header 空间不足够, 为了处理由此产生的迭代更新; 对于长度变小的收缩情况不做考虑 | static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) |
| __ziplistDelete | 在 zl 中, 从指定位置 p 开始, 连续删除 num 个节点 | static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) |
| __ziplistInsert | 将字符串 s 插入到 zl 的指定位置 p | static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) |
| ziplistPush | 向 zl 头部或尾部压入字符串 s | unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) |
| ziplistIndex | 根据给定的 index, 获取 zl 节点 | unsigned char *ziplistIndex(unsigned char *zl, int index) |
| ziplistNext | 返回给定节点 p 的下个节点 | unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) |
| ziplistPrev | 返回给定节点 p 的前置节点 | unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) |
| ziplistGet | 获取指定节点 p 的值, 若是字符串, 字符串指针存储在 *sstr, 字符串长度存储在 *slen; 若是整数, 将值存储在 *sval | unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) |
| ziplistInsert | 将字符串 s 插入到 zl 的指定位置 p | unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) |
| ziplistDelete | 删除 zl 中指定位置 p 的节点, 并更新 p | unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) |
| ziplistDeleteRange | 删除 zl 中从 index 开始, 连续 num 个节点 | unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) |
| ziplistCompare | 将 p 所指向的节点值与给定的字符串 sstr 进行比较, 相等返回1, 不相等返回0 | unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) |
| ziplistFind | 从指定节点 p 开始, 每次跳过 skip 个节点, 将节点值与字符串 vstr 比较, 找到相等的节点, 返回 | unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) |
| ziplistLen | 返回 zl 的节点数, 若节点数小于 2^16 - 2 时, 直接取 zllen, 若大于此值, 则进行遍历计算长度 | unsigned int ziplistLen(unsigned char *zl) |
| ziplistBlobLen | 返回 zl 占用的字节总数 zlbytes | size_t ziplistBlobLen(unsigned char *zl) |
| ziplistRepr | 打印 zl 的一些信息 (zlbytes, zllen, zltail, entryN) | void ziplistRepr(unsigned char *zl) |