转载

【每日一博】Redis有序集合与列表占用内存分析

在说正题之前需要先了解几种定义：字典、压缩列表与跳跃表。

字典：非常常见的数据结构，key-value结构。

常见的实现有红黑树（stl中的map），哈希表（stl中的unordered_map）。红黑树的查找操作具有O（logN）的时间复杂度。哈希表的查找操作具有O(1)的时间复杂度。 redis中的字典使用哈希表作为底层实现。

压缩列表：由一些列特殊编码的连续内存块组成的顺序型数据结构。

压缩列表可以包含多种节点（只能保存一种的那叫数组）。压缩列表的优点是节省内存。顺序结构拥有的缺点压缩列表全都有。

跳跃表：一种有序数据结构，它通过在每个节点中维护多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O（logN）、最坏O（N）时间复杂度的节点查找。

redis中的跳跃表由zskiplist和zskiplistNode两个结构组成，其中 zskiplist用于保存跳跃表的信息（比如表头节点、表尾节点、长度），而 zskiplistNode用于表示跳跃表节点。跳跃表中的节点按照分支大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。在同一跳跃表中，多个节点可以包含相同的分值，但每节点的成员对象必须是唯一的。

进入正题，为什么redis中的有序集合占用内存比列表大？

先说redis中的列表的实现，redis中的列表底层使用压缩列表或链表来实现。redis列表有两种不同的编码（实现方式）： ziplist和linkedlist。在特定的条件下，编码格式可以进行相互转换。当列表对象保存的所有字符串元素的长度都小于64字节，并且列表对象的元素数量小于512时，列表对象使用ziplist。反之，使用linkedlist编码。

重点说一下有序集合的实现，redis中有序集合的实现要更加复杂，包含 ziplist和skiplist两种不同编码。

ziplist编码的有序集合对象使用压缩列表作为底层实现。每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。

skiplist编码的有序集合对象使用zset结果作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。zset结构中的跳跃表按照分值从小到大保存了所有的集合元素，通过这个跳跃表，可以有序结合进行范围型操作，例如zrank、zrange。 zset结构中的字典保存了有序集合中成员到分值的映射，通过这个字典，可以用O(1)的时间复杂度查找成员的分值。虽然zset使用两种数据结构来保存数据，但这两种数据结构使用指针来共享相同元素的成员和分值，所以并不会产生任何重复的成员或者分值。

当有序集合保存的元素数量小于128个，并且所有元素成员的长度小于64字节时，使用ziplist编码。反之，使用skiplist编码。

为什么有序集合要同时使用跳跃表和字典来实现呢？

单独使用字典时，查找快，只需要O(1)的时间复杂度，但是范围操作就需要对字典元素进行排序，完成这种排序至少需要O(NlogN)的时间复杂度，以及额外的O(N)的内存空间。

单独使用跳跃表时，跳跃表执行范围操作的优点会被保留，但是查找的效率会下降，查找的时间复杂度会从O(1)上升到O(logN)。

通过以上的分析可以看到，列表对象的实现相比有序集合对象的实现要简单的多，没有那么多乱七八糟的事情。所以，有序集合会比列表占用更多的内存。

正文到此结束