Redis数据结构-压缩列表

“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 的组成结构，以及 ziplist 节点的编码方式。再介绍 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)。

Redis数据结构-压缩列表

"Redis源码学习"