redis底層數(shù)據(jù)結構是什么？針對這個問題，今天小編總結了這篇文章，希望能幫助更多想解決這個問題的朋友找到更加簡單易行的辦法。

河曲網(wǎng)站建設公司創(chuàng)新互聯(lián),河曲網(wǎng)站設計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為河曲上1000+提供企業(yè)網(wǎng)站建設服務。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請找那個售后服務好的河曲做網(wǎng)站的公司定做！

1、概述

相信使用過Redis的各位同學都很清楚，Redis 是一個基于鍵值對（key-value）的分布式存儲系統(tǒng)，與Memcached類似，卻優(yōu)于Memcached的一個高性能的key-value數(shù)據(jù)庫。

在《Redis設計與實現(xiàn)》這樣描述：

Redis數(shù)據(jù)庫里面的每個鍵值對（key-value） 都是由對象（object）組成的：

數(shù)據(jù)庫鍵總是一個字符串對象（string object）;

數(shù)據(jù)庫的值則可以是字符串對象、列表對象（list）、哈希對象（hash）、集合對象（set）、有序集合（sort set）對象這五種對象中的其中一種。

我們?yōu)槭裁磿fRedis 優(yōu)于Memcached 呢，因為Redis 的出現(xiàn)，豐富了memcached 中key-value的存儲不足，在部分場合可以對關系數(shù)據(jù)庫起到很好的補充作用，而且這些數(shù)據(jù)類型都支持push/pop、add/remove及取交集并集和差集及更豐富的操作，而且這些操作都是原子性的。

我們今天探討的并不是Redis 中value 的數(shù)據(jù)類型，而是他們的具體實現(xiàn)——底層數(shù)據(jù)類型。

Redis 底層數(shù)據(jù)結構有一下數(shù)據(jù)類型：

1、簡單動態(tài)字符串

2、鏈表

3、字典

4、跳躍表

5、整數(shù)集合

6、壓縮列表

7、對象

2、簡單動態(tài)字符串（simple dynamic string）SDS

2.1 概述

Redis 是一個開源的使用ANSI C語言編寫的key-value 數(shù)據(jù)庫，我們可能會較為主觀的認為 Redis 中的字符串就是采用了C語言中的傳統(tǒng)字符串表示，但其實不然，Redis 沒有直接使用C語言傳統(tǒng)的字符串表示，而是自己構建了一種名為簡單動態(tài)字符串（simple dynamic string SDS）的抽象類型，并將SDS用作Redis 的默認字符串表示：

redis>SET msg "hello world"
OK

設置一個key= msg，value = hello world 的新鍵值對，他們底層是數(shù)據(jù)結構將會是：

鍵（key）是一個字符串對象，對象的底層實現(xiàn)是一個保存著字符串“msg” 的SDS；

值（value）也是一個字符串對象，對象的底層實現(xiàn)是一個保存著字符串“hello world” 的SDS

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

2.2  SDS 的定義

Redis 中定義動態(tài)字符串的結構：

/*  
 * 保存字符串對象的結構  
 */  
struct sdshdr {  
      
    // buf 中已占用空間的長度  
    int len;  
  
    // buf 中剩余可用空間的長度  
    int free;  
  
    // 數(shù)據(jù)空間  
    char buf[];  
};

1、len 變量，用于記錄buf 中已經(jīng)使用的空間長度（這里指出Redis 的長度為5）

2、free 變量，用于記錄buf 中還空余的空間（初次分配空間，一般沒有空余，在對字符串修改的時候，會有剩余空間出現(xiàn)）

3、buf 字符數(shù)組，用于記錄我們的字符串（記錄Redis）

2.3  SDS 與 C 字符串的區(qū)別

傳統(tǒng)的C 字符串 使用長度為N+1 的字符串數(shù)組來表示長度為N 的字符串，這樣做在獲取字符串長度，字符串擴展等操作的時候效率低下。C 語言使用這種簡單的字符串表示方式，并不能滿足Redis 對字符串在安全性、效率以及功能方面的要求

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

傳統(tǒng)的C 字符串 使用長度為N+1 的字符串數(shù)組來表示長度為N 的字符串，所以為了獲取一個長度為C字符串的長度，必須遍歷整個字符串。

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

2.3.2 杜絕緩沖區(qū)溢出

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

假設程序中有兩個在內(nèi)存中緊鄰著的 字符串 s1 和 s2，其中s1 保存了字符串“redis”，二s2 則保存了字符串“MongoDB”：

