歡迎光臨
每天分享高質量文章

通俗易懂的 Redis 的 5 種資料結構基礎教程

點擊上方“芋道原始碼”,選擇“置頂公眾號”

技術文章第一時間送達!

原始碼精品專欄

 

Redis有5個基本資料結構,string、list、hash、set和zset。它們是日常開發中使用頻率非常高應用最為廣泛的資料結構,把這5個資料結構都吃透了,你就掌握了Redis應用知識的一半了。

string

首先我們從string談起。string表示的是一個可變的位元組陣列,我們初始化字串的內容、可以拿到字串的長度,可以獲取string的字串,可以改寫string的字串內容,可以追加子串。

Redis的字串是動態字串,是可以修改的字串,內部結構實現上類似於Java的ArrayList,採用預分配冗餘空間的方式來減少記憶體的頻繁分配,如圖中所示,內部為當前字串實際分配的空間capacity一般要高於實際字串長度len。當字串長度小於1M時,擴容都是加倍現有的空間,如果超過1M,擴容時一次只會多擴1M的空間。需要註意的是字串最大長度為512M。

初始化字串 需要提供「變數名稱」和「變數的內容」

set ireader beijing.zhangyue.keji.gufen.youxian.gongsi
OK

獲取字串的內容 提供「變數名稱」

get ireader
"beijing.zhangyue.keji.gufen.youxian.gongsi"

獲取字串的長度 提供「變數名稱」

> strlen ireader
(integer) 42

獲取子串 提供「變數名稱」以及開始和結束位置[start, end]

> getrange ireader 28 34
"youxian"

改寫子串 提供「變數名稱」以及開始位置和標的子串

setrange ireader 28 wooxian
(integer) 42  # 傳回長度
get ireader
"beijing.zhangyue.keji.gufen.wooxian.gongsi"

追加子串

append ireader .hao
(integer) 46 # 傳回長度
get ireader
"beijing.zhangyue.keji.gufen.wooxian.gongsi.hao"

遺憾的是字串沒有提供字串插入方法和子串刪除方法。

計數器
如果字串的內容是一個整數,那麼還可以將字串當成計數器來使用。

set ireader 42
OK
get ireader
"42"
> incrby ireader 100
(integer142
get ireader
"142"
> decrby ireader 100
(integer42
get ireader
"42"
> incr ireader  # 等價於incrby ireader 1
(integer143
> decr ireader  # 等價於decrby ireader 1
(integer142

計數器是有範圍的,它不能超過Long.Max,不能低於Long.MIN

set ireader 9223372036854775807
OK
> incr ireader
(errorERR increment or decrement would overflow
set ireader -9223372036854775808
OK
> decr ireader
(errorERR increment or decrement would overflow

過期和刪除 字串可以使用del指令進行主動刪除,可以使用expire指令設置過期時間,到點會自動刪除,這屬於被動刪除。可以使用ttl指令獲取字串的壽命。

> expire ireader 60
(integer1  # 1表示設置成功,0表示變數ireader不存在
> ttl ireader
(integer50  # 還有50秒的壽命,傳回-2表示變數不存在,-1表示沒有設置過期時間
> del ireader
(integer1  # 刪除成功傳回1
get ireader
(nil)  # 變數ireader沒有了

list

Redis將串列資料結構命名為list而不是array,是因為串列的儲存結構用的是鏈表而不是陣列,而且鏈表還是雙向鏈表。因為它是鏈表,所以隨機定位性能較弱,首尾插入刪除性能較優。如果list的串列長度很長,使用時我們一定要關註鏈表相關操作的時間複雜度。

負下標 鏈表元素的位置使用自然數0,1,2,....n-1表示,還可以使用負數-1,-2,...-n來表示,-1表示「倒數第一」,-2表示「倒數第二」,那麼-n就表示第一個元素,對應的下標為0

佇列/堆棧 鏈表可以從表頭和表尾追加和移除元素,結合使用rpush/rpop/lpush/lpop四條指令,可以將鏈表作為佇列或堆棧使用,左向右向進行都可以

# 右進左出
> rpush ireader go
(integer) 1
> rpush ireader java python
(integer) 3
> lpop ireader
"go"
> lpop ireader
"java"
> lpop ireader
"python"
# 左進右出
> lpush ireader go java python
(integer) 3
> rpop ireader
"go"
...
# 右進右出
> rpush ireader go java python
(integer) 3
> rpop ireader 
"python"
...
# 左進左出
> lpush ireader go java python
(integer) 3
> lpop ireader
"python"
...

在日常應用中,串列常用來作為異步佇列來使用。

長度 使用llen指令獲取鏈表長度

> rpush ireader go java python
(integer) 3
> llen ireader
(integer) 3

隨機讀 可以使用lindex指令訪問指定位置的元素,使用lrange指令來獲取鏈表子元素串列,提供start和end下標引數

> rpush ireader go java python
(integer) 3
> lindex ireader 1
"java"
> lrange ireader 0 2
1) "go"
2) "java"
3) "python"
> lrange ireader 0 -1  # -1表示倒數第一
1) "go"
2) "java"
3) "python"

使用lrange獲取全部元素時,需要提供end_index,如果沒有負下標,就需要首先通過llen指令獲取長度,才可以得出end_index的值,有了負下標,使用-1代替end_index就可以達到相同的效果。

修改元素 使用lset指令在指定位置修改元素。

> rpush ireader go java python
(integer) 3
> lset ireader 1 javascript
OK
> lrange ireader 0 -1
1) "go"
2) "javascript"
3) "python"

