一、簡介

Redis中所有的的數(shù)據(jù)結(jié)構(gòu)都是通過一個唯一的字符串key來獲取相應(yīng)的value數(shù)據(jù)。
Redis有5種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，分別是：

• string（字符串）
• list（列表）
• hash（字典）
• set（集合）
• zset（有序集合）

其中l(wèi)ist、set、hash、zset這四種數(shù)據(jù)結(jié)構(gòu)是容器型數(shù)據(jù)結(jié)構(gòu)，它們共享下面兩條通用規(guī)則：

• create if not exists：容器不存在則創(chuàng)建
• drop if no elements：如果容器中沒有元素，則立即刪除容器，釋放內(nèi)存

本文將詳細講述的是Redis的5種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。

二、string（字符串）

1、string(字符串)相關(guān)介紹

1.1 string(字符串)的內(nèi)部結(jié)構(gòu)

string(字符串)是Redis最簡單也是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)，它的內(nèi)部是一個字符數(shù)組。如圖所示：

Redis中string(字符串)是動態(tài)字符串，允許修改；它在結(jié)構(gòu)上的實現(xiàn)類似于Java中的ArrayList（默認構(gòu)造一個大小為10的初始數(shù)組），這是冗余分配內(nèi)存的思想，也稱為預(yù)分配；這種思想可以減少擴容帶來的性能消耗。

1.2 string(字符串)的擴容

當(dāng)string(字符串)的大小達到擴容閾值時，將會對string(字符串)進行擴容，string(字符串)的擴容主要有以下幾個點：

1. 長度小于1MB，擴容后為原先的兩倍; length = length * 2
2. 長度大于1MB，擴容后增加1MB; length = length + 1MB
3. 字符串的長度最大值為 512MB

2、string(字符串)的指令

2.1 單個鍵值對增刪改查操作

set -> key 不存在則新增，存在則修改

set key value

get -> 查詢，返回對應(yīng)key的value，不存在返回(nil)

get key

del -> 刪除指定的key(key可以是多個)

del key [key …]

示例：

 1127.0.0.1:6379> set name liziba
 2OK
 3127.0.0.1:6379> get name
 4"liziba"
 5127.0.0.1:6379> set name liziba001
 6OK
 7127.0.0.1:6379> get name
 8"liziba001"
 9127.0.0.1:6379> del name
10(integer) 1
11127.0.0.1:6379> get name
12(nil)

2.2 批量鍵值對

批量鍵值讀取和寫入最大的優(yōu)勢在于節(jié)省網(wǎng)絡(luò)傳輸開銷

mset -> 批量插入

mset key value [key value …]

mget -> 批量獲取

mget key [key …]

示例：

1127.0.0.1:6379> mset name1 liziba1 name2 liziba2 name3 liziba3
2OK
3127.0.0.1:6379> mget name1 name2 name3
41) "liziba1"
52) "liziba2"
63) "liziba3"

2.3 過期set命令

過期set是通過設(shè)置一個緩存key的過期時間，使得緩存到期后自動刪除從而失效的機制。
?
方式一：

expire key seconds

示例：

1127.0.0.1:6379> set name liziba
2OK
3127.0.0.1:6379> get name
4"liziba"
5127.0.0.1:6379> expire name 10   # 10s 后get name 返回 nil
6(integer) 1
7127.0.0.1:6379> get name
8(nil)

方式二：

setex key seconds value

示例：

1127.0.0.1:6379> setex name 10 liziba    # 10s 后get name 返回 nil
2OK
3127.0.0.1:6379> get name
4(nil)

2.4 不存在創(chuàng)建存在不更新

上面的set操作不存在創(chuàng)建，存在則更新；此時如果需要存在不更新的場景，那么可以使用如下這個指令
?
setnx -> 不存在創(chuàng)建存在不更新

setnx key value

示例：

 1127.0.0.1:6379> get name
 2(nil)
 3127.0.0.1:6379> setnx name liziba        
 4(integer) 1
 5127.0.0.1:6379> get name
 6"liziba"
 7127.0.0.1:6379> setnx name liziba_98        # 已經(jīng)存在再次設(shè)值，失敗
 8(integer) 0
 9127.0.0.1:6379> get name
10"liziba"

2.5計數(shù)

string(字符串)也可以用來計數(shù)，前提是value是一個整數(shù)，那么可以對它進行自增的操作。自增的范圍必須在signed long的區(qū)間訪問內(nèi)，[-9223372036854775808,9223372036854775808]

incr -> 自增1

incr key

示例：

1127.0.0.1:6379> set fans 1000
2OK
3127.0.0.1:6379> incr fans # 自增1
4(integer) 1001

incrby -> 自定義累加值

1127.0.0.1:6379> set fans 1000
2OK
3127.0.0.1:6379> incr fans
4(integer) 1001
5127.0.0.1:6379> incrby fans 999
6(integer) 2000

測試value為整數(shù)的自增區(qū)間

最大值：

