SDS

SDS全稱是Simple Dynamic String，具有如下顯著的特點：

1. 常數(shù)復(fù)雜度獲取字符串長度：C語言獲取一個字符串的長度需要遍歷整個字符串時間復(fù)雜度為O(N)，而SDS在屬性len中記錄了字符串長度，獲取字符串長度的時間復(fù)雜度為O(1)。
2. 杜絕緩沖區(qū)溢出：C字符串在執(zhí)行拼接字符串時，如果長度不夠會產(chǎn)生緩沖區(qū)溢出的問題，而SDS在拼接字符串時，會先檢查空間是否足夠，如果不滿足會將空間自動擴(kuò)展至執(zhí)行修改所需的大小，然后再執(zhí)行操作。
3. 減少修改字符串時帶來的內(nèi)存重分配次數(shù)：C字符串的長度和底層數(shù)組的長度之間存在著關(guān)聯(lián)性，每次增加或縮小一個C字符串，程序都需要對C字符串的數(shù)據(jù)進(jìn)行內(nèi)存重分配操作，為了避免C字符串的這種缺陷，SDS通過未使用空間解除了字符串長度和底層數(shù)組間的關(guān)系，通過未使用空間SDS實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。
   其中; 空間預(yù)分配：SDS內(nèi)部為當(dāng)前字符串實際分配的空間，一般要高于實際字符串的長度，當(dāng)字符串的長度小于1M時，擴(kuò)容都是擴(kuò)一倍，如果超過1M，擴(kuò)容是最多擴(kuò)1M的空間，字符串的最大長度是512M。
   惰性空間釋放：用于優(yōu)化SDS字符串的縮短操作，當(dāng)需要縮短SDS的字符串時，程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)，而是使用free屬性將這些字節(jié)的數(shù)量記錄下來，并等待將來使用。
4. 二進(jìn)制安全：SDS的API都是二進(jìn)制安全的，都會以處理二進(jìn)制的方式處理SDS存放在buf數(shù)組里的數(shù)據(jù)，寫入什么樣，讀取就是什么樣，redis不是用buf屬性來保存字符，而是保存一系列的二進(jìn)制數(shù)據(jù)。
5. 兼容部分C字符串函數(shù)。

dict

dict是一個基于哈希表的數(shù)據(jù)結(jié)構(gòu)，在不要求數(shù)據(jù)有序存儲，且能保持較低的哈希值沖突概率的前提下，查詢的時間復(fù)雜度接近O(1)。它采用某個哈希函數(shù)從key計算得到在哈希表中的位置，采用拉鏈法解決沖突，并在裝載因子（load factor）超過預(yù)定值時自動擴(kuò)展內(nèi)存，引發(fā)重哈希（rehashing）。Redis的dict實現(xiàn)最顯著的一個特點，就在于它的重哈希。它采用了一種稱為漸進(jìn)式哈希的方法，在需要擴(kuò)展內(nèi)存時避免一次性對所有key進(jìn)行重哈希，而是將重哈希操作分散到對于dict的各個增刪改查的操作中去。這種方法能做到每次只對一小部分key進(jìn)行重哈希，而每次重哈希之間不影響dict的操作。dict之所以這樣設(shè)計，是為了避免重哈希期間單個請求的響應(yīng)時間劇烈增加，這與前面提到的“快速響應(yīng)時間”的設(shè)計原則是相符的。

當(dāng)裝載因子大于 1 的時候，Redis 會觸發(fā)擴(kuò)容，將hash擴(kuò)大為原來大小的 2 倍左右；當(dāng)裝載因子小于 0.1 的時候，Redis 就會觸發(fā)縮容，hash縮小為原來的一半左右。

ziplist

ziplist的特點如下：

1. ziplist使用一整塊連續(xù)的內(nèi)存，將表中每一項存放在前后連續(xù)的地址空間內(nèi)，類似于一個數(shù)組。Ziplist內(nèi)的集合元素按score從小到大排序，score較小的排在表頭位置。
2. ziplist對于值的存儲采用了變長的編碼方式，對于大的整數(shù)，就多用一些字節(jié)來存儲，而對于小的整數(shù)，就少用一些字節(jié)來存儲。

