思維導圖：

 

我是redis

你好，我是 redis

一個叫Antirez的男人帶我來到這個充滿復雜的世界上。

 

聊到我的出生，那跟MySQL大哥脫不了關系呀，我是來幫助他的，所謂天降猛男redis就是我了，真想對他說：

“

我還沒有來到這個世界上的時候，剛開始挺好的，互聯網前期，咱們的用戶請求也不多，主要是一些靜態網站和小游戲，這 有啥難的 ，MYSQL大哥一個頂倆好吧。但天有不測風云，歷史不會停止步伐的。用戶請求的數據也隨之暴漲，每天用戶的 每一次請求 都變成了對它的一個又一個的 讀寫操作 ，MYSQL直呼“快殺了我吧”，每年的“618”或者過年買票的時候，都是MYSQL受苦受累的日子啊！

”

反思 問題 出現在哪里，MYSQL大哥開始頭頭分析起來，原來有一大半的用戶請求tm都是 讀操作 ，而且經常又是查一個東西，簡直浪費我 磁盤IO 的時間。后來我的爸爸突發奇想，你看看別人 CPU的緩存 是很快的呀，給數據庫加個緩存就解決了唄，于是我就出生了！出生沒幾天，我就來給MYSQL大哥解決問題，效果也還不錯，我們也成為了 好基友 ，常常手拉手在后端服務器中配合，大致如圖：

 

為了方便與內存對接，我支持好幾種數據結構的存儲：

“

String

Hash

List

Set

SortedSet

Bitmap

......

”

因為把MYSQL里 登記的數據 都放到我的內存里來，就不去執行慢如蝸牛的I/O操作，所以下次找我肯定比找MYSQL要 省去 不少的時間呢。

可別小瞧這一個微小的操作，可幫MYSQL大哥減輕了不小的負擔！我緩存的數據也逐漸增長，有

相當部分

的時間都給他擋住了用戶請求，這下他可就清閑自在了！

“

那今天就給大家聊一聊，咱的看家本領，內存是如何 管 上面的數據類型的。說著，我拿筆給大家 畫 一張圖：

”

 

看看，我的肚子里用了一個redisObject對象來展示所有的 value和key 。type就是value對象是 那種 數據類型，第二個encoding就是不同的數據類型在Redis內部是如何 放 的。

譬如： type=String 則表示value存儲的是一個普通字符串，那我推斷出 encoding 可以是raw或者是int。但是我稍加思索，哎，還要解釋下 底層數據結構 ，你知道嗎？底層的底層，你有了解過嗎？跟著我擺起來哈。

下面是各自對應的數據結構；

 

可以看出來，有很多類型都是使用 兩種結構 ，就像set在元素比較少的時候，且都是數字的情況下會用 整數列表 ，隨著數據增加就變成 哈希表 。但是我有一個比較大的疑問，這些類型都對應不同的數據結構，想想redis 整體的結構

是啥樣的呢？再舉個例子，現在有一個

key對應的value

是我們的list類型的，那就對應著上面的雙向鏈表啊？那咱第一步就要找到這個key,就可找到雙向鏈表了噻；

看看全局哈希表

其實啊，我這里是有一個大的哈希表的，在 你們的眼 里可能就是類似的長數組，在它上面的每個空間，都可以看做一個哈希桶，長這樣：

 

每一個key經過我肚子里面的hash算法就會給你算出一個位置，怎么來算請看下面：

哈希算法：Redis計算哈希值和索引值方法如下：

//1、使用字典設置的哈希函數，計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
//2、使用哈希表的sizemask屬性和第一步得到的哈希值，計算索引值
index = hash & dict->ht[x].sizemask;

那它就對應一個哈希桶唄。 壯士請注意 ，這個過程是很快的哈。只有O(1)哦，這個過程咱就算出 內存地址 ，那你就直接去找就行了。然后我們把這個key放到hash桶里面去。記住啊壯士，這個桶里面 保存的是引用 哈，不是你的 那個對象（狗頭） 。就好比哈希桶里面保存的是key家的門牌號一樣（實質內存地址），那我們就用了0(1)的復雜度就這樣找到這個key。，因為用key去查找value的時候，只需要在經過依次hash能馬上找到哈希桶，就能定位到這個 鍵值對 的內存地址了。

 