插入元素 使用linsert指令在串列的中間位置插入元素,有經驗的程式員都知道在插入元素時,我們經常搞不清楚是在指定位置的前面插入還是後面插入,所以antirez在linsert指令里增加了方向引數before/after來顯示指示前置和後置插入。不過讓人意想不到的是linsert指令並不是通過指定位置來插入,而是通過指定具體的值。這是因為在分佈式環境下,串列的元素總是頻繁變動的,意味著上一時刻計算的元素下標在下一時刻可能就不是你所期望的下標了。

> rpush ireader go java python
(integer) 3
> linsert ireader before java ruby
(integer) 4
> lrange ireader 0 -1
1) "go"
2) "ruby"
3) "java"
4) "python"

到目前位置,我還沒有在實際應用中發現插入指定的應用場景。

刪除元素 串列的刪除操作也不是通過指定下標來確定元素的,你需要指定刪除的最大個數以及元素的值

> rpush ireader go java python
(integer) 3
> lrem ireader 1 java
(integer) 1
> lrange ireader 0 -1
1) "go"
2) "java"

定長串列 在實際應用場景中,我們有時候會遇到「定長串列」的需求。比如要以走馬燈的形式實時顯示中獎用戶名串列,因為中獎用戶實在太多,能顯示的數量一般不超過100條,那麼這裡就會使用到定長串列。維持定長串列的指令是ltrim,需要提供兩個引數start和end,表示需要保留串列的下標範圍,範圍之外的所有元素都將被移除。

> rpush ireader go java python javascript ruby erlang rust cpp
(integer) 8
> ltrim ireader -3 -1
OK
> lrange ireader 0 -1
1) "erlang"
2) "rust"
3) "cpp"

如果指定引數的end對應的真實下標小於start,其效果等價於del指令,因為這樣的引數表示需要需要保留串列元素的下標範圍為空。

快速串列


如果再深入一點,你會發現Redis底層儲存的還不是一個簡單的linkedlist,而是稱之為快速鏈表quicklist的一個結構。首先在串列元素較少的情況下會使用一塊連續的記憶體儲存,這個結構是ziplist,也即是壓縮串列。它將所有的元素緊挨著一起儲存,分配的是一塊連續的記憶體。當資料量比較多的時候才會改成quicklist。因為普通的鏈表需要的附加指標空間太大,會比較浪費空間。比如這個串列里存的只是int型別的資料,結構上還需要兩個額外的指標prev和next。所以Redis將鏈表和ziplist結合起來組成了quicklist。也就是將多個ziplist使用雙向指標串起來使用。這樣既滿足了快速的插入刪除性能,又不會出現太大的空間冗餘。

