当前位置：首页 > article >正文

【Redis数据结构】ziplist 压缩列表

article 2025/2/24 8:54:43

1. ziplist 简介

压缩列表（ziplist）是 redis 当中列表和哈希键的底层实现方式之一，若哈希键或者列表当中元素个数较少并且均为小整数和长度较短的字符串，那么 redis 就会把 ziplist 作为其底层实现

2. ziplist 底层结构

2.1 思考

redis 设计者为什么要使用 ziplist 这种结构，而不像一些主流编程语言中使用双向链表作为其实现呢？这是因为 redis 作为内存级数据库，对内存占用要求极为苛刻，因此 redis 设计者没有采用指针存储链接关系（因为指针占4/8字节），ziplist 使用顺序存储（借助特定比特位表示前后节点的长度达到节省内存的效果）

2.2 压缩列表数据结构

如上图所示， ziplist 包含以下几部分内容：

zlbytes：固定占用 4 字节，记录整个压缩列表占用的字节总数
zltail：固定占用 4 字节，记录尾节点（entryN）到压缩列表起始位置的字节总数
zllen：固定占用 2 字节，记录存储的节点个数
entryX：内存大小不定，由存储的内容决定
zlend：固定占用 1 字节，且为固定值 0xFF，用于标记压缩列表的结束

上图展示了一个 ziplist 的存储内容：

zlbytes：表示该 ziplist 结构一共占用 80 字节
zltail：表示 entry3 尾节点距离 ziplist 起始地址处一共占用 60 字节
zllen：表示一共存储了 3 个节点
zlend：固定 0xFF，表示结束

2.3 内部节点数据结构

每一个 entry 的内部结构如下图所示：

其中各个字段的含义如下：

previous_entry_length：存储大小为1字节或5字节，表示前一个节点占用的字节数
encoding：存储大小为1字节或2字节或5字节，表示编码方式以及内容占用的长度
content：实际存储的内容

2.3.1 previous_entry_length

该字段表示存储的上一个节点的长度，其中如果上一个节点长度 < 254 则使用 1 字节来存储，否则使用 5 字节存储（第一个字节使用固定的 0xFE，后面四个字节表示实际长度），凭借该字段就可以实现链表的反向查找

2.3.2 encoding

前面我们介绍过了，ziplist 既可以存储整数，也可以存储字符串等字节数组，那么应该如何来区分呢？只需要借助 encoding 的前两个比特位即可

case1：content 内容为字符串等字节数组

如果开头是 00 则表示 encoding 占用 1 字节，剩余 6 位为 content 的长度
如果开头是 01 则表示 encoding 占用 2 字节，剩余 14 位为 content 的长度
如果开头是 10 则表示 encoding 占用 5 字节，剩余 4 字节为 content 的长度

case2：content 内容为整数（此时 encoding 占用 1 字节）

如果是 11000000，则表示 content 整数类型为 int16_t
如果是 11010000，则表示 content 整数类型为 int32_t
如果是 11100000，则表示 content 整数类型为 int64_t
如果是 11110000，则表示 content 整数类型为 24 位有符号整数
如果是 11111110，则表示 content 整数类型为 8 位有符号整数
如果是 1111xxxx，则表示 content 实际内容为 xxxx 部分（此时无需content额外存储）

2.3.3 content

content 字段保存实际存储的值（有可能是字符串等字节数组，也可能是整数值）其数据类型和存储长度可以通过 encoding 字段得知

示例：假设某个 entry 内部 encoding 前8位为 00001011，请推断 content 的类型以及读取内容

根据开头前两位为00，可以得知存储的是字符串（字节数组）且 encoding 大小占用 1 字节，因此 content 的长度就是 11

3. ziplist 级联更新

前面我们介绍过：entry 当中的 previous_entry_length 保存着前一个节点的长度大小，如果小于 254 则使用 1 字节来存储，否则就使用 5 字节来存储

如图所示，假设现在 entry1、entry2、entry3的长度都介于 250 - 253 之间，由于 entry1 没有前一个节点，因此 entry1 的 previous_entry_length 占用 1 字节，但是现在我们向 entry1 前插入一个新节点（长度为255）此时 entry1 需要更新 previous_entry_length 为 5 字节空间，此时 entry2 同样需要更新字段长度。。。因此引发了后续级联的更新！！！