那問題來了

“

hash算法是不能保證 所有的key 經過算法出來的值都一樣，那就是會有哈希沖突的存在，就是 兩個key放到了同一個桶 中，這可怎么辦呢？

”

我們就用 鏈表 來解決這個問題，就是兩個在一個桶中的元素，我們就用一個next指針把它們 連在一起 ，經過hash算出來之后找到一個鍵值對， 對比看著 如果不是，根據next指針再找下一個比就行。我們都知道鏈表是一種常用的數據結構，而C語言內部是 沒有內置 這種數據結構的實現，所以我redis會自己構建了 鏈表 的實現。

其中每個

鏈表節點

使用一個listNode結構表示:(下圖的右部分）：

//鏈表節點
typedef struct listNode{
     struct listNode * prev;
     struct listNode * next;
     void * value;  
}

下圖是有兩部分，由list和listNode兩個數據結構構成。一部分是“ 統籌部分 ”是左邊，一部分是“ 具體實施 “：右邊；

 

主體”統籌部分“：

head指向具體 雙向鏈表的頭

tail指向具體 雙向鏈表的尾

len雙向鏈表的

長度

；

具體"實施方"：

可以看出每個鏈表節點都有指向 前置節點prev 和 后置節點next 的指針，組成一個雙向鏈表。每個鏈表結構，有表頭表尾指針和鏈表長度等信息。另外表頭節點和前置和表尾節點的 后置都是NULL ，所以是無環鏈表。

在總結下：

特點：

• 雙端 ：鏈表節點帶有prev和next指針，找到某個節點的前置節點和后置節點的 時間復雜度都是O(N)
• 無環 ：表頭節點的prev指針和表尾節點的next 都指向NULL，對立案表的訪問時以 NULL為截止
• 表頭與表尾 ：因為鏈表帶有head指針和tail指針，程序獲取鏈表頭結點和尾節點的時間復雜度為O(1)
• 長度計數器 ：鏈表中存有記錄鏈表 長度 的屬性**len
• 多態 ：鏈表節點使用void* 指針來保存節點值，并且可以通過list結構的dup 、free、match三個屬性是節點值設置類型特定函數。

這時我們可以通過直接操作list來操作鏈表會更加的方便：

typedef struct list {
    //表頭節點
    listNode  * head;
    //表尾節點
    listNode  * tail;
    //鏈表長度
    unsigned long len;
    //節點值復制函數
    void *(*dup) (void *ptr);
    //節點值釋放函數
    void (*free) (void *ptr);
    //節點值對比函數
    int (*match)(void *ptr, void *key);
}

“

那么當元素越來越多之后，一個哈希桶所 對應的鏈表 就會越來越長，我們知道鏈表上的遍歷時間復雜度是O(n)的，那么會嚴重 影響性能 ，Redis這種追求快的數據庫看來是絕對不能夠 容忍 的，那么要怎么處理，就是rehash操作。

”

rehash和漸進式rehash操作

redis會在 內部再新建 一個長度為原始長度2倍的空哈希表，然后原哈希表上的元素 重新rehash 到新的哈希表中去，然后我們再使用新的哈希表即可。

那么，這樣還是有個問題要解決呀！

要知道redis中存儲的數據可能是成百萬上千萬的，我們 重新rehash 一次未免太耗時了吧，因為redis中操作大部分是 單線程 的。

“

這個過程可能會阻斷其他操作很長時間，這是不能忍受的，那要怎么處理呢？

”

首先redis是采用了 漸進式rehash 的操作，就是會有一個變量，指向第一個哈希桶，然后redis每執行一個添加key，刪除key的類似命令，就順便 copy一個哈希桶中的數據 到新的哈希表中去，這樣細水長流的操作，是不會影響什么性能，就會所有的數據都被重新hash到新的哈希表中。

那么在這個過程中，當然再有寫的操作，會直接把數據放到新的哈希表中，保證舊的肯定有 copy完 的時候，如果這段時間對數據庫的操作比較少，也沒有關系，redis 內部也有定時 任務，每隔一段時間也會copy一次。

動態字符串SDS

SDS的全稱"simple dynamic string"。redis中所有場景中出現的字符串，基本都是由SDS來實現的。

所有 非數字的key 。例如 set msg "hello world" 中的key msg.

字符串數據類型的值 。例如 set msg "hello world"中的msg的值"hello wolrd"

最后是兩者結合：

非字符串數據類型中的“字符串值”

。例如 RPUSH fruits "Apple""banana""cherry"中的"apple" "banana" "cherry"都是;

上面的例子，我們可以很直觀地看到我們在平常使用redis的時候，創建的字符串到底是一個什么樣子的數據類型。除了用來保存字符串以外，SDS還被用作 緩沖區 （buffer）AOF模塊中的 AOF緩沖區 。

SDS 的定義

動態字符串的結構：

/*  
* 保存字符串對象的結構  
*/  
struct sdshdr {  
    
  // buf 中已占用空間的長度  
  int len;  

  // buf 中剩余可用空間的長度  
  int free;  

  // 數據空間  
  char buf[];  
};  

SDS長這樣：

 

SDS示例

• len 變量，用于記錄buf 中已經 使用的空間長度 （這里指出Redis的長度為5）；
• free 變量，用于記錄buf修改后的還有 空余的空間 ，一般初次分配空間的時候，是沒有空余的，在對字符串修改的時候，就會有剩余空間出現；
• buf 字符數組，用來記錄 我們的字符串 （記錄Redis）

SDS 與 C 字符串的區別

那么傳統的C字符串使用長度為 N+1的字符串數組 來表示 長度為N的字符串 ，所以為了獲取一個長度為C字符串的長度，必須遍歷整個字符串。

這樣做在獲取字符串長度的時候，字符串擴展等操作的時候 效率比較低 。C語言用這種 簡單 的字符串表示方式，但是并不能滿足Redis對字符串在安全性、效率以及功能方面的要求：

獲取字符串長度（SDS O（1）/C 字符串 O(n)）

“

和C 字符串不同，SDS的數據結構中，有專門用于 保存字符串長度 的變量，我們可以通過獲取len屬性的值，如下圖的，直接知道字符串長度：

 

”

杜絕緩沖區溢出

C 字符串是不會記錄字符串長度的，除了獲取的時候復雜度高以外，還容易導致緩沖區溢出。

我們現在假設程序中有兩個在內存中 緊鄰著的字符串s1和s2 ，其中s1保存了字符串“ redis ”，而s2 則保存了字符串“ MongoDb ”：

 

如果我們現在將s1的內容修改為 redis cluster ，但是我又忘了重新為 s1分配足夠的空間 ，這時候就會出現以下問題：

 

我們可以看到，原本s2中的內容已經 被S1的給占領 了，s2現在是cluster，而不是“Mongodb”。Redis 中SDS 的 空間分配策略 完全 杜絕 了發生緩沖區溢出的可能性：

“

我們需要對一個SDS進行修改的時候，redis會在執行 拼接操作 之前，預先檢查給定SDS空間是否是足夠的，如果不夠，會先 拓展SDS 的空間 ，然后再執行拼接操作；

”

 

 

減少修改字符串時帶來的內存重分配次數

C字符串在進行字符串的擴充和收縮的時候，都常常會面臨著 內存空間 重新分配的問題。

• 字符串拼接會產生字符串的內存空間的 擴充 ，在拼接的過程中，原來的字符串的大小很可能 小于 拼接后的字符串的大小，那么這樣的話，就會導致一旦 忘記申請 分配空間，就會導致內存的溢出。
• 字符串在進行收縮的時候，內存空間會 相應的收縮 ，而如果在進行字符串的切割的時候，沒有對內存的空間進行一個重新分配，那么這部分多出來的空間就成為了內存泄露。*

下面我們對SDS進行拓展，那就需要進行 空間的拓展 ，redis會將SDS的長度修改為13字節，并且將未使用空間同樣修改成1字節；

 

 

因為在上一次修改字符串的時候已經拓展了空間，再次進行修改字符串的時候你會發現空間是足夠使用，因此就不要進行空間拓展了。

 

通過這種 預分配策略 ，SDS將連續增長N次字符串所需的 內存重分配次數 從必定N次會降低為最多N次

惰性空間釋放

我們在觀察SDS的結構的時候,可以看到里面有free屬性，是用于 記錄空余空間 的。我們除了在拓展字符串的時候會使用到free來進行記錄空余空間以外，在對字符串進行收縮的時候，我們也可以使用free 屬性來進行 記錄剩余空間 ，這樣做的好處就是避免下次對字符串進行再次修改的時候，我們 再對 字符串的空間進行拓展。

“

但是，我們并不是說不能釋放SDS中空余的空間，SDS 提供了相應的API，讓我們可以在 有需要 的時候，會 自行釋放 SDS的空余空間；

”

通過惰性空間釋放，SDS避免了縮短字符串時所需的 內存重分配 操作，并未將來可能有的增長操作提供了優化，嗯值得點贊！

 

二進制安全

強調 的是C字符串中的字符必須符合某種 編碼 ，并且除了字符串的末尾之外，字符串里面不包含 空字符 ，否則最先被程序讀入的空字符將被誤認為是字符串結尾，那就尷尬了，這些 限制 使得C字符串只能保存文本數據，而不能保存想圖片，音頻，視頻，壓縮文件這樣的 二進制 數據。

“

但是在Redis中，不是靠空字符來判斷字符串的結束的，而是通過 len 這個屬性。那么，即便是中間出現了空字符對于SDS來說，讀取該字符仍然是可以的。

”

如這樣：

 

兼容部分C字符串函數

雖然SDS的API都是二進制安全的，但他們同樣要遵循C字符串以 空字符串結尾 的慣例。

再次總結

C字符串	SDS
獲取字符串長度的復雜度為O（N)	獲取字符串長度的復雜度為O(1)
API 是不安全的，可能會造成緩沖區溢出	API 是安全的，不會造成緩沖區溢出
修改字符串長度N次必然需要執行N次內存重分配	修改字符串長度N次最多執行N次內存重分配
只能保存文本數據	可以保存二進制數據和文本文數據
可以使用所有<String.h>庫中的函數	可以使用一部分<string.h>庫中的函數

