redis数据类型--zset

数据结构：

zset是有序的，不运行重复的，带有分值score的

数据结构对比：

操作命令：

zadd myzset 10 java 20 python 20 ruby 40 mysql 50 php （添加）

zrange myzset 0 -1 withscores （通过score进行排序从小到大）

zrevrange myzset 0 -1 withscores （通过score进行排序从大到小）

zrangebyscore myzset 20 30 （通过score取出20-30的产品）

zrem myzset java python （将java和python移除）

zscard myzset （统计总数）

zincrby myzset 5 java （将java加5分）

zcount myzset 20 50 （统计20-50之间有多少个）

zrank myzset java （java在set中处于第几个位置，从0开始）

zscore myzset java （java有多少分）

存储实现原理：

在redis.conf文件中有两行这么写的

zset-max-ziplist-entries 128 # zset中压缩列表ziplist最大的元素是128个，超过128将会使用跳表skiplist+dict来存储

zset-max-ziplist-value 64 # zset中压缩列表ziplist中每个元素最大的个数是64个，超过64将会使用跳表skiplist+dict来存储

什么是跳表skiplist dict呢？我们先来看下面一张图：

这是一个有序的链表，当我们要将20这个数字插入到链表中的时候，他是从开始到结尾一个一个进行比对直到找到21之后才停止，这样他的效率就很低，时间复杂度是O（n），查找也是一样的道理。

怎么优化呢，skiplist是怎么实现的呢？再来看下面一张图：

假如我们每相邻两个节点增加一个指针（或者理解为有三个元素进入了第二层），让指针指向下下个节点。

这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半（上图中是 7, 19, 26）。在插入一个数据的时候，

决定要放到那一层，取决于一个算法（在 redis 中 t_zset.c 有一个 zslRandomLevel 这个方法）。现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数

据大的节点时，再回到原来的链表中的下一层进行查找。比如，我们想查找 23，查找的路径是沿着下图中标红的指针所指向的方向进行的：

1. 23 首先和 7 比较，再和 19 比较，比它们都大，继续向后比较。

2. 但 23 和 26 比较的时候，比 26 要小，因此回到下面的链表（原链表），与 22比较。

3. 23 比 22 要大，沿下面的指针继续向后和 26 比较。23 比 26 小，说明待查数据 23 在原链表中不存在，在这个查找过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。这就是跳跃表。

可以看到他将某些元素中加了指针，这有点类似于数组中的二分法查找，但是链表中没有数组，所以用指针的方式来实现，看下面源码

源码位置：server.h

typedef struct zskiplistNode {

    sds ele; /* zset 的元素 */

    double score; /* 分值 */

    struct zskiplistNode *backward; /* 后退指针 */

    struct zskiplistLevel {

        struct zskiplistNode *forward; /* 前进指针，对应 level 的下一个节点 */

        unsigned long span; /* 从当前节点到下一个节点的跨度（跨越的节点数） */

    }level[]; /* 层 */

}zskiplistNode;

typedef struct zskiplist {

    struct zskiplistNode *header, *tail; /* 指向跳跃表的头结点和尾节点 */

    unsigned long length; /* 跳跃表的节点数 */ int level; /* 最大的层数 */

} zskiplist;

typedef struct zset {

    dict *dict;

    zskiplist *zsl;

} zset;

随机获取层数的函数，源码位置t_zset.c

int zslRandomLevel(void) {

    int level = 1;

    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))

        level += 1;

    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;

}

应用场景：

排行榜

id 为 6001 的新闻点击数加 1：zincrby hotNews:20190926 1 n6001

获取今天点击最多的 15 条：zrevrange hotNews:20190926 0 15 withscores

巴特西

redis数据类型--zset

最新文章

热门文章