1127.0.0.1:6379> set fans 9223372036854775808
2OK
3127.0.0.1:6379> incr fans
4(error) ERR value is not an integer or out of range

最小值：

1127.0.0.1:6379> set money -9223372036854775808
2OK
3127.0.0.1:6379> incrby money -1
4(error) ERR increment or decrement would overflow

三、list（列表）

1、list(列表)相關(guān)介紹

1.1 list(列表)的內(nèi)部結(jié)構(gòu)

Redis的列表相當(dāng)于Java語言中的LinkedList，它是一個雙向鏈表數(shù)據(jù)結(jié)構(gòu)（但是這個結(jié)構(gòu)設(shè)計比較巧妙，后面會介紹），支持前后順序遍歷。鏈表結(jié)構(gòu)插入和刪除操作快，時間復(fù)雜度O(1)，查詢慢，時間復(fù)雜度O(n)。

1.2 list(列表)的使用場景

根據(jù)Redis雙向列表的特性，因此其也被用于異步隊列的使用。實際開發(fā)中將需要延后處理的任務(wù)結(jié)構(gòu)體序列化成字符串，放入Redis的隊列中，另一個線程從這個列表中獲取數(shù)據(jù)進行后續(xù)處理。其流程類似如下的圖：
?

2、list(列表)的指令

2.1 右進左出—隊列

隊列在結(jié)構(gòu)上是先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)（比如排隊購票的順序），常用于消息隊列類似的功能，例如消息排隊、異步處理等場景。通過它可以確保元素的訪問順序。
lpush -> 從左邊邊添加元素

lpush key value [value …]

rpush -> 從右邊添加元素

rpush key value [value …]

llen -> 獲取列表的長度

llen key

lpop -> 從左邊彈出元素

lpop key

 1127.0.0.1:6379> rpush code java c python    # 向列表中添加元素
 2(integer) 3
 3127.0.0.1:6379> llen code    # 獲取列表長度
 4(integer) 3
 5127.0.0.1:6379> lpop code # 彈出最先添加的元素
 6"java"
 7127.0.0.1:6379> lpop code    
 8"c"
 9127.0.0.1:6379> lpop code
10"python"
11127.0.0.1:6379> llen code
12(integer) 0
13127.0.0.1:6379> lpop code
14(nil)

2.2 右進右出——棧

棧在結(jié)構(gòu)上是先進后出（FILO）的數(shù)據(jù)結(jié)構(gòu)（比如彈夾壓入子彈，子彈被射擊出去的順序就是棧），這種數(shù)據(jù)結(jié)構(gòu)一般用來逆序輸出。
lpush -> 從左邊邊添加元素

lpush key value [value …]

rpush -> 從右邊添加元素

rpush key value [value …]

rpop -> 從右邊彈出元素

rpop code

 1127.0.0.1:6379> rpush code java c python
 2(integer) 3
 3127.0.0.1:6379> rpop code            # 彈出最后添加的元素
 4"python"
 5127.0.0.1:6379> rpop code
 6"c"
 7127.0.0.1:6379> rpop code
 8"java"
 9127.0.0.1:6379> rpop code
10(nil)

2.3 慢操作

列表(list)是個鏈表數(shù)據(jù)結(jié)構(gòu)，它的遍歷是慢操作，所以涉及到遍歷的性能將會遍歷區(qū)間range的增大而增大。注意list的索引運行為負數(shù)，-1代表倒數(shù)第一個，-2代表倒數(shù)第二個，其它同理。
lindex -> 遍歷獲取列表指定索引處的值

lindex key ind

lrange -> 獲取從索引start到stop處的全部值

lrange key start stop

ltrim -> 截取索引start到stop處的全部值，其它將會被刪除

ltrim key start stop

 1127.0.0.1:6379> rpush code java c python
 2(integer) 3
 3127.0.0.1:6379> lindex code 0        # 獲取索引為0的數(shù)據(jù)
 4"java"
 5127.0.0.1:6379> lindex code 1   # 獲取索引為1的數(shù)據(jù)
 6"c"
 7127.0.0.1:6379> lindex code 2        # 獲取索引為2的數(shù)據(jù)
 8"python"
 9127.0.0.1:6379> lrange code 0 -1    # 獲取全部 0 到倒數(shù)第一個數(shù)據(jù)  == 獲取全部數(shù)據(jù)
101) "java"
112) "c"
123) "python"
13127.0.0.1:6379> ltrim code 0 -1    # 截取并保理 0 到 -1 的數(shù)據(jù) == 保理全部
14OK
15127.0.0.1:6379> lrange code 0 -1
161) "java"
172) "c"
183) "python"
19127.0.0.1:6379> ltrim code 1 -1    # 截取并保理 1 到 -1 的數(shù)據(jù) == 移除了索引為0的數(shù)據(jù) java
20OK
21127.0.0.1:6379> lrange code 0 -1
221) "c"
232) "python"

3、list(列表)深入理解