壓縮表

壓縮表是一種Redis用來 節省內存 的一系列特殊編碼的 順序性連續存儲 的表結構，我們知道數組這種數據結構，每一個空間的大小都是一樣的，這樣我們存儲較小元素節點的時候就會造成 內存的浪費 ，而壓縮鏈表可以做到每一個元素的節點的 大小都不一樣 。當一個哈希鍵只含少量鍵值對，并且每個鍵值對的鍵和值也是小整數值或者長度比較短的字符串的時候，Redis就采用壓縮列表做底層實現;

長這樣：

 

圖里 entry 的結構是這樣的：

 

previous_entry_length屬性以字節為單位，記錄了壓縮列表中 前一個節點的長度 。該屬性的長度可以是1字節或者是5字節。如果前一個節點的長度 小于

254 字節，那么該屬性長度為1字節，保存的是小于 254的值。那如果前一節點的長度

大于等于

254字節，那么長度需要為5字節，屬性的第一字節會被設置為0xFE (254)之后的4個字節保存其長度。

參數：

zlbytes ：4 字節。記錄整個壓縮列表占用的內存字節數，在內存重分配或者計算 zlend 的位置時使用。

zltail ：4 字節。記錄壓縮列表表尾節點記錄壓縮列表的起始地址有多少個字節，可以通過該屬性直接確定表尾節點的地址，無需遍歷。

