二、鏈表

鏈表的聲明與實(shí)現(xiàn)在/src/adlist.h、/src/adlist.c中

十年的高碑店網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整高碑店建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)公司從事“高碑店網(wǎng)站設(shè)計”,“高碑店網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實(shí)執(zhí)行。

//雙向鏈表
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

//每個鏈表使用一個list結(jié)構(gòu)來表示，這個結(jié)構(gòu)帶有表頭節(jié)點(diǎn)指針、表尾節(jié)點(diǎn)指針，以及鏈表長度等信息
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

通過為鏈表設(shè)置不同的類型特定函數(shù)，Redis的鏈表可以用來保存各種不同類型的值

三、字典

字典的聲明與實(shí)現(xiàn)在src/dict.h、src/dict.c。字典是redis的底層基礎(chǔ)，對數(shù)據(jù)庫的增刪改查也是構(gòu)建在對字典的操作之上的

在源碼注釋中，字典叫哈希表（hash table)，實(shí)現(xiàn)了insert/del/replace/find/get-random-element 這些操作，使用鏈?zhǔn)椒ㄌ幚砉_突

重要結(jié)構(gòu)體定義：

• 哈希表節(jié)點(diǎn)實(shí)體

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* 同一個籃子的下一個Entry */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
} dictEntry;

• 類型方法接口

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(dict *d, const void *key);
    void *(*valDup)(dict *d, const void *obj);
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    void (*keyDestructor)(dict *d, void *key);
    void (*valDestructor)(dict *d, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Allow a dictEntry to carry extra caller-defined metadata.  The
     * extra memory is initialized to 0 when a dictEntry is allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;

• 哈希表結(jié)構(gòu)實(shí)現(xiàn)

struct dict {
    //dictType 包含了一系列的用于操作特定類型鍵值對的函數(shù)，Redis會為用途不同的字典設(shè)置不同de
    dictType *type;
    //dictEntry結(jié)構(gòu)保存著一個鍵值對。通常只使用ht_table[0],只有在對ht_table[0]進(jìn)行rehash時，才使用ht_table[1]
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    //rehashidx 記錄rehash的進(jìn)度，沒有進(jìn)行rehash時為-1,另外，負(fù)載因子設(shè)定為1.618，在server.h中定義
    long rehashidx;
    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* size的指數(shù) (size = 1<<exp) */
};

四、跳表

跳表是一種有序數(shù)據(jù)結(jié)構(gòu)，通過在每個節(jié)點(diǎn)中維持多個指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的，在大部分情況下，跳表的效率可以和平衡樹相媲美，并且實(shí)現(xiàn)更為簡單

Redis使用跳表作為有序集合鍵的底層實(shí)現(xiàn)之一

因還未在源碼找到跳表實(shí)現(xiàn)，故先跳過

五、整數(shù)集合（intset）

intset是redis用來保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)，可以保存類型為int16_t、int32_t、int64_t的整數(shù)值，并且保證集合中不會出現(xiàn)重復(fù)元素

該數(shù)據(jù)結(jié)構(gòu)在intset.h中定義

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

升級

當(dāng)我們要將一個新元素添加到整數(shù)集合里面，并且新元素的類型比整數(shù)集合現(xiàn)有所有元素的類型都要長時，intset需要先進(jìn)行升級(upgrade)，然后才能將新元素添加到intset里面，升級分為三步驟：

1. 根據(jù)新元素類型，擴(kuò)展intset底層數(shù)組的空間大小，并為新元素分配空間。
2. 將底層數(shù)組現(xiàn)有的所有元素轉(zhuǎn)換成與新元素相同的類型，將轉(zhuǎn)換后的元素放在正確的位置上，并且在放置元素時，維持有序
3. 將新元素添加到底層數(shù)組

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);    //當(dāng)前編碼
    uint8_t newenc = _intsetValueEncoding(value);   //新元素編碼
    int length = intrev32ifbe(is->length);   //intrev32ifbe()是一個宏，只有在目標(biāo)主機(jī)是大端序的時候會轉(zhuǎn)換為小端序
    int prepend = value < 0 ? 1 : 0;             //判斷元素位置

    /* 修改intset編碼并重新分配內(nèi)存 */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);     

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));   //秒啊，如果prepend為1，前面就會空出來位置放新元素，否則后面空出來

    /* 因為引發(fā)升級的新元素總是比該intset的所有元素長度都大，所以要么會放在最開頭，要么放在最末尾 */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

壓縮列表(ziplist)

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

本文名稱：Redis學(xué)習(xí) -- 常用數(shù)據(jù)結(jié)構(gòu)
當(dāng)前路徑：http://chinadenli.net/article24/dsoipce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、虛擬主機(jī)、網(wǎng)站收錄、網(wǎng)站導(dǎo)航、網(wǎng)站策劃、手機(jī)網(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)