手机版
你好,游客 登录 注册 搜索
背景:
阅读新闻

Redis中有序集合与列表占用内存分析

[日期:2015-02-13] 来源:oschina.net  作者:justfairytale [字体: ]

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

字典:非常常见的数据结构,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安装及简单测试 http://www.linuxidc.com/Linux/2014-05/101544.htm

Redis集群明细文档 http://www.linuxidc.com/Linux/2013-09/90118.htm

Ubuntu 12.10下安装Redis(图文详解)+ Jedis连接Redis http://www.linuxidc.com/Linux/2013-06/85816.htm

Redis系列-安装部署维护篇 http://www.linuxidc.com/Linux/2012-12/75627.htm

CentOS 6.3安装Redis http://www.linuxidc.com/Linux/2012-12/75314.htm

Redis安装部署学习笔记 http://www.linuxidc.com/Linux/2014-07/104306.htm

Redis配置文件redis.conf 详解 http://www.linuxidc.com/Linux/2013-11/92524.htm

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

本文永久更新链接地址http://www.linuxidc.com/Linux/2015-02/113338.htm

linux
相关资讯       Redis内存  Redis有序集合 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款