免费A片在线播放,亚洲国产精品99久久,亚洲一区二区网站,国产精品无码天天爽视频,欧美性爱一区,能看熟女不卡视频,国产特级毛片A片WWW,成人网站污

sorted_set 是什么？

sorted_set 就是 zset ，是 redis 里面的數(shù)據(jù)之一，有序集合

有序集合是集合的一部分，有序集合給每個(gè)元素多設(shè)置了一個(gè)分?jǐn)?shù)，相當(dāng)于多了一個(gè)維度，redis 也是利用這個(gè)維度進(jìn)行排序的

實(shí)際應(yīng)用

redis-cli 連接上 redis-server ，使用 help @sorted_set 查看有序結(jié)合支持的命令

# redis-cli -p 6379
127.0.0.1:6379> ping
PONG
127.0.0.1:6379>
127.0.0.1:6379> help @sorted_set

  BZPOPMAX key [key ...] timeout
  summary: Remove and return the member with the highest score from one or more sorted sets, or block until one is available
  since: 5.0.0
....
復(fù)制代碼

summary

對(duì)這個(gè)命令的概括

since

這個(gè)命令從 redis 哪一個(gè)版本就開始提供了

舉個(gè)例子

在 sorted_set 中添加一個(gè) key，這個(gè)key 里面有 3 個(gè)成員，3 個(gè)成員對(duì)應(yīng)的分支如下：

成員	分值
pig	9
dog	2
cat	6

127.0.0.1:6379> zadd k1 9 pig 2 dog 6 cat
(integer) 3
復(fù)制代碼

獲取有序集合的所有值，默認(rèn)是按照有效到大的方式來展示，因?yàn)閿?shù)據(jù)存入到 redis 內(nèi)存中，物理內(nèi)存的結(jié)果是從左到右，逐個(gè)遞增的

127.0.0.1:6379> ZRANGE k1 0 -1
1) "dog"
2) "cat"
3) "pig"
復(fù)制代碼

獲取排名從小到大的前 2 位怎么做？

127.0.0.1:6379> ZRANGE k1 0 1 withscores
1) "dog"
2) "2"
3) "cat"
4) "6"
復(fù)制代碼

獲取從大到小的排名前 2 位呢？

下面這個(gè)是正確的，使用 ZrevRANGE 來獲取

127.0.0.1:6379> ZrevRANGE k1 0 1 withscores
1) "pig"
2) "9"
3) "cat"
4) "6"
復(fù)制代碼

下面這個(gè)是錯(cuò)誤的

127.0.0.1:6379> ZRANGE k1 -2 -1 withscores
1) "cat"
2) "6"
3) "pig"
4) "9"
復(fù)制代碼

例子2

咱們對(duì)以下幾個(gè)學(xué)生設(shè)置分?jǐn)?shù)，按照權(quán)重來做一個(gè)排名

k1	分?jǐn)?shù)
xiaoming	90
zhangsan	40
lisi	60

k2	分?jǐn)?shù)
xiaohong	30
zhangsan	70
wangwu	50

127.0.0.1:6379> flushall
OK
127.0.0.1:6379> zadd k1 90 xiaoming 40 zhangsan 60 lisi
(integer) 3
127.0.0.1:6379> zadd k2 30 xiaohong 70 zhangsan 50 wangwu
(integer) 3
127.0.0.1:6379> ZUNIONSTORE unkey 2 k1 k2 weights 0.5 1
(integer) 5
復(fù)制代碼

按照權(quán)重來排序，k1 占比 0.5 ， k2 占比 1，計(jì)算排名，實(shí)際例子可以用來計(jì)算按照權(quán)重的總分

127.0.0.1:6379> ZUNIONSTORE unkey 2 k1 k2 weights 0.5 1
(integer) 5
127.0.0.1:6379> Zrange unkey 0 -1 withscores
 1) "lisi"
 2) "30"
 3) "xiaohong"
 4) "30"
 5) "xiaoming"
 6) "45"
 7) "wangwu"
 8) "50"
 9) "zhangsan"
10) "90"
復(fù)制代碼

k1 和 k1 取成員的最大值來進(jìn)行排名，實(shí)際例子可以是多個(gè)科目成績的最高分進(jìn)行排名

127.0.0.1:6379> ZUNIONSTORE unkey2 2 k1 k2 aggregate max
(integer) 5
127.0.0.1:6379> zrange unkey2 0 -1 withscores
 1) "xiaohong"
 2) "30"
 3) "wangwu"
 4) "50"
 5) "lisi"
 6) "60"
 7) "zhangsan"
 8) "70"
 9) "xiaoming"
10) "90"
復(fù)制代碼

那么我們思考一下，sorted_set 的排序是如何實(shí)現(xiàn)的呢？

sorted_set 排序?qū)崿F(xiàn)原理

排序是通過 skiplist 跳表來實(shí)現(xiàn)的，skiplist 是一個(gè)類平衡樹

skiplist 本質(zhì)上也是一種查找結(jié)構(gòu)，用于解決算法中的查找問題

Redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)詳解 這本書中有說到，查找問題的解法有如下 2 類：

基于各種平衡樹
基于哈希表

skiplist 跳表不屬于上述任何一個(gè)，他可以說是一個(gè) 類平衡樹

咱們來舉個(gè)例子：

例如有如下跳表，總共有 3 層