Redis底層存儲list(列表)不是一個簡單的LinkedList，而是quicklist ——“快速列表”。關(guān)于quicklist是什么，下面會簡單介紹，具體源碼我也還在學(xué)習(xí)中，后面大家一起探討。
quicklist是多個ziplist(壓縮列表)組成的雙向列表；而這個ziplist(壓縮列表)又是什么呢？ziplist指的是一塊連續(xù)的內(nèi)存存儲空間，Redis底層對于list(列表)的存儲，當(dāng)元素個數(shù)少的時候，它會使用一塊連續(xù)的內(nèi)存空間來存儲，這樣可以減少每個元素增加prev和next指針帶來的內(nèi)存消耗，最重要的是可以減少內(nèi)存碎片化問題。
?

3.1 常見的鏈表結(jié)構(gòu)示意圖

每個node節(jié)點元素，都會持有一個prev->執(zhí)行前一個node節(jié)點和next->指向后一個node節(jié)點的指針（引用），這種結(jié)構(gòu)雖然支持前后順序遍歷，但是也帶來了不小的內(nèi)存開銷，如果node節(jié)點僅僅是一個int類型的值，那么可想而知，引用的內(nèi)存比例將會更大。

3.2 ziplist示意圖

ziplist是一塊連續(xù)的內(nèi)存地址，他們之間無需持有prev和next指針，能通過地址順序?qū)ぶ吩L問。

3.3 quicklist示意圖

quicklist是由多個ziplist組成的雙向鏈表。

四、hash（字典）?

1、hash(字典)相關(guān)介紹

1.1 hash(字典)的內(nèi)部結(jié)構(gòu)

Redis的hash(字典)相當(dāng)于Java語言中的HashMap，它是根據(jù)散列值分布的無序字典，內(nèi)部的元素是通過鍵值對的方式存儲。

hash(字典)的實現(xiàn)與Java中的HashMap（JDK1.7）的結(jié)構(gòu)也是一致的，它的數(shù)據(jù)結(jié)構(gòu)也是數(shù)組+鏈表組成的二維結(jié)構(gòu)，節(jié)點元素散列在數(shù)組上，如果發(fā)生hash碰撞則使用鏈表串聯(lián)在數(shù)組節(jié)點上。

1.2 hash(字典)擴容

Redis中的hash(字典)存儲的value只能是字符串值，此外擴容與Java中的HashMap也不同。Java中的HashMap在擴容的時候是一次性完成的，而Redis考慮到其核心存取是單線程的性能問題，為了追求高性能，因而采取了漸進式rehash策略。
漸進式rehash指的是并非一次性完成，它是多次完成的，因此需要保理舊的hash結(jié)構(gòu)，所以Redis中的hash(字典)會存在新舊兩個hash結(jié)構(gòu)，在rehash結(jié)束后也就是舊hash的值全部搬遷到新hash之后，新的hash在功能上才會完全替代以前的hash。

1.3 hash(字典)的相關(guān)使用場景

hash(字典)可以用來存儲對象的相關(guān)信息，一個hash(字典)代表一個對象，hash的一個key代表對象的一個屬性，key的值代表屬性的值。hash(字典)結(jié)構(gòu)相比字符串來說，它無需將整個對象進行序列化后進行存儲。這樣在獲取的時候可以進行部分獲取。所以相比之下hash(字典)具有如下的優(yōu)缺點：

• 讀取可以部分讀取，節(jié)省網(wǎng)絡(luò)流量
• 存儲消耗的高于單個字符串的存儲

2 hash(字典)相關(guān)指令

2.1 hash(字典)常用指令

hset -> hash(字典)插入值，字典不存在則創(chuàng)建 key代表字典名稱，field 相當(dāng)于 key，value是key的值

hset key field value

hmset -> 批量設(shè)值

hmset key field value [field value …]

示例：

17.0.0.1:6379> hset book java "Thinking in Java"        # 字符串包含空格需要""包裹
2(integer) 1
3127.0.0.1:6379> hset book python "Python code"
4(integer) 1
5127.0.0.1:6379> hset book c "The best of c"
6(integer) 1
7127.0.0.1:6379> hmset book go "concurrency in go" mysql "high-performance MySQL" # 批量設(shè)值
8OK

hget -> 獲取字典中的指定key的value

hget key field

hgetall -> 獲取字典中所有的key和value，換行輸出

hgetall key

示例：

1127.0.0.1:6379> hget book java
2"Thinking in Java"
3127.0.0.1:6379> hgetall book
41) "java"
52) "Thinking in Java"
63) "python"
74) "Python code"
85) "c"
96) "The best of c"

hlen -> 獲取指定字典的key的個數(shù)

hlen key

舉例：

1127.0.0.1:6379> hlen book
2(integer) 5

2.2 hash(字典)使用小技巧

在string(字符串)中可以使用incr和incrby對value是整數(shù)的字符串進行自加操作，在hash(字典)結(jié)構(gòu)中如果單個子key是整數(shù)也可以進行自加操作。
hincrby -> 增對hash(字典)中的某個key的整數(shù)value進行自加操作