hash

哈希等價於Java語言的HashMap或者是Python語言的dict,在實現結構上它使用二維結構,第一維是陣列,第二維是鏈表,hash的內容key和value存放在鏈表中,陣列里存放的是鏈表的頭指標。通過key查找元素時,先計算key的hashcode,然後用hashcode對陣列的長度進行取模定位到鏈表的表頭,再對鏈表進行遍歷獲取到相應的value值,鏈表的作用就是用來將產生了「hash碰撞」的元素串起來。Java語言開發者會感到非常熟悉,因為這樣的結構和HashMap是沒有區別的。哈希的第一維陣列的長度也是2^n。

增加元素 可以使用hset一次增加一個鍵值對,也可以使用hmset一次增加多個鍵值對

> hset ireader go fast
(integer) 1
> hmset ireader java fast python slow
OK

獲取元素 可以通過hget定位具體key對應的value,可以通過hmget獲取多個key對應的value,可以使用hgetall獲取所有的鍵值對,可以使用hkeys和hvals分別獲取所有的key串列和value串列。這些操作和Java語言的Map接口是類似的。

> hmset ireader go fast java fast python slow
OK
> hget ireader go
"fast"
> hmget ireader go python
1"fast"
2"slow"
> hgetall ireader
1"go"
2"fast"
3"java"
4"fast"
5"python"
6"slow"
> hkeys ireader
1"go"
2"java"
3"python"
> hvals ireader
1"fast"
2"fast"
3"slow"

刪除元素 可以使用hdel刪除指定key,hdel支持同時刪除多個key

> hmset ireader go fast java fast python slow
OK
> hdel ireader go
(integer) 1
> hdel ireader java python
(integer) 2

判斷元素是否存在 通常我們使用hget獲得key對應的value是否為空就直到對應的元素是否存在了,不過如果value的字串長度特別大,通過這種方式來判斷元素存在與否就略顯浪費,這時可以使用hexists指令。

> hmset ireader go fast java fast python slow
OK
> hexists ireader go
(integer) 1

計數器 hash結構還可以當成計數器來使用,對於內部的每一個key都可以作為獨立的計數器。如果value值不是整數,呼叫hincrby指令會出錯。

