摘要： 你真的懂Redis的5種基本資料結構嗎？這些知識點或許你還需要看看。
本文分享自華為雲社群《你真的懂Redis的5種基本資料結構嗎？這些知識點或許你還需要看看》，作者：李子捌。
Redis中所有的的資料結構都是通過一個唯一的字元串key來擷取相應的value資料。
Redis有5種基礎資料結構，分别是：
string（字元串）
list（清單）
hash（字典）
set（集合）
zset（有序集合）
其中list、set、hash、zset這四種資料結構是容器型資料結構，它們共享下面兩條通用規則：
create if not exists：容器不存在則建立
drop if no elements：如果容器中沒有元素，則立即删除容器，釋放記憶體
本文将詳細講述的是Redis的5種基礎資料結構。
string(字元串)是Redis最簡單也是使用最廣泛的資料結構，它的内部是一個字元數組。如圖所示：
Redis中string(字元串)是動态字元串，允許修改；它在結構上的實作類似于Java中的ArrayList（預設構造一個大小為10的初始數組），這是備援配置設定記憶體的思想，也稱為預配置設定；這種思想可以減少擴容帶來的性能消耗。
當string(字元串)的大小達到擴容門檻值時，将會對string(字元串)進行擴容，string(字元串)的擴容主要有以下幾個點：
長度小于1MB，擴容後為原先的兩倍; length = length * 2
長度大于1MB，擴容後增加1MB; length = length + 1MB
字元串的長度最大值為 512MB
set -> key 不存在則新增，存在則修改
set key value
get -> 查詢，傳回對應key的value，不存在傳回(nil)
get key
del -> 删除指定的key(key可以是多個)
del key [key …]
示例：
批量鍵值讀取和寫入最大的優勢在于節省網絡傳輸開銷
mset -> 批量插入
mset key value [key value …]
mget -> 批量擷取
mget key [key …]
過期set是通過設定一個緩存key的過期時間，使得緩存到期後自動删除進而失效的機制。
方式一：
expire key seconds
方式二：
setex key seconds value
上面的set操作不存在建立，存在則更新；此時如果需要存在不更新的場景，那麼可以使用如下這個指令
setnx -> 不存在建立存在不更新
setnx key value
string(字元串)也可以用來計數，前提是value是一個整數，那麼可以對它進行自增的操作。自增的範圍必須在signed long的區間通路内，[-9223372036854775808,9223372036854775808]
incr -> 自增1
incr key
incrby -> 自定義累加值
incrby key increment
測試value為整數的自增區間
最大值：
最小值：
Redis的清單相當于Java語言中的LinkedList，它是一個雙向連結清單資料結構（但是這個結構設計比較巧妙，後面會介紹），支援前後順序周遊。連結清單結構插入和删除操作快，時間複雜度O(1)，查詢慢，時間複雜度O(n)。
根據Redis雙向清單的特性，是以其也被用于異步隊列的使用。實際開發中将需要延後處理的任務結構體序列化成字元串，放入Redis的隊列中，另一個線程從這個清單中擷取資料進行後續處理。其流程類似如下的圖：
隊列在結構上是先進先出（FIFO）的資料結構（比如排隊購票的順序），常用于消息隊列類似的功能，例如消息排隊、異步處理等場景。通過它可以確定元素的通路順序。
lpush -> 從左邊邊添加元素
lpush key value [value …]
rpush -> 從右邊添加元素
rpush key value [value …]
llen -> 擷取清單的長度
llen key
lpop -> 從左邊彈出元素
lpop key
棧在結構上是先進後出（FILO）的資料結構（比如彈夾壓入子彈，子彈被射擊出去的順序就是棧），這種資料結構一般用來逆序輸出。
rpop -> 從右邊彈出元素
rpop code
清單(list)是個連結清單資料結構，它的周遊是慢操作，是以涉及到周遊的性能将會周遊區間range的增大而增大。注意list的索引運作為負數，-1代表倒數第一個，-2代表倒數第二個，其它同理。
lindex -> 周遊擷取清單指定索引處的值
lindex key ind
lrange -> 擷取從索引start到stop處的全部值
lrange key start stop
ltrim -> 截取索引start到stop處的全部值，其它将會被删除
ltrim key start stop
Redis底層存儲list(清單)不是一個簡單的LinkedList，而是quicklist ——“快速清單”。關于quicklist是什麼，下面會簡單介紹，具體源碼我也還在學習中，後面大家一起探讨。
quicklist是多個ziplist(壓縮清單)組成的雙向清單；而這個ziplist(壓縮清單)又是什麼呢？ziplist指的是一塊連續的記憶體存儲空間，Redis底層對于list(清單)的存儲，當元素個數少的時候，它會使用一塊連續的記憶體空間來存儲，這樣可以減少每個元素增加prev和next指針帶來的記憶體消耗，最重要的是可以減少記憶體碎片化問題。
每個node節點元素，都會持有一個prev->執行前一個node節點和next->指向後一個node節點的指針（引用），這種結構雖然支援前後順序周遊，但是也帶來了不小的記憶體開銷，如果node節點僅僅是一個int類型的值，那麼可想而知，引用的記憶體比例将會更大。
ziplist是一塊連續的記憶體位址，他們之間無需持有prev和next指針，能通過位址順序尋址通路。
quicklist是由多個ziplist組成的雙向連結清單。
Redis的hash(字典)相當于Java語言中的HashMap，它是根據散列值分布的無序字典，内部的元素是通過鍵值對的方式存儲。
hash(字典)的實作與Java中的HashMap（JDK1.7）的結構也是一緻的，它的資料結構也是數組+連結清單組成的二維結構，節點元素散列在數組上，如果發生hash碰撞則使用連結清單串聯在數組節點上。
Redis中的hash(字典)存儲的value隻能是字元串值，此外擴容與Java中的HashMap也不同。Java中的HashMap在擴容的時候是一次性完成的，而Redis考慮到其核心存取是單線程的性能問題，為了追求高性能，因而采取了漸進式rehash政策。
漸進式rehash指的是并非一次性完成，它是多次完成的，是以需要保理舊的hash結構，是以Redis中的hash(字典)會存在新舊兩個hash結構，在rehash結束後也就是舊hash的值全部搬遷到新hash之後，新的hash在功能上才會完全替代以前的hash。
hash(字典)可以用來存儲對象的相關資訊，一個hash(字典)代表一個對象，hash的一個key代表對象的一個屬性，key的值代表屬性的值。hash(字典)結構相比字元串來說，它無需将整個對象進行序列化後進行存儲。這樣在擷取的時候可以進行部分擷取。是以相比之下hash(字典)具有如下的優缺點：
讀取可以部分讀取，節省網絡流量
存儲消耗的高于單個字元串的存儲
hset -> hash(字典)插入值，字典不存在則建立 key代表字典名稱，field 相當于 key，value是key的值
hset key field value
hmset -> 批量設值
hmset key field value [field value …]
hget -> 擷取字典中的指定key的value
hget key field
hgetall -> 擷取字典中所有的key和value，換行輸出
hgetall key
hlen -> 擷取指定字典的key的個數
hlen key
舉例：
在string(字元串)中可以使用incr和incrby對value是整數的字元串進行自加操作，在hash(字典)結構中如果單個子key是整數也可以進行自加操作。
hincrby -> 增對hash(字典)中的某個key的整數value進行自加操作
hincrby key field increment
注意如果不是整數會報錯。
Redis的set(集合)相當于Java語言裡的HashSet，它内部的鍵值對是無序的、唯一的。它的内部實作了一個所有value為null的特殊字典。
集合中的最後一個元素被移除之後，資料結構被自動删除，記憶體被回收。
set(集合)由于其特殊去重複的功能，我們可以用來存儲活動中中獎的使用者的ID，這樣可以保證一個使用者不會中獎兩次。
sadd -> 添加集合成員，key值集合名稱，member值集合元素，元素不能重複
sadd key member [member …]
smembers -> 檢視集合中所有的元素，注意是無序的
smembers key
sismember -> 查詢集合中是否包含某個元素
sismember key member
scard -> 擷取集合的長度
scard key
spop -> 彈出元素，count指彈出元素的個數
spop key [count]
zset(有序集合)是Redis中最常問的資料結構。它類似于Java語言中的SortedSet和HashMap的結合體，它一方面通過set來保證内部value值的唯一性，另一方面通過value的score（權重）來進行排序。這個排序的功能是通過Skip List（跳躍清單）來實作的。
zset(有序集合)的最後一個元素value被移除後，資料結構被自動删除，記憶體被回收。
利用zset的去重和有序的效果可以由很多使用場景，舉兩個例子：
存儲粉絲清單，value是粉絲的ID，score是關注時間戳，這樣可以對粉絲關注進行排序
存儲學生成績，value使學生的ID，score是學生的成績，這樣可以對學生的成績排名
zadd key [NX|XX] [CH] [INCR] score member [score member …]
超出範圍的下标并不會引起錯誤。 比如說，當 start 的值比有序集的最大下标還要大，或是 start > stop 時， zrange 指令隻是簡單地傳回一個空清單。 另一方面，假如 stop 參數的值比有序集的最大下标還要大，那麼 Redis 将 stop 當作最大下标來處理。
可以通過使用 WITHSCORES 選項，來讓成員和它的 score 值一并傳回，傳回清單以 value1,score1, …, valueN,scoreN 的格式表示。 用戶端庫可能會傳回一些更複雜的資料類型，比如數組、元組等。
zrange key start stop [WITHSCORES]
其中成員的位置按 score 值遞減(從大到小)來排列。 具有相同 score 值的成員按字典序的逆序(reverse lexicographical order)排列。 除了成員按 score 值遞減的次序排列這一點外， ZREVRANGE 指令的其他方面和 ZRANGE key start stop [WITHSCORES] 指令一樣
zrevrange key start stop [WITHSCORES]
zcard key
zscore key member z
排名以 0 為底，也就是說，score 值最小的成員排名為 0
zrank key member
min 和 max 可以是 -inf 和 +inf ，這樣一來，你就可以在不知道有序集的最低和最高 score 值的情況下，使用 [ZRANGEBYSCORE]這類指令。
預設情況下，區間的取值使用閉區間，你也可以通過給參數前增加 ( 符号來使用可選的[開區間]小于或大于)
zrangebyscore key min max [WITHSCORES] [LIMIT offset count]
zrem key member [member …]
跳表全稱叫做跳躍表，簡稱跳表。跳表是一個随機化的資料結構，實質就是一種可以進行二分查找的有序連結清單。跳表在原有的有序連結清單上面增加了多級索引，通過索引來實作快速查找。跳表不僅能提高搜尋性能，同時也可以提高插入和删除操作的性能。
Skip List(跳躍清單)這種随機的資料結構，可以看做是一個二叉樹的變種，它在性能上與紅黑樹、AVL樹很相近；但是Skip List(跳躍清單)的實作相比前兩者要簡單很多，目前Redis的zset實作采用了Skip List(跳躍清單)（其它還有LevelDB等也使用了跳躍清單）。
RBT紅黑樹與Skip List(跳躍清單)簡單對比：
RBT紅黑樹
插入、查詢時間複雜度O(logn)
資料天然有序
實作複雜，設計變色、左旋右旋平衡等操作
需要加鎖
Skip List跳躍清單
實作簡單，連結清單結構
無需加鎖
這裡貼出Skip List的論文，需要詳細研究的請看論文，下文部分公式、代碼、圖檔出自該論文。
Skip Lists: A Probabilistic Alternative to Balanced Trees
https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf
先通過一張動圖來了解Skip List的插入節點元素的流程，此圖來自維基百科。
2.3.1 計算随機層數算法
首先分析的是執行插入操作時計算随機數的過程，這個過程會涉及層數的計算，是以十分重要。對于節點他有如下特性：
節點都有第一層的指針
節點有第i層指針，那麼第i+1層出現的機率為p
節點有最大層數限制，MaxLevel
計算随機層數的僞代碼：
論文中的示例
Java版本
代碼中包含兩個變量P和MaxLevel，在Redis中這兩個參數的值分别是：
2.3.2 節點包含的平均指針數目
Skip List屬于空間換時間的資料結構，這裡的空間指的就是每個節點包含的指針數目，這一部分是額外的内記憶體開銷，可以用來度量空間複雜度。random()是個随機數，是以産生越高的節點層數，機率越低（Redis标準源碼中的晉升率資料1/4，相對來說Skip List的結構是比較扁平的，層高相對較低）。其定量分析如下：
level = 1 機率為1-p
level >=2 機率為p
level = 2 機率為p(1-p)
level >= 3 機率為p^2
level = 3 機率為p^2(1-p)
level >=4 機率為p^3
level = 4 機率為p^3(1-p)
……
得出節點的平均層數（節點包含的平均指針數目）：
是以Redis中p=1/4計算的平均指針數目為1.33
2.3.3 時間複雜度計算
以下推算來自論文内容
假設p=1/2，在以p=1/2生成的16個元素的跳過清單中，我們可能碰巧具有9個元素，1級3個元素，3個元素3級元素和1個元素14級（這不太可能，但可能會發生）。我們該怎麼處理這種情況？如果我們使用标準算法并在第14級開始我們的搜尋，我們将會做很多無用的工作。那麼我們應該從哪裡開始搜尋？此時我們假設SkipList中有n個元素，第L層級元素個數的期望是1/p個；每個元素出現在L層的機率是p^(L-1), 那麼第L層級元素個數的期望是 n * (p^L-1)；得到1 / p =n * (p^L-1)
是以我們應該選擇MaxLevel = log(1/p)^n
定義：MaxLevel = L(n) = log(1/p)^n
推算Skip List的時間複雜度，可以用逆向思維，從層數為i的節點x出發，傳回起點的方式來回溯時間複雜度，節點x點存在兩種情況：
節點x存在(i+1)層指針，那麼向上爬一級，機率為p，對應下圖situation c.
節點x不存在(i+1)層指針，那麼向左爬一級，機率為1-p，對應下圖situation b.
設C(k) = 在無限清單中向上攀升k個level的搜尋路徑的預期成本（即長度）那麼推演如下：
上面推演的結果可知，爬升k個level的預期長度為k/p，爬升一個level的長度為1/p。
由于MaxLevel = L(n)， C(k) = k / p，是以期望值為：(L(n) – 1) / p；将L(n) = log(1/p)^n 代入可得：(log(1/p)^n - 1) / p；将p = 1 / 2 代入可得：2 * log2^n - 2，即O(logn)的時間複雜度。
Skip List跳躍清單通常具有如下這些特性
Skip List包含多個層，每層稱為一個level，level從0開始遞增
Skip List 0層，也就是最底層，應該包含所有的元素
每一個level/層都是一個有序的清單
level小的層包含level大的層的元素，也就是說元素A在X層出現，那麼 想X>Z>=0的level/層都應該包含元素A
每個節點元素由節點key、節點value和指向目前節點所在level的指針數組組成
假設初始Skip List跳躍清單中已經存在這些元素，他們分布的結構如下所示：
此時查詢節點88，它的查詢路線如下所示：
從Skip List跳躍清單最頂層level3開始，往後查詢到10 < 88 && 後續節點值為null && 存在下層level2
level2 10往後周遊，27 < 88 && 後續節點值為null && 存在下層level1
level1 27往後周遊，88 = 88，查詢命中
Skip List的初始結構與2.3中的初始結構一緻，此時假設插入的新節點元素值為90，插入路線如下所示：
查詢插入位置，與Skip List查詢方式一緻，這裡需要查詢的是第一個比90大的節點位置，插入在這個節點的前面， 88 < 90 < 100
構造一個新的節點Node(90)，為插入的節點Node(90)計算一個随機level，這裡假設計算的是1，這個level時随機計算的，可能時1、2、3、4…均有可能，level越大的可能越小，主要看随機因子x ，層數的機率大緻計算為 (1/x)^level ，如果level大于目前的最大level3，需要新增head和tail節點
節點構造完畢後，需要将其插入清單中，插入十分簡單步驟 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);
删除的流程就是查詢到節點，然後删除，重新将删除節點左右兩邊的節點以連結清單的形式組合起來即可，這裡不再畫圖
實作一個Skip List比較簡單，主要分為兩個步驟：
定義Skip List的節點Node，節點之間以連結清單的形式存儲，是以節點持有相鄰節點的指針，其中prev與next是同一level的前後節點的指針，down與up是同一節點的多個level的上下節點的指針
定義Skip List的實作類，包含節點的插入、删除、查詢，其中查詢操作分為升序查詢和降序查詢（往後和往前查詢），這裡實作的Skip List預設節點之間的元素是升序連結清單
Node節點類主要包括如下重要屬性：
score -> 節點的權重，這個與Redis中的score相同，用來節點元素的排序作用
value -> 節點存儲的真實資料，隻能存儲String類型的資料
prev -> 目前節點的前驅節點，同一level
next -> 目前節點的後繼節點，同一level
down -> 目前節點的下層節點，同一節點的不同level
up -> 目前節點的上層節點，同一節點的不同level
SkipList主要包括如下重要屬性：
head -> SkipList中的頭節點的最上層頭節點（level最大的層的頭節點），這個節點不存儲元素，是為了建構清單和查詢時做查詢起始位置的，具體的結構請看2.3中的結構
tail -> SkipList中的尾節點的最上層尾節點（level最大的層的尾節點），這個節點也不存儲元素，是查詢某一個level的終止标志
level -> 總層數
size -> Skip List中節點元素的個數
random -> 用于随機計算節點level，如果 random.nextDouble() < 1/2則需要增加目前節點的level，如果目前節點增加的level超過了總的level則需要增加head和tail(總level)
點選關注，第一時間了解華為雲新鮮技術~