hincrby key field increment

1127.0.0.1:6379> hset liziba money 10
2(integer) 1
3127.0.0.1:6379> hincrby liziba money -1
4(integer) 9
5127.0.0.1:6379> hget liziba money
6"9"

注意如果不是整數(shù)會報錯。

1127.0.0.1:6379> hset liziba money 10.1
2(integer) 1
3127.0.0.1:6379> hincrby liziba money 1
4(error) ERR hash value is not an integer

五、set（集合）

1、set(集合)相關(guān)介紹

1.1 set(集合)的內(nèi)部結(jié)構(gòu)

Redis的set(集合)相當(dāng)于Java語言里的HashSet，它內(nèi)部的鍵值對是無序的、唯一的。它的內(nèi)部實現(xiàn)了一個所有value為null的特殊字典。
集合中的最后一個元素被移除之后，數(shù)據(jù)結(jié)構(gòu)被自動刪除，內(nèi)存被回收。

1.2 set(集合)的使用場景

set(集合)由于其特殊去重復(fù)的功能，我們可以用來存儲活動中中獎的用戶的ID，這樣可以保證一個用戶不會中獎兩次。
?

2、set(集合)相關(guān)指令

sadd -> 添加集合成員，key值集合名稱，member值集合元素，元素不能重復(fù)

sadd key member [member …]

1127.0.0.1:6379> sadd name zhangsan
2(integer) 1
3127.0.0.1:6379> sadd name zhangsan        # 不能重復(fù)，重復(fù)返回0
4(integer) 0
5127.0.0.1:6379> sadd name lisi wangwu liumazi # 支持一次添加多個元素
6(integer) 3

smembers -> 查看集合中所有的元素，注意是無序的

smembers key

1127.0.0.1:6379> smembers name    # 無序輸出集合中所有的元素
21) "lisi"
32) "wangwu"
43) "liumazi"
54) "zhangsan"

sismember -> 查詢集合中是否包含某個元素

sismember key member

127.0.0.1:6379> sismember name lisi  # 包含返回1
(integer) 1
127.0.0.1:6379> sismember name tianqi # 不包含返回0
(integer) 0

scard -> 獲取集合的長度

scard key

1127.0.0.1:6379> scard name
2(integer) 4

spop -> 彈出元素，count指彈出元素的個數(shù)

spop key [count]

127.0.0.1:6379> spop name            # 默認彈出一個
"wangwu"
127.0.0.1:6379> spop name 3    
1) "lisi"
2) "zhangsan"
3) "liumazi

六、zset（有序集合）

1、zset(有序集合)相關(guān)介紹

1.1 zset(有序集合)的內(nèi)部結(jié)構(gòu)

zset(有序集合)是Redis中最常問的數(shù)據(jù)結(jié)構(gòu)。它類似于Java語言中的SortedSet和HashMap的結(jié)合體，它一方面通過set來保證內(nèi)部value值的唯一性，另一方面通過value的score（權(quán)重）來進行排序。這個排序的功能是通過Skip List（跳躍列表）來實現(xiàn)的。
zset(有序集合)的最后一個元素value被移除后，數(shù)據(jù)結(jié)構(gòu)被自動刪除，內(nèi)存被回收。

1.2 zset(有序集合)的相關(guān)使用場景

利用zset的去重和有序的效果可以由很多使用場景，舉兩個例子：

• 存儲粉絲列表，value是粉絲的ID，score是關(guān)注時間戳，這樣可以對粉絲關(guān)注進行排序
• 存儲學(xué)生成績，value使學(xué)生的ID，score是學(xué)生的成績，這樣可以對學(xué)生的成績排名

2、zset(有序集合)相關(guān)指令

1、zadd -> 向集合中添加元素，集合不存在則新建，key代表zset集合名稱，score代表元素的權(quán)重，member代表元素

zadd key [NX|XX] [CH] [INCR] score member [score member …]

127.0.0.1:6379> zadd name 10 zhangsan
(integer) 1
127.0.0.1:6379> zadd name 10.1 lisi
(integer) 1
127.0.0.1:6379> zadd name 9.9 wangwu
(integer) 1

2、zrange -> 按照score權(quán)重從小到大排序輸出集合中的元素，權(quán)重相同則按照value的字典順序排序([lexicographical order])
超出范圍的下標并不會引起錯誤。 比如說，當(dāng) start 的值比有序集的最大下標還要大，或是 start > stop 時， zrange 命令只是簡單地返回一個空列表。 另一方面，假如 stop 參數(shù)的值比有序集的最大下標還要大，那么 Redis 將 stop 當(dāng)作最大下標來處理。
可以通過使用 WITHSCORES 選項，來讓成員和它的 score 值一并返回，返回列表以 value1,score1, …, valueN,scoreN 的格式表示。 客戶端庫可能會返回一些更復(fù)雜的數(shù)據(jù)類型，比如數(shù)組、元組等。