> hincrby ireader go 1
(integer1
> hincrby ireader python 4
(integer4
> hincrby ireader java 4
(integer4
> hgetall ireader
1"go"
2"1"
3"python"
4"4"
5"java"
6"4"
> hset ireader rust good
(integer1
127.0.0.1:6379> hincrby ireader rust 1
(error) ERR hash value is not an integer

擴容 當hash內部的元素比較擁擠時(hash碰撞比較頻繁),就需要進行擴容。擴容需要申請新的兩倍大小的陣列,然後將所有的鍵值對重新分配到新的陣列下標對應的鏈表中(rehash)。如果hash結構很大,比如有上百萬個鍵值對,那麼一次完整rehash的過程就會耗時很長。這對於單執行緒的Redis里來說有點壓力山大。所以Redis採用了漸進式rehash的方案。它會同時保留兩個新舊hash結構,在後續的定時任務以及hash結構的讀寫指令中將舊結構的元素逐漸遷移到新的結構中。這樣就可以避免因擴容導致的執行緒卡頓現象。

縮容 Redis的hash結構不但有擴容還有縮容,從這一點出發,它要比Java的HashMap要厲害一些,Java的HashMap只有擴容。縮容的原理和擴容是一致的,只不過新的陣列大小要比舊陣列小一倍。

set

Java程式員都知道HashSet的內部實現使用的是HashMap,只不過所有的value都指向同一個物件。Redis的set結構也是一樣,它的內部也使用hash結構,所有的value都指向同一個內部值。

增加元素 可以一次增加多個元素

> sadd ireader go java python
(integer) 3

讀取元素 使用smembers列出所有元素,使用scard獲取集合長度,使用srandmember獲取隨機count個元素,如果不提供count引數,預設為1

> sadd ireader go java python
(integer) 3
> smembers ireader
1) "java"
2) "python"
3) "go"
> scard ireader
(integer) 3
> srandmember ireader
"java"

刪除元素 使用srem刪除一到多個元素,使用spop刪除隨機一個元素

> sadd ireader go java python rust erlang
(integer) 5
> srem ireader go java
(integer) 2
> spop ireader
"erlang"

判斷元素是否存在 使用sismember指令,只能接收單個元素

> sadd ireader go java python rust erlang
(integer) 5
> sismember ireader rust
(integer) 1
> sismember ireader javascript
(integer) 0

sortedset

SortedSet(zset)是Redis提供的一個非常特別的資料結構,一方面它等價於Java的資料結構Map,可以給每一個元素value賦予一個權重score,另一方面它又類似於TreeSet,內部的元素會按照權重score進行排序,可以得到每個元素的名次,還可以通過score的範圍來獲取元素的串列。

zset底層實現使用了兩個資料結構,第一個是hash,第二個是跳躍串列,hash的作用就是關聯元素value和權重score,保障元素value的唯一性,可以通過元素value找到相應的score值。跳躍串列的目的在於給元素value排序,根據score的範圍獲取元素串列。

增加元素 通過zadd指令可以增加一到多個value/score對,score放在前面

zadd ireader 4.0 python
(integer) 1
zadd ireader 4.0 java 1.0 go
(integer) 2

長度 通過指令zcard可以得到zset的元素個數

> zcard ireader
(integer) 3

刪除元素 通過指令zrem可以刪除zset中的元素,可以一次刪除多個

> zrem ireader go python
(integer) 2

計數器 同hash結構一樣,zset也可以作為計數器使用。

zadd ireader 4.0 python 4.0 java 1.0 go
(integer) 3
zincrby ireader 1.0 python
"5"

獲取排名和分數 通過zscore指令獲取指定元素的權重,通過zrank指令獲取指定元素的正向排名,通過zrevrank指令獲取指定元素的反向排名[倒數第一名]。正向是由小到大,負向是由大到小。

> zscore ireader python
"5"
> zrank ireader go  # 分數低的排名考前,rank值小
(integer) 0
> zrank ireader java
(integer) 1
> zrank ireader python
(integer) 2
> zrevrank ireader python
(integer) 0

根據排名範圍獲取元素串列 通過zrange指令指定排名範圍引數獲取對應的元素串列,攜帶withscores引數可以一併獲取元素的權重。通過zrevrange指令按負向排名獲取元素串列[倒數]。正向是由小到大,負向是由大到小。

> zrange ireader 0 -1  # 獲取所有元素
1"go"
2"java"
3"python"
127.0.0.1:6379> zrange ireader 0 -1 withscores
1"go"
2"1"
3"java"
4"4"
5"python"
6"5"
> zrevrange ireader 0 -1 withscores
1"python"
2"5"
3"java"
4"4"
5"go"
6"1"

根據score範圍獲取串列 通過zrangebyscore指令指定score範圍獲取對應的元素串列。通過zrevrangebyscore指令獲取倒排元素串列。正向是由小到大,負向是由大到小。引數-inf表示負無窮,+inf表示正無窮。

> zrangebyscore ireader 0 5
1) "go"
2) "java"
3) "python"
> zrangebyscore ireader -inf +inf withscores
1) "go"
2) "1"
3) "java"
4) "4"
5) "python"
6) "5"
> zrevrangebyscore ireader +inf -inf withscores  # 註意正負反過來了
1) "python"
2) "5"
3) "java"
4) "4"
5) "go"
6) "1"

根據範圍移除元素串列 可以通過排名範圍,也可以通過score範圍來一次性移除多個元素