如果我們現(xiàn)在將s1 的內(nèi)容修改為redis cluster，但是又忘了重新為s1 分配足夠的空間，這時候就會出現(xiàn)，原本s2 中的內(nèi)容已經(jīng)被S1的內(nèi)容給占領了，s2 現(xiàn)在為 cluster，而不是“Mongodb”。

Redis 中SDS 的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性：

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

2.3.3 減少修改字符串時帶來的內(nèi)存重分配次數(shù)　

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

1. 字符串拼接會產(chǎn)生字符串的內(nèi)存空間的擴充，在拼接的過程中，原來的字符串的大小很可能小于拼接后的字符串的大小，那么這樣的話，就會導致一旦忘記申請分配空間，就會導致內(nèi)存的溢出。

2. 字符串在進行收縮的時候，內(nèi)存空間會相應的收縮，而如果在進行字符串的切割的時候，沒有對內(nèi)存的空間進行一個重新分配，那么這部分多出來的空間就成為了內(nèi)存泄露。

舉個例子：我們需要對下面的SDS進行拓展，則需要進行空間的拓展，這時候redis 會將SDS的長度修改為13字節(jié)，并且將未使用空間同樣修改為1字節(jié)

因為在上一次修改字符串的時候已經(jīng)拓展了空間，再次進行修改字符串的時候會發(fā)現(xiàn)空間足夠使用，因此無須進行空間拓展

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

2.3.4 惰性空間釋放

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

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

通過惰性空間釋放，SDS 避免了縮短字符串時所需的內(nèi)存重分配操作，并未將來可能有的增長操作提供了優(yōu)化

2.3.5 二進制安全

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

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

例如：

2.3.6 兼容部分C字符串函數(shù)

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

2.3.7 總結

3、鏈表

3.1 概述

鏈表提供了高效的節(jié)點重排能力，以及順序性的節(jié)點訪問方式，并且可以通過增刪節(jié)點來靈活地調(diào)整鏈表的長度。

鏈表在Redis 中的應用非常廣泛，比如列表鍵的底層實現(xiàn)之一就是鏈表。當一個列表鍵包含了數(shù)量較多的元素，又或者列表中包含的元素都是比較長的字符串時，Redis 就會使用鏈表作為列表鍵的底層實現(xiàn)?！?/p>

3.2 鏈表的數(shù)據(jù)結構

每個鏈表節(jié)點使用一個 listNode結構表示（adlist.h/listNode）：

typedef struct listNode{
      struct listNode *prev;
      struct listNode * next;
      void * value;  
}

多個鏈表節(jié)點組成的雙端鏈表：

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

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

list 組成的結構圖：

3.3 鏈表的特性

雙端：鏈表節(jié)點帶有prev 和next 指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的時間復雜度都是O（N）

無環(huán)：表頭節(jié)點的 prev 指針和表尾節(jié)點的next 都指向NULL，對立案表的訪問時以NULL為截止

表頭和表尾：因為鏈表帶有head指針和tail 指針，程序獲取鏈表頭結點和尾節(jié)點的時間復雜度為O(1)

長度計數(shù)器：鏈表中存有記錄鏈表長度的屬性 len

多態(tài)：鏈表節(jié)點使用 void* 指針來保存節(jié)點值，并且可以通過list 結構的dup 、 free、 match三個屬性為節(jié)點值設置類型特定函數(shù)。

4、字典

4.1 概述

字典，又稱為符號表（symbol table）、關聯(lián)數(shù)組（associative array）或映射（map），是一種用于保存鍵值對的抽象數(shù)據(jù)結構。　

在字典中，一個鍵（key）可以和一個值（value）進行關聯(lián)，字典中的每個鍵都是獨一無二的。在C語言中，并沒有這種數(shù)據(jù)結構，但是Redis 中構建了自己的字典實現(xiàn)。

舉個簡單的例子：

redis > SET msg "hello world"
OK

創(chuàng)建這樣的鍵值對（“msg”，“hello world”）在數(shù)據(jù)庫中就是以字典的形式存儲

4.2 字典的定義

4.2.1 哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 結構定義：

typedef struct dictht {
   //哈希表數(shù)組
   dictEntry **table;
   //哈希表大小
   unsigned long size;

   //哈希表大小掩碼，用于計算索引值
   unsigned long sizemask;
   //該哈希表已有節(jié)點的數(shù)量
   unsigned long used;
}

一個空的字典的結構圖如下：

我們可以看到，在結構中存有指向dictEntry 數(shù)組的指針，而我們用來存儲數(shù)據(jù)的空間既是dictEntry

