命令學習可以使用 在線redis環境。

數據類型

Redis 比較常見的數據結構有 string、list、hash、set、sorted set 等，但是 Redis 還有比較高級的3種數據結構：HyperLogLog、Geo、BloomFilter。

String（字符串）

String 是 Redis 最簡單最常用的數據結構，也是 Memcached 唯一的數據結構。在平時的開發中，String 可以說是使用最頻繁的了。

底層實現：

• 如果一個字符串對象保存的是整數值， 并且這個整數值可以用 long 類型來表示， 那么字符串對象會將整數值保存在字符串對象結構的 ptr 屬性里面（將 void* 轉換成 long ）， 并將字符串對象的編碼設置為 int 。
• 如果字符串對象保存的是一個字符串值， 并且這個字符串值的長度大于 39 字節， 那么字符串對象將使用一個簡單動態字符串（SDS）來保存這個字符串值， 并將對象的編碼設置為 raw。
• 如果字符串對象保存的是一個字符串值， 并且這個字符串值的長度小于等于 39 字節， 那么字符串對象將使用 embstr 編碼的方式來保存這個字符串值。

應用場景：

• 緩存：string 最常用的就是緩存功能，會將一些更新不頻繁但是查詢頻繁的數據緩存起來，以此來減輕 DB 的壓力。
• 計數器：可以用來計數，通過 incr 操作，如統計網站的訪問量、文章訪問量等。

List（列表）

基本概念:

list 是有序可重復列表，和 Java 的 LinkedList 比較像，可以通過索引查詢；插入刪除速度快。

底層實現：

Redis 3.2之前：

• 列表對象的編碼可以是壓縮列表 ziplist 或者 雙向循環鏈表 linkedlist 。
• 列表對象保存的所有字符串元素的長度都小于 64 字節并且保存的元素數量小于 512 個，使用 ziplist 編碼；否則使用 linkedlist；

Redis 3.2之后：
使用quicklist，它是一個雙向鏈表，而且是一個基于ziplist的雙向鏈表，quicklist的每個節點都是一個ziplist，結合了雙向鏈表和ziplist的優點。

使用場景:

• 消息隊列：Redis 的 list 是有序的列表結構，可以實現阻塞隊列，使用左進右出的方式。Lpush 用來生產 從左側插入數據，Brpop 用來消費，用來從右側 阻塞的消費數據。
• 數據的分頁展示： lrange 命令需要兩個索引來獲取數據，這個就可以用來實現分頁，可以在代碼中計算兩個索引值，然后來 redis 中取數據。
• 可以用來實現粉絲列表以及最新消息排行等功能。

Hash（散列）

基本概念：

Redis 散列可以存儲多個鍵值對之間的映射。和字符串一樣，散列存儲的值既可以是字符串又可以是數值，并且用戶同樣可以對散列存儲的數字值執行自增或自減操作。這個和 Java 的 HashMap 很像，每個 HashMap 有自己的名字，同時可以存儲多個 k/v 對。

底層實現:

• 哈希對象的編碼可以是 ziplist 或者 hashtable 。
• 哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于 64 字節并且保存的鍵值對數量小于 512 個，使用ziplist 編碼；否則使用 hashtable；

應用場景：

• Hash 更適合存儲結構化的數據，比如 Java 中的對象；其實 Java 中的對象也可以用 string 進行存儲，只需要將 對象 序列化成 json 串就可以，但是如果這個對象的某個屬性更新比較頻繁的話，那么每次就需要重新將整個對象序列化存儲，這樣消耗開銷比較大。可如果用 hash 來存儲 對象的每個屬性，那么每次只需要更新要更新的屬性就可以。
• 購物車場景：可以以用戶的 id 為 key ，商品的 id 為存儲的 field ，商品數量為鍵值對的value，這樣就構成了購物車的三個要素。

Set（集合）

基本概念：

Redis 的 set 和 list 都可以存儲多個字符串，他們之間的不同之處在于，list是有序可重復，而set是無序不可重復。

底層實現：

• 集合對象的編碼可以是 intset 或者 hashtable 。
• 如果集合對象保存的所有元素都是整數值并且保存的元素數量不超過 512 個，則使用 intset 編碼；否則使用 hashtable；

應用場景：

• 標簽：可以將博客網站每個人的標簽用 set 集合存儲，然后還按每個標簽 將用戶進行歸并。
• 存儲好友/粉絲：set 具有去重功能；還可以利用set并集功能得到共同好友之類的功能。