zllen ：2 字節。記錄了壓縮列表包含的節點數量，由于只有2字節大小，那么小于65535時，表示節點數量。等于 65535 時，需要遍歷得到總數。

entry ：列表節點，長度不定，由內容決定。

zlend

：1字節，特殊值 0xFF ，來標記壓縮列表的結束。

壓縮列表節點保存的是 一個字節數組 或者 一個整數值 ：字節數組可以是下列值：

• 長度小于等于 2^6-1 字節的字節數組
• 長度小于等于 2^14-1 字節的字節數組
• 長度小于等于 2^32-1 字節的字節數組整數可以是六種長度;
• 4 位長，介于 0 到 12 之間的無符號整數
• 1 字節長的有符號整數
• 3 字節長的有符號整數
• int16_t 類型整數
• int32_t 類型整數
• int64_t 類型整數

元素的遍歷

先找到列表尾部元素：

 

然后再根據 ziplist 節點元素中的 previous_entry_length 屬性，來逐個來遍歷:

 

連鎖更新

再次看看 entry元素的結構，有一個 previous_entry_length 字段，它的長度要么都是1個字節，要么都是5個字節：

• 前一節點的長度小于 254 字節，則 previous_entry_length長度為1字節
• 前一節點的長度小于 254 字節，則 previous_entry_length長度為5字節假如現在有一組壓縮列表，長度都在250字節至253字節之間，突然新增一新節點 new， 長度大于等于254字節，會出現：

 

