跳跃表中的每个节点是一个 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),而如果单独使用字典虽然获取元素很快,但是字典是无序的,所以如果要范围查找就需要对其进行排序,这又是一个耗时的操作,所以 Redis 综合了两种数据结构来最大程度的提升性能,这也是 Redis 设计的精妙之处。
ziplist 编码压缩列表在列表对象和哈希对象都有使用到,想详细了解的可以点击这里。
ziplist 和 skiplist 编码转换当有序集合对象同时满足以下两个条件时,会使用 ziplist 编码进行存储:
有序集合对象中保存的元素个数小于 128 个(可以通过配置 zset-max-ziplist-entries 修改)。
有序集合对象中保存的所有元素的总长度小于 64 字节(可以通过配置 zset-max-ziplist-value 修改)。
有序集合对象常用命令zadd key score1 member1 score2 member2:将一个或多个元素(member)及其 score 添加到有序集合 key 中。
zscore key member:返回有序集合 key 中 member 成员的 score。
zincrby key num member:将有序集合 key 中的 member 加上 num,num 可以为负数。
zcount key min max:返回有序集合 key 中 score 值在 [min,max] 区间的 member 数量。
zrange key start stop:返回有序集合 key 中 score 从小到大排列后在 [start,stop] 区间的所有 member。
zrevrange key start stop:返回有序集合 key 中 score 从大到小排列后在 [start,stop] 区间的所有 member。