<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • 【Redis 系列】redis 學習十四,sorted_set 初步探究梳理

    sorted_set 是什么?

    sorted_set 就是 zset ,是 redis 里面的數據之一,有序集合

    有序集合是集合的一部分,有序集合給每個元素多設置了一個分數,相當于多了一個維度,redis 也是利用這個維度進行排序的

    實際應用

    redis-cli 連接上 redis-server ,使用 help @sorted_set 查看有序結合支持的命令

    # 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
    ....
    

    image-20210829191900460

    • summary

    對這個命令的概括

    • since

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

    舉個例子

    sorted_set 中添加一個 key,這個key 里面有 3 個成員 ,3 個成員對應的分支如下:

    成員 分值
    pig 9
    dog 2
    cat 6

    image-20210829195411654

    127.0.0.1:6379> zadd k1 9 pig 2 dog 6 cat
    (integer) 3
    

    獲取有序集合的所有值,默認是按照有效到大的方式來展示,因為數據存入到 redis 內存中,物理內存的結果是從左到右,逐個遞增的

    127.0.0.1:6379> ZRANGE k1 0 -1
    1) "dog"
    2) "cat"
    3) "pig"
    

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

    127.0.0.1:6379> ZRANGE k1 0 1 withscores
    1) "dog"
    2) "2"
    3) "cat"
    4) "6"
    

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

    下面這個是正確的,使用 ZrevRANGE 來獲取

    127.0.0.1:6379> ZrevRANGE k1 0 1 withscores
    1) "pig"
    2) "9"
    3) "cat"
    4) "6"
    

    下面這個是錯誤的

    127.0.0.1:6379> ZRANGE k1 -2 -1 withscores
    1) "cat"
    2) "6"
    3) "pig"
    4) "9"
    

    例子2

    咱們對以下幾個學生設置分數,按照權重來做一個排名

    k1 分數
    xiaoming 90
    zhangsan 40
    lisi 60
    k2 分數
    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
    

    按照權重來排序,k1 占比 0.5 , k2 占比 1,計算排名,實際例子可以用來計算按照權重的總分

    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"
    

    k1 和 k1 取成員的最大值來進行排名,實際例子可以是多個科目成績的最高分進行排名

    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"
    

    那么我們思考一下,sorted_set 的排序是如何實現的呢?

    sorted_set 排序實現原理

    排序是通過 skiplist 跳表來實現的,skiplist 是一個類平衡樹

    skiplist 本質上也是一種查找結構,用于解決算法中的查找問題

    Redis內部數據結構詳解 這本書中有說到,查找問題的解法有如下 2 類:

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

    skiplist 跳表 不屬于上述任何一個,他可以說是一個 類平衡樹

    咱們來舉個例子:

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

    現在要將 15 這個數字插入這個跳表

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

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

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

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

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

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

    根據上面這個例子,我們可以明白,skiplist 就是一個特殊的鏈表,叫做跳表,或者是跳躍表

    我們還發現,這么多層鏈表,就是最下面這一層的鏈表元素是最全的,其他層都是稀疏的鏈表,這些鏈表里面的指針故意跳過了一些節點(越高層的鏈表跳過的節點越多

    這就使得我們在查找數據的時候能夠先在高層的鏈表中進行查找,然后逐層降低,最終降到第一層鏈表來精確地確定數據位置

    這種方式過程中是跳過了很多節點的,因此也就加快了我們的查找速度

    無論是增刪改查,都是需要先查詢的,先明確查找到需要操作的位置,再進行操作

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

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

    我們查看到 redis src/server.h 中有對 skiplist 的結構定義

    /* 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;
    

    zskiplist ,跳躍表

    length 跳躍表 長度
    level 目前跳躍表的最大層數節點

    zskiplist 定義了真正的skiplist結構:

    • 頭指針header和尾指針tail

    • 鏈表長度length,即鏈表包含的節點總數

      這里需要注意一點:

      新創建的 skiplist 包含一個空的頭指針,這個頭指針不包含在 length 計數中

    • level表示skiplist的總層數,就是所有節點層數的最大值

    zskiplistNode , 跳躍表的節點

    score 分值
    backward 后退指針
    forward 前進指針

    zskiplistNode 定義了 skiplist 的節點結構:

    • 存放的是sdszadd命令在將數據插入到skiplist里面之前先進行了解碼,這樣做的目的應該是為了方便在查找的時候對數據進行字典序的比較

    • score 字段是數據對應的分數

    • backward 字段是指向鏈表前一個節點的指針(前向指針),每一個節點只有1個前向指針,所以只有第1層鏈表是一個雙向鏈表。

    • level[] 存放指向各層鏈表后一個節點的指針(后向指針)

      每層對應1個后向指針,用forward字段表示。

    • span值 ,是每個后向指針還對應了一個 span,它表示當前的指針跨越了多少個節點span用于計算元素排名(rank)

    關于 redis 源碼中,創建節點,插入節點,刪除節點的源碼都在 src/t_zset.c 里面,詳細的源碼流程感興趣的可以細細品讀一下,還在品讀中

    參考資料:

    • redis_doc

    • reids 源碼 src/t_zset.csrc/server.h

    歡-迎點贊,關注,收藏

    朋友們,你的支持和鼓勵,是我堅持分享,提高質量的動力

    好了,本次就到這里

    技術是開放的,我們的心態,更應是開放的。擁抱變化,向陽而生,努力向前行。

    我是小魔童哪吒,歡迎點贊關注收藏,下次見~

    posted @ 2022-05-03 12:39  小魔童哪吒  閱讀(26)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看