g3

程序需要 不斷 的對壓縮列表進行 空間重分配 工作，直到結束。

除了增加操作，刪除操作也有可能帶來“連鎖更新”。請看下面這張圖， ziplist 中所有 entry 節點的長度都在250字節至253字節之間，big節點長度大于254字節，small節點小于254字節：

 

在我看來，壓縮列表實際上 類似于一個數組 ，數組中的每一個元素都對應保存一個數據。和數組不同的是，壓縮列表在 表頭有三個字段 zlbytes、zltail 和 zllen，分別表示列表長度、列表尾的偏移量和列表中的entry數；壓縮列表在表尾還有一個 zlend ，表示列表結束罷了。

字典

“

又叫 符號表 或者關聯數組、或映射（map），是一種用于 保存鍵值對 的抽象數據結構。字典中的每一個鍵key都是唯一的，通過key可以對值來進行 查找或修改 。C語言中沒有內置這種數據結構的實現，所以字典依然是 Redis自己實現的；示例：

”

redis > SET msg "hello world"
OK

（“msg”，“hello world”）這個就是字典;

哈希表結構：

typedef struct dictht{
     //哈希表數組
     dictEntry **table;
     //哈希表大小
     unsigned long size;
     //哈希表大小掩碼，用于計算索引值
     //總是等于 size-1
     unsigned long sizemask;
     //該哈希表已有節點的數量
     unsigned long used;
 
}dictht