zrange key start stop [WITHSCORES]

127.0.0.1:6379> zrange name 0 -1 # 獲取所有元素，按照score的升序輸出
1) "wangwu"
2) "zhangsan"
3) "lisi"
127.0.0.1:6379> zrange name 0 1        # 獲取第一個和第二個slot的元素
1) "wangwu"
2) "zhangsan"
127.0.0.1:6379> zadd name 10 tianqi    # 在上面的基礎(chǔ)上添加score為10的元素
(integer) 1
127.0.0.1:6379> zrange name 0 2    # key相等則按照value字典排序輸出
1) "wangwu"
2) "tianqi"
3) "zhangsan"
127.0.0.1:6379> zrange name 0 -1 WITHSCORES # WITHSCORES 輸出權(quán)重
1) "wangwu"
2) "9.9000000000000004"
3) "tianqi"
4) "10"
5) "zhangsan"
6) "10"
7) "lisi"
8) "10.1"

3、zrevrange -> 按照score權(quán)重從大到小輸出集合中的元素，權(quán)重相同則按照value的字典逆序排序
其中成員的位置按 score 值遞減(從大到小)來排列。 具有相同 score 值的成員按字典序的逆序(reverse lexicographical order)排列。 除了成員按 score 值遞減的次序排列這一點外， ZREVRANGE 命令的其他方面和 ZRANGE key start stop [WITHSCORES] 命令一樣

zrevrange key start stop [WITHSCORES]

127.0.0.1:6379> zrevrange name 0 -1 WITHSCORES
1) "lisi"
2) "10.1"
3) "zhangsan"
4) "10"
5) "tianqi"
6) "10"
7) "wangwu"
8) "9.9000000000000004"

4、zcard -> 當(dāng) key 存在且是有序集類型時，返回有序集的基數(shù)。 當(dāng) key 不存在時，返回 0

zcard key

127.0.0.1:6379> zcard name
(integer) 4

5、zscore -> 返回有序集 key 中，成員 member 的 score 值，如果 member 元素不是有序集 key 的成員，或 key 不存在，返回 nil

zscore key member z

127.0.0.1:6379> zscore name zhangsan
"10"
127.0.0.1:6379> zscore name liziba
(nil)

6、zrank -> 返回有序集 key 中成員 member 的排名。其中有序集成員按 score 值遞增(從小到大)順序排列。
排名以 0 為底，也就是說，score 值最小的成員排名為 0

zrank key member

127.0.0.1:6379> zrange name 0 -1
1) "wangwu"
2) "tianqi"
3) "zhangsan"
4) "lisi"
127.0.0.1:6379> zrank name wangwu
(integer) 0

7、zrangebyscore -> 返回有序集 key 中，所有 score 值介于 min 和 max 之間(包括等于 min 或 max )的成員。有序集成員按 score 值遞增(從小到大)次序排列。
min 和 max 可以是 -inf 和 +inf ，這樣一來，你就可以在不知道有序集的最低和最高 score 值的情況下，使用 [ZRANGEBYSCORE]這類命令。
默認情況下，區(qū)間的取值使用閉區(qū)間，你也可以通過給參數(shù)前增加 ( 符號來使用可選的[開區(qū)間]小于或大于)

zrangebyscore key min max [WITHSCORES] [LIMIT offset count]

127.0.0.1:6379> zrange name 0 -1 WITHSCORES # 輸出全部元素
1) "wangwu"
2) "9.9000000000000004"
3) "tianqi"
4) "10"
5) "zhangsan"
6) "10"
7) "lisi"
8) "10.1" 
127.0.0.1:6379> zrangebyscore name 9 10
1) "wangwu"
2) "tianqi"
3) "zhangsan"
127.0.0.1:6379> zrangebyscore name 9 10 WITHSCORES    # 輸出分數(shù)
1) "wangwu"
2) "9.9000000000000004"
3) "tianqi"
4) "10"
5) "zhangsan"
6) "10"
127.0.0.1:6379> zrangebyscore name -inf 10 # -inf 從負無窮開始
1) "wangwu"
2) "tianqi"
3) "zhangsan"
127.0.0.1:6379> zrangebyscore name -inf +inf    # +inf 直到正無窮
1) "wangwu"
2) "tianqi"
3) "zhangsan"
4) "lisi"
127.0.0.1:6379> zrangebyscore name (10 11  #  10 < score <=11
1) "lisi"
127.0.0.1:6379> zrangebyscore name (10 (10.1  # 10 < socre < -11
(empty list or set)
127.0.0.1:6379> zrangebyscore name (10 (11 
1) "lisi"

8、zrem -> 移除有序集 key 中的一個或多個成員，不存在的成員將被忽略

zrem key member [member …]

 127.0.0.1:6379> zrange name 0 -1
 1) "wangwu"
 2) "tianqi"
 3) "zhangsan"
 4) "lisi"
 127.0.0.1:6379> zrem name zhangsan # 移除元素
 (integer) 1
 127.0.0.1:6379> zrange name 0 -1
 1) "wangwu"
 2) "tianqi"
 3) "lisi"