命令：

> sadd family mother # 嘗試將 mother 添加進 family 集合中 (integer)1 # 返回 1 表示添加成功，0 表示元素已經存在集合中 > sadd family father (integer)1 > sadd family father (intger)0 > smembers family # 獲取集合中所有的元素 1)"mother" 2)"father" > sismember family father # 判斷 father 是否在 family 集合中 (integer)1 # 1 存在；0 不存在 > sismber family son (integer)0 > srem family son # 移除 family 集合中元素 son (integer)1 # 1 表示存在并且移除成功;0 表示存在該元素 > srem family som (integer)0 > sadd family1 mother (integer)1 > smembers family 1)"mother" 2)"father" > smember family1 1)"mother" > sinter family family1 # 獲取 family 和 family1 的交集 1)"mother" > sadd family1 son (integer)1 > sunion family family1 # 獲取 family 和 family1 的并集 1)"mother" 2)"father" > sdiff family family1 # 獲取 family 和 family1 的差集（就是family有但是family1沒有的元素） 1)"father"

zset（有序集合）

基本概念：

有序集合和散列一樣，都用于存儲鍵值對：其中有序集合的每個鍵稱為成員（member），都是獨一無二的，而有序集合的每個值稱為分值（score），都必須是浮點數。可以根據分數進行排序，有序集合是Redis里面唯一既可以根據成員訪問元素（這一點和散列一樣），又可以根據分值以及分值的排列順序來訪問元素的結構。和Redis的其他結構一樣，用戶可以對有序集合執行添加、移除和獲取等操作。

底層實現：

• 有序集合的編碼可以是 ziplist 或者 skiplist
• 如果有序集合保存的元素數量小于 128 個并且保存的所有元素成員的長度都小于 64 字節，用 ziplist 編碼；否則使用skiplist；
• 當ziplist作為zset的底層存儲結構時候，每個集合元素使用兩個緊挨在一起的 ziplist 節點來保存，第一個節點保存元素的成員，第二個元素保存元素的分值。
• 當skiplist作為zset的底層存儲結構的時候，使用skiplist按序保存元素及分值，使用dict來保存元素和分值的映射關系。

應用場景：

• 排行榜：有序集合最常用的場景。如新聞網站對熱點新聞排序，比如根據點擊量、點贊量等。
• 帶權重的消息隊列：重要的消息 score 大一些，普通消息 score 小一些，可以實現優先級高的任務先執行。

命令：

> zadd class 100 member1 # 將member1元素及其score值100加入到 有序集合 class中 (integer)1 > zadd class 90 member2 80 member3 # 批量添加 (integer)2 > zrange class 0 -1 withscores # 獲取有序集合中的值與score，并按 score 排序 1)"member3" 2)"80" 3)"member2" 4)"90" 5)"member1" 6)"100" > zrem class member1 # 刪除 class 中 的member1 (integer)1

HyperLogLog

基本概念：

Redis 在 2.8.9 版本添加了 HyperLogLog 結構。

Redis HyperLogLog 是用來做基數統計的算法，所謂基數，也就是不重復的元素。

優點

在輸入元素的數量或者體積非常大時，計算基數所需的空間總是固定的、并且是很小的。在 Redis 里面，每個 HyperLogLog 鍵只需要花費 12 KB 內存，就可以計算接近 2^64 個不同元素的基數。

缺點

因為 HyperLogLog 只會根據輸入元素來計算基數，而不會儲存輸入元素本身，所以 HyperLogLog 不能像集合那樣，返回輸入的各個元素。

估算的值，可能存在誤差

應用場景：

網頁統計UV （瀏覽用戶數量，同一天同一個ip多次訪問算一次訪問，目的是計數，而不是保存用戶）
傳統的方式是使用set保存用戶的id，可以統計set中元素數量作為標準判斷。
但如果這種方式保存大量用戶id，會占用大量內存，我們的目的是為了計數，而不是去保存id。

命令：

> pfadd user_login_20210523 tom # user_login_20210523是key；tom 是登錄的用戶 (integer)1 > pfadd user_login_20210523 tom jack lilei 的用戶 (integer)1 > pfcount user_login_20210523 # 獲取 key 對應值的數量，同一個用戶多次登錄只統計一次 (integer) 3 > pfadd user_login_20210522 sira (integer)1 > pfcount user_login_20210523 user_login_20210522 # 統計22號和23號一共有多少登陸的用戶 (integer)4 > pfmerge user_login_20210522_23 user_login_20210522 user_login_20210523 # 將2個鍵內容合并 "OK" > pfcount user_login_20210522_23 (integer)4

