今天我们来记一下压缩列表(ZIPLIST),压缩列表在Redis的五种数据结构中用的是最多的一个,可以从Redis(版本4.0)日记--数据类型和底层编码这篇日记中知道,使用压缩列表为底层编码数据结构的有list、zset、hash这三种数据类型,而且从版本3.2开始使用的quicklist,也是结合了ziplist和linkedlist两种数据结构来进行list优化的。
数据结构及详细解析全在图中了:放大观看更清晰哦

压缩列表数据结构?
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>压缩列表里包括以上结构:uint32_t zlbytes:记录整个压缩列表占用的字节数:在对整个压缩列表进行内存重分配或者计算zlend时使用uint32_t zltail:一个偏移量,记录压缩列表表尾节点距离压缩列表开始地址有多少字节:用于计算表尾节点地址uint16_t zllen:当小于uint16_max(65535)时可以直接表示压缩列表节点数量,当大于uint16_max(65535)时,节点数量需要遍历整个压缩列表才能得出若干entry: 根据存储的内容决定uint8_t zlend:固定值0xFF(255),用于标记压缩列表末端
压缩列表节点数据结构?
/* 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 previos 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 bytesheader. Integers always use a single byte.*/unsigned int len; /* Bytes used to represent the actual entry.For strings this is just the string lengthwhile for integers it is 1, 2, 3, 4, 8 or0 (for 4 bit immediate) depending on thenumber range. */unsigned int headersize; /* prevrawlensize + lensize. */unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending onthe entry encoding. However for 4 bitsimmediate integers this can assume a rangeof values and must be range-checked. */unsigned char *p; /* Pointer to the very start of the entry, thatis, this points to prev-entry-len field. */} zlentry;
文章转载自无限递归,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。