七、Skip List

1、簡介

跳表全稱叫做跳躍表，簡稱跳表。跳表是一個隨機化的數(shù)據(jù)結(jié)構(gòu)，實質(zhì)就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現(xiàn)快速查找。跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。

Skip List(跳躍列表)這種隨機的數(shù)據(jù)結(jié)構(gòu)，可以看做是一個二叉樹的變種，它在性能上與紅黑樹、AVL樹很相近；但是Skip List(跳躍列表)的實現(xiàn)相比前兩者要簡單很多，目前Redis的zset實現(xiàn)采用了Skip List(跳躍列表)（其它還有LevelDB等也使用了跳躍列表）。

RBT紅黑樹與Skip List(跳躍列表)簡單對比：
RBT紅黑樹

1. 插入、查詢時間復(fù)雜度O(logn)
2. 數(shù)據(jù)天然有序
3. 實現(xiàn)復(fù)雜，設(shè)計變色、左旋右旋平衡等操作
4. 需要加鎖

Skip List跳躍列表

1. 插入、查詢時間復(fù)雜度O(logn)
2. 數(shù)據(jù)天然有序
3. 實現(xiàn)簡單，鏈表結(jié)構(gòu)
4. 無需加鎖

2、Skip List算法分析

2.1 Skip List論文

這里貼出Skip List的論文，需要詳細研究的請看論文，下文部分公式、代碼、圖片出自該論文。
Skip Lists: A Probabilistic Alternative to Balanced Trees

https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf

2.2 Skip List動態(tài)圖

先通過一張動圖來了解Skip List的插入節(jié)點元素的流程，此圖來自維基百科。

2.3 Skip List算法性能分析

2.3.1 計算隨機層數(shù)算法

首先分析的是執(zhí)行插入操作時計算隨機數(shù)的過程，這個過程會涉及層數(shù)的計算，所以十分重要。對于節(jié)點他有如下特性：

• 節(jié)點都有第一層的指針
• 節(jié)點有第i層指針，那么第i+1層出現(xiàn)的概率為p
• 節(jié)點有最大層數(shù)限制，MaxLevel

計算隨機層數(shù)的偽代碼：
論文中的示例

Java版本

public int randomLevel(){
    int level = 1;
    // random()返回一個[0...1)的隨機數(shù)
    while (random() < p && level < MaxLevel){ 
        level += 1;
    }
    return level;
}

代碼中包含兩個變量P和MaxLevel，在Redis中這兩個參數(shù)的值分別是：

1p = 1/4
2MaxLevel = 64

2.3.2 節(jié)點包含的平均指針數(shù)目

Skip List屬于空間換時間的數(shù)據(jù)結(jié)構(gòu)，這里的空間指的就是每個節(jié)點包含的指針數(shù)目，這一部分是額外的內(nèi)內(nèi)存開銷，可以用來度量空間復(fù)雜度。random()是個隨機數(shù)，因此產(chǎn)生越高的節(jié)點層數(shù)，概率越低（Redis標準源碼中的晉升率數(shù)據(jù)1/4，相對來說Skip List的結(jié)構(gòu)是比較扁平的，層高相對較低）。其定量分析如下：

• 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)
• ……

得出節(jié)點的平均層數(shù)（節(jié)點包含的平均指針數(shù)目）：

所以Redis中p=1/4計算的平均指針數(shù)目為1.33
?

2.3.3 時間復(fù)雜度計算

以下推算來自論文內(nèi)容
假設(shè)p=1/2，在以p=1/2生成的16個元素的跳過列表中，我們可能碰巧具有9個元素，1級3個元素，3個元素3級元素和1個元素14級（這不太可能，但可能會發(fā)生）。我們該怎么處理這種情況？如果我們使用標準算法并在第14級開始我們的搜索，我們將會做很多無用的工作。那么我們應(yīng)該從哪里開始搜索？此時我們假設(shè)SkipList中有n個元素，第L層級元素個數(shù)的期望是1/p個；每個元素出現(xiàn)在L層的概率是p^(L-1), 那么第L層級元素個數(shù)的期望是 n * (p^L-1)；得到1 / p =n * (p^L-1)

1 / p = n * (p^L-1)
n = (1/p)^L
L = log(1/p)^n

所以我們應(yīng)該選擇MaxLevel = log(1/p)^n
定義：MaxLevel = L(n) = log(1/p)^n
?

推算Skip List的時間復(fù)雜度，可以用逆向思維，從層數(shù)為i的節(jié)點x出發(fā)，返回起點的方式來回溯時間復(fù)雜度，節(jié)點x點存在兩種情況：

• 節(jié)點x存在(i+1)層指針，那么向上爬一級，概率為p，對應(yīng)下圖situation c.
• 節(jié)點x不存在(i+1)層指針，那么向左爬一級，概率為1-p，對應(yīng)下圖situation b.

