“Better code, better life. ”
Redis
数据结构–压缩列表
压缩列表(
ziplist
)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么是小整数值,要么就是长度比较短的字符串,那么Redis
就会选择使用压缩列表来做列表键的底层实现。
ziplist
是由一系列特殊编码的内存块构成的列表, 一个 ziplist
可以包含多个节点(entry), 每个节点可以保存一个长度受限的字符数组(不以 \0
结尾的 char
数组)或者整数, 包括:
-
字符数组
长度小于等于
63
(2^6−1)字节的字符数组长度小于等于
16383
(2^14−1) 字节的字符数组长度小于等于
4294967295
(2^32−1)字节的字符数组 -
整数
4
位长,介于0
至12
之间的无符号整数1
字节长,有符号整数3
字节长,有符号整数int16_t
类型整数int32_t
类型整数int64_t
类型整数
本章先介绍 ziplist
的组成结构, 以及 ziplis
t 节点的编码方式。 再介绍 ziplist
的添加操作和删除操作的执行过程, 以及这两种操作可能引起的连锁更新现象。 最后介绍 ziplist
的遍历方法和节点查找方式。
组成结构
Redis
中没有对ziplist
单独定一个一个结构体,它是一个纯粹的内存映射,比较类似TCP数据包的格式,根据数据包固定长度的header来解析整个结构。ziplist
主要有header,entries,end三个部分。其中header和end长度是固定的,而每个entry的长度根据存储的内容而定。
下图展示了一个 ziplist
的典型分布结构:
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
图中各个域的作用如下:
域 | 长度/类型 | 域的值 |
---|---|---|
zlbytes |
uint32_t |
整个 ziplist 占用的内存字节数,对 ziplist 进行内存重分配,或者计算末端时使用。 |
zltail |
uint32_t |
到达 ziplist 表尾节点的偏移量。 通过这个偏移量,可以在不遍历整个 ziplist 的前提下,弹出表尾节点。 |
zllen |
uint16_t |
ziplist 中节点的数量。 当这个值小于 UINT16_MAX (65535 )时,这个值就是 ziplist 中节点的数量; 当这个值等于 UINT16_MAX 时,节点的数量需要遍历整个 ziplist 才能计算得出。 |
entryX |
? |
ziplist 所保存的节点,各个节点的长度根据内容而定。 |
zlend |
uint8_t |
255 的二进制值 1111 1111 (UINT8_MAX ) ,用于标记 ziplist 的末端。 |
为了方便地取出 ziplist
的各个域以及一些指针地址, ziplist
模块定义了以下宏:
宏 | 作用 | 算法复杂度 |
---|---|---|
ZIPLIST_BYTES(ziplist) |
取出 zlbytes 的值 |
θ(1) |
ZIPLIST_TAIL_OFFSET(ziplist) |
取出 zltail 的值 |
θ(1) |
ZIPLIST_LENGTH(ziplist) |
取出 zllen 的值 |
θ(1) |
ZIPLIST_HEADER_SIZE |
返回 ziplis header 部分的长度,总是固定的 10 字节 |
θ(1) |
ZIPLIST_ENTRY_HEAD(ziplist) |
返回到达 iplist 第一个节点(表头)的地址 |
θ(1) |
ZIPLIST_ENTRY_TAIL(ziplist) |
返回到达 ziplist 最后一个节点(表尾)的地址 |
θ(1) |
ZIPLIST_ENTRY_END(ziplist) |
返回 ziplist 的末端,也即是 zlend 之前的地址 |
θ(1) |
因为 ziplist
header 部分的长度总是固定的(4
字节 + 4
字节 + 2
字节), 因此将指针移动到表头节点的复杂度为常数时间; 除此之外, 因为表尾节点的地址可以通过 zltail
计算得出, 因此将指针移动到表尾节点的复杂度也为常数时间。
节点结构
Redis
中定义了一个zlentry
的结构,但正如注释中所说,这并不是实际存储的结构,只是一个辅助用的结构。
/* We use this function to receive information about a ziplist entry.
* Note that this is not how the data is actually encoded, is just what we
* get filled by a function in order to operate more easily. */
typedef struct zlentry {
unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
unsigned int prevrawlen; /* Previous entry len. */
unsigned int lensize; /* Bytes used to encode this entry type/len.
For example strings have a 1, 2 or 5 bytes
header. Integers always use a single byte.*/
unsigned int len; /* Bytes used to represent the actual entry.
For strings this is just the string length
while for integers it is 1, 2, 3, 4, 8 or
0 (for 4 bit immediate) depending on the
number range. */
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
the entry encoding. However for 4 bits
immediate integers this can assume a range
of values and must be range-checked. */
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
一个 ziplist
可以包含多个节点,每个节点可以划分为以下几个部分:
area |<------------------- entry -------------------->|
+------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
+------------------+----------+--------+---------+
以下几个小节将分别对这个四个部分进行介绍。
pre_entry_length
pre_entry_length
记录了前一个节点的长度,通过这个值,可以进行指针计算,从而跳转到上一个节点。
area |<---- previous entry --->|<--------------- current entry ---------------->|
size 5 bytes 1 byte ? ? ?
+-------------------------+-----------------------------+--------+---------+
component | ... | pre_entry_length | encoding | length | content |
| | | | | |
value | | 0000 0101 | ? | ? | ? |
+-------------------------+-----------------------------+--------+---------+
^ ^
address | |
p = e - 5 e
上图展示了如何通过一个节点向前跳转到另一个节点: 用指向当前节点的指针 e
, 减去 pre_entry_length
的值(0000 0101
的十进制值, 5
), 得出的结果就是指向前一个节点的地址 p
。
根据编码方式的不同, pre_entry_length
域可能占用 1
字节或者 5
字节:
1
字节:如果前一节点的长度小于254
字节,便使用一个字节保存它的值。5
字节:如果前一节点的长度大于等于254
字节,那么将第1
个字节的值设为254
,然后用接下来的4
个字节保存实际长度。
作为例子, 以下是个长度为 1
字节的 pre_entry_length
域, 域的值为 128
(二进制为 1000 0000
):
area |<------------------- entry -------------------->|
size 1 byte ? ? ?
+------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | 1000 0000 | | | |
+------------------+----------+--------+---------+
而以下则是个长度为 5 字节的 pre_entry_length
域, 域的第一个字节被设为 254
的二进制 1111 1110
, 而之后的四个字节则被设置为 10086
的二进制 10 0111 0110 0110
(多余的高位用 0
补完):
area |<------------------------------ entry ---------------------------------->|
size 5 bytes ? ? ?
+-------------------------------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
| | | | |
| 11111110 00000000000000000010011101100110 | ? | ? | ? |
+-------------------------------------------+----------+--------+---------+
|<------->|<------------------------------->|
1 byte 4 bytes
encoding 和 length
encoding
和 length
两部分一起决定了 content
部分所保存的数据的类型(以及长度)。
其中, encoding
域的长度为两个 bit , 它的值可以是 00
、 01
、 10
和 11
:
00
、01
和10
表示content
部分保存着字符数组。11
表示content
部分保存着整数。
以 00
、 01
和 10
开头的字符数组的编码方式如下:
编码 | 编码长度 | content 部分保存的值 |
---|---|---|
00bbbbbb |
1 byte | 长度小于等于 63 字节的字符数组。 |
01bbbbbb xxxxxxxx |
2 byte | 长度小于等于 16383 字节的字符数组。 |
10____ aaaaaaaa bbbbbbbb cccccccc dddddddd |
5 byte | 长度小于等于 4294967295 的字符数组。 |
表格中的下划线 _
表示留空,而变量 b
、 x
等则代表实际的二进制数据。为了方便阅读,多个字节之间用空格隔开。
11
开头的整数编码如下:
编码 | 编码长度 | content 部分保存的值 |
---|---|---|
11000000 |
1 byte | int16_t 类型的整数 |
11010000 |
1 byte | int32_t 类型的整数 |
11100000 |
1 byte | int64_t 类型的整数 |
11110000 |
1 byte | 24 bit 有符号整数 |
11111110 |
1 byte | 8 bit 有符号整数 |
1111xxxx |
1 byte | 4 bit 无符号整数,介于 0 至 12 之间 |
content
content
部分保存着节点的内容,类型和长度由 encoding
和 length
决定。
以下是一个保存着字符数组 hello world
的节点的例子:
area |<---------------------- entry ----------------------->|
size ? 2 bit 6 bit 11 byte
+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | ? | 00 | 001011 | hello world |
+------------------+----------+--------+---------------+
encoding
域的值 00
表示节点保存着一个长度小于等于 63 字节的字符数组, length
域给出了这个字符数组的准确长度 —— 11
字节(的二进制 001011
), content
则保存着字符数组值 hello world
本身(为了方便表示, content
部分使用字符而不是二进制表示)。
以下是另一个节点,它保存着整数 10086
:
area |<---------------------- entry ----------------------->|
size ? 2 bit 6 bit 2 bytes
+------------------+----------+--------+---------------+
component | pre_entry_length | encoding | length | content |
| | | | |
value | ? | 11 | 000000 | 10086 |
+------------------+----------+--------+---------------+
encoding
域的值 11
表示节点保存的是一个整数; 而 length
域的值 000000
表示这个节点的值的类型为 int16_t
; 最后, content
保存着整数值 10086
本身(为了方便表示, content
部分用十进制而不是二进制表示)。
ziplist
的创建
/* The size of a ziplist header: two 32 bit integers for the total
* bytes count and last item offset. One 16 bit integer for the number
* of items field. */
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
/* Size of the "end of ziplist" entry. Just one byte. */
#define ZIPLIST_END_SIZE (sizeof(uint8_t))
/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
unsigned char *zl = zmalloc(bytes);
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = 0;
zl[bytes-1] = ZIP_END;
return zl;
}
函数 ziplistNew
用于创建一个新的空白 ziplist
,这个 ziplist
可以表示为下图:
area |<---- ziplist header ---->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 1 byte
+---------+--------+-------+-----------+
component | zlbytes | zltail | zllen | zlend |
| | | | |
value | 1011 | 1010 | 0 | 1111 1111 |
+---------+--------+-------+-----------+
^
|
ZIPLIST_ENTRY_HEAD
&
address ZIPLIST_ENTRY_TAIL
&
ZIPLIST_ENTRY_END
空白 ziplist
的表头、表尾和末端处于同一地址。
创建了 ziplist
之后, 就可以往里面添加新节点了, 根据新节点添加位置的不同, 这个工作可以分为两类来进行:
- 将节点添加到
ziplist
末端:在这种情况下,新节点的后面没有任何节点。 - 将节点添加到某个/某些节点的前面:在这种情况下,新节点的后面有至少一个节点。
添加新节点到末尾
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
unsigned char *p;
p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
return __ziplistInsert(zl,p,s,slen);
}
/* Insert item at "p". */
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /* initialized to avoid warning. Using a value
that is easy to see if for some reason
we use it uninitialized. */
zlentry tail;
/* Find out prevlen for the entry that is inserted. */
if (p[0] != ZIP_END) {
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
prevlen = zipRawEntryLength(ptail);
}
}
/* See if the entry can be encoded */
if (zipTryEncoding(s,slen,&value,&encoding)) {
/* 'encoding' is set to the appropriate integer encoding */
reqlen = zipIntSize(encoding);
} else {
/* 'encoding' is untouched, however zipStoreEntryEncoding will use the
* string length to figure out how to encode it. */
reqlen = slen;
}
/* We need space for both the length of the previous entry and
* the length of the payload. */
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
/* When the insert position is not equal to the tail, we need to
* make sure that the next entry can hold this entry's length in
* its prevlen field. */
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
/* Store offset because a realloc may change the address of zl. */
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
p = zl+offset;
/* Apply memory move when necessary and update tail offset. */
if (p[0] != ZIP_END) {
/* Subtract one because of the ZIP_END bytes */
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
/* This element will be the new tail. */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
/* Write the entry */
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
将新节点添加到 ziplist
的末端需要执行以下三个步骤:
- 记录到达
ziplist
末端所需的偏移量(因为之后的内存重分配可能会改变ziplist
的地址,因此记录偏移量而不是保存指针) - 根据新节点要保存的值,计算出编码这个值所需的空间大小,以及编码它前一个节点的长度所需的空间大小,然后对
ziplist
进行内存重分配。 - 设置新节点的各项属性:
pre_entry_length
、encoding
、length
和content
。 - 更新
ziplist
的各项属性,比如记录空间占用的zlbytes
,到达表尾节点的偏移量zltail
,以及记录节点数量的zllen
。
举个例子,假设现在要将一个新节点添加到只含有一个节点的 ziplist
上,程序首先要执行步骤 1 ,定位 ziplist
的末端:
area |<---- ziplist header ---->|<--- entries -->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 1 bytes
+---------+--------+-------+----------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | zlend |
| | | | | |
value | 10000 | 1010 | 1 | ? | 1111 1111 |
+---------+--------+-------+----------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
然后执行步骤 2 ,程序需要计算新节点所需的空间:
假设我们要添加到节点里的值为字符数组 hello world
, 那么保存这个值共需要 12 字节的空间:
- 11 字节用于保存字符数组本身;
- 另外 1 字节中的 2 bit 用于保存类型编码
00
, 而其余 6 bit 则保存字符数组长度11
的二进制001011
。
另外,节点还需要 1 字节, 用于保存前一个节点的长度 5
(二进制 101
)。
合算起来,为了添加新节点, ziplist 总共需要多分配 13 字节空间。 以下是分配完成之后, ziplist 的样子:
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 10000 | 1010 | 1 | ? | pre_entry_length | 1111 1111 |
| | | | | ? | |
| | | | | | |
| | | | | encoding | |
| | | | | ? | |
| | | | | | |
| | | | | length | |
| | | | | ? | |
| | | | | | |
| | | | | content | |
| | | | | ? | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
步骤三,更新新节点的各项属性(为了方便表示, content
的内容使用字符而不是二进制来表示):
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 10000 | 1010 | 1 | ? | pre_entry_length | 1111 1111 |
| | | | | 101 | |
| | | | | | |
| | | | | encoding | |
| | | | | 00 | |
| | | | | | |
| | | | | length | |
| | | | | 001011 | |
| | | | | | |
| | | | | content | |
| | | | | hello world | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^
| |
address ZIPLIST_ENTRY_HEAD ZIPLIST_ENTRY_END
&
ZIPLIST_ENTRY_TAIL
最后一步,更新 ziplist 的 zlbytes
、 zltail
和 zllen
属性:
area |<---- ziplist header ---->|<------------ entries ------------>|<-- end -->|
size 4 bytes 4 bytes 2 bytes 5 bytes 13 bytes 1 bytes
+---------+--------+-------+----------------+------------------+-----------+
component | zlbytes | zltail | zllen | entry 1 | entry 2 | zlend |
| | | | | | |
value | 11101 | 1111 | 10 | ? | pre_entry_length | 1111 1111 |
| | | | | 101 | |
| | | | | | |
| | | | | encoding | |
| | | | | 00 | |
| | | | | | |
| | | | | length | |
| | | | | 001011 | |
| | | | | | |
| | | | | content | |
| | | | | hello world | |
| | | | | | |
+---------+--------+-------+----------------+------------------+-----------+
^ ^ ^
| | |
address | ZIPLIST_ENTRY_TAIL ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_HEAD
到这一步,添加新节点到表尾的工作正式完成。
插入新节点到某个节点前面
比起将新节点添加到 ziplist 的末端, 将一个新节点添加到某个/某些节点的前面要复杂得多, 因为这种操作除了将新节点添加到 ziplist 以外, 还可能引起后续一系列节点的改变。
举个例子,假设我们要将一个新节点 new
添加到节点 prev
和 next
之间:
add new entry here
|
V
+----------+----------+----------+----------+----------+
| | | | | |
| prev | next | next + 1 | next + 2 | ... |
| | | | | |
+----------+----------+----------+----------+----------+
程序首先为新节点扩大 ziplist 的空间:
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | ??? | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
|<-------->|
expand
space
然后设置 new
节点的各项值 —— 到目前为止,一切都和前面介绍的添加操作一样:
set value,
property,
length,
etc.
|
v
+----------+----------+----------+----------+----------+----------+
| | | | | | |
| prev | new | next | next + 1 | next + 2 | ... |
| | | | | | |
+----------+----------+----------+----------+----------+----------+
现在,新的 new
节点取代原来的 prev
节点, 成为了 next
节点的新前驱节点, 不过, 因为这时 next
节点的 pre_entry_length
域编码的仍然是 prev
节点的长度, 所以程序需要将 new
节点的长度编码进 next
节点的 pre_entry_length
域里, 这里会出现三种可能:
next
的pre_entry_length
域的长度正好能够编码new
的长度(都是 1 字节或者都是 5 字节)next
的pre_entry_length
只有 1 字节长,但编码new
的长度需要 5 字节next
的pre_entry_length
有 5 字节长,但编码new
的长度只需要 1 字节
对于情况 1 和 3 , 程序直接更新 next
的 pre_entry_length
域。
如果是第二种情况, 那么程序必须对 ziplist 进行内存重分配, 从而扩展 next
的空间。 然而,因为 next
的空间长度改变了, 所以程序又必须检查 next
的后继节点 —— next+1
, 看它的 pre_entry_length
能否编码 next
的新长度, 如果不能的话,程序又需要继续对 next+1
进行扩容。。。
这就是说, 在某个/某些节点的前面添加新节点之后, 程序必须沿着路径挨个检查后续的节点,是否满足新长度的编码要求, 直到遇到一个能满足要求的节点(如果有一个能满足,则这个节点之后的其他节点也满足), 或者到达 ziplist 的末端 zlend
为止, 这种检查操作的复杂度为 O(N2)O(N2) 。
不过,因为只有在新添加节点的后面有连续多个长度接近 254 的节点时, 这种连锁更新才会发生, 所以可以普遍地认为, 这种连锁更新发生的概率非常小, 在一般情况下, 将添加操作看成是 O(N)O(N) 复杂度也是可以的。
执行完这三种情况的其中一种后, 程序更新 ziplist
的各项属性, 至此,添加操作完成。
小结
-
ziplist
是由一系列特殊编码的内存块构成的列表,可以保存字符数组或整数值,同时是哈希键、列表键和有序集合键的底层实现之一。 -
ziplist
典型分布结构如下:area |<---- ziplist header ---->|<----------- entries ------------->|<-end->| size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte +---------+--------+-------+--------+--------+--------+--------+-------+ component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend | +---------+--------+-------+--------+--------+--------+--------+-------+ ^ ^ ^ address | | | ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END | ZIPLIST_ENTRY_TAIL
-
ziplist
节点的分布结构如下:area |<------------------- entry -------------------->| +------------------+----------+--------+---------+ component | pre_entry_length | encoding | length | content | +------------------+----------+--------+---------+
-
添加和删除 ziplist 节点有可能会引起连锁更新,因此,添加和删除操作的最坏复杂度为 O(N^2) ,不过,因为连锁更新的出现概率并不高,所以一般可以将添加和删除操作的复杂度视为 O(N)。