Redis主要數據結構：簡單動態字元串(SDS)、雙端鏈表、字典、跳躍表、整數集合、壓縮列表和快速列表； 一、簡單動態字元串(SDS)： Redis沒有直接使用C語言中的傳統的位元組數組保存字元串，而是自行構建了簡單動態字元串(SDS)，C字元串只是作為簡單動態字元串(SDS)的字面量，用於在無需對字 ...
Redis主要數據結構：簡單動態字元串(SDS)、雙端鏈表、字典、跳躍表、整數集合、壓縮列表和快速列表；
一、簡單動態字元串(SDS)：
Redis沒有直接使用C語言中的傳統的位元組數組保存字元串，而是自行構建了簡單動態字元串(SDS)，C字元串只是作為簡單動態字元串(SDS)的字面量，用於在無需對字元串值進行修改的地方。
結構：
struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* 表示字元串真正的長度，不包含空終止字元*/ uint8_t alloc; /* 表示字元串的最大容量，不包含Header和最後的空終止字元 */ unsigned char flags; /*表示header的類型*/ char buf[]; };
sds結構一共有五種Header定義，其目的是為了滿足不同長度的字元串可以使用不同大小的Header，從而節省記憶體。
通過使用SDS代替C字元串的優點：
- 將獲取字元串長度所需的複雜度降低到O(1)；
- 杜絕緩衝區溢出的情況；
當SDS需要修改時，首先會檢查SDS的空間是否滿足修改所需的要求，如果不滿足會自動進行空間擴容。sds規定：如果擴展後的字元串總長度小於1M則新字元串長度為擴展後的兩倍；如果大於1M，則新的總長度為擴展後的總長度加上1M；這樣做的目的是減少Redis記憶體分配的次數，同時儘量節省空間。
- 減少修改字元串是帶來的記憶體重新分配次數；
//如果程式執行的是增長字元串的操作，比如拼接操作(append)，那麼在執行這個操作之前，程式需要先通過記憶體重分配來擴展底層數組的空間大小一一如果忘了這一步就會產生緩衝區溢出。
//如果程式執行的是縮短字元串的操作，比如截斷操作(trim)，那麼在執行這個操作之後，程式需要通過記憶體重分配來釋放字元串不再使用的那部分空間一一如果忘了這一步就會產生記憶體泄漏。
//SDS通過未使用空間， SDS實現了空間預分配(同上擴容)和惰性空間釋放(同回收sds空餘空間的函數)兩種優化策略。
- 二進位安全。
C 字元串裡面不能包含空字元，否則最先被程式讀人的空字元將被誤認為是字元串結尾，這些使得C 字元串只能保存文本數據。雖然資料庫一般用於保存文本數據，但使用資料庫來保存像圖片、音頻、視頻、壓縮文件二進位數據的場景也不少見，因此，為了確保Redis 可以適用於各種不同的使用場景， SDS 的API 都是二進位安全的(binary-safe)，所有SDS API 都會以處理二進位的方式來處理SDS 存放在buf數組裡的數據，程式不會對其中的數據做任何限制、過濾、或者假設，數據在寫入時是什麼樣的，它被讀取時就是什麼樣。
主要操作：
sds釋放函數sdsfree、sds動態調整函數sdsMakeRoomFor、回收sds空餘空間的函數sdsRemoveFreeSpace(實際上，就是重新分配一塊記憶體，將原有數據拷貝到新記憶體上，並釋放原有空間，程式並不立即使用記憶體重分配來回收縮短後多出來的位元組，而是使用free 屬性將這些位元組的數量記錄起來，並等待將來使用)、sds連接操作函數sdscatlen。
https://blog.csdn.net/terence1212/article/details/53542072
https://blog.csdn.net/DERRANTCM/article/details/78898416
二、雙端鏈表
因為Redis 使用的C 語言並沒有內置這種數據結構，所以Redis 構建了自己的鏈表實現。
鏈表在Redis 中的應用非常廣泛，比如列表鍵的底層實現之一就是鏈表。除了鏈表鍵之外，發佈與訂閱、慢查詢、監視器等功能也用到了鏈表， Redis 伺服器本身還使用鏈表來保存多個客戶端的狀態信息，以及使用鏈表來構建客戶端輸出緩衝區( output buffer)。
結構：
Redis為雙端鏈表的每一個節點定義瞭如下的結構體：
typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode;
與一般的雙端鏈表無異，定義了鏈表節點的結構體之後，下麵就定義鏈表的結構體，用來方便管理鏈表節點，其結構體定義如下：
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;
Redis為sdlist定義了一個迭代器結構，其能正序和逆序的訪問list結構：
typedef struct listIter { listNode *next; int direction; } listIter;
Redis 的鏈表實現的特性可以總結如下：
- 雙端：鏈表節點帶有prev 和next 指針，獲取某個節點的前置節點和後置節點的複雜度都是O(1)。
- 無環：表頭節點的prev 指針和表尾節點的next 指針都指向NULL ，對鏈表的訪問以NULL 為終點。
- 帶表頭指針和表尾指針：通過list 結構的head 指針和tail 指針，程式獲取鏈表的表頭節點和表尾節點的複雜度為O(1)。
- 帶鏈表長度計數器：程式使用list 結構的len 屬性來對list 持有的鏈表節點進行計數，程式獲取鏈表中節點數量的複雜度為O(1)。
- 多態：鏈表節點使用void*指針來保存節點值，並且可以通過list 結構的dup、free、match 三個屬性為節點值設置類型特定函數，所以鏈表可以用於保存各種不同類型的值。
https://blog.csdn.net/DERRANTCM/article/details/78908070
三、字典
字典是一種用於保存鍵值對(key-value pair)的抽象數據結構。在字典中，一個鍵(key)可以和一個值(value)進行關聯（或者說將鍵映射為值），這些關聯的鍵和值就稱為鍵值對。因此Redis 構建了自己的字典實現。
Redis 的資料庫就是使用字典來作為底層實現的，對資料庫的增、刪、查、改操作也是構建在對字典的操作之上的。字典還是哈希鍵的底層實現之一，當一個哈希鍵包含的鍵值對比較多，又或者鍵值對中的元素都是比較長的字元串時， Redis 就會使用字典作為哈希鍵的底層實現。
結構：
typedef struct dict { dictType *type; // 類型特定函數 void *privdata; // 私有數據 dictht ht[2]; // 哈希表 long rehashidx; //rehash 索引,當 rehash 不在進行時，值為 -1 unsigned long iterators; // 目前正在運行的安全迭代器的數量 } dict;
type 屬性和privdata 屬性是針對不同類型的鍵值對，為創建多態字典而設置的：
type 屬性是一個指向dietType 結構的指針，每個dietType 結構保存了一簇用於操作特定類型鍵值對的函數， Redis 會為用途不同的字典設置不同的類型特定函數。
而privdata 屬性則保存了需要傳給那些類型特定函數的可選參數。
typedef struct dictType { uint64_t (*hashFunction)(const void *key); // 計算哈希值的函數 void *(*keyDup)(void *privdata, const void *key); // 複製鍵的函數 void *(*valDup)(void *privdata, const void *obj); // 複製值的函數 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 對比鍵的函數 void (*keyDestructor)(void *privdata, void *key); // 銷毀鍵的函數 void (*valDestructor)(void *privdata, void *obj); // 銷毀值的函數 } dictType;
ht 屬性是一個包含兩個項的數組，數組中的每個項都是一個dictht 哈希表，一般情況下，字典只使用ht[0]哈希表， ht[l]哈希表只會在對ht[0]哈希表進行rehash 時使用。除了ht[1]之外，另一個和rehash 有關的屬性就是rehashidx ，它記錄了rehash 目前的進度，如果目前沒有在進行rehash ，那麼它的值為-1。圖4-3 展示了一個普通狀態下（沒有進行rehash)的字典。
typedef struct dictht { dictEntry **table;// 哈希表數組 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩蜀，用於計算索引值, 總是等於size-1 unsigned long used; // 該哈希表已有節點的數量 } dictht;
table 屬性是一個數組，數組中的每個元素都是一個指向dict.h/dictEntry 結構的指針，每個dictEntry 結構保存著一個鍵值對。
typedef struct dictEntry { void *key; // 鍵 union {// 值 void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; // 指向下個哈希表節點，形成鏈表 } dictEntry;
key 屬性保存著鍵值對中的鍵，而v 屬性則保存著鍵值對中的值，其中鍵值對的值可以是一個指針，或者是一個uint64_t 整數，又或者是一個int64_t 整數。
next 屬性是指向另一個哈希表節點的指針，這個指針可以將多個哈希值相同的鍵值對連接在一次，以此來解決鍵衝突(collision)的問題。
（與HashMap一樣的hash方法）
主要操作：
- 哈希演算法：
當要將一個新的鍵值對添加到字典裡面時，程式需要先根據鍵值對的鍵計算出哈希值和索引值，然後再根據索引值，將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。Redis 計算哈希值和索引值的方法如下：
- ＃使用字典設置的哈希函數，計算鍵key 的哈希值
- hash= dict->type->hashFunction(key);
- ＃使用哈希表的sizemask 屬性和哈希值，計算出索引值
- ＃根據情況不同， ht[x]可以是ht[0]或者ht[1]
- index = hash 品dict->ht[x].sizemask;
- 解決鍵衝突：
當有兩個或以上數量的鍵被分配到了哈希表數組的同一個索引上面時，我們稱這些鍵發生了衝突(collision)。redis的哈希表使用鏈地址法(separate chaining)來解決鍵衝突，每個哈希表節點都有一個next 指針，多個哈希表節點可以用next 指針構成一個單向鏈表，被分配到同一個索引上的多個節點可以用這個單向鏈表連接起來，這就解決了鍵衝突的問題。
- rehash
隨著操作的不斷執行，哈希表保存的鍵值對會逐漸地增多或者減少，為了讓哈希表的負載因數(load factor)維持在一個合理的範圍之內，當哈希表保存的鍵值對數量太多或者太少時，程式需要對哈希表的大小進行相應的擴展或者收縮。
- 擴展和收縮哈希表的工作可以通過執行rehash（重新散列）操作來完成， Redis對字典的哈希表執行rehash的步驟如下：
- 為字典的ht[1]哈希表分配空間，這個哈希表的空間大小取決於要執行的操作，以及ht[0]當前包含的鍵值對數量（也即是ht[0].used 屬性的值）：
- 如果執行的是擴展操作，那麼ht[1]的大小為第一個大於等於ht[0] .used*2的2^n(2 的n 次方幕）；
- 如果執行的是收縮操作，那麼ht[1]的大小為第一個大於等於ht[0] .used 的2^n
- 將保存在ht[0]中的所有鍵值對rehash 到ht[1]上面： rehash指的是重新計算鍵的哈希值和索引值，然後將鍵值對放置到ht[l]哈希表的指定位置上。
- 當ht[0]包含的所有鍵值對都遷移到了ht[1]之後(ht [0]變為空表），釋放ht[0]，將ht [1]設置為ht[0] ，併在ht[1]新創建一個空白哈希表，為下一次rehash做準備。
- 哈希表的擴展與收縮
當以下條件中的任意一個被滿足時，程式會自動開始對哈希表執行擴展操作：
- 伺服器目前沒有在執行BGSAVE 命令或者BGREWRITEAOF 命令，並且哈希表的負載因於大於等於1。
- 伺服器目前正在執行BGSAVE 命令或者BGREWRITEAOF 命令，並且哈希表的負載因數大於等於5。
其中哈希表的負載因數可以通過公式：
＃負載因數＝哈希表巳保存節點數量/哈希表大小load factor= ht[0].used / ht[0].size
- 漸進式rehash
擴展或收縮哈希表需要將ht[0]裡面的所有鍵值對rehash到ht[l]裡面，但是，這個rehash 動作並不是一次性、集中式地完成的，而是分多次、漸進式地完成的。這樣做的原因在於為了避免rehash對伺服器性能造成影響。以下是哈希表漸進式rehash 的詳細步驟：
- 為ht [1]分配空間，讓字典同時持有ht[0]和ht[l]兩個哈希表。
- 在字典中維持一個索引計數器變數rehashidx ，並將它的值設置為0 ，表示rehash工作正式開始。
- 在rehash 進行期間，每次對字典執行添加、刪除、查找或者更新操作時，程式除了執行指定的操作以外，還會順帶將ht[0]哈希表在rehashidx 索引上的所有鍵值對rehash到ht[l]，當rehash工作完成之後，程式將rehashidx 屬性的值增1。
- 隨著字典操作的不斷執行，最終在某個時間點上，ht[0]的所有鍵值對都會被rehash 至ht[l]，這時程式將rehashidx 屬性的值設為-1，表示rehash 操作已完成。
漸進式rehash 的好處在於它採取分而治之的方式，將rehash 鍵值對所需的計算工作均攤到對字典的每個添加、刪除、查找和更新操作上，從而避免了集中式rehash 而帶來的龐大計算量。
- 漸進式rehash 執行期間的哈希表操作
字典的刪除(delete)、查找(find)、更新(update)等操作會在兩個哈希表上進行。新添加到字典的鍵值對一律會被保存到ht[l]裡面，而ht[0]則不再進行任何添加操作。
https://blog.csdn.net/DERRANTCM/article/details/78993135
四、跳躍表
跳躍表(skiplist)是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。
跳躍表支持平均O(logN)、最壞O(N)（的複雜度的節點查找，還可以通過順序性操作來批量處理節點。在大部分情況下，跳躍表的效率可以和平衡樹相媲美，並且因為跳躍表的實現比平衡樹要來得更為簡單，所以有不少程式都使用跳躍表來代替平衡樹。
Redis 使用跳躍表作為有序集合鍵的底層實現之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員(member)是比較長的字元串時， Redis 就會使用跳躍表作為有序集合鍵的底層實現。
Redis 只在兩個地方用到了跳躍表，一個是實現有序集合鍵，另一個是在集群節點中用作內部數據結構。
結構：
跳躍表數據結構 跳躍表的結構體定義在server.h文件中。其中包括跳躍表節點zskiplistNode和跳躍表zskiplist兩個結構體。
typedef struct zskiplistNode { sds ele; // 成員對象 double score; // 分值 struct zskiplistNode *backward; // 後向指針 struct zskiplistLevel {// 層 struct zskiplistNode *forward; // 前向指針 unsigned int span; // 跨度 } level[]; } zskiplistNode;
層(level)：節點中用Ll 、L2 、L3 等字樣標記節點的各個層， Ll 代表第一層， L2代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用於訪問位於表尾方向的其他節點，而跨度則記錄了前進指針所指向節點和當前節點的距離。跳躍表節點的level 數組可以包含多個元素，每個元素都包含一個指向其他節點的指針，程式可以通過這些層來加快訪問其他節點的速度，一般來說，層的數量越多，訪問其他節點的速度就越快。
每次創建一個新跳躍表節點的時候，程式都根據事次定律(power law，越大的數出現的概率越小）隨機生成一個介於1 和32 之間的值作為level 數組的大小，這個大小就是層的“高度”。
跨度：層的跨度(level [i] . span 屬性）用於記錄兩個節點之間的距離：
兩個節點之間的跨度越大，它們相距得就越遠。指向NULL 的所有前進指針的跨度都為0 ，因為它們沒有連向任何節點。
遍歷操作只使用前進指針就可以完成了，跨度實際上是用來計算排位(rank)的：在查找某個節點的過程中，將沿途訪問過的所有層的跨度累計起來，得到的結果就是目標節點在跳躍表中的排位。
多個跳躍表節點就可以組成一個跳躍表：
typedef struct zskiplist { struct zskiplistNode *header, *tail; // 跳躍表的表頭節點和表尾節點 unsigned long length; // 表中節點的數量 int level; // 表中層數最大的節點層數 } zskiplist;
通過使用length 屬性來記錄節點的數量，程式可以在0(1)複雜度內返回跳躍表的長度。level 屬性則用於在O(1)複雜度內獲取跳躍表中層高最大的那個節點的層數量。
跳躍表基本操作 Redis中關於跳躍表的相關操作函數定義在t_zset.c文件中：
跳躍表操作：
創建一個跳躍表
zskiplist *zslCreate(void) { int j; zskiplist *zsl; // 申請記憶體 zsl = zmalloc(sizeof(*zsl)); // 初始化跳躍表屬性 zsl->level = 1; zsl->length = 0; // 創建一個層數為32，分值為0，成員對象為NULL的表頭結點 zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); // 設定每層的forward指針指向NULL for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { zsl->header->level[j].forward = NULL; zsl->header->level[j].span = 0; } // 設定backward指向NULL zsl->header->backward = NULL; zsl->tail = NULL; return zsl; }
創建一個跳躍表節點：
zskiplistNode *zslCreateNode(int level, double score, sds ele) { // 申請記憶體 zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel)); // 設定分值 zn->score = score; // 設定成員對象 zn->ele = ele; return zn; }
插入節點：
往跳躍表中插入一個節點，必然會改變跳錶的長度，可能會改變其長度。而且對於插入位置處的前後節點的backward和forward指針均要改變。 插入節點的關鍵在找到在何處插入該節點，跳躍表是按照score分值進行排序的，其查找步驟大致是：從當前最高的level開始，向前查找，如果當前節點的score小於插入節點的score，繼續向前；反之，則降低一層繼續查找，直到第一層為止。此時，插入點就位於找到的節點之後。
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { // updata[]數組記錄每一層位於插入節點的前一個節點 zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; // rank[]記錄每一層位於插入節點的前一個節點的排名 unsigned int rank[ZSKIPLIST_MAXLEVEL]; int i, level; serverAssert(!isnan(score)); x = zsl->header; // 從最高層開始查找 for (i = zsl->level-1; i >= 0; i--) { // 存儲rank值是為了交叉快速地到達插入位置 rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; // 前向指針不為空，前置指針的分值小於score或當前向指針的分值等於空但成員對象不等於0的情況下，繼續向前查找 while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && sdscmp(x->level[i].forward->ele,ele) < 0))) { rank[i] += x->level[i].span; x = x->level[i].forward; } // 存儲當前層上位於插入節點的前一個節點 update[i] = x; } // 此處假設插入節點的成員對象不存在於當前跳躍表內，即不存在重覆的節點 // 隨機生成一個level值 level = zslRandomLevel(); if (level > zsl->level) { // 如果level大於當前存儲的最大level值 // 設定rank數組中大於原level層以上的值為0 // 同時設定update數組大於原level層以上的數據 for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } // 更新level值 zsl->level = level; } // 創建插入節點 x = zslCreateNode(level,score,ele); for (i = 0; i < level; i++) { // 針對跳躍表的每一層，改變其forward指針的指向 x->level[i].forward = update[i]->level[i].forward; update[i]->level[i].forward = x; // 更新插入節點的span值 x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); update[i]->level[i].span = (rank[0] - rank[i]) + 1; } // 更新高層的span值 for (i = level; i < zsl->level; i++) { update[i]->level[i].span++; } // 設定插入節點的backward指針 x->backward = (update[0] == zsl->header) ? NULL : update[0]; if (x->level[0].forward) x->level[0].forward->backward = x; else zsl->tail = x; zsl->length++; return x; }
跳躍表刪除：
Redis提供了三種跳躍表節點刪除操作。分別如下：
根據給定分值和成員來刪除節點，由zslDelete函數實現；
根據給定分值來刪除節點，由zslDeleteByScore函數實現；
根據給定排名來刪除節點，由zslDeleteByRank函數實現
上述三種操作的刪除節點部分都由zslDeleteNode函數完成。zslDeleteNode函數用於刪除某個節點，需要給定當前節點和每一層下當前節點的前一個節點。
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) { int i; for (i = 0; i < zsl->level; i++) { if (update[i]->level[i].forward == x) { // 如果x存在於該層，則需要修改前一個節點的前向指針 update[i]->level[i].span += x->level[i].span - 1; update[i]->level[i].forward = x->level[i].forward; } else { // 反之，則只需要將span-1 update[i]->level[i].span -= 1; } } // 修改backward指針，需要考慮x是否為尾節點 if (x->level[0].forward) { x->level[0].forward->backward = x->backward; } else { zsl->tail = x->backward; } while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL) zsl->level--; zsl->length--; }
獲取給定分值和成員的節點的排名：
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) { zskiplistNode *x; unsigned long rank = 0; int i; x = zsl->header; // 從最高層開始查詢 for (i = zsl->level-1; i >= 0; i--) { // 前向指針不為空，前置指針的分值小於score或當前向指針的分值等於空但成員對象不等於o的情況下，繼續向前查找 while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && sdscmp(x->level[i].forward->ele,ele) <= 0))) { rank += x->level[i].span; x = x->level[i].forward; } // 此時x可能是header，所以此處需要判斷一下 if (x->ele && sdscmp(x->ele,ele) == 0) { return rank; } } return 0; }
區間操作：
Redis提供了一些區間操作，用於獲取某段區間上的節點或者刪除某段區間上的所有節點等操作，這些操作大大提高了Redis的易用性：
- 獲取某個區間上第一個符合範圍的節點。zslFirstInRange；
- 獲取某個區間上最後一個符合範圍的節點。zslLastInRange；
- 刪除給定分值範圍內的所有元素。zslDeleteRangeByScore；
- 刪除給定排名區間內的所有節點。zslDeleteRangeByRank。
https://blog.csdn.net/DERRANTCM/article/details/78999143
https://blog.csdn.net/terence1212/article/details/53543799
五、整數集合
整數集合(intset)是Redis 用於保存整數值的集合抽象數據結構，它可以保存類型為int16_t 、int32_t 或者int64_t 的整數值，並且保證集合中不會出現重覆元素。
結構：
每個intset.h/intset 結構表示一個整數集合：
typedef struct intset { uint32_t encoding; // 編碼方式 uint32_t length; // 集合包含的元素數量 int8_t contents[];// 保存元素的數組 } intset;
操作：
- 升級
每當我們要將一個新元素添加到整數集合裡面，並且新元素的類型比整數集合現有所有元素的類型都要長時，整數集合需要先進行升級(upgrade)，然後才能將新元素添加到整數集合裡面。整數集合的升級策略有兩個好處，一個是提升整數集合的靈活性，另一個是儘可能地節約空間
升級整數集合併添加新元素共分為三步進行：
- 根據新元素的類型，擴展整數集合底層數組的空間大小，併為新元素分配空間。
- 將底層數組現有的所有元素都轉換成與新元素相同的類型，並將類型轉換後的元素放置到正確的位上，而且在放置元素的過程中，需要繼續維持底層數組的有序性質不變。
- 將新元素添加到底層數組裡面。
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { // 獲取當前編碼格式 uint8_t curenc = intrev32ifbe(is->encoding); // 獲取需要升級到的編碼格式 uint8_t newenc = _intsetValueEncoding(value); // 獲取原整數集中的整數個數 int length = intrev32ifbe(is->length); // 由於待添加的元素一定是大於或者小於整數集中所有元素，故此處需要判斷添加到新數據集的頭部或者尾部 // 如果value為正，則添加到新數據集的尾部；反之則添加到首部 int prepend = value < 0 ? 1 : 0; // 設定新的編碼格式 is->encoding = intrev32ifbe(newenc); // 對原數據集進行擴容 is = intsetResize(is,intrev32ifbe(is->length)+1); // 採用從後往前的重編碼順序，這樣就避免覆蓋數據了。 while(length--) // 將原數據集中的數據依次賦值到新數據集中 // _intsetGetEncoded(is,length,curenc)獲取數據集is的第length位上的數據，curenc為原數據集的編碼格式 // _intsetSet將數據集is的第length+prepend位上設定為上一函數返回的值 _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc)); // 將待添加的數據添加到首部或者尾部 if (prepend) _intsetSet(is,0,value); else _intsetSet(is,intrev32ifbe(is->length),value); // 修改新數據集的長度 is->length = intrev32ifbe(intrev32ifbe(is->length)+1); return is; }
- 降級：整數集合不支持降級操作，一旦對數組進行了升級，編碼就會一直保持升級後的狀態。
六、壓縮列表
當一個列表鍵只包含少量的列表項，並且每個列表項要麼就是小整數型或者是長度較短的字元串。常用來作為列表建和哈希鍵的底層實現。為了節約記憶體而開發。
zlbytes：4位元組，記錄整個壓縮列表占用記憶體的位元組數
zltail：4位元組，記錄壓縮列表尾部節點距離起始地址的偏移量
zllen：2位元組，記錄壓縮列表包含的節點數量
entry：不定，列表中的每個節點
zlend：1位元組，特殊值0xFF，標記壓縮列表的結束。
七、快速列表（quicklist）
quicklist結構意思為一個由ziplist組成的雙向鏈表，鏈表中的每一個節點都以壓縮列表ziplist的結構保存著數據，而ziplist有多個entry節點，保存著數據。相當與一個quicklist節點保存的是一片數據，而不再是一個數據。
- quicklist巨集觀上是一個雙向鏈表，因此，它具有一個雙向鏈表的有點，進行插入或刪除操作時非常方便，雖然複雜度為O(n)，但是不需要記憶體的複製，提高了效率，而且訪問兩端元素複雜度為O(1)。
- quicklist微觀上是一片片entry節點，每一片entry節點記憶體連續且順序存儲，可以通過二分查找以 log2(n) 的複雜度進行定位。
結構：
quicklist表頭結構：
typedef struct quicklist { //指向頭部(最左邊)quicklist節點的指針 quicklistNode *head; //指向尾部(最右邊)quicklist節點的指針 quicklistNode *tail; //ziplist中的entry節點計數器 unsigned long count; //quicklist的quicklistNode節點計數器 unsigned int len; //保存ziplist的大小，配置文件設定，占16bits int fill : 16; //保存壓縮程度值，配置文件設定，占16bits，0表示不壓縮 unsigned int compress : 16; } quicklist;
quicklist節點結構：
typedef struct quicklistNode { struct quicklistNode *prev; //前驅節點指針 struct quicklistNode *next; //後繼節點指針 //不設置壓縮數據參數recompress時指向一個ziplist結構 //設置壓縮數據參數recompress指向quicklistLZF結構 unsigned char *zl;
unsigned int sz; //壓縮列表ziplist的總長度 unsigned int count : 16; //ziplist中包的節點數，占16 bits長度 //表示是否採用了LZF壓縮演算法壓縮quicklist節點，1表示壓縮過，2表示沒壓縮，占2 bits長度 unsigned int encoding : 2; //表示一個quicklistNode節點是否採用ziplist結構保存數據，2表示壓縮了，1表示沒壓縮，預設是2，占2bits長度 unsigned int container : 2; //標記quicklist節點的ziplist之前是否被解壓縮過，占1bit長度 //如果recompress為1，則等待被再次壓縮 unsigned int recompress : 1; unsigned int attempted_compress : 1; /* 節點太小無法壓縮//測試時使用 */ unsigned int extra : 10; //額外擴展位，占10bits長度 } quicklistNode;
壓縮過的ziplist結構—quicklistLZF：
typedef struct quicklistLZF { //表示被LZF演算法壓縮後的ziplist的大小 unsigned int sz; /* LZF size in bytes*/ //保存壓縮後的ziplist的數組，柔性數組 char compressed[]; } quicklistLZF;
管理ziplist信息的結構quicklistEntry：
typedef struct quicklistEntry { const quicklist *quicklist; //指向所屬的quicklist的指針 quicklistNode *node; //指向所屬的quicklistNode節點的指針 unsigned char *zi; //指向當前ziplist結構的指針 unsigned char *value; //指向當前ziplist結構的字元串vlaue成員 long long longval; //指向當前ziplist結構的整數value成員 unsigned int sz; //保存當前ziplist結構的位元組數大小 int offset; //保存相對ziplist的偏移量 } quicklistEntry;
https://blog.csdn.net/terence1212/article/details/53770882