設(shè)C(k) = 在無限列表中向上攀升k個level的搜索路徑的預(yù)期成本（即長度）那么推演如下：

C(0)=0
C(k)=(1-p)×(情況b的查找長度) + p×(情況c的查找長度)
C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)
C(k)=1/p+C(k-1)
C(k)=k/p

上面推演的結(jié)果可知，爬升k個level的預(yù)期長度為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)的時間復(fù)雜度。

3、Skip List特性及其實現(xiàn)

2.1 Skip List特性

Skip List跳躍列表通常具有如下這些特性

Skip List包含多個層，每層稱為一個level，level從0開始遞增Skip List 0層，也就是最底層，應(yīng)該包含所有的元素每一個level/層都是一個有序的列表level小的層包含level大的層的元素，也就是說元素A在X層出現(xiàn)，那么 想X>Z>=0的level/層都應(yīng)該包含元素A每個節(jié)點元素由節(jié)點key、節(jié)點value和指向當(dāng)前節(jié)點所在level的指針數(shù)組組成

2.2 Skip List查詢

假設(shè)初始Skip List跳躍列表中已經(jīng)存在這些元素，他們分布的結(jié)構(gòu)如下所示：

此時查詢節(jié)點88，它的查詢路線如下所示：

從Skip List跳躍列表最頂層level3開始，往后查詢到10 < 88 && 后續(xù)節(jié)點值為null && 存在下層level2level2 10往后遍歷，27 < 88 && 后續(xù)節(jié)點值為null && 存在下層level1level1 27往后遍歷，88 = 88，查詢命中

2.3 Skip List插入

Skip List的初始結(jié)構(gòu)與2.3中的初始結(jié)構(gòu)一致，此時假設(shè)插入的新節(jié)點元素值為90，插入路線如下所示：

查詢插入位置，與Skip List查詢方式一致，這里需要查詢的是第一個比90大的節(jié)點位置，插入在這個節(jié)點的前面， 88 < 90 < 100構(gòu)造一個新的節(jié)點Node(90)，為插入的節(jié)點Node(90)計算一個隨機level，這里假設(shè)計算的是1，這個level時隨機計算的，可能時1、2、3、4…均有可能，level越大的可能越小，主要看隨機因子x ，層數(shù)的概率大致計算為 (1/x)^level ，如果level大于當(dāng)前的最大level3，需要新增head和tail節(jié)點節(jié)點構(gòu)造完畢后，需要將其插入列表中，插入十分簡單步驟 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

2.4 Skip List刪除

刪除的流程就是查詢到節(jié)點，然后刪除，重新將刪除節(jié)點左右兩邊的節(jié)點以鏈表的形式組合起來即可，這里不再畫圖
?

4、手寫實現(xiàn)一個簡單Skip List

實現(xiàn)一個Skip List比較簡單，主要分為兩個步驟：

1. 定義Skip List的節(jié)點Node，節(jié)點之間以鏈表的形式存儲，因此節(jié)點持有相鄰節(jié)點的指針，其中prev與next是同一level的前后節(jié)點的指針，down與up是同一節(jié)點的多個level的上下節(jié)點的指針
2. 定義Skip List的實現(xiàn)類，包含節(jié)點的插入、刪除、查詢，其中查詢操作分為升序查詢和降序查詢（往后和往前查詢），這里實現(xiàn)的Skip List默認節(jié)點之間的元素是升序鏈表

3.1 定義Node節(jié)點

Node節(jié)點類主要包括如下重要屬性：

1. score -> 節(jié)點的權(quán)重，這個與Redis中的score相同，用來節(jié)點元素的排序作用
2. value -> 節(jié)點存儲的真實數(shù)據(jù)，只能存儲String類型的數(shù)據(jù)
3. prev -> 當(dāng)前節(jié)點的前驅(qū)節(jié)點，同一level
4. next -> 當(dāng)前節(jié)點的后繼節(jié)點，同一level
5. down -> 當(dāng)前節(jié)點的下層節(jié)點，同一節(jié)點的不同level
6. up -> 當(dāng)前節(jié)點的上層節(jié)點，同一節(jié)點的不同level

package com.liziba.skiplist;

/**
 * <p>
 *      跳表節(jié)點元素
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/7/5 21:01
 */
public class Node {

    /** 節(jié)點的分數(shù)值，根據(jù)分數(shù)值來排序 */
    public Double score;
    /** 節(jié)點存儲的真實數(shù)據(jù) */
    public String value;
    /** 當(dāng)前節(jié)點的 前、后、下、上節(jié)點的引用 */
    public Node prev, next, down, up;

    public Node(Double score) {
        this.score = score;
        prev = next = down = up = null;
    }

    public Node(Double score, String value) {
        this.score = score;
        this.value = value;
    }
}

3.2 SkipList節(jié)點元素的操作類

SkipList主要包括如下重要屬性：