> zremrangebyrank ireader 0 1
(integer) 2  # 刪掉了2個元素
> zadd ireader 4.0 java 1.0 go
(integer) 2
> zremrangebyscore ireader -inf 4
(integer) 2
> zrange ireader 0 -1
1) "python"

跳躍串列 zset內部的排序功能是通過「跳躍串列」資料結構來實現的,它的結構非常特殊,也比較複雜。這一塊的內容深度讀者要有心理準備。

因為zset要支持隨機的插入和刪除,所以它不好使用陣列來表示。我們先看一個普通的鏈表結構。

我們需要這個鏈表按照score值進行排序。這意味著當有新元素需要插入時,需要定位到特定位置的插入點,這樣才可以繼續保證鏈表是有序的。通常我們會通過二分查找來找到插入點,但是二分查找的物件必須是陣列,只有陣列才可以支持快速位置定位,鏈表做不到,那該怎麼辦?

想想一個創業公司,剛開始只有幾個人,團隊成員之間人人平等,都是聯合創始人。隨著公司的成長,人數漸漸變多,團隊溝通成本隨之增加。這時候就會引入組長制,對團隊進行劃分。每個團隊會有一個組長。開會的時候分團隊進行,多個組長之間還會有自己的會議安排。公司規模進一步擴展,需要再增加一個層級——部門,每個部門會從組長串列中推選出一個代表來作為部長。部長們之間還會有自己的高層會議安排。

跳躍串列就是類似於這種層級制,最下麵一層所有的元素都會串起來。然後每隔幾個元素挑選出一個代表來,再將這幾個代表使用另外一級指標串起來。然後在這些代表裡再挑出二級代表,再串起來。最終就形成了金字塔結構。

想想你老家在世界地圖中的位置:亞洲–>中國->安徽省->安慶市->樅陽縣->湯溝鎮->田間村->xxxx號,也是這樣一個類似的結構。

「跳躍串列」之所以「跳躍」,是因為內部的元素可能「身兼數職」,比如上圖中間的這個元素,同時處於L0、L1和L2層,可以快速在不同層次之間進行「跳躍」。

定位插入點時,先在頂層進行定位,然後下潛到下一級定位,一直下潛到最底層找到合適的位置,將新元素插進去。你也許會問那新插入的元素如何才有機會「身兼數職」呢?

跳躍串列採取一個隨機策略來決定新元素可以兼職到第幾層,首先L0層肯定是100%了,L1層只有50%的概率,L2層只有25%的概率,L3層只有12.5%的概率,一直隨機到最頂層L31層。絕大多數元素都過不了幾層,只有極少數元素可以深入到頂層。串列中的元素越多,能夠深入的層次就越深,能進入到頂層的概率就會越大。

這還挺公平的,能不能進入中央不是靠拼爹,而是看運氣。




如果你對 Dubbo 感興趣,歡迎加入我的知識星球一起交流。

知識星球

目前在知識星球(https://t.zsxq.com/2VbiaEu)更新瞭如下 Dubbo 原始碼解析如下:

01. 除錯環境搭建
02. 專案結構一覽
03. 配置 Configuration
04. 核心流程一覽

05. 拓展機制 SPI

06. 執行緒池

07. 服務暴露 Export

08. 服務取用 Refer

09. 註冊中心 Registry

10. 動態編譯 Compile

11. 動態代理 Proxy

12. 服務呼叫 Invoke

13. 呼叫特性 

14. 過濾器 Filter

15. NIO 服務器

16. P2P 服務器

17. HTTP 服務器

18. 序列化 Serialization

19. 集群容錯 Cluster

20. 優雅停機

21. 日誌適配

22. 狀態檢查

23. 監控中心 Monitor

24. 管理中心 Admin

25. 運維命令 QOS

26. 鏈路追蹤 Tracing


一共 60 篇++

原始碼不易↓↓↓

點贊支持老艿艿↓↓

赞(0)

分享創造快樂