2018-1-3 by Atlas

---

1. SDS

• 描述

redis底層是C語言編寫，而redis沒有直接使用C語言的字符串表示，是自己構(gòu)建了一種名為簡單動態(tài)字符串的抽象類型，即SDS（simple dynamic string）。
redis數(shù)據(jù)庫里，包含字符串值的鍵值對在底層都是SDS實(shí)現(xiàn)的，可以說SDS是基石。
AOF模塊中的AOF緩沖區(qū)，以及客戶端狀態(tài)中的輸入緩沖區(qū)，都是SDS實(shí)現(xiàn)的。

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站設(shè)計(jì)、做網(wǎng)站、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)嵩明,十多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792

• 定義

struct sdshdr {
        // 記錄buf數(shù)組中已使用字節(jié)的數(shù)量
        // 等于SDS所保存字符串的長度
        int len;
        // 記錄buf數(shù)組中未使用字節(jié)的數(shù)量
        int free;
        // 字節(jié)數(shù)組，用于保存字符串
        char buf[];
}

• 結(jié)構(gòu)

• free屬性值為0，表示這個SDS沒有未使用空間。
• len屬性值為5，表示這個SDS保存了一個5字節(jié)長的字符串。
• buf屬性是char類型數(shù)組，數(shù)組前5個字節(jié)分別保存'R'、'e'、'd'、'i'、's'5個字符，最后1個字節(jié)保存了空字符'\0'。
• buf長度=len+free+1。

• 策略

• SDS遵循C字符串以空字符'\0'結(jié)尾的慣例好處是可以直接重用一部分C字符串函數(shù)。
• 較C字符串SDS在len屬性中記錄了SDS本身的長度，從而獲取SDS長度復(fù)雜度僅為O（1）。
• 較C字符串SDS讀取字符不是通過結(jié)尾空字符'\0'而是len屬性因此更安全，使得redis不僅可以保存文本數(shù)據(jù)，還可以保存任意格式的二進(jìn)制數(shù)據(jù)。
• 較C字符串SDS的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能，檢查free屬性是否滿足修改需求，如果不滿足，自動拓展空間然后再執(zhí)行修改操作，如果空間足夠，則無需執(zhí)行內(nèi)存重分配。
• 空間分配策略優(yōu)化策略空間預(yù)分配和惰性空間釋放減少了內(nèi)存重分配次數(shù)。
• 空間預(yù)分配公式：
  如果修改SDS后，SDS的len將小于1MB，那么分配和len屬性同樣大小的free空間；
  如果修改SDS后，SDS的len將大于等于1MB，那么分配1MB的free空間。
• 惰性空間釋放策略即SDS空間修改操作釋放多出來的空間保留，避免縮短字符串的內(nèi)存重分配和提供將來有可能的字符串增長。
• SDS提供了釋放SDS空間的API，所以不必?fù)?dān)心惰性空間釋放會造成內(nèi)存浪費(fèi)。

2. LIST

• 描述

鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的節(jié)點(diǎn)訪問方式，并且可以通過增刪節(jié)點(diǎn)來靈活地調(diào)整鏈表的長度。
列表鍵的底層實(shí)現(xiàn)之一就是鏈表。
發(fā)布與訂閱、慢查詢、監(jiān)視器等功能也用到了鏈表，redis服務(wù)器本身還使用鏈表來保存多個客戶端的狀態(tài)信息，以及使用鏈表來構(gòu)建客戶端輸出緩沖區(qū)。

• 定義

typeof struct listNode {
        // 前置節(jié)點(diǎn)
        struct listNode *prev;
        // 后置節(jié)點(diǎn)
        struct listNode *next;
        // 節(jié)點(diǎn)的值
        void *value;
} listNode;

typeof struct list {
        // 表頭節(jié)點(diǎn)
        listNode *head;
        // 表尾節(jié)點(diǎn)
        listNode *tail;
        // 鏈表包含的節(jié)點(diǎn)數(shù)量
        unsigned long len;
        // 節(jié)點(diǎn)值復(fù)制函數(shù)
        void *(*dup)(void *ptr);
        // 節(jié)點(diǎn)值釋放函數(shù)
        void (*free)(void *ptr);
        // 節(jié)點(diǎn)值對比函數(shù)
        int (*match)(void *ptr,void *key);
} list;

• 結(jié)構(gòu)

• 策略

雙端：鏈表節(jié)點(diǎn)帶有prev和next指針，獲取某個節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的復(fù)雜度都是O（1）。
無環(huán)：表頭節(jié)點(diǎn)的prev指針和表尾節(jié)點(diǎn)的next指針都指向NULL，對鏈表的訪問以NULL為終點(diǎn)。
帶鏈表長度計(jì)數(shù)器：list結(jié)構(gòu)的len屬性使得獲取鏈表節(jié)點(diǎn)數(shù)量的復(fù)雜度是O（1）。
多態(tài)：鏈表節(jié)點(diǎn)使用void *指針來保存節(jié)點(diǎn)值，并且可以通過list結(jié)構(gòu)的dup、free、match屬性為節(jié)點(diǎn)設(shè)置類型特定函數(shù)，所以鏈表可以保存各種不同類型的值。