1. head -> SkipList中的頭節(jié)點的最上層頭節(jié)點（level最大的層的頭節(jié)點），這個節(jié)點不存儲元素，是為了構(gòu)建列表和查詢時做查詢起始位置的，具體的結(jié)構(gòu)請看2.3中的結(jié)構(gòu)
2. tail -> SkipList中的尾節(jié)點的最上層尾節(jié)點（level最大的層的尾節(jié)點），這個節(jié)點也不存儲元素，是查詢某一個level的終止標志
3. level -> 總層數(shù)
4. size -> Skip List中節(jié)點元素的個數(shù)
5. random -> 用于隨機計算節(jié)點level，如果 random.nextDouble() < 1/2則需要增加當(dāng)前節(jié)點的level，如果當(dāng)前節(jié)點增加的level超過了總的level則需要增加head和tail(總level)

package com.liziba.skiplist;

import java.util.Random;

/**
 * <p>
 *      跳表實現(xiàn)
 * </p>
 *
 * @Author: Liziba
 */
public class SkipList {

    /** 最上層頭節(jié)點 */
    public Node head;
    /** 最上層尾節(jié)點 */
    public Node tail;
    /** 總層數(shù) */
    public int level;
    /** 元素個數(shù) */
    public int size;
    public Random random;

    public SkipList() {
        level = size = 0;
        head = new Node(null);
        tail = new Node(null);
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 查詢插入節(jié)點的前驅(qū)節(jié)點位置
     *
     * @param score
     * @return
     */
    public Node fidePervNode(Double score) {
        Node p = head;
        for(;;) {
            // 當(dāng)前層(level)往后遍歷，比較score，如果小于當(dāng)前值，則往后遍歷
            while (p.next.value == null && p.prev.score <= score)
                p = p.next;
            // 遍歷最右節(jié)點的下一層(level)
            if (p.down != null)
                p = p.down;
            else
                break;
        }
        return p;
    }

    /**
     * 插入節(jié)點，插入位置為fidePervNode(Double score)前面
     *
     * @param score
     * @param value
     */
    public void insert(Double score, String value) {

        // 當(dāng)前節(jié)點的前置節(jié)點
        Node preNode = fidePervNode(score);
        // 當(dāng)前新插入的節(jié)點
        Node curNode = new Node(score, value);
        // 分數(shù)和值均相等則直接返回
        if (curNode.value != null && preNode.value != null && preNode.value.equals(curNode.value)
                  && curNode.score.equals(preNode.score)) {
            return;
        }

        preNode.next = curNode;
        preNode.next.prev = curNode;
        curNode.next = preNode.next;
        curNode.prev = preNode;

        int curLevel = 0;
        while (random.nextDouble() < 1/2) {
            // 插入節(jié)點層數(shù)(level)大于等于層數(shù)(level)，則新增一層(level)
            if (curLevel >= level) {
                Node newHead = new Node(null);
                Node newTail = new Node(null);
                newHead.next = newTail;
                newHead.down = head;
                newTail.prev = newHead;
                newTail.down = tail;
                head.up = newHead;
                tail.up = newTail;
                // 頭尾節(jié)點指針修改為新的，確保head、tail指針一直是最上層的頭尾節(jié)點
                head = newHead;
                tail = newTail;
                ++level;
            }

            while (preNode.up == null)
                preNode = preNode.prev;

            preNode = preNode.up;

            Node copy = new Node(null);
            copy.prev = preNode;
            copy.next = preNode.next;
            preNode.next.prev = copy;
            preNode.next = copy;
            copy.down = curNode;
            curNode.up = copy;
            curNode = copy;

            ++curLevel;
        }
        ++size;
    }

    /**
     * 查詢指定score的節(jié)點元素
     * @param score
     * @return
     */
    public Node search(double score) {
        Node p = head;
        for (;;) {
            while (p.next.score != null && p.next.score <= score)
                p = p.next;
            if (p.down != null)
                p = p.down;
            else // 遍歷到最底層
                if (p.score.equals(score))
                    return p;
                return null;
        }
    }

    /**
     * 升序輸出Skip List中的元素 （默認升序存儲，因此從列表head往tail遍歷）
     */
    public void dumpAllAsc() {
        Node p = head;
        while (p.down != null) {
            p = p.down;
        }
        while (p.next.score != null) {
            System.out.println(p.next.score + "-->" + p.next.value);
            p = p.next;
        }
    }

    /**
     * 降序輸出Skip List中的元素
     */
    public void dumpAllDesc() {
        Node p = tail;
        while (p.down != null) {
            p = p.down;
        }
        while (p.prev.score != null) {
            System.out.println(p.prev.score + "-->" + p.prev.value);
            p = p.prev;
        }
    }


    /**
     * 刪除Skip List中的節(jié)點元素
     * @param score
     */
    public void delete(Double score) {
        Node p = search(score);
        while (p != null) {
            p.prev.next = p.next;
            p.next.prev = p.prev;
            p = p.up;
        }
    }
}

到此這篇關(guān)于多維度深入分析Redis的5種基本數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了。希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論