quicklist

quicklist是一個雙向鏈表，而且是一個基于ziplist的雙向鏈表，quicklist的每個節(jié)點都是一個ziplist，比如，一個包含3個節(jié)點的quicklist，如果每個節(jié)點的ziplist又包含4個數(shù)據(jù)項，那么對外表現(xiàn)上，這個list就總共包含12個數(shù)據(jù)項。

quicklist的結(jié)構(gòu)為什么這樣設(shè)計呢？總結(jié)起來，大概又是一個空間和時間的折中：

1. 雙向鏈表便于在表的兩端進(jìn)行push和pop操作，但是它的內(nèi)存開銷比較大。首先，它在每個節(jié)點上除了要保存數(shù)據(jù)之外，還要額外保存兩個指針；其次，雙向鏈表的各個節(jié)點是單獨(dú)的內(nèi)存塊，地址不連續(xù)，節(jié)點多了容易產(chǎn)生內(nèi)存碎片。
2. ziplist由于是一整塊連續(xù)內(nèi)存，所以存儲效率很高。但是，它不利于修改操作，每次數(shù)據(jù)變動都會引發(fā)一次內(nèi)存的realloc。特別是當(dāng)ziplist長度很長的時候，一次realloc可能會導(dǎo)致大批量的數(shù)據(jù)拷貝，進(jìn)一步降低性能。
   不過，這也帶來了一個新問題：到底一個quicklist節(jié)點包含多長的ziplist合適呢？比如，同樣是存儲12個數(shù)據(jù)項，既可以是一個quicklist包含3個節(jié)點，而每個節(jié)點的ziplist又包含4個數(shù)據(jù)項，也可以是一個quicklist包含6個節(jié)點，而每個節(jié)點的ziplist又包含2個數(shù)據(jù)項。

這又是一個需要找平衡點的難題。我們只從存儲效率上分析一下：

1. 每個quicklist節(jié)點上的ziplist越短，則內(nèi)存碎片越多。內(nèi)存碎片多了，有可能在內(nèi)存中產(chǎn)生很多無法被利用的小碎片，從而降低存儲效率。這種情況的極端是每個quicklist節(jié)點上的ziplist只包含一個數(shù)據(jù)項，這就蛻化成一個普通的雙向鏈表了。
2. 每個quicklist節(jié)點上的ziplist越長，則為ziplist分配大塊連續(xù)內(nèi)存空間的難度就越大。有可能出現(xiàn)內(nèi)存里有很多小塊的空閑空間（它們加起來很多），但卻找不到一塊足夠大的空閑空間分配給ziplist的情況。這同樣會降低存儲效率。這種情況的極端是整個quicklist只有一個節(jié)點，所有的數(shù)據(jù)項都分配在這僅有的一個節(jié)點的ziplist里面。這其實蛻化成一個ziplist了。

可見，一個quicklist節(jié)點上的ziplist要保持一個合理的長度。那到底多長合理呢？這可能取決于具體應(yīng)用場景。實際上，Redis提供了一個配置參數(shù)list-max-ziplist-size，就是為了讓使用者可以來根據(jù)自己的情況進(jìn)行調(diào)整。

list-max-ziplist-size -2

這個參數(shù)可以取正值，也可以取負(fù)值。

當(dāng)取正值的時候，表示按照數(shù)據(jù)項個數(shù)來限定每個quicklist節(jié)點上的ziplist長度。比如，當(dāng)這個參數(shù)配置成5的時候，表示每個quicklist節(jié)點的ziplist最多包含5個數(shù)據(jù)項。

當(dāng)取負(fù)值的時候，表示按照占用字節(jié)數(shù)來限定每個quicklist節(jié)點上的ziplist長度。這時，它只能取-1到-5這五個值，每個值含義如下：