哈希表是數組(表）table 組成，table里面每個元素都是指向 dict.h 或者 dictEntry 這個結構，dictEntry 結構：

typedef struct dictEntry{
    //鍵
    void *key;
    //值
    union{
         void *val;
         uint64_tu64;
         int64_ts64;
    }v;

    //指向下一個哈希表節點，形成鏈表
    struct dictEntry *next;
}dictEntry

哈希表就略微有點復雜。哈希表的制作方法一般有兩種，一種是： 開放尋址法 ，一種是拉鏈法。redis的哈希表的制作使用的是 拉鏈法 。

整體結構如圖：

 

哈希1

“

也是分為兩部分：左邊橘黃色部分和右邊藍色部分，同樣，也是”統籌“和”實施“的關系。具體 哈希表的實現 ，都是在 藍色部分 實現的,好！先來看看藍色部分：

”

 

這也會分為左右兩邊“統籌”和“實施”的兩部分。

右邊部分很容易理解：就是通常用 拉鏈表實現 的哈希表的樣式；數組就是bucket，一般不同的key首先會定位到不同的bucket，若key重復，就用鏈表把 沖突的key串 起來。

新建key的過程：

 

哈3

假如重復了：

 

哈4

rehash

“

再來看看哈希表總體圖中左邊橘黃色的“統籌”部分，其中有兩個關鍵的屬性：ht和 rehashidx。ht是一個 數組 ，有且只有倆元素ht[0]和ht[1];其中，ht[0]存放的是 redis中使用的哈希表 ，而ht[1]和rehashidx和哈希表是有 rehash 有關系的。

”

rehash指的是 重新計算 鍵的哈希值和索引值，然后將鍵值對 重排 的過程。

加載因子

（load factor）=ht[0].used/ht[0].size；

擴容和收縮標準

擴容：

• 沒有 執行BGSAVE和BGREWRITEAOF指令的情況下，哈希表的加載因子大于 等于1。
• 正在執行 BGSAVE和BGREWRITEAOF指令的情況下，哈希表的加載因子大于 等于5 。

收縮:

• 加載因子小于0.1時，程序自動開始對哈希表進行收縮操作;

擴容和收縮的數量；

擴容：

第一個大于等于 ht[0].used*2的 2^n(2的n次方冪);

收縮：

第一個大于等于 ht[0].used的 2^n(2的n次方冪)。(以下部分屬于細節分析，可以跳過直接看擴容步驟)

對于收縮，我當時陷入了疑慮：收縮標準是加載因子 小于0.1 的時候，也就是說假如哈希表中有4個元素的話，哈希表的長度只要大于40，就會進行收縮，假如有一個長度大于40，但是 存在的元素為4 即( ht[0].used為4)的哈希表，進行收縮，那收縮后的值為多少？

我想了一下：按照前文所講的內容，應該是4。但是，假如是4， 存在和收縮后的長度相等 ，是不是又該擴容？

假如收縮后 長度為4

，不僅不會收縮，甚至還會

報錯

；

我們回過頭來再看看設定：題目可能成立嗎？哈希表的擴容都是 2倍增長的 ，最小是4， 4 ===》 8 ====》 16 =====》 32 ======》 64 ====》 128

“

也就是說：不存在長度為 40多的情況，只能是64。但是如果是64的話，64 X 0.1（收縮界限）= 6.4 ，也就是說在減少到6的時候，哈希表就會收縮，會縮小到多少呢？是8。此時，再繼續減少到4，也不會再收縮了。所以，根本不存在一個長度大于40，但是存在的元素為4的哈希表的。

”

擴容步驟

 

收縮步驟

 

漸進式refresh

在"擴容步驟"和"收縮步驟" 兩幅動圖中每幅圖的 第四步驟 “將ht[0]中的數據利用哈希函數 重新計算 ，rehash到ht[1]”，并不是一步完成的，而是分成N多步，循序漸進地完成的。因為hash中有可能存放幾千萬甚至上億個key，畢竟Redis中每個 hash中可以存 2^32-1 鍵值對 （40多億），假如一次性將這些鍵值rehash的話，可能會導致服務器在一段時間內停止服務，畢竟哈希函數就得 計算一陣子呢 (對吧(#^.^#))。

哈希表的refresh是分多次、漸進式進行的。

漸進式refresh和下圖中左邊橘黃色的“統籌”部分中的rehashidx密切相關：

• rehashidx 的數值就是現在rehash的 元素位置
• rehashidx 等于-1的時候說明沒有在進行refresh

甚至在進行期間，每次對哈希表的增刪改查操作，除了正常執行之外，還會順帶將ht[0]哈希表相關鍵值對 rehash 到ht[1]。

以擴容步驟 舉例 ：

 

intset

整數集合是 集合鍵 的底層實現方式之一。

 

跳表

跳表這種數據結構長這樣：

 

redis中把跳表抽象成如下所示：

 

看這個圖，左邊“統籌”，右邊實現。

統籌部分 有幾點要說：

• header: 跳表表頭
• tail:跳表表尾
• level:層數最大的那個節點的層數
• length：跳表的長度

實現部分有以下幾點說：

• 表頭：是鏈表的哨兵節點，不記錄主體數據。是個 雙向鏈表分值 是有順序的
• o1、o2、o3是節點所保存的成員，是一個指針，可以指向一個SDS值。
• 層級高度最高是32。沒每次創建一個新的節點的時候，程序都會 隨機生成 一個介于1和32之間的值作為level 數組的大小 ，這個大小就是“高度”

redis五種數據結構的實現

redis對象

redis中并沒有 直接使用 以上所說的那種數據結構來實現鍵值數據庫，而是基于一種對象，對象底層再 間接的引用 上文所說的 具體 的數據結構。

就像這樣：

 

字符串

 

其中：embstr和raw都是由 SDS動態字符串 構成的。唯一區別是： raw 是分配內存的時候，redis object和sds各分配一塊內存，而embstr是redisobject和raw 在一塊兒內存 中。

列表

 

列表

hash

 

哈希

set

 

set

set

 

zset

跳躍表

是一種 有序 數據結構，它通過在 每個節點 中維持 多個指向其它節點 的指針，從而達到快速訪問節點的目的。具有如下 性質 ：

1、由很多層結構組成；

2、每一層都是一個有序的鏈表，排列順序為由高層到底層，且至少包含兩個鏈表節點，分別是前面的 head節點 和后面的 nil節點 ；

3、最底層的鏈表包含了所有的元素；

4、如果一個元素出現在某一層的鏈表中，那么在 該層之下 的鏈表也全 都會出現 （上一層的元素是當前層的元素的子集）；

5、鏈表中的每個節點都包含兩個指針，一個指向 同層的下一個鏈表節點 ，另一個指向 下層的同一個鏈表節點 ；

 

跳躍表節點定義如下：

typedef struct zskiplistNode {
     //層
     struct zskiplistLevel{
           //前進指針
           struct zskiplistNode *forward;
           //跨度
           unsigned int span;
     }level[];
 
     //后退指針
     struct zskiplistNode *backward;
     //分值
     double score;
     //成員對象
     robj *obj;
 
} zskiplistNode
  多個跳躍表節點構成一個跳躍表：

typedef struct zskiplist{
     //表頭節點和表尾節點
     structz skiplistNode *header, *tail;
     //表中節點的數量
     unsigned long length;
     //表中層數最大的節點的層數
     int level;
 
}zskiplist;

 

各個功能

“

①、搜索：從最高層的鏈表節點開始，如果比 當前節點要大 和比當前層的下一個節點要小，那么則往下找，也就是和當前層的下一層的節點的下一個節點進行比較，以此類推，一直找到 最底層的最后一個節點 ，如果找到則返回，反之則返回空。

②、插入：首先確定 插入的層數 ，有一種方法是假設拋一枚硬幣，如果是正面就累加，直到遇見反面為止，最后記錄正面的次數作為插入的層數。當確定 插入的層數k 后，則需要將 新元素 插入到從底層到k層。

③、刪除：在各個層中找到包含 指定值的節點

，然后將節點從鏈表中刪除即可，如果刪除以后

只剩下

頭尾兩個節點，則刪除這一層。

”

整數集合

用于保存 整數值 的集合抽象數據類型，它可以保存類型為int16_t、int32_t 或者int64_t 的整數值，并且保證集合中 不會出現重復 元素。定義如下：

typedef struct intset{
     //編碼方式
     uint32_t encoding;
     //集合包含的元素數量
     uint32_t length;
     //保存元素的數組
     int8_t contents[];
 
}intset;

整數集合的每個元素都是 contents 數組 的一個數據項，它們按照從小到大的 順序排列 ，并且不包含任何重復項。

length屬性記的是 contents數組的大小。

需要注意的是雖然 contents 數組聲明為 int8_t 類型，但是實際 上contents數組并不保存 任何 int8_t 類型的值 ，其真正類型有 encoding 來決定。

①、升級

當我們新增的元素類型比原集合元素類型的長度要大時，需要對 整數集合 進行升級，才能將新元素放入整數集合中。具體步驟：

1、根據新元素類型，擴展整數集合底層數組的大小，并為 新元素 分配空間。

2、將底層數組現有的所有元素都轉成與新元素相同類型的元素，并將 轉換后的元素 放到正確的位置，放置過程中，維持整個元素 順序 都是有序的。

3、將新元素添加到整數集合中是有序的呀！

 

升級能極大地節省內存。

②、降級

整數集合不支持降級操作，一旦對數組進行了升級， 編碼 就會一直保持升級后的狀態

總結

“

大多數情況下，Redis使用 簡單字符串SDS作為字符串 的表示，相對于C語言字符串，SDS具有常數復雜度獲取字符串長度，杜絕了 緩存區的溢出 ，減少了修改字符串長度時所需的 內存重分配次數 ，以及二進制安全能存儲各種類型的文件，并且還兼容部分C函數。

”

通過為鏈表設置不同類型的特定函數，Redis鏈表可以保存各種 不同類型的值 ，除了用作列表鍵，還在發布與訂閱、慢查詢、監視器等方面發揮作用（后面會介紹）。

Redis的字典底層使用 哈希表實現 ，每個字典通常有兩個哈希表，一個平時使用，另一個用于rehash時使用，使用 鏈地址法 解決哈希沖突。

跳躍表通常是有序集合的底層實現之一，表中的節點按照 分值大小 進行排序。

整數集合是 集合鍵 的底層實現之一，底層由數組構成， 升級特性 能盡可能的節省內存。

壓縮列表是Redis為 節省內存 而開發的順序型數據結構，經常作為列表鍵和哈希鍵的底層實現。

原文鏈接：
https://mp.weixin.qq.com/s?__biz=MzAwMDg2OTAxNg==&mid=2652049856&idx=1&sn=05d77ad89bb84bf55cea9e17e6192a04&utm_source=tuicool&utm_medium=referral