Redis数据类型-Hash-存储结构之ziplist

ziplist（压缩列表）

ziplist 是一个经过特殊编码的双向链表，旨在提高内存效率。

它可以存储 字符串 或者 整数，存储整数时是采用整数的二进制而不是字符串形式存储。

他能在O(1)的时间复杂度下完成list两端的push和pop操作。

由于每个操作都需要重新分配 ziplist 使用的内存，因此实际复杂性与 ziplist 使用的内存量有关。

zlbytes

记录 ziplist 整个结构体的占用空间大小,占4个字节 32 位无符号整型。这个结构有个很大的用处，就是当需要修改 ziplist 时候不需要遍历即可知道其本身的大小。

zltail

记录整个压缩列表（ziplist）最后一个entry（数据）的偏移量，占4个字节，32位的无符号整形。所以尾部进行pop操作的时候不需要先遍历一次。

zllen

记录整个压缩列表的 entry 数量，占用2个字节，16位无符号整形，最多元素数目：(2^16)-1。备注：如果超过了，则zllen字段无法获取压缩列表元素的数目，此时需要通过遍历整个压缩列表才能获取到元素数目

entry

存储压缩列表（ziplist）元素的地方，可以是字节数或者整数。它下面又包含如下属性：

1. pre_entry_length ：记录了前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点。
2. encoding：数据的编码形式（字符串还是数字，长度是多少）
   1. encoding 域的长度为两个 bit ， 它的值可以是 00 、 01 、 10 和 11
   2. 00 、 01 和 10 表示 content 部分保存着字符数组
   3. 11 表示 content 部分保存着整数
3. length：存储数据的长度
4. content：实际存储的数据，它由encoding和length两部分一起决定了所保存的数据的类型以及长度

zlend

压缩列表（ziplist）的结尾，占一个字节，8位无符号整形。固定为：0xFF（255），为ziplist的结束标识

总结

1. ziplist是为了尽可能的节省存储空间，将数据进行紧凑的存储
2. 修改操作耗费性能：ziplist在内存中是高度紧凑的连续存储，这意味着它对修改并不友好，如果要对ziplist做修改类的操作，那就需重新分配新的内存来存储新的ziplist，代价很大
3. 添加和删除 ziplist 节点有可能会引起连锁更新，因此，添加和删除操作的最坏复杂度为 O(N^2)，不过，因为连锁更新的出现概率并不高，所以一般可以将添加和删除操作的复杂度视为 O(N) 。
4. 列表的节点之间并不是通过指针连接，而是记录上一个节点和本节点长度来寻址，内存占用较低。用当前的地址减去这个长度，就可以很容易的获取到了上一个节点的位置，通过一个一个节点向前回溯，来达到从表尾往表头遍历的操作
5. 优点：
   1. 节省内存
6. 缺点：
   1. 不能保存过多的元素，否则性能就会下降
   2. 不能保存过大的元素，否则容易导致内存重新分配，甚至引起连锁更新