Redis从入门到精通【高阶篇】之底层数据结构压缩列表(ZipList)详解

2023-06-30

节点列表数据结构

👏简介：大家好，我是冰点，从业11年，目前在物流独角兽企业从事技术管理和架构设计方面工作，之前的把博客作为技术流水账在写。现在准备把多年的积累整理一下，成体系的分享给大家，也算是对多年开发生涯的总结。如果你在工作和学习中遇到问题也可反馈给我(iceicepip)，路漫漫其修远兮，吾将上下而求索。&

👏 简介：大家好，我是冰点，从业11年，目前在物流独角兽企业从事技术管理和架构设计方面工作，之前的把博客作为技术流水账在写。现在准备把多年的积累整理一下，成体系的分享给大家，也算是对多年开发生涯的总结。如果你在工作和学习中遇到问题也可反馈给我(iceicepip)，路漫漫其修远兮，吾将上下而求索。

🏳️‍🌈2023计划：
🚩1. 将多年来整理的Redis学习和实践笔记整理并发布成专栏。
🚩2. 将最近2年在groovy实践应用上的沉淀的初稿，发布成书籍。
🚩3. 将多年来整理的MySQL学习研究笔记整理并发布成专栏。
🚩4. 根据技术交流群答疑的问题，整理成博客文章发布分享。

文章目录

- 1. 压缩列表的结构
- 2. 压缩列表的操作
- 3. 压缩列表的优缺点
- - 3.1优点：
  - 3.2缺点：
- 4. 总结
- 5. 推荐阅读

前面的Redis从入门到精通的基础篇和进阶篇都是在使用层面和概念层面，本章节，我们了解一下redis的底层数据结构，上几个章节，我们讲了SDS,字典。本章节我们聊一下ZipList。

压缩列表（ZipList）就是redis为了节约内存而设计开发的数据结构，并且作为列表键和哈希键的底层实现之一。Redis中的压缩列表（ZipList）是一种特殊的数据结构，用于存储一系列的连续元素。ZipList是Redis中的底层数据结构之一，常用于存储列表和哈希表等数据类型的底层实现。在本文中，我们将深入了解Redis中的压缩列表，包括ZipList的结构和操作等。

1. 压缩列表的结构

Redis中的压缩列表（ZipList）是由一系列的节点（entry）组成的。每个节点可以是一个字节数组（byte array）、一个整数或者一个指针。在ZipList中，每个节点的大小是不固定的，取决于节点所包含的数据类型和数据大小。ZipList中节点的个数也是不固定的，可以根据需要动态增加或减少。

ZipList的结构如下图所示：

+--------+--------+--------+--------+--+-----+
| zlbytes| zltail | zllen  |entry1  |..|entryN|
+--------+--------+--------+--------+--+-----+
1
2
3

zlbytes字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数
zltail字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量. 用于快速定位最后一个entry, 以快速完成pop等操作
zllen字段的类型是uint16_t, 它指的是整个ziplit中entry的数量. 这个值只占2bytes（16位）: 如果ziplist中entry的数目小于65535(2的16次方), 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到.
zlend是一个终止字节, 其值为全F, 即0xff. ziplist保证任何情况下, 一个entry的首字节都不会是255

其中，zlbytes是压缩列表的长度（包括所有的字节），zltail是指向压缩列表尾部的指针，zllen是压缩列表中节点的个数，entry1到entryN是压缩列表中的所有节点。

###节点结构
在压缩列表中，每个节点的结构如下：

+--------+--------+
| prevlen| encoding| data  |
+--------+--------+
1
2
3

prevlen是前一个节点的长度（单位为字节），encoding是数据的编码方式，data是节点的实际数据。在压缩列表中，prevlen和encoding都是可选的。当节点的前一个节点的长度小于254字节时，prevlen字段被省略，encoding字段存储在数据之前，否则prevlen字段占用5个字节，encoding字段存储在prevlen后面的5个字节中。

