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)。

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

Ubuntu 14.04下Redis安装及简单测试

Redis集群明细文档

Ubuntu 12.10下安装Redis(图文详解)+ Jedis连接Redis

Redis系列-安装部署维护篇

CentOS 6.3安装Redis

Redis安装部署学习笔记

Redis配置文件redis.conf 详解

Redis 的详细介绍请点这里
Redis 的下载地址请点这里

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/e906c436d45052aad9424b77b305d391.html