redis中使用的數(shù)據(jù)結(jié)構(gòu)有:

• dict 字典,就是個哈希表,實現(xiàn)和HashMap類似,不做闡述;不同的是在哈希表resize()的時候是分步執(zhí)行的,后續(xù)篇幅再說明。

• sds 很多項目都對自己的字符串進(jìn)行了封裝,作用類似于leveldb的slice。

• linkedlist 雙端鏈表，迭代器的實現(xiàn)是通過鏈表的pre和next實現(xiàn)的，是個BidirctionalIterator。代碼中只實現(xiàn)了ForwardIterator的功能。

• zipmap 已不再使用了

• inset 一個緊致的有序整型數(shù)組。

• ziplist 也是一個鏈表，但是它的內(nèi)存是連續(xù)的，在數(shù)據(jù)量小的時候使用，增長到一定的大小會轉(zhuǎn)化成list或者skiplist

• skiplist 跳躍表，實現(xiàn)在t_zset.c中

本文只闡述inset，ziplist，skiplist三種數(shù)據(jù)結(jié)構(gòu)。

1.ziplist

直接借用代碼注釋上ziplist的存儲結(jié)構(gòu)：

/*
area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL

• zlbytes 記錄了整個ziplist占用的內(nèi)存大??；
• zltail 記錄尾節(jié)點(diǎn)的相對于ziplist實例指針的偏移量；
• zllen 是整個list的節(jié)點(diǎn)數(shù)量的無符號數(shù)，占2個字節(jié)，可以最大表示2**16-1，實際使用保留了0xffff ffff ,即大于等于這個數(shù)的時候，已經(jīng)不能通過此值來取得節(jié)點(diǎn)的數(shù)量了；
• zlend 固定為0xff。
• entry 的結(jié)構(gòu)并不是代碼中給的結(jié)構(gòu)體zlentry。而是如下結(jié)構(gòu):

size              1/5 bytes      1/2/5 bytes    ?   
            +---------------+---------------+-------+
component   | pre_entry_len | cur_entry_len | value |
            +---------------+---------------+-------+

這是個變長的結(jié)構(gòu)，pre節(jié)點(diǎn)小于254則pre_entry_len占用1字節(jié)，否則5字節(jié),為什么不是255字節(jié)呢？255會和zlend產(chǎn)生沖突；cur_entry_len中包含了編碼信息（以字符串編碼還是數(shù)字，數(shù)字編碼能減少內(nèi)存長度)和本節(jié)點(diǎn)的長度信息,數(shù)字格式編碼固定占用1字節(jié)；字符串格式編碼數(shù)據(jù)小于127字節(jié)占1字節(jié)，小于0x3fff 占用2字節(jié)，否則5個字節(jié)。

因此ziplist有如下特點(diǎn):

• 內(nèi)存連續(xù)，數(shù)據(jù)緊湊。
• 查找效率o(n)
• 雙端查詢，可前后遍歷，類似于nodelist.

了解了數(shù)據(jù)結(jié)構(gòu)，思考下如何對其增加一個節(jié)點(diǎn)p，p的大小為sp。

• 1.ziplist長度發(fā)生變化，zlbytes要增加entry的內(nèi)存大?。?/li>
• 2.zltail也要做相應(yīng)改變，如果插入的是尾節(jié)點(diǎn)，則zltail等于ziplist到新節(jié)點(diǎn)p的距離，否則是原值加上新節(jié)點(diǎn)p的長度。
• 3.內(nèi)存大小發(fā)生改變，需要realloc個更大的內(nèi)存。
• 4.對于在新節(jié)點(diǎn)以后的節(jié)點(diǎn)，后移sp個單位。接下來要更新p以后的節(jié)點(diǎn)內(nèi)容:
• 4.1如果p的前一個節(jié)點(diǎn)的長度和p節(jié)點(diǎn)的長度一樣長，那么皆大歡喜。只需要更新p節(jié)點(diǎn)后一個節(jié)點(diǎn)的pre_entry_len值；
• 4.2如果比p節(jié)點(diǎn)的長度大(5字節(jié)對1字節(jié))，也ok，存下來，浪費(fèi)4個字節(jié)內(nèi)存。
• 4.3如果比p節(jié)點(diǎn)的長度小(1字節(jié)對5字節(jié))，意味著p以后的節(jié)點(diǎn)長度會發(fā)生變化，增加4個字節(jié)來存儲p的長度，zltail和ziplist也要同時加4;同時由于p->next節(jié)點(diǎn)長度發(fā)生變化，p->next->next也要去做一次判斷，需要重復(fù)步驟4，直到不滿足4.3的情況為止。

經(jīng)過以上步驟，就可以大概還原redis中的代碼實現(xiàn)了，也可以看出來ziplist的增刪代價是很大的，改變一個節(jié)點(diǎn)的復(fù)雜度最差是（n^2);一個節(jié)點(diǎn)改動，可能牽一發(fā)而動全身，所以ziplist是不適合大數(shù)據(jù)量的存儲的。

2.inset

inset 實際是一個整數(shù)數(shù)組，結(jié)構(gòu)如下:

typedef struct intset {
    
    uint32_t encoding;

    uint32_t length;

    int8_t contents[];

} intset;

其中encoding是編碼方式，有16位，32位，64位三種取值；length是inset集合中保存的元素個數(shù)，contents為保存的數(shù)據(jù)。下面是inset的特點(diǎn)和實現(xiàn)方式.

• 1.初始化的inset是16位編碼的，如果inset里面只保存了16位的數(shù)字，那么這個編碼方式將保持不變。

• 2.inset是有序不重復(fù)的，從小到大排列，每次插入/刪除會觸發(fā)inset的大小調(diào)整,length+1。

• 3.如果插入了比當(dāng)前編碼范圍更大的數(shù)字，會觸發(fā)intsetUpgradeAndAdd()，下面以16位-> 32位擴(kuò)展為例。

• 3.1 重新調(diào)整contents大小，大小為原(size+1)*2，更新encoding的值為INTSET_ENC_INT32;

• 3.2 新數(shù)字肯定是位于數(shù)組開頭或者結(jié)尾，如果是在結(jié)尾，將原數(shù)組的每個數(shù)從原位置pos移到pos2的位置，否則是(pos+1)2；

• 3.3 插入新的數(shù)據(jù)，intsetUpgradeAndAdd()過程結(jié)束

• 4.刪除不改變inset的編碼方式，即如果原inset為32位，刪光了inset里的16位不能表示的數(shù)字以后，inset也不會恢復(fù)到16位，代價太大，即intsetUpgradeAndAdd()的過程是不可逆的。

• 5.在inset中查找一個數(shù)采用二分查找。

根據(jù)這些特點(diǎn)，寫出inset的實現(xiàn)，想必不難，inset的特點(diǎn)是在存儲的數(shù)據(jù)為小值的時候，占用的內(nèi)存較小，但是只要插入了一個64位的數(shù)據(jù)，那么inset就沒有優(yōu)勢了，插入和刪除的時間復(fù)雜度都是o(n)，因此不適合做大數(shù)量的存儲。

3.skiplist

跳表是一個特殊的有序鏈表，盜一張網(wǎng)圖吧。

跳表結(jié)構(gòu)

結(jié)構(gòu)如下

typedef struct zskiplist {

    // 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
    struct zskiplistNode *header, *tail;

    // 表中節(jié)點(diǎn)的數(shù)量
    unsigned long length;

    // 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
    int level;

} zskiplist;

節(jié)點(diǎn)的結(jié)構(gòu)

typedef struct zskiplistNode {

    // 成員對象
    robj *obj;

    // 分值
    double score;

    // 后退指針
    struct zskiplistNode *backward;

    // 層
    struct zskiplistLevel {

        // 前進(jìn)指針
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

簡述下跳表的特點(diǎn)

• 跳表是一個排序鏈表，redis中以score的大小做排序，增刪改查的效率均是o(logn)，由于其實現(xiàn)更易于理解和實現(xiàn)而被廣泛使用。
• 跳表是不穩(wěn)定的，即同樣是創(chuàng)建一個跳表，插入若干相同的值，內(nèi)部的數(shù)據(jù)結(jié)構(gòu)可能是不一致的。
• 每個節(jié)點(diǎn)的大小不固定，不固定的原因是節(jié)點(diǎn)的擁有的forward指針個數(shù)不定，這個數(shù)值是在節(jié)點(diǎn)創(chuàng)建的時候隨機(jī)選取的一個正整數(shù)，redis實現(xiàn)默認(rèn)最大層數(shù)是32。
• redis中的跳表增加了一個指向前節(jié)點(diǎn)的backward來往前遍歷;一個span，用于計算forward節(jié)點(diǎn)和本節(jié)點(diǎn)中間的跨度，以方便zcount等命令來計算范圍內(nèi)score的數(shù)量。

如何插入一個數(shù)據(jù)?redis排序順序是從頭到尾，按照score從小到大。如果要增加一個值，首先需要確定插入后的順序，假設(shè)跳表為skl ，新節(jié)點(diǎn)為n。

• 1. 找到每一層比新節(jié)點(diǎn)score小，而且距離最近的節(jié)點(diǎn)，保存為update[]。
• 2. 隨機(jī)產(chǎn)生新節(jié)點(diǎn)的層高，對每一層的forward節(jié)點(diǎn)復(fù)制，令n->level[i]->forward = update[i]->level[i]->forward，給新節(jié)點(diǎn)的所有forward指針賦值。令update[i]->forward = n使新節(jié)點(diǎn)和其所有前置節(jié)點(diǎn)關(guān)聯(lián);實際上和雙向鏈表操作類似。

如何查找一個節(jié)點(diǎn)p?

• 場景1.根據(jù)score范圍查找內(nèi)容，對應(yīng)zrange命令。查找左界和右界，中間的范圍及所求。左界和右界算法類似，從head的頂層forward節(jié)點(diǎn)開始，如果比p的score小，那么讓head = forward 繼續(xù)此步驟.如果等于score那么返回。如果小于那么代表需要找的左界在head和forward之間，跳到下一層重復(fù)此步驟。

• 場景2.根據(jù)內(nèi)容查找score，對應(yīng)zscore命令。redis不查找skiplist，而是額外使用了個hash表來達(dá)到o(1)的效率。

迭代器如何設(shè)計?

• 可知n->level[0]->forward的步長是1，循環(huán)forward可以遍歷整個跳表。
  推薦跳表的leveldb版實現(xiàn)。
  綜上，redis的數(shù)據(jù)結(jié)構(gòu)分析告一段落。