redis源码分析教程之压缩链表ziplist详解-创新互联

前言

压缩列表（ziplist）是由一系列特殊编码的内存块构成的列表，它对于Redis的数据存储优化有着非常重要的作用。这篇文章总结一下redis中使用非常多的一个数据结构压缩链表ziplist。该数据结构在redis中说是无处不在也毫不过分，除了链表以外，很多其他数据结构也是用它进行过渡的，比如前面文章提到的SortedSet。下面话不多说了，来一起看看详细的介绍吧。

一、压缩链表ziplist数据结构简介

首先从整体上看下ziplist的结构，如下图：

压缩链表ziplist结构图

可以看出字段很多，字节大小也不同，但这也就是压缩链表的精髓所在了，我们依次总结一下。

总结为ziplist的头跟尾，下面再总结一下重中之重的entry字段。

一般来说，一个entry由prevlen，encoding，entry-data三个字段组成，但当entry是个很小的整数时，会根据编码省略掉entry-data字段。下面依次进行总结：

首先是字段prevlen：表示前一个entry的长度，有两种编码方式。

• 当长度小于255字节时，用一个字节存储。
• 当长度大于等于255时，用五个字节进行存储，其中第一个字节会被设置为255表示前一个entry的长度由后面四个字节表示。

然后是字段encoding：它会根据当前元素内容的不同会采用不同的编码方式，如下：

1、如果元素内容为字符串，encoding的值分别为：

00xx xxxx ：00开头表示该字符串的长度用6个bit表示。

01xx xxxx | xxxx xxxx ：01开头表示字符串的长度由14bit表示，这14个bit采用大端存储。

1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10开头表示后续的四个字节为字符串长度，这32个bit采用大端存储。

2、如果元素内容为数字，encoding的值分别为：

1100 0000：表示数字占用后面2个字节。

1101 0000：表示数字占用后面4个字节。

1110 0000：表示数字占用后面8个字节。

1111 0000 ：表示数字占用后面3个字节。

1111 1110 ：表示数字占用后面1个字节。

1111 1111 ：表示压缩链表中最后一个元素（特殊编码）。

1111 xxxx ：表示只用后4位表示0~12的整数，由于0000，1110跟1111三种已经被占用，也就是说这里的xxxx四位只能表示0001~1101，转换成十进制就是数字1~13，但是redis规定它用来表示0~12，因此当遇到这个编码时，我们需要取出后四位然后减1来得到正确的值。

最后是字段entry-data：如果元素的值为字符串，则保存元素本身的值。如果元素的值为很小的数字（按上面编码规则即0~12），则没有该字段。

压缩链表的编码非常复杂，但这也正是该数据结构的精髓所在，一起来看一个例子吧：

注：这个例子是redis源码中提到的

//由元素2，5组成的压缩链表
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
 |  |  | | | |
 zlbytes zltail entries "2" "5" end
//字符串"Hello World"编码后的内容
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。