GEO

基本概念：

在 Redis 3.2 版本中新增了一種叫 geo 的數據結構，它主要用來存儲地理位置信息，并對存儲的信息進行操作。

應用場景：

用于存儲地理信息以及對地理信息作操作的場景。

例如：

• 查看附近的人
• 微信位置共享
• 地圖上直線距離的展示

BloomFilter（布隆過濾器）

基本概念：

一種數據結構，是由一串很長的二進制向量組成，可以將其看成一個二進制數組。既然是二進制，那么里面存放的不是0，就是1，但是初始默認值都是0。

主要作用是：判斷一個元素是否在某個集合中。比如說，我想判斷20億的號碼中是否存在某個號碼，如果直接插DB，那么數據量太大時間會很慢；如果將20億數據放到緩存中，緩存也裝不下。這個時候用布隆過濾器最合適.

布隆過濾器是用于判斷一個元素是否在集合中。通過一個位數組和N個hash函數實現。

優點：

• 空間效率高，所占空間小。
• 查詢時間短。

缺點：

• 元素添加到集合中后，不能被刪除。
• 有一定的誤判率

底層實現：

Redis提供的Bitmaps這個“數據結構”可以實現對位的操作。Bitmaps本身不是一種數據結構，實際上就是字符串，但是它可以對字符串的位進行操作。

可以把Bitmaps想象成一個以位為單位數組，數組中的每個單元只能存0或者1，數組的下標在bitmaps中叫做偏移量。單個bitmaps的最大長度是512MB，即2^32個比特位。

應用場景

• 數據庫防止穿庫。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter來減少不存在的行或列的磁盤查找。避免代價高昂的磁盤查找會大大提高數據庫查詢操作的性能。
• 業務場景中判斷用戶是否閱讀過某視頻或文章，比如抖音或頭條，當然會導致一定的誤判，但不會讓用戶看到重復的內容。
• 緩存宕機、緩存擊穿場景，一般判斷用戶是否在緩存中，如果在則直接返回結果，不在則查詢db，如果來一波冷數據，會導致緩存大量擊穿，造成雪崩效應，這時候可以用布隆過濾器當緩存的索引，只有在布隆過濾器中，才去查詢緩存，如果沒查詢到，則穿透到db。如果不在布隆器中，則直接返回。
• WEB攔截器，如果相同請求則攔截，防止重復被攻擊。用戶第一次請求，將請求參數放入布隆過濾器中，當第二次請求時，先判斷請求參數是否被布隆過濾器命中。可以提高緩存命中率。

---

數據結構

redis內部整體的存儲結構是一個大字典，內部是數組實現的hash，key沖突通過掛鏈表去實現，每個dictEntry為一個key/value對象，value為定義的redisObject，即對象。

對象 redisObject

