[TOC] # 通俗易懂的Redis數據結構基礎教程  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 (integer) 142 > get ireader "142" > decrby ireader 100 (integer) 42 > get ireader "42" > incr ireader # 等價于incrby ireader 1 (integer) 43 > decr ireader # 等價于decrby ireader 1 (integer) 42 復制代碼 ~~~ 計數器是有范圍的，它不能超過Long.Max，不能低于Long.MIN ~~~ > set ireader 9223372036854775807 OK > incr ireader (error) ERR increment or decrement would overflow > set ireader -9223372036854775808 OK > decr ireader (error) ERR increment or decrement would overflow 復制代碼 ~~~ **過期和刪除**字符串可以使用del指令進行主動刪除，可以使用expire指令設置過期時間，到點會自動刪除，這屬于被動刪除。可以使用ttl指令獲取字符串的壽命。 ~~~ > expire ireader 60 (integer) 1 # 1表示設置成功，0表示變量ireader不存在 > ttl ireader (integer) 50 # 還有50秒的壽命，返回-2表示變量不存在，-1表示沒有設置過期時間 > del ireader (integer) 1 # 刪除成功返回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) "python" 復制代碼 ~~~ **定長列表**在實際應用場景中，我們有時候會遇到「定長列表」的需求。比如要以走馬燈的形式實時顯示中獎用戶名列表，因為中獎用戶實在太多，能顯示的數量一般不超過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 (integer) 1 > hincrby ireader python 4 (integer) 4 > hincrby ireader java 4 (integer) 4 > hgetall ireader 1) "go" 2) "1" 3) "python" 4) "4" 5) "java" 6) "4" > hset ireader rust good (integer) 1 > 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<String, Double>`，可以給每一個元素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" > 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層。絕大多數元素都過不了幾層，只有極少數元素可以深入到頂層。列表中的元素越多，能夠深入的層次就越深，能進入到頂層的概率就會越大。 這還挺公平的，能不能進入中央不是靠拼爹，而是看運氣。 轉載至：https://juejin.im/post/5b53ee7e5188251aaa2d2e16