3. HASH

• 描述

字典是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。
字典中的鍵都是獨(dú)一無二的。
redis數(shù)據(jù)庫就是使用字典來作為底層實(shí)現(xiàn)的。
字典還是哈希鍵的底層實(shí)現(xiàn)之一。

• 定義

typeof struct dictEntry {
        // 鍵
        void *key;
        // 值
        union{
                void *val;
                unit64_t u64;
                int64_t s64;
        } v;
        // 下個節(jié)點(diǎn)
        struct dictEntry *next;
} dictEntry;

typeof struct dictht {
        // 哈希表數(shù)組
        dictEntry **table;
        // 哈希表大小
        unsigned long size;
        // 哈希表大小掩碼，用于計(jì)算索引值
        // 總是等于size-1
        unsigned long sizemask;
        // 哈希表已有節(jié)點(diǎn)的數(shù)量
        unsigned long used;
} dictht;

typeof struct dictType {
        // 計(jì)算哈希值的函數(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);
        // 銷毀值的函數(shù)
        void (*valDestructor)(void *privdata, void *val);
} dictType;

typeof struct dict {
        // 類型特定函數(shù)
        dictType *type;
        // 私有數(shù)據(jù)
        void *privadata;
        // 哈希表
        dictht ht[2];
        // rehash索引
        // 當(dāng)不在進(jìn)行rehash時，值為-1
        int trehashidx;
} dict;

• 結(jié)構(gòu)

• 策略

• ht屬性是包含兩個項(xiàng)的數(shù)組，一般情況下，字典只是用ht[0]，ht[1]只有rehash時使用。
• 哈希算法：
  hash = dict->type->hashFuncton(key);
  index = hash&dict->ht[x].sizemash;
• hash沖突的解決途徑是鏈接地址法。
• 與java數(shù)據(jù)結(jié)構(gòu)hashMap不同，是單鏈表，相同是，插入表頭位置，新插入的節(jié)點(diǎn)更偏向接下來被訪問。
• rehash操作：
  如果執(zhí)行拓展操作，那么ht[1]的大小為第一個大于等于ht[0].used*2的2的n次方冪；
  如果執(zhí)行收縮操作，那么ht[1]的大小為第一個大于等于ht[0].used的2的n次方冪。
• 哈希表負(fù)載因子公式：
  負(fù)載因子 = 哈希表已保存節(jié)點(diǎn)數(shù)量 / 哈希表大小
  load_factor = ht[0].used / ht[0].size
• 程序自動執(zhí)行哈希表拓展操作的條件：
  服務(wù)器目前沒有在執(zhí)行BGSAVE或BGREWRITEAOF命令，并且負(fù)載因子大于等于1。
  服務(wù)器目前正在執(zhí)行BGSAVE或BGREWRITEAOF命令，并且負(fù)載因子大于等于5。
• 程序自動執(zhí)行哈希表收縮操作的條件：
  哈希表的負(fù)載因子小于0.1。
• 哈希表分而治之漸進(jìn)式rehash步驟：
  1）為ht[1]分配空間，字典同時持有ht[0]和ht[1]。
  2）rehashidx設(shè)置為0，表示rehash開始。
  3）rehash進(jìn)行期間，每次對字典執(zhí)行刪除、查找或者更新操作時，會在兩個哈希表上進(jìn)行，程序除了執(zhí)行指定的操作外，還會順帶將ht[0]的鍵值對rehash到ht[1]，每次對字典執(zhí)行添加操作時，新添加的鍵值對一律保存到ht[1]而不在對ht[0]添加，當(dāng)rehash后，將rehashidx值增一。
  4）隨著字典操作的不斷進(jìn)行，最終某個時間點(diǎn)，ht[0]的所有鍵值對都會rehash到ht[1]，將rehashidx設(shè)為-1，表示rehash操作完成。
  5）釋放ht[0]，并將ht[1]設(shè)置為ht[0]，然后為ht[1]分配一個空白哈希表。

4. SKIPLIST

• 描述

跳躍表是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點(diǎn)中維持多個指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。
跳躍表支持平均O（logN）、最壞O（N）復(fù)雜度的節(jié)點(diǎn)查找，還可以通過順序性來批量處理節(jié)點(diǎn)。
大部分情況下，跳躍表的效率和平衡樹相媲美，并且實(shí)現(xiàn)較為簡單。
redis使用跳躍表一個地方是作為有序集合鍵的底層實(shí)現(xiàn)之一，另一個地方是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。

• 定義

