<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 有序集 [TOC=2,3] `REDIS_ZSET` (有序集)是 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 、 [ZCOUNT](http://redis.readthedocs.org/en/latest/sorted_set/zcount.html#zcount "(in Redis 命令參考 v2.8)") 等命令的操作對象,它使用 `REDIS_ENCODING_ZIPLIST` 和 `REDIS_ENCODING_SKIPLIST` 兩種方式編碼: ![digraph redis_zset { node [shape=plaintext, style = filled]; edge [style = bold]; // type REDIS_ZSET [label="有序集合\nREDIS_ZSET", fillcolor = "#95BBE3"]; // encoding REDIS_ENCODING_ZIPLIST [label="ziplist\nREDIS_ENCODING_ZIPLIST", fillcolor = "#FADCAD"]; REDIS_ENCODING_SKIPLIST [label="跳躍表\nREDIS_ENCODING_SKIPLIST", fillcolor = "#FADCAD"]; // edge REDIS_ZSET -> REDIS_ENCODING_ZIPLIST; REDIS_ZSET -> REDIS_ENCODING_SKIPLIST; // datastruct 1 ziplist [label="ziplist"]; REDIS_ENCODING_ZIPLIST -> ziplist; // datastruct 2 zset [label="redis.h/zset"]; dict [label="dict.h/dict"]; zskiplist [label="redis.h/zskiplist"]; REDIS_ENCODING_SKIPLIST -> zset; zset -> dict; zset -> zskiplist;}](https://box.kancloud.cn/2015-09-13_55f4effcf0888.svg) ### 編碼的選擇 在通過 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 命令添加第一個元素到空 `key` 時,程序通過檢查輸入的第一個元素來決定該創建什么編碼的有序集。 如果第一個元素符合以下條件的話,就創建一個 `REDIS_ENCODING_ZIPLIST` 編碼的有序集: - 服務器屬性 `server.zset_max_ziplist_entries` 的值大于 `0` (默認為 `128` )。 - 元素的 `member` 長度小于服務器屬性 `server.zset_max_ziplist_value` 的值(默認為 `64` )。 否則,程序就創建一個 `REDIS_ENCODING_SKIPLIST` 編碼的有序集。 ### 編碼的轉換 對于一個 `REDIS_ENCODING_ZIPLIST` 編碼的有序集,只要滿足以下任一條件,就將它轉換為 `REDIS_ENCODING_SKIPLIST` 編碼: - `ziplist` 所保存的元素數量超過服務器屬性 `server.zset_max_ziplist_entries` 的值(默認值為 `128` ) - 新添加元素的 `member` 的長度大于服務器屬性 `server.zset_max_ziplist_value` 的值(默認值為 `64` ) ### ZIPLIST 編碼的有序集 當使用 `REDIS_ENCODING_ZIPLIST` 編碼時,有序集將元素保存到 `ziplist` 數據結構里面。 其中,每個有序集元素以兩個相鄰的 `ziplist` 節點表示,第一個節點保存元素的 `member` 域,第二個元素保存元素的 `score` 域。 多個元素之間按 `score` 值從小到大排序,如果兩個元素的 `score` 相同,那么按字典序對 `member` 進行對比,決定那個元素排在前面,那個元素排在后面。 ~~~ |<-- element 1 -->|<-- element 2 -->|<-- ....... -->| +---------+---------+--------+---------+--------+---------+---------+---------+ | ZIPLIST | | | | | | | ZIPLIST | | ENTRY | member1 | score1 | member2 | score2 | ... | ... | ENTRY | | HEAD | | | | | | | END | +---------+---------+--------+---------+--------+---------+---------+---------+ score1 <= score2 <= ... ~~~ 雖然元素是按 `score` 域有序排序的,但對 `ziplist` 的節點指針只能線性地移動,所以在 `REDIS_ENCODING_ZIPLIST` 編碼的有序集中,查找某個給定元素的復雜度為 \(O(N)\) 。 每次執行添加/刪除/更新操作都需要執行一次查找元素的操作,因此這些函數的復雜度都不低于 \(O(N)\) ,至于這些操作的實際復雜度,取決于它們底層所執行的 `ziplist` 操作。 ### SKIPLIST 編碼的有序集 當使用 `REDIS_ENCODING_SKIPLIST` 編碼時,有序集元素由 `redis.h/zset` 結構來保存: ~~~ /* * 有序集 */ typedef struct zset { // 字典 dict *dict; // 跳躍表 zskiplist *zsl; } zset; ~~~ `zset` 同時使用字典和跳躍表兩個數據結構來保存有序集元素。 其中,元素的成員由一個 `redisObject` 結構表示,而元素的 `score` 則是一個 `double` 類型的浮點數,字典和跳躍表兩個結構通過將指針共同指向這兩個值來節約空間(不用每個元素都復制兩份)。 下圖展示了一個 `REDIS_ENCODING_SKIPLIST` 編碼的有序集: ![digraph zset { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; label = "在實際中,字典和跳躍表通過指針來共享元素的 member 和 score\n圖中對每個元素都重復顯示了一遍,只是為了展示的方便"; zset [label = "<head>zset |<dict>dict |<zskiplist> zskiplist"]; // skiplist skiplist [label ="<head>zskipNode |<3> |<2> |<1> |<score>score\n NULL |<robj>robj\n NULL", fillcolor = "#FADCAD"]; six [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 6 |<robj>robj\n x", fillcolor = "#FADCAD"]; ten [label = "<head>zskipNode | <1> |<score>score\n 10 |<robj>robj\n y", fillcolor = "#FADCAD"]; fiften [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 15 |<robj>robj\n z", fillcolor = "#FADCAD"]; zset:dict -> dict:head; zset:zskiplist -> skiplist:head; skiplist:3 -> six:3; skiplist:2 -> six:2; skiplist:1 -> six:1; six:1 -> ten:1; six:2 -> fiften:2; six:3 -> fiften:3; ten:1 -> fiften:1; // dict dict [label = "<head>dictht | ... |<table> table | ...", fillcolor = "#A8E270"]; bucket [label = "<head>dictEntry**\n(bucket) |<0> 0 |<1> 1 |<2> 2", fillcolor = "#95BBE3"]; entry_x [label = "<head>dictEntry |{<key>key\n x |<value>value\n 6}", fillcolor = "#F2F2F2"]; entry_y [label = "<head>dictEntry |{<key>key\n y |<value>value\n 10}", fillcolor = "#F2F2F2"]; entry_z [label = "<head>dictEntry |{<key>key\n z |<value>value\n 15}", fillcolor = "#F2F2F2"]; dict:table -> bucket:head; bucket:0 -> entry_x:head; bucket:1 -> entry_y:head; bucket:2 -> entry_z:head;}](https://box.kancloud.cn/2015-09-13_55f4effd05d06.svg) 通過使用字典結構,并將 `member` 作為鍵,`score` 作為值,有序集可以在 \(O(1)\) 復雜度內: - 檢查給定 `member` 是否存在于有序集(被很多底層函數使用); - 取出 `member` 對應的 `score` 值(實現 [ZSCORE](http://redis.readthedocs.org/en/latest/sorted_set/zscore.html#zscore "(in Redis 命令參考 v2.8)") 命令)。 另一方面,通過使用跳躍表,可以讓有序集支持以下兩種操作: - 在 \(O(\log N)\) 期望時間、 \(O(N)\) 最壞時間內根據 `score` 對 `member` 進行定位(被很多底層函數使用); - 范圍性查找和處理操作,這是(高效地)實現 [ZRANGE](http://redis.readthedocs.org/en/latest/sorted_set/zrange.html#zrange "(in Redis 命令參考 v2.8)") 、 [ZRANK](http://redis.readthedocs.org/en/latest/sorted_set/zrank.html#zrank "(in Redis 命令參考 v2.8)") 和 [ZINTERSTORE](http://redis.readthedocs.org/en/latest/sorted_set/zinterstore.html#zinterstore "(in Redis 命令參考 v2.8)") 等命令的關鍵。 通過同時使用字典和跳躍表,有序集可以高效地實現按成員查找和按順序查找兩種操作。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看