4.2.2 哈希表節(jié)點（ dictEntry ）

dictEntry 結構定義：

typeof struct dictEntry{
   //鍵
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;

}

在數(shù)據(jù)結構中，我們清楚key 是唯一的，但是我們存入里面的key 并不是直接的字符串，而是一個hash 值，通過hash 算法，將字符串轉換成對應的hash 值，然后在dictEntry 中找到對應的位置。

這時候我們會發(fā)現(xiàn)一個問題，如果出現(xiàn)hash 值相同的情況怎么辦？Redis 采用了鏈地址法：

當k1 和k0 的hash 值相同時，將k1中的next 指向k0 想成一個鏈表。

4.2.3 字典

typedef struct dict {
    // 類型特定函數(shù)
    dictType *type;
    // 私有數(shù)據(jù)
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in trehashidx;

}

type 屬性 和privdata 屬性是針對不同類型的鍵值對，為創(chuàng)建多態(tài)字典而設置的。

ht 屬性是一個包含兩個項（兩個哈希表）的數(shù)組

普通狀態(tài)下的字典：

4.3 解決哈希沖突

在上述分析哈希節(jié)點的時候我們有講到：在插入一條新的數(shù)據(jù)時，會進行哈希值的計算，如果出現(xiàn)了hash值相同的情況，Redis 中采用了連地址法（separate chaining）來解決鍵沖突。

每個哈希表節(jié)點都有一個next 指針，多個哈希表節(jié)點可以使用next 構成一個單向鏈表，被分配到同一個索引上的多個節(jié)點可以使用這個單向鏈表連接起來解決hash值沖突的問題。

舉個例子：

現(xiàn)在哈希表中有以下的數(shù)據(jù)：k0 和k1

我們現(xiàn)在要插入k2，通過hash 算法計算到k2 的hash 值為2，即我們需要將k2 插入到dictEntry[2]中：

在插入后我們可以看到，dictEntry指向了k2，k2的next 指向了k1，從而完成了一次插入操作（這里選擇表頭插入是因為哈希表節(jié)點中沒有記錄鏈表尾節(jié)點位置）

4.4 Rehash

隨著對哈希表的不斷操作，哈希表保存的鍵值對會逐漸的發(fā)生改變，為了讓哈希表的負載因子維持在一個合理的范圍之內(nèi)，我們需要對哈希表的大小進行相應的擴展或者壓縮，這時候，我們可以通過 rehash（重新散列）操作來完成。

4.4.1 目前的哈希表狀態(tài)：

我們可以看到，哈希表中的每個節(jié)點都已經(jīng)使用到了，這時候我們需要對哈希表進行拓展。

4.4.2 為哈希表分配空間

哈希表空間分配規(guī)則：

如果執(zhí)行的是拓展操作，那么ht[1] 的大小為第一個大于等于ht[0] 的2的n次冪

如果執(zhí)行的是收縮操作，那么ht[1] 的大小為第一個大于等于ht[0] 的2的n次冪

因此這里我們?yōu)閔t[1] 分配 空間為8，

4.4.3 數(shù)據(jù)轉移

將ht[0]中的數(shù)據(jù)轉移到ht[1]中，在轉移的過程中，需要對哈希表節(jié)點的數(shù)據(jù)重新進行哈希值計算

數(shù)據(jù)轉移后的結果：

4.4.4 釋放ht[0]

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

4.4.5 漸進式 rehash

上面我們說到，在進行拓展或者壓縮的時候，可以直接將所有的鍵值對rehash 到ht[1]中，這是因為數(shù)據(jù)量比較小。在實際開發(fā)過程中，這個rehash 操作并不是一次性、集中式完成的，而是分多次、漸進式地完成的。

漸進式rehash 的詳細步驟：

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

2、在幾點鐘維持一個索引計數(shù)器變量rehashidx，并將它的值設置為0，表示rehash 開始

3、在rehash 進行期間，每次對字典執(zhí)行CRUD操作時，程序除了執(zhí)行指定的操作以外，還會將ht[0]中的數(shù)據(jù)rehash 到ht[1]表中，并且將rehashidx加一

4、當ht[0]中所有數(shù)據(jù)轉移到ht[1]中時，將rehashidx 設置成-1，表示rehash 結束

采用漸進式rehash 的好處在于它采取分而治之的方式，避免了集中式rehash 帶來的龐大計算量。

關于redis底層數(shù)據(jù)結構就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。