目錄
?
1.字符串
1.1 SDS定義
1.2 SDS1好處
2.列表
2.1 void 實現(xiàn)多態(tài)
3 字典
3.1 ? 底層實現(xiàn)是hash表
3.2 字典結(jié)構(gòu)
3.3?哈希算法
3.3.1 rehash
3.3.2 rehash的觸發(fā)時機
3.3.3?漸進式rehash
擴展或收縮哈希表需要將ht[0]里面的所有鍵值對rehash到ht[1]里面，但是，這個rehash動作并不是一次性、集中式地完成的，而是分多次、漸進式地完成的。
4.跳躍表
4.1 跳躍表-zskiplistNode?
4.2?跳躍表 - zskiplist
5.壓縮列表
1.字符串
- Redis沒有直接使用C語言傳統(tǒng)的字符串表示（以空字符結(jié)尾的字符數(shù)組，以下簡稱C字符串），而是自己構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string，SDS）的抽象類型（對象），并將SDS用作Redis的默認(rèn)字符串表示。
- 在Redis里面，C字符串只會作為字符串字面量（string literal）用在一些無須對字符串值進行修改的地方，比如打印日志，當(dāng)Redis需要的不僅僅是一個字符串字面量，而是一個可以被修改的字符串值時，Redis就會使用SDS來表示字符串值。
- 除了用來保存數(shù)據(jù)庫中的字符串值之外，SDS還被用作緩沖區(qū)（buffer）：AOF模塊中的AOF緩沖區(qū)，以及客戶端狀態(tài)中的輸入緩沖區(qū)，都是由SDS實現(xiàn)的
1.1 SDS定義
struct sdshdr {
//SDS所保存字符串的長度
int len;
// 記錄buf數(shù)組中未使用字節(jié)的數(shù)量
int free;
// 字節(jié)數(shù)組，用于保存字符串
char buf[];
};
1.2 SDS1好處
- C 語言的字符串如果想要得到他的長度，需要進行遍歷，意味著時間復(fù)雜度為 o(N)。如果使用sds，我們的長度直接從len屬性里獲取，o(1). 本質(zhì)上，其實就是多了一個len屬性，保存了我們的字符串的長度；
- C語言的字符串如果進行我們的 擴展（增加字符串的長度） 或者 縮減（減少字符串的長度）。 進行擴展：我們必須要提前分配內(nèi)存空間，一旦忘了分配，造成緩沖區(qū)溢出；進行縮減：必須要有意識的進行空間的釋放，否則造成空間浪費。無論是進行擴展還是縮減，都需要進行內(nèi)存的重新分配，耗時啊。 SDS 來說，他不會造成緩沖區(qū)溢出的問題，是封裝好的對象，他已經(jīng)為我們考慮了這部分內(nèi)存的擴展及縮減問題。
- 二進制安全問題。C 語言來說，他的字符串是二進制不安全的，因為C語言的 空字符 結(jié)尾的設(shè)計，如果一個字符串中間有空字符串，那么 c語言的字符串的二進制轉(zhuǎn)化會遺棄第一個空字符出現(xiàn)的后邊的所有內(nèi)容。 舉例： m \0 s g \0. ?如果是 C語言進行二進制轉(zhuǎn)化，只對 m 進行轉(zhuǎn)化； SDS 就不是啦，我們是自己封裝的對象，我們能支持二進制的安全性，我能全部進行轉(zhuǎn)化。
2.列表
列表鍵的底層實現(xiàn)就是一個鏈表，鏈表中的每個節(jié)點都保存了一個數(shù)值
typedef struct list {
// 表頭節(jié)點
listNode * head;
// 表尾節(jié)點
listNode * tail;
// 鏈表所包含的節(jié)點數(shù)量
unsigned long len;
// 節(jié)點值復(fù)制函數(shù)
void *(*dup)(void *ptr);
// 節(jié)點值釋放函數(shù)
void (*free)(void *ptr);
// 節(jié)點值對比函數(shù)
int (*match)(void *ptr,void *key);
} list;
typedef struct listNode {
// 前置節(jié)點
struct listNode * prev;
// 后置節(jié)點
struct listNode * next;
// 節(jié)點的值
void * value;
}listNode;
2.1 void 實現(xiàn)多態(tài)
- ?void 這里代表的是 多態(tài)。 ? ? 如果你在java里想復(fù)制一個值，那么你是不是要么 知道這個值的類型，要么你使用 object 。 對于 redis 來說，由于 list 里可以存放各種類型的數(shù)值，那么，如果你要進行多種類型值的一些統(tǒng)一操作的話，需要使用 void 的返回值類型，這里體現(xiàn)了 我們 多態(tài)的一個性質(zhì)。
3 字典
3.1 ? 底層實現(xiàn)是hash表
?Redis的字典使用哈希表作為底層實現(xiàn)，一個哈希表（dictht）里面可以有多個哈希表節(jié)點（dictEntry ），而每個哈希表節(jié)點（dictEntry ）就保存了字典中的一個鍵值對。
Redis字典所使用的哈希表由dict.h/dictht結(jié)構(gòu)定義：
Redis字典所使用的哈希表由dict.h/dictht結(jié)構(gòu)定義：
typedef struct dictht {
// 哈希表節(jié)點組成的數(shù)組
dictEntry **table; //
// 哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計算索引值 總是等于size-1
unsigned long sizemask;
// 該哈希表已有節(jié)點的數(shù)量（非null節(jié)點）
unsigned long used;
} dictht;
哈希表節(jié)點使用dictEntry結(jié)構(gòu)表示，每個dictEntry結(jié)構(gòu)都保存著一個鍵值對：
typedef struct dictEntry {
// 鍵
void *key;
// 值
union{
void *val;
uint64_tu64;
int64_ts64;
} v;
// 指向下個哈希表節(jié)點，形成鏈表 （hash 沖突，鏈地址法）
struct dictEntry *next;
} dictEntry;
3.2 字典結(jié)構(gòu)
字典，是基于 hash 表的結(jié)構(gòu)上，再次進行的一層封裝
Redis中的字典由dict.h/dict結(jié)構(gòu)表示：
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表數(shù)組，包含兩個 dictht
dictht ht[2];
// rehash索引當(dāng)rehash不在進行時，值為-1
int rehashidx;
} dict;
type屬性是一個指向dictType結(jié)構(gòu)的指針，每個dictType結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對的函數(shù)，Redis會為用途不同的字典設(shè)置不同的類型特定函數(shù)。
·而privdata屬性則保存了需要傳給那些類型特定函數(shù)的可選參數(shù)。
typedef struct dictType {
// 計算哈希值的函數(shù)
unsigned int (*hashFunction)(const void *key);
// 復(fù)制鍵的函數(shù)
void *(*keyDup)(void *privdata, const void *key);
// 復(fù)制值的函數(shù)
void *(*valDup)(void *privdata, const void *obj);
// 對比鍵的函數(shù)
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 銷毀鍵的函數(shù)
void (*keyDestructor)(void *privdata, void *key);
- ht屬性是一個包含兩個哈希表的數(shù)組，數(shù)組中的每個項都是一個dictht哈希表，一般情況下，字典只使用ht[0]哈希表，ht[1]哈希表只會在對ht[0]哈希表進行rehash時使用。
- 除了ht[1]之外，另一個和rehash有關(guān)的屬性就是rehashidx，它記錄了rehash目前的進度，如果目前沒有在進行rehash，那么它的值為-1。
3.3?哈希算法
當(dāng)要將一個新的鍵值對添加到字典里面時，程序需要先根據(jù)鍵值對的鍵計算出哈希值和索引值，然后再根據(jù)索引值，將包含新鍵值對的哈希表節(jié)點放到哈希表數(shù)組的指定索引上面
- 計算哈希值的函數(shù) ：int hashValue = unsigned int (*hashFunction)(const void *key);
- 獲取最終的hash 值 ：?hashValue & ?ht[x].sizemask。
3.3.1 rehash
隨著操作的不斷執(zhí)行，哈希表保存的鍵值對會逐漸地增多或者減少，為了讓哈希表的負(fù)載因子（load factor）維持在一個合理的范圍之內(nèi)，當(dāng)哈希表保存的鍵值對數(shù)量太多或者太少時，程序需要對哈希表的大小進行相應(yīng)的擴展或者收縮。 擴展和收縮哈希表的工作可以通過執(zhí)行rehash（重新散列）操作來完成，Redis對字典的哈希表執(zhí)行rehash的步驟如下：
- 為字典的dict.ht[1]哈希表分配空間 ·如果執(zhí)行的是擴展操作，那么ht[1]的大小為第一個大于等于ht[0].used*2的2 n（2的n次方冪）； ? ? ? ht0 中 used = 10；為ht1分配的大小是 10*2 = 20？2的4次方是 16， 2的 5次方是 32. 32 是第一個大于 20的并且是 2 的 n次冪，所以 ht1的空間分配大小為 32。 如果執(zhí)行的是收縮操作，那么ht[1]的大小為第一個大于等于ht[0].used的2 n。 ? ? ?ht0 中 used = 10，那么 2的 4次方是 16， 16是第一個大于10的并且未 2的 n次冪的數(shù)字，所以此時 ht1的空間分配大小為 16.
- 將保存在ht[0]中的所有鍵值對rehash到ht[1]上面。 dictTyppe里邊的第一個函數(shù)結(jié)果 & sizemask （如果是擴展，sizemask = 31； 如果是收縮，sizemask = 15）
- 當(dāng)ht[0]包含的所有鍵值對都遷移到了ht[1]之后（ht[0]變?yōu)榭毡恚?，釋放ht[0]，將ht[1]設(shè)置為ht[0]，并在ht[1]新創(chuàng)建一個空白哈希表，為下一次rehash做準(zhǔn)備。
3.3.2 rehash的觸發(fā)時機
當(dāng)以下條件中的任意一個被滿足時，程序會自動開始對哈希表執(zhí)行擴展操作：
- 服務(wù)器目前沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于1。 比如，我的hash表 size是 8， 現(xiàn)在有10個used（有hash沖突，肯定有鏈表結(jié)構(gòu)），此時負(fù)載因子是 10 /8=1.25 > 1 。并且沒有bgsvae和 reWaof，此時觸發(fā) 擴展 rehash。
- 服務(wù)器目前正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子大于等于5。 比如 我的hash表 size是 8， 現(xiàn)在有10個used（有hash沖突，肯定有鏈表結(jié)構(gòu)），此時負(fù)載因子是 10 /8=1.25 > 1 ，這時候，由于有 bg和 bgre，所以不能觸發(fā)。 但是隨著時間的推移，我的 used 變成了 80， 此時負(fù)載因子是 80/8=10. 及時現(xiàn)在有bg和rebg，還是可以觸發(fā) rehash
3.3.3?漸進式rehash
-
擴展或收縮哈希表需要將ht[0]里面的所有鍵值對rehash到ht[1]里面，但是，這個rehash動作并不是一次性、集中式地完成的，而是分多次、漸進式地完成的。
- 這樣做的原因在于，如果哈希表里保存的鍵值對數(shù)量不是三四個，而是四百萬、四千萬甚至四億個鍵值對，那么要一次性將這些鍵值對全部rehash到ht[1]的話，龐大的計算量可能會導(dǎo)致服務(wù)器在一段時間內(nèi)停止服務(wù)。因此，為了避免rehash對服務(wù)器性能造成影響，服務(wù)器不是一次性將ht[0]里面的所有鍵值對全部rehash到ht[1]，而是分多次、漸進式地將ht[0]里面的鍵值對慢慢地rehash到ht[1]。
哈希表漸進式rehash的詳細(xì)步驟：文章來源：http://www.zghlxwxcb.cn/news/detail-405521.html
- 為ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表。
- 在字典中維持一個索引計數(shù)器變量rehashidx，并將它的值設(shè)置為0，表示rehash工作正式開始。 在rehash進行期間，每次對字典執(zhí)行添加、刪除、查找或者更新操作時，程序除了執(zhí)行指定的操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]，當(dāng)rehash工作完成之后，程序?qū)ehashidx屬性的值增一。每遷移一個 keyvalue，就需要在 rehashidx 上自增 1. 如果有10萬個值，我們 rehashidx會從0自增到 10萬結(jié)束。
- 隨著字典操作的不斷執(zhí)行，最終在某個時間點上，ht[0]的所有鍵值對都會被rehash至ht[1]，這時程序?qū)ehashidx屬性的值設(shè)為-1，表示rehash操作已完成。包括之前所說的 ，ht1成為了 ht0，再重新創(chuàng)建一個空的 ht1備用。
4.跳躍表
- 跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達(dá)到快速訪問節(jié)點的目的。跳躍表支持平均O（logN）、最壞O（N）復(fù)雜度的節(jié)點查找，還可以通過順序性操作來批量處理節(jié)點。
- Redis使用跳躍表作為有序集合鍵的底層實現(xiàn)之一，如果一個有序集合包含的元素數(shù)量比較多，又或者有序集合中元素的成員（member）是比較長的字符串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現(xiàn)。 和鏈表、字典等數(shù)據(jù)結(jié)構(gòu)被廣泛地應(yīng)用在Redis內(nèi)部不同，Redis只在兩個地方用到了跳躍表，一個是實現(xiàn)有序集合鍵，另一個是在集群節(jié)點中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)，除此之外，跳躍表在Redis里面沒有其他用途。
- Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結(jié)構(gòu)定義，其中zskiplistNode結(jié)構(gòu)用于表示跳躍表節(jié)點，而zskiplist結(jié)構(gòu)則用于保存跳躍表節(jié)點的相關(guān)信息。
4.1 跳躍表-zskiplistNode?
- 跳躍表節(jié)點的level數(shù)組可以包含多個元素，每個元素都包含一個指向其他節(jié)點的指針，程序可以通過這些層來加快訪問其他節(jié)點的速度，一般來說，層的數(shù)量越多，訪問其他節(jié)點的速度就越快。每次創(chuàng)建一個新跳躍表節(jié)點的時候，隨機生成一個介于1和32之間的值作為level數(shù)組的大小，這個大小就是層的“高度”
- 每個層都有一個指向表尾方向的前進指針（level[i].forward屬性），用于從表頭向表尾方向訪問節(jié)點。
- 節(jié)點的后退指針（backward屬性）用于從表尾向表頭方向訪問節(jié)點：跟可以一次跳過多個節(jié)點的前進指針不同，因為每個節(jié)點只有一個后退指針，所以每次只能后退至前一個節(jié)點。
typedef struct zskiplistNode {
// 層
struct zskiplistLevel {
// 前進指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
// 后退指針
struct zskiplistNode *backward;
// 分值（例：你的賬號排名）
double score;
// 成員對象 （例： 你的游戲賬號）
robj *obj;
} zskiplistNode;
4.2?跳躍表 - zskiplist
- header和tail指針分別指向跳躍表的表頭和表尾節(jié)點，通過這兩個指針，程序定位表頭節(jié)點和表尾節(jié)點的復(fù)雜度為O（1）。
- 通過使用length屬性來記錄節(jié)點的數(shù)量，程序可以在O（1）復(fù)雜度內(nèi)返回跳躍表的長度。 level屬性則用于在O（1）復(fù)雜度內(nèi)獲取跳躍表中層高最大的那個節(jié)點的層數(shù)量
typedef struct zskiplist {
//
表頭節(jié)點和表尾節(jié)點
structz skiplistNode *header, *tail;
//
表中節(jié)點的數(shù)量
unsigned long length;
//
表中層數(shù)最大的節(jié)點的層數(shù)
int level;
} zskiplist;
5.壓縮列表
- 壓縮列表（ziplist）是列表和哈希的底層實現(xiàn)之一。當(dāng)一個列表鍵只包含少量列表項，并且每個列表項要么就是小整數(shù)值，要么就是長度比較短的字符串，那么Redis就會使用壓縮列表來做列表鍵的底層實現(xiàn)。
- 壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)。一個壓縮列表可以包含任意多個節(jié)點（entry），每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值
文章來源地址http://www.zghlxwxcb.cn/news/detail-405521.html
到了這里，關(guān)于redis 底層數(shù)據(jù)結(jié)構(gòu)詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
