Redis数据结构——压缩列表

本文主要是介绍Redis数据结构——压缩列表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，且每个列表项要么是小整数值，要么是长度较短的字符串，Redis则使用压缩列表作为列表键的底层实现。当一个哈希键只包含少量键值对，且每个键值对要么是小整数值，要么是长度较短的字符串，Redis则使用压缩列表作为哈希键的底层实现。

1.压缩列表的数据结构

压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构，是为了节约内存开发的。，以下为压缩列表的组成部分：

• zlbytes：记录整个压缩列表占用的内存字节数，长度为4字节。
• zltail：记录压缩列表表尾节点距离压缩列表起始地址有多少字节，长度为4字节。
• zllen：记录压缩列表所有的节点数量，当这个属性的值小于UINT16_MAX时，属性的值即压缩列表节点数量，否则压缩列表的真实节点数量需要遍历整个压缩列表才能计算得出。长度为2字节。
• entryx：压缩列表包含的每个节点，长度不定。
• zlend：特殊值0xFF，用于标记压缩列表的末端。

每个压缩列表的节点可以保存一个字节数组或一个整数值。以下为压缩列表节点的组成部分：

• previous_entry_length：以字节为单位，记录了前一个节点的长度。该属性长度可以为1或5字节，当前一个节点长度小于254字节时，previous_entry_length属性长度为1字节；否则previous_entry_length属性长度为5字节。previous_entry_length属性使得获取当前节点的前一个节点的复杂度为O(1)。
• encoding：记录了节点content属性所保存数据的类型以及长度。
• content：保存节点的值。

2.连锁更新 

前面提到每个节点的previous_entry_length属性记录了前一个节点的长度，当前一个节点长度小于254字节时，previous_entry_length长度为1字节，否则previous_entry_length长度为5字节。当压缩列表的每个节点的长度介于250-253字节之间时，向压缩列表添加一个长度大于254的节点 ，其下一个节点的previous_entry_length属性长度仅为1字节，此时需要扩张为5字节，而这一操作又会引起下一个节点的previous_entry_length需要进行扩张...Redis将这种在特殊情况下产生的连续多次空间扩展操作称为连锁更新。

连锁更新在最坏情况下需要对压缩列表执行N次空间重分配，而每次重分配最坏复杂度为O(N)，因此连锁更新的最坏复杂度为O()。

虽然连锁更新的复杂度很高，但是造成性能问题的几率是很低的：

• 首先，压缩列表里要恰好有多个连续的、长度介于250-253字节之间的节点，连锁更新才可能被触发，但实际上这种情况不多见。
• 其次，只要被更新的节点不多，就不会对性能造成任何影响。

这篇关于Redis数据结构——压缩列表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！