現(xiàn)在要將 15 這個(gè)數(shù)字插入這個(gè)跳表

用 15 去第一層看，比 2 大，那么往下走

15 比 23 小且比 2 大，那么往下走

15 比 23 小，比 8 大，那么 15 就插入這里了

插入這里，第三層 8 的指針指向 15, 23的指針也指向 15

第二層 2 的指針指向 15，15 指向 23

第三層 2 的指針也指向 15， 15 指向 NULL

根據(jù)上面這個(gè)例子，我們可以明白，skiplist 就是一個(gè)特殊的鏈表，叫做跳表，或者是跳躍表

我們還發(fā)現(xiàn)，這么多層鏈表，就是最下面這一層的鏈表元素是最全的，其他層都是稀疏的鏈表，這些鏈表里面的指針故意跳過了一些節(jié)點(diǎn)（越高層的鏈表跳過的節(jié)點(diǎn)越多）

這就使得我們?cè)诓檎覕?shù)據(jù)的時(shí)候能夠先在高層的鏈表中進(jìn)行查找，然后逐層降低，最終降到第一層鏈表來精確地確定數(shù)據(jù)位置

這種方式過程中是跳過了很多節(jié)點(diǎn)的，因此也就加快了我們的查找速度

無論是增刪改查，都是需要先查詢的，先明確查找到需要操作的位置，再進(jìn)行操作

skiplist和平衡樹、哈希表的比較

	skiplist	平衡樹	哈希表
算法實(shí)現(xiàn)難度	簡單	較難
查找單個(gè)`key`	時(shí)間復(fù)雜度為O(log n)	時(shí)間復(fù)雜度為O(log n)	在保持較低的哈希值沖突概率的前提下查找時(shí)間復(fù)雜度接近O(1) 性能更高一些
范圍查找	適合	適合	不適合
范圍查找是否復(fù)雜	非常簡單只需要在找到小值之后對(duì)第1層鏈表進(jìn)行若干步的遍歷就可以實(shí)現(xiàn)	復(fù)雜需要對(duì)平衡樹做一些改造
插入和刪除操作	簡單又快速只需要修改相鄰節(jié)點(diǎn)的指針	可能引發(fā)子樹的調(diào)整
內(nèi)存占用	靈活個(gè)節(jié)點(diǎn)包含的指針數(shù)目平均為`1/(1-p)`，具體取決于參數(shù)`p`的大小	平衡樹每個(gè)節(jié)點(diǎn)包含2個(gè)指針（分別指向左右子樹）

我們查看到 redis src/server.h 中有對(duì) skiplist 的結(jié)構(gòu)定義

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        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;
復(fù)制代碼

zskiplist ，跳躍表


length	跳躍表長度
level	目前跳躍表的最大層數(shù)節(jié)點(diǎn)

zskiplist 定義了真正的skiplist結(jié)構(gòu)：

頭指針header和尾指針tail。
鏈表長度length，即鏈表包含的節(jié)點(diǎn)總數(shù)
這里需要注意一點(diǎn)：
新創(chuàng)建的 skiplist 包含一個(gè)空的頭指針，這個(gè)頭指針不包含在 length 計(jì)數(shù)中
level表示skiplist的總層數(shù)，就是所有節(jié)點(diǎn)層數(shù)的最大值

zskiplistNode ，跳躍表的節(jié)點(diǎn)


score	分值
backward	后退指針
forward	前進(jìn)指針

zskiplistNode 定義了 skiplist 的節(jié)點(diǎn)結(jié)構(gòu)：

存放的是sds，zadd命令在將數(shù)據(jù)插入到skiplist里面之前先進(jìn)行了解碼，這樣做的目的應(yīng)該是為了方便在查找的時(shí)候?qū)?shù)據(jù)進(jìn)行字典序的比較
score 字段是數(shù)據(jù)對(duì)應(yīng)的分?jǐn)?shù)
backward 字段是指向鏈表前一個(gè)節(jié)點(diǎn)的指針（前向指針），每一個(gè)節(jié)點(diǎn)只有1個(gè)前向指針，所以只有第1層鏈表是一個(gè)雙向鏈表。
level[] 存放指向各層鏈表后一個(gè)節(jié)點(diǎn)的指針（后向指針）
每層對(duì)應(yīng)1個(gè)后向指針，用forward字段表示。
span值，是每個(gè)后向指針還對(duì)應(yīng)了一個(gè) span，它表示當(dāng)前的指針跨越了多少個(gè)節(jié)點(diǎn)span用于計(jì)算元素排名(rank)

關(guān)于 redis 源碼中，創(chuàng)建節(jié)點(diǎn)，插入節(jié)點(diǎn)，刪除節(jié)點(diǎn)的源碼都在 src/t_zset.c 里面，詳細(xì)的源碼流程感興趣的可以細(xì)細(xì)品讀一下，還在品讀中

參考資料：

redis_doc
reids 源碼 src/t_zset.c 和 src/server.h

歡-迎點(diǎn)贊，關(guān)注，收藏

朋友們，你的支持和鼓勵(lì)，是我堅(jiān)持分享，提高質(zhì)量的動(dòng)力

作者：小魔童哪吒
鏈接：https://juejin.cn/post/7002267427086008327
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

【Redis 系列】redis 學(xué)習(xí)，sorted_set 初步探究梳理

sorted_set 是什么？