根据不同的数据类型，压缩列表中节点的编码方式也有所不同，下面是常用的节点编码方式：

字节数组（byte array）：

+--------+--------+---------------+
| prevlen| 0xc000 |    length     |
+--------+--------+---------------+
|              data               |
+---------------------------------+
1
2
3
4
5

其中，0xc000是一个特殊的编码方式，用于标识节点存储的是字节数组。length是字节数组的长度，data是字节数组的实际数据。

整数：

+--------+--------+--------+
| prevlen|  int   |   int  |
+--------+--------+--------+
1
2
3

其中，int是一个整数，可以是8位、16位或32位的有符号整数。

指针：

+--------+--------+--------+
| prevlen|  0x01  |  ptr   |
+--------+--------+--------+
1
2
3

其中，0x01是一个特殊的编码方式，用于标识节点存储的是指针。ptr是一个指针，可以指向任意的内存地址。

2. 压缩列表的操作

Redis中的压缩列表支持以下常用的操作：

压缩列表的创建

unsigned char *zl = ziplistNew();
1

压缩列表的添加

zl = ziplistPush(zl, s, len, ZIPLIST_TAIL);
1

其中，s是一个字节数组，len是字节数组的长度，ZIPLIST_TAIL表示在压缩列表的尾部添加节点。

zl = ziplistPushInt(zl, value);
1

其中，value是一个整数，表示在压缩列表的尾部添加整数节点。

压缩列表的删除

zl = ziplistDelete(zl, &p);
1

其中，p是一个指向要删除的节点的指针。

压缩列表的遍历

unsigned char *p = ziplistIndex(zl, index);
unsigned char *entry = NULL;
unsigned int entry_len = 0;
long long entry_int = 0;
int ret = ziplistGet(p, &entry, &entry_len, &entry_int);
1
2
3
4
5

其中，index是节点的下标，p是指向节点的指针，entry是节点的数据（字节数组或整数），entry_len是字节数组的长度，entry_int是整数的值，ret表示节点的数据类型（字节数组或整数）。

压缩列表的长度

unsigned int ziplistLen(unsigned char *zl);
1

以上是常用的压缩列表操作，还有其他的操作可以参考Redis源代码中的ziplist.h和ziplist.c文件。

3. 压缩列表的优缺点

3.1优点：

紧凑的存储结构使得压缩列表的空间占用更小，可以在一定程度上减少内存碎片的发生。
压缩列表支持动态增加和删除节点，可以随着数据的增长而自动扩容或缩容，不需要预先分配空间。
压缩列表的节点采用紧凑的存储方式，使得节点访问和遍历的效率较高。同时，压缩列表支持从头和尾部两个方向同时遍历节点。

3.2缺点：

节点大小不固定，当节点的大小随着数据的增长而不断变化时，可能会导致内存碎片的发生，从而增加了内存分配和释放的成本。
压缩列表不支持快速的节点插入和删除操作，因为在插入或删除节点时，需要对后面的节点进行移动，会导致频繁的内存复制操作，从而影响性能。如果需要频繁进行插入和删除操作，建议使用链表等其他数据结构。
压缩列表的节点的数据类型和大小有限制，不适合存储大量的大型数据。例如，压缩列表最大支持512MB的大小，单个节点最大支持64KB的大小，单个整数节点最大支持32位的有符号整数。如果需要存储大量的大型数据，建议使用其他数据结构，例如哈希表或有序集合。

4. 总结

本文详细介绍了Redis中的压缩列表（ZipList），包括ZipList的结构和操作等。压缩列表是Redis中的底层数据结构之一，常用于存储列表和哈希表等数据类型的底层实现。压缩列表具有紧凑的存储结构、支持动态增加和删除节点、支持快速的节点访问和遍历等优点，但也有节点大小不固定、不支持快速的节点插入和删除操作等缺点。在实际应用中，需要根据具体的需求选择合适的数据结构来存储数据。