來源：blog.csdn.net/zwx900102/article/details/113096979
前言
在 Redis 中，有一種資料型別，當在存盤的時候會同時采用兩種資料結構來進行分別存盤，那么 Redis 為什么要這么做呢？這么做會造成同一份資料占用兩倍空間嗎？
五種基本型別之集合物件
Redis 中的集合物件是一個包含字串型別元素的無序集合，集合中元素唯一不可重復，
集合物件的底層資料結構有兩種：intset 和 hashtable，內部通過編碼來進行區分：
intset 編碼
intset（整數集合）可以保存型別為 int16_t，int32_t，int64_t 的整數值，并且保證集合中沒有重復元素，
intset 資料結構定義如下（原始碼 inset.h 內）：
typedef struct intset {
uint32_t encoding;//編碼方式
uint32_t length;//當前集合中的元素數量
int8_t contents[];//集合中具體的元素
} intset;
下圖就是一個 intset 的集合物件存盤簡圖：
encoding
在 intset 內部的 encoding 記錄了當前整數集合的資料存盤型別，主要有三種：
- INTSET_ENC_INT16
此時 contents[] 內的每個元素都是一個 int16_t 型別的整數值，范圍是：-32768 ~ 32767（-2 的 15 次方 ~ 2 的 15 次方 - 1），
- INTSET_ENC_INT32
此時 contents[] 內的每個元素都是一個 int32_t 型別的整數值，范圍是：-2147483648 ~ 2147483647（-2 的 31 次方 ~ 2 的 31 次方 - 1），
- INTSET_ENC_INT64
此時 contents[] 內的每個元素都是一個 int64_t 型別的整數值，范圍是：-9223372036854775808 ~ 9223372036854775807（-2 的 63 次方 ~ 2 的 63 次方 - 1），
contents[]
contents[] 雖然結構的定義上寫的是 int8_t 型別，但是實際存盤型別是由上面的 encoding 來決定的，
整數集合的升級
假如一開始整數集合中的元素都是 16 位的，采用 int16_t 型別來存盤，此時需要再存盤一個 32 位的整數，那么就需要對原先的整數集合進行升級，升級之后才能將 32 位的整數存盤到整數集合內，這就涉及到了整數集合的型別升級，升級程序主要有 4 個步驟：
- 根據新添加元素的型別來擴展底層陣列空間的大小，按照升級后現有元素的位數來分配新的空間，
- 將現有的元素進行型別轉換，并將轉換型別后的元素從后到前逐個重新放回到陣列內，
- 將新元素放到陣列的頭部或者尾部（因為觸發升級的條件就是當前陣列的整數型別無法存盤新元素，所以新元素要么比現有元素都大，要么就比現有元素都小），
- 將 encoding 屬性修改為最新的編碼，并且同步修改 length 屬性，
PS：和字串物件的編碼一樣，整數集合的型別一旦發生升級，將會保持編碼，無法降級，
升級示例
1.假如我們有一個集合存盤的 encoding 是 int16_t，內部存盤了 3 個元素：
2.這時候需要插入一個整數 50000，發現存盤不下去，而 50000 是一個 int32_t 型別整數，所以需要申請新空間，申請空間大小為 4 * 32 - 48=80，
3.現在新的陣列內要放置 4 個元素，原來的陣列排在第 3，所以需要將升級后的 3 移動到 64-95 位，
4.繼續將升級后的 2 移動到 32-63 位，
5.繼續將升級后的 1 移動到 0-31 位，
6.然后會將 50000 放到 96-127 位，
7.最后會修改 encoding 和 length 屬性，修改之后就完成了本次的升級，
hashtable 編碼
hashtable 結構在前面講述哈希物件的時候進行過詳細分析，想詳細了解的可以點擊這里，
intset 和 hashtable 編碼轉換
當一個集合滿足以下兩個條件時，Redis 會選擇使用 intset 編碼：
- 集合物件保存的所有元素都是整數值，
- 集合物件保存的元素數量小于等于 512 個（這個閾值可以通過組態檔
set-max-intset-entries來控制），
一旦集合中的元素不滿足上面兩個條件，則會選擇使用 hashtable 編碼，
集合物件常用命令
sadd key member1 member2：將一個或多個元素 member 加入到集合 key 當中，并回傳添加成功的數目，如果元素已存在則被忽略，sismember key member：判斷元素 member 是否存在集合 key 中，srem key member1 member2：移除集合 key 中的元素，不存在的元素會被忽略，smove source dest member：將元素 member 從集合 source 中移動到 dest 中，如果 member 不存在，則不執行任何操作，smembers key：回傳集合 key 中所有元素，
了解了操作集合物件的常用命令，我們就可以來驗證下前面提到的哈希物件的型別和編碼了，在測驗之前為了防止其他 key 值的干擾，我們先執行 flushall 命令清空 Redis 資料庫，
依次執行如下命令：
sadd num 1 2 3 //設定 3 個整數的集合，會使用 intset 編碼
type num //查看型別
object encoding num //查看編碼
sadd name 1 2 3 test //設定 3 個整數和 1 個字串的集合，會使用 hashtable 編碼
type name //查看型別
object encoding name //查看編碼
得到如下效果：
可以看到，當設定的元素里面只有整數時，集合使用的就是 intset 編碼，當設定的元素中含有非整數時，使用的就是 hashtable 編碼，
五種基本型別之有序集合物件
Redis 中的有序集合和集合的區別是有序集合中的每個元素都會關聯一個 double 型別的分數，然后按照分數從小到大的順序進行排列，換句話說，有序集合的順序是由我們自己設值的時候通過分數來確定的，
有序集合物件的底層資料結構有兩種：skiplist 和 ziplist，內部同樣是通過編碼來進行區分：
skiplist 編碼
skiplist 即跳躍表，有時候也簡稱為跳表，使用 skiplist 編碼的有序集合物件使用了 zset 結構來作為底層實作，而zset 中同時包含了一個字典和一個跳躍表，
跳躍表
跳躍表是一種有序的資料結構，其主要特點是通過在每個節點中維持多個指向其他節點的指標，從而達到快速訪問節點的目的，
大部分情況下，跳躍表的效率可以等同于平衡樹，但是跳躍表的實作卻遠遠比平衡樹的實作簡單，所以 Redis 選擇了使用跳躍表來實作有序集合，
下圖是一個普通的有序鏈表，我們如果想要找到 35 這個元素，只能從頭開始遍歷到尾（鏈表中元素不支持隨機訪問，所以不能用二分查找，而陣列中可以通過下標隨機訪問，所以二分查找一般適用于有序陣列），時間復雜度是 O(n)，
那么假如我們可以直接跳到鏈表的中間，那就可以節省很多資源了，這就是跳表的原理，如下圖所示就是一個跳表的資料結構示例：
上圖中 level1，level2，level3 就是跳表的層級，每一個 level 層級都有一個指向下一個相同 level 層級元素的指標，比如上圖我們遍歷尋找元素 35 的時候就有三種方案：
- 第 1 種就是執行 level1 層級的指標，需要遍歷 7 次（
1->8->9->12->15->20->35）才能找到元素 35， - 第 2 種就是執行 level2 層級的指標，只需要遍歷 5 次（
1->9->12->15->35）就能找到元素 35， - 第 3 種就是執行 level3 層級的元素，這時候只需要遍歷 3 次（
1->12->35）就能找到元素 35 了，大大提升了效率，
skiplist 的存盤結構
跳躍表中的每個節點是一個 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 編碼
壓縮串列在串列物件和哈希物件都有使用到，想詳細了解的可以點擊這里，
https://blog.csdn.net/zwx900102/article/details/112651435
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，zrangebyscore key min max：回傳有序集合中按 score 從小到大排列后在 [min,max] 區間的所有元素，注意這里默認是閉區間，但是可以在 max 和 min 的數值前面加上(或者[來控制開閉區間，zrevrangebyscore key max min：回傳有序集合中按 score 從大到小排列后在 [min,max] 區間的所有元素，注意這里默認是閉區間，但是可以在 max 和 min 的數值前面加上(或者[來控制開閉區間，zrank key member：回傳有序集合中 member 中元素排名（從小到大），回傳的結果從 0 開始計算，zrevrank key member：回傳有序集合中 member 中元素排名（從大到小），回傳的結果從 0 開始計算，zlexcount key min max：回傳有序集合中 min 和 max 之間的 member 數量，注意這個命令中的 min 和 max 前面必須加(或者[來控制開閉區間，特殊值 - 和 + 分別表示負無窮和正無窮，
了解了操作有序集合物件的常用命令，我們就可以來驗證下前面提到的哈希物件的型別和編碼了，在測驗之前為了防止其他 key 值的干擾，我們先執行 flushall 命令清空 Redis 資料庫，
在執行命令之前，我們先把組態檔中的引數 zset-max-ziplist-entries 修改為 2，然后重啟 Redis 服務，
重啟完成之后依次執行如下命令：
zadd name 1 zs 2 lisi //設定 2 個元素會使用 ziplist
type name //查看型別
object encoding name //查看編碼
zadd address 1 beijing 2 shanghai 3 guangzhou 4 shenzhen //設定4個元素則會使用 skiplist編碼
type address //查看型別
object encoding address //查看編碼
得到如下效果：
總結
本文主要分析了集合物件和有序集合物件的底層存盤結構 intset 和 skiplist 的實作原理，并且重點分析了有序集合如何實作排序以及為何同時使用兩種資料結構（字典和跳表）同時進行進行存盤資料的原因，
近期熱文推薦：
1.1,000+ 道 Java面試題及答案整理(2022最新版)
2.勁爆！Java 協程要來了，，，
3.Spring Boot 2.x 教程，太全了！
4.別再寫滿屏的爆爆爆炸類了，試試裝飾器模式，這才是優雅的方式！！
5.《Java開發手冊（嵩山版）》最新發布，速速下載！
覺得不錯，別忘了隨手點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/469756.html
標籤：Java