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

in 编程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

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

    字典:非常常见的数据结构,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)。


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












关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看