/** Redis 對象*/ typedef struct redisObject {// 類型 4bitsunsigned type:4;// 編碼方式 4bitsunsigned encoding:4;// LRU 時間（相對于 server.lruclock） 24bitsunsigned lru:22;// 引用計數 Redis里面的數據可以通過引用計數進行共享 32bitsint refcount;// 指向對象的值 64-bitvoid *ptr; } robj;

*ptr指向具體的數據結構的地址；type表示該對象的類型，即 String,List,Hash,Set,Zset 中的一個，但為了提高存儲效率與程序執行效率，每種對象的底層數據結構實現都可能不止一種，encoding 表示對象底層所使用的編碼。

redis對象底層的八種數據結構：

REDIS_ENCODING_INT（long 類型的整數）REDIS_ENCODING_EMBSTR embstr （編碼的簡單動態字符串）REDIS_ENCODING_RAW （簡單動態字符串）REDIS_ENCODING_HT （字典）REDIS_ENCODING_LINKEDLIST （雙端鏈表）REDIS_ENCODING_ZIPLIST （壓縮列表）REDIS_ENCODING_INTSET （整數集合）REDIS_ENCODING_SKIPLIST （跳躍表和字典）

對象類型與底層數據結構之間的關系：

簡單動態字符串 SDS

SDS(simple dynamic string)

與C字符串對比

相比于C字符串的好處

減少內存重分配

為減少內存重分配次數，Redis SDS 實現了空間預分配和惰性空間釋放兩種策略。

空間預分配：

如果sds修改后，sds長度（len的值）小于1mb，那么會分配與len相同大小的未使用空間，此時len與free值相同。例如，修改之后字符串長度為100字節，那么會給分配100字節的未使用空間。最終sds空間實際為 100 + 100 + 1(保存空字符’\0’)；

如果大于等于1mb，每次給分配1mb未使用空間

惰性空間釋放：
對字符串進行縮短操作時，程序不立即使用內存重新分配來回收縮短后多余的字節，而是使用 free 屬性將這些字節的數量記錄下來，等待后續使用（sds也提供api，我們可以手動觸發字符串縮短）；

鏈表

Redis 中的鏈表是雙向循環鏈表

typedef struct listNode {// 前驅節點struct listNode *prev;// 后繼節點struct listNode *next;// 值void *value;} listNode; typedef struct list {// 表頭指針listNode *head;// 表尾指針listNode *tail;// 節點數量unsigned long len;// 復制函數void *(*dup)(void *ptr);// 釋放函數void (*free)(void *ptr);// 比對函數int (*match)(void *ptr, void *key); } list;

Redis 的鏈表實現的特性可以總結如下：

• 雙端： 鏈表節點帶有 prev 和 next 指針， 獲取某個節點的前置節點和后置節點的復雜度都是 O(1) 。
• 無環： 表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL ， 對鏈表的訪問以 NULL 為終點。
• 帶表頭指針和表尾指針： 通過 list 結構的 head 指針和 tail 指針， 程序獲取鏈表的表頭節點和表尾節點的復雜度為 O(1) 。
• 帶鏈表長度計數器： 程序使用 list 結構的 len 屬性來對 list 持有的鏈表節點進行計數， 程序獲取鏈表中節點數量的復雜度為 O(1) 。
• 多態： 鏈表節點使用 void* 指針來保存節點值， 并且可以通過 list 結構的 dup 、 free 、 match 三個屬性為節點值設置類型特定函數， 所以鏈表可以用于保存各種不同類型的值。

總結：

• 鏈表被廣泛用于實現 Redis 的各種功能， 比如列表鍵， 發布與訂閱， 慢查詢， 監視器， 等等。
• 每個鏈表節點由一個 listNode 結構來表示， 每個節點都有一個指向前置節點和后置節點的指針， 所以 Redis 的鏈表實現是雙端鏈表。
• 每個鏈表使用一個 list 結構來表示， 這個結構帶有表頭節點指針、表尾節點指針、以及鏈表長度等信息。
• 因為鏈表表頭節點的前置節點和表尾節點的后置節點都指向 NULL ， 所以 Redis 的鏈表實現是無環鏈表。
• 通過為鏈表設置不同的類型特定函數， Redis 的鏈表可以用于保存各種不同類型的值。

字典 dict

Redis 的字典以及本身的數據庫都是使用字典（dict）作為底層實現。

字典底層是使用哈希表（hashtable）作為底層實現。

dict 內部的數據結構：

typedef struct dict {dictType *type;// 私有數據void *privdata;// 2個哈希表dictht ht[2];// rehashing not in progress if rehashidx == -1 long rehashidx; // number of iterators currently runningint iterators; } dict;typedef struct dictht {// 指針數組，這個hash的桶dictEntry **table;// 元素個數unsigned long size;// 掩碼，用于計算索引值。等于 size-1unsigned long sizemask;// 已有節點的數量unsigned long used; } dictht;dictEntry是用來真正存儲key->value的地方 typedef struct dictEntry {// 鍵void *key;// 值union {// 指向具體redisObjectvoid *val;uint64_t u64;int64_t s64;} v;// 指向下個哈希表節點，形成鏈表struct dictEntry *next; } dictEntry;

每個dict中都用兩個hashtable。一般情況下只使用ht[0]，ht[1]只會在對ht[0] rehash時使用。

在dict擴容縮容的時候，需要分配新的hashtable，然后進行漸近式搬遷，這時候兩個hashtable分別存儲舊的hashtable和新的hashtable。搬遷結束后，舊hashtable刪除，新的取而代之。

哈希算法

采用 Murmurhash 算法計算鍵的哈希值，優點在于即使鍵是有規律的，輸出的值仍然有隨機分布性；此外計算速度也很快。

計算出 hash 值后，通過與 sizemask 進行&操作獲取在數組中的索引。

解決鍵沖突

采用鏈地址法解決鍵沖突，類似 JDK 1.7。

漸進式rehash

擴容和縮容都會通過rehash來實現。所謂漸進式rehash是指我們的大字典的擴容是比較消耗時間的，需要重新申請新的數組，然后將舊字典所有鏈表的元素重新掛接到新的數組下面，是一個O(n)的操作。但是因為我們的redis是單線程的，無法承受這樣的耗時過程，所以采用了漸進式rehash小步搬遷，雖然慢一點，但是可以搬遷完畢。

步驟

為ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個hash表

在字典中維持一個索引計數器變量rehashidx，并將它的值設置為0，表示rehash工作正式開始

在rehash進行期間，每次對字典執行添加，刪除，查找或者更新操作時，程序除了執行特定的操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1],當rehash工作完成之后，程序將rehashidx屬性的值增1

隨著字典操作的不斷執行，最終在某個時間點上，ht[0]的所有鍵值對都會被rehash至ht[1]，這時程序將rehashidx屬性的值設為-1，表示rehash操作已完成

將ht[0]釋放，然后將ht[1]設置成ht[0]，最后為ht[1]分配一個空白哈希表

rehash觸發條件

擴容

我們的擴容一般會在Hash表中的元素個數等于第一維數組的長度的時候，就會開始擴容。擴容的大小是原數組的兩倍。不過在redis在做bgsave（RDB持久化操作的過程）時，為了減少內存頁的過多分離（Copy On Write），redis不會去擴容。

但是如果hash表的元素個數已經到達了第一維數組長度的5倍的時候，就會強制擴容，不管你是否在持久化。

縮容

當我們的hash表元素逐漸刪除的越來越少的時候。redis就會對hash表進行縮容來減少第一維數組長度的空間占用。縮容的條件是元素個數低于數組長度的10%，并且縮容不考慮是否在做redis持久化。

不用考慮bgsave主要是因為我們的縮容的內存都是已經使用過的，縮容的時候可以直接置空，而且由于申請的內存比較小，同時會釋放掉一些已經使用的內存，不會增大系統的壓力。

跟JDK的HashMap的區別

• 數據結構上，采用了兩個數組保存數據，發生hash沖突時，只采用了鏈地址法解決hash沖突，并沒有跟jdk1.8一樣當鏈表超過8時優化成紅黑樹，因此插入元素時跟jdk1.7的hashmap一樣采用的是頭插法。
• 在發生擴容時，跟jdk的hashmap一次性、集中式進行擴容不一樣，采取的是漸進式的rehash，每次操作只會操作當前的元素，在當前數組中移除或者存放到新的數組中，直到老數組的元素徹底變成空表。
• 當負載因子小于0.1時，會自動進行縮容。jdk的hashmap出于性能考慮，不提供縮容的操作。
• redis使用MurmurHash來計算哈希表的鍵的hash值，而jdk的hashmap使用key.hashcode()的高十六位跟低十六位做與運算獲得鍵的hash值。

跳表 skiplist

跳表支持平均O(logN)，最壞O(N)復雜度的節點查找，還可以通過順序性操作批量處理節點。

大部分情況下，跳表效率可以跟平衡樹媲美。

Redis使用跳表作為zset的底層實現之一。當zset包含元素數量多，或者元素成員是比較長的字符串時，就會使用跳表。

/** 跳躍表*/ typedef struct zskiplist {// 頭節點，尾節點struct zskiplistNode *header, *tail;// 節點數量unsigned long length;// 目前表內節點的最大層數int level; } zskiplist;/** 跳躍表節點*/ typedef struct zskiplistNode {// member 對象robj *obj;// 分值double score;// 后退指針struct zskiplistNode *backward;// 層struct zskiplistLevel {// 前進指針struct zskiplistNode *forward;// 這個層跨越的節點數量unsigned int span;} level[]; } zskiplistNode;

zskiplist結構：

• header:指向跳躍表的表頭節點，通過這個指針程序定位表頭節點的時間復雜度就為O(1)；
• tail:指向跳躍表的表尾節點,通過這個指針程序定位表尾節點的時間復雜度就為O(1)；
• level:記錄目前跳躍表內,層數最大的那個節點的層數(表頭節點的層數不計算在內)，通過這個屬性可以再O(1)的時間復雜度內獲取層高最好的節點的層數；
• length:記錄跳躍表的長度,也即是,跳躍表目前包含節點的數量(表頭節點不計算在內)，通過這個屬性，程序可以再O(1)的時間復雜度內返回跳躍表的長度。

zskiplistNode結構：

• 層(level):
  節點中用L1、L2、L3等字樣標記節點的各個層,L1代表第一層,L2代表第二層,以此類推。
  每個層都帶有兩個屬性:前進指針和跨度。前進指針用于訪問位于表尾方向的其他節點,而跨度則記錄了前進指針所指向節點和當前節點的距離(跨度越大、距離越遠)。在上圖中,連線上帶有數字的箭頭就代表前進指針,而那個數字就是跨度。當程序從表頭向表尾進行遍歷時,訪問會沿著層的前進指針進行。
  每次創建一個新跳躍表節點的時候,程序都根據冪次定律(powerlaw,越大的數出現的概率越小)隨機生成一個介于1和32之間的值作為level數組的大小,這個大小就是層的“高度”。

• 后退(backward)指針：
  節點中用BW字樣標記節點的后退指針,它指向位于當前節點的前一個節點。后退指針在程序從表尾向表頭遍歷時使用。與前進指針所不同的是每個節點只有一個后退指針，因此每次只能后退一個節點。

• 分值(score):
  各個節點中的1.0、2.0和3.0是節點所保存的分值。在跳躍表中,節點按各自所保存的分值從小到大排列。

• 成員對象(oj):
  各個節點中的o1、o2和o3是節點所保存的成員對象。在同一個跳躍表中,各個節點保存的成員對象必須是唯一的,但是多個節點保存的分值卻可以是相同的:分值相同的節點將按照成員對象在字典序中的大小來進行排序,成員對象較小的節點會排在前面(靠近表頭的方向),而成員對象較大的節點則會排在后面(靠近表尾的方向)。

一些操作的時間復雜度

• 查詢：O(logN)
• 插入：O(logN)
• 刪除：O(logN)

為什么沒有用紅黑樹替代跳表

• 在Redis中會有大量的范圍查詢的功能需求，紅黑樹在范圍查找這方面的效率不如跳躍表，所以在范圍查詢方面使用跳躍表更優
• 紅黑樹的數據結構更為復雜，紅黑樹的插入和刪除操作可能會引發子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速
• 一般來說，紅黑樹每個節點包含2個指針，而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis里的實現一樣，取p=1/4，那么平均每個節點包含1.33個指針，比平衡樹更有優勢。

整數集合 intset

Redis 的集合相當于Java中的 HashSet，它內部的鍵值對是無序、唯一的。它的內部實現相當于一個特殊的字典，字典中所有的 value 都是一個值 NULL。集合Set類型底層編碼包括 hashtable 和 intset。

intset是一個有序集合，查找元素的復雜度為O(logN)（采用二分法）。但插入時不一定為O(logN)，因為有可能涉及到升級操作。比如當集合里全是int16_t型的整數，這時要插入一個int32_t，那么為了維持集合中數據類型的一致，那么所有的數據都會被轉換成int32_t類型，涉及到內存的重新分配，這時插入的復雜度就為O(N)了。intset不支持降級操作。

typedef struct intset {uint32_t encoding;// length就是數組的實際長度uint32_t length;// contents 數組是實際保存元素的地方，數組中的元素有以下兩個特性：// 1.沒有重復元素// 2.元素在數組中從小到大排列int8_t contents[]; } intset;// encoding 的值可以是以下三個常量的其中一個 #define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t))

壓縮列表 ziplist

ziplist 是 List 和 Hash 類型的底層實現之一。

ziplist 可以看做是一種壓縮的雙向鏈表，它的好處是更能節省內存空間，因為它所存儲的內容都是在連續的內存區域當中的。

當列表對象元素不大，每個元素也不大的時候，就采用ziplist存儲。但當數據量過大時就ziplist就不是那么好用了。因為為了保證他存儲內容在內存中的連續性，插入的復雜度是O(N)，即每次插入都會重新進行realloc。redisObject對象結構中ptr所指向的就是一個ziplist。整個ziplist只需要malloc一次，它們在內存中是一塊連續的區域。

1、zlbytes：用于記錄整個壓縮列表占用的內存字節數
　
2、zltail：記錄要列表尾節點距離壓縮列表的起始地址有多少字節
　
3、zllen：記錄了壓縮列表包含的節點數量。

4、entryX：壓縮列表包含的各個節點

5、zlend：用于標記壓縮列表的末端

為什么數據量大時不用ziplist？

因為ziplist是一段連續的內存，插入的時間復雜度為O(n)，而且每當插入新的元素需要 realloc 做內存擴展；而且如果超出ziplist內存大小，還會做重新分配的內存空間，并將內容復制到新的地址。如果數量大的話，重新分配內存和拷貝內存會消耗大量時間。所以不適合大型字符串，也不適合存儲量多的元素。

快速列表 quickList

快速列表是ziplist和linkedlist的混合體，是將linkedlist按段切分，每一段用ziplist來緊湊存儲，多個ziplist之間使用雙向指針鏈接。

數據結構：

typedef struct quicklistNode {struct quicklistNode *prev; //上一個node節點struct quicklistNode *next; //下一個nodeunsigned char *zl; //保存的數據 壓縮前ziplist 壓縮后壓縮的數據unsigned int sz; /* ziplist size in bytes */unsigned int count : 16; /* count of items in ziplist */unsigned int encoding : 2; /* RAW==1 or LZF==2 */unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */unsigned int recompress : 1; /* was this node previous compressed? */unsigned int attempted_compress : 1; /* node can't compress; too small */unsigned int extra : 10; /* more bits to steal for future usage */ } quicklistNode;

• prev: 指向鏈表前一個節點的指針。
• next: 指向鏈表后一個節點的指針。
• zl: 數據指針。如果當前節點的數據沒有壓縮，那么它指向一個ziplist結構；否則，它指向一個quicklistLZF結構。
• sz: 表示zl指向的ziplist的總大小（包括zlbytes, zltail, zllen, zlend和各個數據項）。需要注意的是：如果ziplist被壓縮了，那么這個sz的值仍然是壓縮前的ziplist大小。
• count: 表示ziplist里面包含的數據項個數。這個字段只有16bit。稍后我們會一起計算一下這16bit是否夠用。
• encoding: 表示ziplist是否壓縮了（以及用了哪個壓縮算法）。目前只有兩種取值：2表示被壓縮了（而且用的是LZF壓縮算法），1表示沒有壓縮。
• container: 是一個預留字段。本來設計是用來表明一個quicklist節點下面是直接存數據，還是使用ziplist存數據，或者用其它的結構來存數據（用作一個數據容器，所以叫container）。但是，在目前的實現中，這個值是一個固定的值2，表示使用ziplist作為數據容器。
• recompress: 當我們使用類似lindex這樣的命令查看了某一項本來壓縮的數據時，需要把數據暫時解壓，這時就設置recompress=1做一個標記，等有機會再把數據重新壓縮。
• attempted_compress: 這個值只對Redis的自動化測試程序有用。我們不用管它。
• extra: 其它擴展字段。目前Redis的實現里也沒用上。

typedef struct quicklistLZF {unsigned int sz; /* LZF size in bytes*/char compressed[]; } quicklistLZF;

quicklistLZF結構表示一個被壓縮過的ziplist。其中：

• sz: 表示壓縮后的ziplist大小。
• compressed: 是個柔性數組（flexible array member），存放壓縮后的ziplist字節數組。

typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count; /* total count of all entries in all ziplists */unsigned long len; /* number of quicklistNodes */int fill : QL_FILL_BITS; /* fill factor for individual nodes */unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[]; } quicklist;

• head: 指向頭節點（左側第一個節點）的指針。
• tail: 指向尾節點（右側第一個節點）的指針。
• count: 所有ziplist數據項的個數總和。
• len: quicklist節點的個數。
• fill: 16bit，ziplist大小設置，存放list-max-ziplist-size參數的值。
• compress: 16bit，節點壓縮深度設置，存放list-compress-depth參數的值。

為什么不直接使用linkedlist？

linkedlist的附加空間相對太高，prev和next指針就要占去16個字節，而且每一個結點都是單獨分配，會加劇內存的碎片化，影響內存管理效率。

參考

• https://mp.weixin.qq.com/s/7ct-mvSIaT3o4-tsMaKRWA
• http://redisbook.com/

總結

以上是生活随笔為你收集整理的Redis数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。