Redis教程

有序集合对象 - 《Redis设计与实现》读书笔记

本文主要是介绍有序集合对象 - 《Redis设计与实现》读书笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

有序集合对象的编码可以是ziplist或者skiplist

  1. ziplist编码的有序集合对象使用压缩列表作为底层实现

每个集合元素使用两个紧挨在一起的压缩列表节点来保存
第一个节点保存元素的成员,第二个节点保存元素的分值
压缩列表内的集合元素按分值从小到大进行排序
分值较小的元素被放置在靠近表头的方向,分值较大的元素被放置在靠近表尾的方向

  1. skiplist编码的有序集合对象使用zset结构作为底层实现
// zset结构
typedef struct zset {
    // 字典: 创建一个从成员到分值的映射,凭此用O(1)复杂度查找给定成员的分值
    // 字典中的每个键值对保存了一个集合元素: 字典的键保存元素的成员,字典的值保存元素的分值
    dict *dict;
    // 跳跃表: 按分值从小到大保存集合元素,凭此对有序集合进行范围型操作
    // 每个跳跃节点都保存一个集合元素: 跳跃节点的ele属性保存了元素的成员,跳跃节点的score属性保存了元素的分值
    zskiplist *zsl;
} zset;

有序集合需要同时使用跳跃表和字典来实现的原因:

  1. 若只使用字典来实现有序集合,由于字典以无序的方式保存集合元素,每次在执行范围型操作需要对所有元素进行排序,这一过程至少O(NlogN)时间复杂度以及额外的O(N)内存空间
  2. 若只使用跳跃表来实现有序集合,根据成员查找分值这一操作的复杂度将从O(1)上升为O(logN)
    综上所述,无论单独使用字典还是跳跃表,在性能上对比同时使用字典和跳跃表都有所降低,所以Redis选择了同时使用字典和跳跃表两种数据结构实现有序集合

注意: 字典和跳跃表会共享元素的成员和分值,并不会造成数据容与,也不会造成内存浪费

编码转换

当有序集合对象可以【同时满足】以下条件时,有序集合对象的编码使用ziplist,否则使用skiplist编码,

  1. 有序集合对象保存的元素数量小于128个
  2. 有序集合对象保存的所有元素成员的长度都小于64字节

编码的转换两个条件的上限值可通过配置文件中的zset-max-ziplist-entries、zset-max-ziplist-value选项进行调整,

源码阅读

  1. 文件:src/t_zset.c
这篇关于有序集合对象 - 《Redis设计与实现》读书笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!