Redis 有序集合

08 Jan 2021

有序集合

Redis 中的有序集合和集合的区别是：有序集合中的每个元素都会关联一个 double 类型的分数，然后按照分数从小到大的顺序进行排列。换句话说，有序集合的顺序是由我们自己设值的时候确定的。

有序集合对象的底层数据结构有两种：skiplist 和 ziplist。内部同样是通过编码来进行区分：

编码属性	描述	object encoding命令返回值
OBJ_ENCODING_SKIPLIST	使用跳跃表实现的有序集合对象	skiplist
OBJ_ENCODING_ZIPLIST	使用压缩列表实现的有序集合对象	ziplist

skiplist

skiplist 即跳跃表，有时候也简称为跳表。使用 skiplist 编码的有序集合对象使用了 zset 结构来作为底层实现，而 zset 中同时包含了一个字典和一个跳跃表。

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

大部分情况下，跳跃表的效率可以等同于平衡树，但是跳跃表的实现却远远比平衡树的实现简单，所以 Redis 选择了使用跳跃表来实现有序集合。

对于普通的有序链表，我们如果想要找到某个元素，只能从头开始遍历到尾（链表中元素不支持随机访问，所以不能用二分查找，而数组中可以通过下标随机访问，所以二分查找一般适用于有序数组），时间复杂度是 O(n)。

那么假如我们可以直接跳到链表的中间，那就可以节省很多资源了，这就是跳表的原理，如下图所示就是一个跳表的数据结构示例：

上图中 level1、level2、level3 就是跳表的层级，每一个 level 层级都有一个指向下一个相同 level 层级元素的指针，比如上图我们遍历寻找元素 35 的时候就有三种方案：

第 1 种：执行 level1 层级的指针，需要遍历 7 次（1->8->9->12->15->20->35）才能找到元素 35。
第 2 种：执行 level2 层级的指针，只需要遍历 5 次（1->9->12->15->35）就能找到元素 35。
第 3 种：执行 level3 层级的元素，这时候只需要遍历 3 次（1->12->35）就能找到元素 35 了，大大提升了效率。
skiplist 的存储结构

跳跃表中的每个节点是一个 zskiplistNode 节点（源码 server.h 内）：

typedef struct zskiplistNode {   
    sds ele;//元素   
    double score;//分值   
    struct zskiplistNode *backward;//后退指针   
    struct zskiplistLevel {//层   
        struct zskiplistNode *forward;//前进指针   
        unsigned long span;//当前节点到下一个节点的跨度（跨越的节点数）   
    } level[];   
} zskiplistNode;   

level（层）
level 即跳跃表中的层，其是一个数组，也就是说一个节点的元素可以拥有多个层，即多个指向其它节点的指针，程序可以通过不同层级的指针来选择最快捷的路径提升访问速度。

level 是在每次创建新节点的时候根据幂次定律（power law）随机生成的一个介于 1~32 之间的数字。

forward（前进指针）
每个层都会有一个指向链表尾部方向元素的指针，遍历元素的时候需要使用到前进指针。
span（跨度）
跨度记录了两个节点之间的距离，需要注意的是，如果指向了 NULL 的话，则跨度为 0。
backward（后退指针）
和前进指针不一样的是后退指针只有一个，所以每次只能后退至前一个节点（上图中没有画出后退指针）。
ele（元素）
跳跃表中元素是一个 sds 对象（早期版本使用的是 redisObject 对象），元素必须唯一、不能重复。
score（分值）
节点的分值是一个 double 类型的浮点数，跳跃表中会将节点按照分值从小到大的顺序排列，不同节点的分值可以重复。

上面介绍的只是跳跃表中的一个节点，多个 zskiplistNode 节点组成了一个 zskiplist 对象：

typedef struct zskiplist {   
    struct zskiplistNode *header, *tail;//跳跃表的头节点和尾结点指针   
    unsigned long length;//跳跃表的节点数   
    int level;//所有节点中最大的层数   
} zskiplist;   

到这里你可能以为有序集合就是用这个 zskiplist 来实现的，然而实际上 Redis 并没有直接使用 zskiplist 来实现，而是用 zset 对象再次进行了一层包装。

typedef struct zset {   
    dict *dict;//字典对象   
    zskiplist *zsl;//跳跃表对象   
} zset;   

所以最终，一个有序集合如果使用了 skiplist 编码，其数据结构如下图所示：

上图中，上面一部分的字典中的 key 就是对应了有序集合中的元素（member），value 就对应了分值（score）；下面一部分中跳跃表整数 1,8,9,12 也是对应了元素（member），最后一排的 double 型数字就是分值（score）。

也就是说字典和跳跃表中的数据都指向了我们存储的元素（两种数据结构最终指向的是同一个地址，所以数据并不会出现冗余存储），Redis 为什么要这么做呢？

为什么同时选择使用字典和跳跃表

有序集合直接使用跳跃表或者单独使用字典完全可以独自实现，但是我们想一下：

如果单独使用跳跃表来实现，那么虽然可以使用跨度大的指针去遍历元素来找到我们需要的数据，但是其复杂度仍然达到了 O(logN)，而字典中获取一个元素的复杂度是 O(1)。
如果单独使用字典，虽然获取元素很快，但是字典是无序的，所以如果要范围查找就需要对其进行排序，这又是一个耗时的操作。

ziplist

见：Redis ziplist

ziplist 和 skiplist 编码转换

当有序集合对象同时满足以下两个条件时，会使用 ziplist 编码进行存储：

有序集合对象中保存的元素个数小于 128 个（可以通过配置 zset-max-ziplist-entries 修改）。
有序集合对象中保存的所有元素的总长度小于 64 字节（可以通过配置 zset-max-ziplist-value 修改）。

errorbeep@home:~$

Archive

About

RSS