Redis源码学习：ziplist的数据结构和连锁更新问题

ziplist

ziplist 是 Redis 中一种紧凑型的列表结构，专门用来存储元素数量少且每个元素较小的数据。它是一个双端链表， 可以在任意一端进行压入/弹出操作，并且该操作的时间复杂度为O(1)。

ziplist数据结构

...

每个元素的结构

ziplist的不足

1、查找复杂度高

虽然ziplist对头尾的操作可以很快，但是，当要查找列表中间的元素时，ziplist 就得从列表头或列表尾遍历才行。而当 ziplist 保存的元素过多时，查找中间数据的复杂度就会增加。因此，ziplist的最大存储元素数量和每个元素的大小直接影响其性能。

• hash-max-ziplist-entries：hash 类型元素数量超过指定数据后时候。使用 hash 存储， 否则使用压缩表。
• hash-max-ziplist-value： hash 类型元素长度超过指定数据后时候。 使用 hash 存储，否则使用压缩链表。
• zset-max-ziplist-entries：zset 类型 压缩列表 ziplist 最大限制元素数。超过指定值将会使用跳表 skiplist + dict 来存储。
• zset-max-ziplist-value：set 类型 压缩列表 ziplist 最大限制大小。超过指定将会使用跳表 skiplist+dict 来存储。

在Redis.conf文件中有默认配置：

# 最大元素个数
hash-max-ziplist-entries 512
# 元素最大字节数
hash-max-ziplist-value 64

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

2、连锁更新问题

由于ziplist 必须使用一块连续的内存空间来保存数据，所以当新插入一个元素时，ziplist 就需要计算其所需的空间大小，并申请相应的内存空间，假设有N个小于255字节的Entry，每一个Entry的pre_entry_len都可以用1个字节存储，现在要在中间插入新的Entry，长度大于254，此时pre_entry_len就需要5字节来存，后续的元素的prevlen字段也需要扩展，就会引起连锁更新的问题。这一系列操作，可以从 ziplist 的元素插入函数__ziplistInsert中看到。

到这里结束，希望本文对你有帮助。