-5: 每個quicklist節(jié)點上的ziplist大小不能超過64 Kb。（注：1kb => 1024 bytes）
-4: 每個quicklist節(jié)點上的ziplist大小不能超過32 Kb。
-3: 每個quicklist節(jié)點上的ziplist大小不能超過16 Kb。
-2: 每個quicklist節(jié)點上的ziplist大小不能超過8 Kb。（-2是Redis給出的默認(rèn)值）
-1: 每個quicklist節(jié)點上的ziplist大小不能超過4 Kb。

intset

intset是一個由整數(shù)組成的有序集合，從而便于進(jìn)行二分查找，用于快速地判斷一個元素是否屬于這個集合。它在內(nèi)存分配上與ziplist有些類似，是連續(xù)的一整塊內(nèi)存空間。

intset的定義如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
 
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

各個字段含義如下：

• encoding: 數(shù)據(jù)編碼，表示intset中的每個數(shù)據(jù)元素用幾個字節(jié)來存儲。它有三種可能的取值：INTSET_ENC_INT16表示每個元素用2個字節(jié)存儲，INTSET_ENC_INT32表示每個元素用4個字節(jié)存儲，INTSET_ENC_INT64表示每個元素用8個字節(jié)存儲。因此，intset中存儲的整數(shù)最多只能占用64bit。
• length: 表示intset中的元素個數(shù)。encoding和length兩個字段構(gòu)成了intset的頭部（header）。
• contents: 是一個柔性數(shù)組（flexible array member），表示intset的header后面緊跟著數(shù)據(jù)元素。這個數(shù)組的總長度（即總字節(jié)數(shù)）等于encoding *length。柔性數(shù)組在Redis的很多數(shù)據(jù)結(jié)構(gòu)的定義中都出現(xiàn)過（例如sds, quicklist, skiplist），用于表達(dá)一個偏移量。
• contents需要單獨(dú)為其分配空間，這部分內(nèi)存不包含在intset結(jié)構(gòu)當(dāng)中。
  其中需要注意的是，intset可能會隨著數(shù)據(jù)的添加而改變它的數(shù)據(jù)編碼：

1. 最開始，新創(chuàng)建的intset使用占內(nèi)存最小的INTSET_ENC_INT16（值為2）作為數(shù)據(jù)編碼。

2. 每添加一個新元素，則根據(jù)元素大小決定是否對數(shù)據(jù)編碼進(jìn)行升級。
   intset與ziplist的比較：

3. ziplist可以存儲任意二進(jìn)制串，而intset只能存儲整數(shù)。

4. ziplist可以對每個數(shù)據(jù)項進(jìn)行不同的變長編碼（每個數(shù)據(jù)項前面都有數(shù)據(jù)長度字段len），而intset只能整體使用一個統(tǒng)一的編碼（encoding）。

skiplist

跳表是一種可以進(jìn)行二分查找的有序鏈表，采用空間換時間的設(shè)計思路，跳表在原有的有序鏈表上面增加了多級索引（例如每兩個節(jié)點就提取一個節(jié)點到上一級），通過索引來實現(xiàn)快速查找。跳表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，支持快速的插入、刪除、查找操作，時間復(fù)雜度都為O(logn)，空間復(fù)雜度為 O(n)。跳表非常靈活，可以通過改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗。

跳表具有以下兩個特點：文章來源地址http://www.zghlxwxcb.cn/news/detail-537160.html

1. 跳表的刪除操作除了要刪除原始鏈表中的節(jié)點，還要刪除索引中的節(jié)點。
2. 插入元素后，索引的動態(tài)更新，不停的往跳表里面插入數(shù)據(jù)，如果不更新索引，就有可能出現(xiàn)某兩個索引節(jié)點之間的數(shù)據(jù)非常多的情況，甚至退化成單鏈表。針對這種情況，我們在添加元素的時候，通過一個隨機(jī)函數(shù)，同時選擇將這個數(shù)據(jù)插入到部分索引層。比如隨機(jī)函數(shù)生成了值 K，那我們就將這個結(jié)點添加到第一級到第K級的索引中。

到了這里，關(guān)于Redis底層數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！