typeof struct zskiplistNode {
        // 后退指針
        struct zskiplistNode *backward;
        // 分值
        double score;
        // 成員對象
        robj *obj;
        // 層
        struct zskiplistLevel {
                // 前進(jìn)指針
                struct zskiplistNode *forward;
                // 跨度
                unsigned int span;
        } level[];
} zskiplistNode;

typeof struct zskiplist {
        // 表頭節(jié)點(diǎn)，表尾節(jié)點(diǎn)
        struct skiplistNode *header,*tail;
        // 表中節(jié)點(diǎn)數(shù)量
        unsigned long length;
        // 表中大層數(shù)
        int level;
} zskiplist;

• 結(jié)構(gòu)

• 策略

header指向跳躍表的表頭節(jié)點(diǎn)。
tail指向跳躍表的表尾節(jié)點(diǎn)。
level記錄跳躍表內(nèi)表頭外層數(shù)大的節(jié)點(diǎn)的層數(shù)。
length記錄跳躍表內(nèi)表頭外節(jié)點(diǎn)的數(shù)量。
層：前進(jìn)指針用于訪問位于表尾方向的節(jié)點(diǎn)，而跨度則記錄前進(jìn)指針指向節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離。
后退指針指向位于當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)，從表尾向表頭遍歷時使用。
各個節(jié)點(diǎn)按各自所保存的分值從小到大排列。

5. INTSET

• 描述

整數(shù)集合是集合鍵的底層實(shí)現(xiàn)之一，當(dāng)一個集合只包含整數(shù)值元素，并且這個集合的元素?cái)?shù)量不多時，redis就會使用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)。
可以保存整數(shù)值類型有int16_t、int32_t、int64_t。

• 定義

typeof struct intset {
        // 編碼方式
        unit32_t encoding;
        // 集合包含的元素?cái)?shù)量
        unit32_t lenght;
        // 保存元素的數(shù)組
        int8_t contents[];
} intset;

• 結(jié)構(gòu)

INTSET_ENC_INT16表示整數(shù)集合的底層實(shí)現(xiàn)是int16_t類型的數(shù)組，集合保存的都是int16_t類型的整數(shù)值。
length屬性值為5表示包含五個元素。
contents數(shù)組按從小到大屬性保存集合的五個元素。
contents數(shù)組的大小等于16 * 5 = 80 位。

INTSET_ENC_INT64表示整數(shù)集合的底層實(shí)現(xiàn)是int64_t類型的數(shù)組，集合保存的都是int64_t類型的整數(shù)值。
length屬性值為4表示包含四個元素。
contents數(shù)組按從小到大屬性保存集合的四個元素。
contents數(shù)組的大小等于64 * 4 = 256 位。

• 策略

升級整數(shù)集合并添加新元素分三步：
1）根據(jù)新元素類型拓展整數(shù)集合底層數(shù)組的空間并為新元素分配空間。
2）將底層數(shù)組現(xiàn)有的所以元素都轉(zhuǎn)換成與新元素相同的類型，并將類型轉(zhuǎn)換后的元素放到正確的位上，需要維持底層數(shù)組的有序性質(zhì)不變。
3）將新元素添加到底層數(shù)組。

6. ZIPLIST

• 描述

壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。
當(dāng)一個列表鍵只包含少量列表項(xiàng)，并且每個列表項(xiàng)要么是小整數(shù)值，要么是短字符串，那么redis會使用壓縮列表來作為列表鍵的底層實(shí)現(xiàn)。
當(dāng)一個哈希鍵只包含少量鍵值對，并且每個鍵值對要么是小整數(shù)值，要么是短字符串，那么redis會使用壓縮列表來作為哈希鍵的底層實(shí)現(xiàn)。

• 定義

一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)?？梢园我舛鄠€節(jié)點(diǎn)，每個節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。

• 結(jié)構(gòu)

zlbytes記錄整個壓縮列表占用的內(nèi)存字節(jié)數(shù)。
zltail記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)，通過整個偏移量，程序無須遍歷整個壓縮列表就可以確定表尾節(jié)點(diǎn)的地址。
zllen記錄壓縮列表的節(jié)點(diǎn)數(shù)量。
entryX是壓縮列表的節(jié)點(diǎn)。
zlend用于標(biāo)記壓縮列表的末端。

• 策略

壓縮列表從表尾節(jié)點(diǎn)倒敘遍歷，首先指針通過zltail偏移量指向表尾節(jié)點(diǎn)，然后通過指向節(jié)點(diǎn)記錄的前一個節(jié)點(diǎn)的長度依次向前遍歷訪問整個壓縮列表。

以上就是redis基本數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)。

參考文獻(xiàn)：《redis設(shè)計(jì)與實(shí)現(xiàn)》

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文標(biāo)題：redis筆記-數(shù)據(jù)結(jié)構(gòu)篇-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://www.rwnh.cn/article40/jhjho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、網(wǎng)站營銷、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、網(wǎng)站導(dǎo)航、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)