目錄
1，string類型
2，list類型
3，hash類型
dictEntry
dictht
dict
4，集合類型
skiplist與平衡樹、哈希表的比較
redis可以存儲五種資料結構：String（字元串）、List（清單）、Set（集合）、Hash（哈希）、Zset（有序集合）。del、type、rename等指令是通用的，另外，注意一點，這些結構都是一個key-資料結構的方式存儲。即為所述：
Redis對象由redisObject結構體表示：
typedef struct redisObject {
unsigned type:4; // 對象的類型，包括
unsigned encoding:4; // 底部為了節省空間，一種type的資料，可以采用不同的存儲方式
unsigned lru:REDIS_LRU_BITS;
int refcount; // 引用計數
void *ptr;
} robj;
注意上面說的主要是redis3.2，最新的redis5版本基本一緻，但是有些檔案找不到，可能有變更。
1，string類型
最大512M，String類型通過 int、SDS(simple dynamic string)作為結構存儲，int用來存放整型資料，sds存放位元組/字元串和浮點型資料。
在redis的源碼中【sds.h】中看到sds的結構如下:
typedef char *sds;
redis3.2分支引入了五種sdshdr類型，目的是為了滿足不同長度字元串可以使用不同大小的Header，進而節省記憶體，每次在建立一個sds時根據sds的實際長度判斷應該選擇什麼類型的sdshdr，不同類型的sdshdr占用的記憶體空間不同。這樣細分一下可以省去很多不必要的記憶體開銷，下面是3.2的sdshdr定義，在5.0.7版本也是一樣的：
typedef char *sds;
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 8表示字元串最大長度是2^8，長度為255 {
uint8_t len; 表示目前sds的長度（機關是位元組）
uint8_t alloc; 表示已為sds配置設定的記憶體空間大小（機關是位元組）
unsigned char flags; 用一個位元組表示目前sdshdr的類型，因為有sdshdr有五種類型，是以至少需要用3位來表示
char buf[]; sds的實際存放位置
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};
sds圖示：
string類型資料結構可用于：使用者郵箱、圖檔等内容。
操作小結：
127.0.0.1:6379> set a man
OK
127.0.0.1:6379> get a
"man"
127.0.0.1:6379> del a
(integer) 1
127.0.0.1:6379> get a
(nil)
2，list類型
清單采用雙向連結清單實作，是以在兩端添加比較快，時間複雜度為O(1)。
redis3.2之前，List類型的value對象内部以linkedlist或者ziplist來實作, 當list的元素個數和單個元素的長度比較小的時候，Redis會采用ziplist（壓縮清單）來實作來減少記憶體占用。否則就會采用linkedlist（雙向連結清單）結構。redis3.2之後，采用的一種叫quicklist的資料結構來存儲list，清單的底層都由quicklist實作。
這兩種存儲方式都有優缺點，雙向連結清單在連結清單兩端進行push和pop操作，在插入節點上複雜度比較低，但是記憶體開銷比較大； ziplist存儲在一段連續的記憶體上，是以存儲效率很高，但是插入和删除都需要頻繁申請和釋放記憶體；
quicklist仍然是一個雙向連結清單，隻是清單的每個節點都是一個ziplist，其實就是linkedlist和ziplist的結合，quicklist中每個節點ziplist都能夠存儲多個資料元素，在源碼中的檔案為【quicklist.c】，在源碼第一行中有解釋為：Adoubly linked list of ziplists意思為一個由ziplist組成的雙向連結清單；
基本操作，lpush、rpush、lpop、rpop、lrange；lrange list-key 0 -1 表示取出全部。
quicklist：
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
int fill : 16;
unsigned int compress : 16;
} quicklist;
quicklist的Node：
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;
unsigned int sz;
unsigned int count : 16;
unsigned int encoding : 2;
unsigned int container : 2;
unsigned int recompress : 1;
unsigned int attempted_compress : 1;
unsigned int extra : 10;
} quicklistNode;
ziplist的總體布局如下：
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
list的存儲如下圖所示：
使用場景：略
操作小節：
127.0.0.1:6379> lpush a 2
(integer) 1
127.0.0.1:6379> lpush a 3
(integer) 2
127.0.0.1:6379> rpush a 1
(integer) 3
127.0.0.1:6379> lrange a 0 -1
1) "3"
2) "2"
3) "1"
127.0.0.1:6379> lindex a 1
"2"
127.0.0.1:6379> lpop a
"3"
127.0.0.1:6379> rpop a
"1"
127.0.0.1:6379> lrange a 0 -1
1) "2"
3，hash類型
hash類型概念上就是map，實作通過hashtable或者ziplist，資料量小的時候用ziplist，資料量大的時候用hashtable，那麼多小才會用ziplist？來看一看源碼：
這一段代碼用來判斷是否要把ziplist轉換成真是的hash，注意隻檢查字元編碼對象
void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
int i;
if (o->encoding != OBJ_ENCODING_ZIPLIST) return;
如果o的編碼不是OBJ_ENCODING_ZIPLIST就不處理
for (i = start; i <= end; i++) {
if (sdsEncodedObject(argv[i]) &&
sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
{
hashTypeConvert(o, OBJ_ENCODING_HT);
break;
}
}
}
轉換還有一段代碼：
#define HASH_SET_TAKE_FIELD (1<<0)
#define HASH_SET_TAKE_VALUE (1<<1)
#define HASH_SET_COPY 0
int hashTypeSet(robj *o, sds field, sds value, int flags) {
int update = 0;
if (o->encoding == OBJ_ENCODING_ZIPLIST) {
unsigned char *zl, *fptr, *vptr;
zl = o->ptr;
fptr = ziplistIndex(zl, ZIPLIST_HEAD);
if (fptr != NULL) {
fptr = ziplistFind(fptr, (unsigned char*)field, sdslen(field), 1);
if (fptr != NULL) {
vptr = ziplistNext(zl, fptr);
serverAssert(vptr != NULL);
update = 1;
zl = ziplistDelete(zl, &vptr);
zl = ziplistInsert(zl, vptr, (unsigned char*)value,
sdslen(value));
}
}
if (!update) {
zl = ziplistPush(zl, (unsigned char*)field, sdslen(field),
ZIPLIST_TAIL);
zl = ziplistPush(zl, (unsigned char*)value, sdslen(value),
ZIPLIST_TAIL);
}
o->ptr = zl;
if (hashTypeLength(o) > server.hash_max_ziplist_entries)
hashTypeConvert(o, OBJ_ENCODING_HT);
} else if (o->encoding == OBJ_ENCODING_HT) {
dictEntry *de = dictFind(o->ptr,field);
if (de) {
sdsfree(dictGetVal(de));
if (flags & HASH_SET_TAKE_VALUE) {
dictGetVal(de) = value;
value = NULL;
} else {
dictGetVal(de) = sdsdup(value);
}
update = 1;
} else {
sds f,v;
if (flags & HASH_SET_TAKE_FIELD) {
f = field;
field = NULL;
} else {
f = sdsdup(field);
}
if (flags & HASH_SET_TAKE_VALUE) {
v = value;
value = NULL;
} else {
v = sdsdup(value);
}
dictAdd(o->ptr,f,v);
}
} else {
serverPanic("Unknown hash encoding");
}
if (flags & HASH_SET_TAKE_FIELD && field) sdsfree(field);
if (flags & HASH_SET_TAKE_VALUE && value) sdsfree(value);
return update;
}
是以有兩種情況會執行，一種是在檢查值字元串長度是否大于64，另一個是檢查所包含的entries大小，是否多于512，即和server.hash_max_ziplist_value、server.hash_max_ziplist_entries這兩個值比較，這兩個值可以在redis.conf中設定：
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
ziplist如前所示，針對hashTable的實作，有三個結構，在dict.h中：
dictEntry
typedef struct dictEntry {
void *key;
union { //因為value有多種類型，是以value用了union來存儲
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; 下一個節點的位址，用來處理碰撞，配置設定到同一索引的元素，形成一個連結清單，記不記得HashMap裡面，也是有一個entry，同樣的概念
} dictEntry;
dictht
實作一個hash表會使用一個buckets存放dictEntry的位址，一般情況下通過hash(key)%len得到的值就是buckets的索引，這個值決定了我們要将此dictEntry節點放入buckets的哪個索引裡,這個buckets實際上就是我們說的hash表。dict.h的dictht結構中table存放的就是buckets的位址
typedef struct dictht {
dictEntry **table; buckets的位址
unsigned long size; buckets的大小，總保持為2^n
unsigned long sizemask; 掩碼，用來計算hash值對應的buckets索引
unsigned long used; 目前dictht有多少個dictEntry節點
} dictht;
dict
dictht是hash的核心，但是隻有一個dictht是不夠的，比如rehash、周遊hash等操作，是以redis定義了一個dict用于支援字典的各種操作，當dictht需要擴容/縮容時，用來管理dictht的遷移，源碼如下：
typedef struct dict {
dictType *type; dictType裡存放的是一堆工具函數的函數指針
void *privdata; 儲存type中的某些函數需要作為參數的資料
dictht ht[2]; 兩個dictht，ht[0]平時用，ht[1] rehash時用（比如擴容時就要rehash）
long rehashidx;
目前rehash到buckets的哪個索引，-1時表示非rehash狀态
unsigned long iterators;
安全疊代器的計數。
} dict;
比如我們要講一個資料存儲到hash表中，那麼會先通過murmur計算key對應的hashcode，然後根據hashcode取模得到bucket的位置，再插入到連結清單中。map簡圖：
使用小結：
127.0.0.1:6379> hset has tfield value
(integer) 1
127.0.0.1:6379> hset has tfield1 value1
(integer) 1
127.0.0.1:6379> hgetall has
1) "tfield"
2) "value"
3) "tfield1"
4) "value1"
127.0.0.1:6379> hget has tfield
"value"
127.0.0.1:6379> hdel has tfield
(integer) 1
127.0.0.1:6379> hgetall has
1) "tfield1"
2) "value1"
4，集合類型
集合set，無序且不重複。集合類型的常用操作是向集合中加入或删除元素、判斷某個元素是否存在。由于集合類型在redis内部是使用的值為空的散清單(hash table)，是以這些操作的時間複雜度都是O(1)。
Set在的底層資料結構以intset或者hashtable來存儲。當set中隻包含整數型的元素時，采用intset來存儲，否則，采用hashtable存儲，但是對于set來說，該hashtable的value值用于為NULL。通過key來存儲元素。圖則類似于hash，隻不過entry裡值用到了field。
使用小結：
127.0.0.1:6379> sadd b b
(integer) 1
127.0.0.1:6379> sadd b c
(integer) 1
127.0.0.1:6379> sadd c c
(integer) 1
127.0.0.1:6379> SMEMBERS b
1) "c"
2) "b"
127.0.0.1:6379> SISMEMBER b c
(integer) 1
127.0.0.1:6379> SREM b c
(integer) 1
127.0.0.1:6379> SMEMBERS b
1) "b"
5，有序集合
有序集合實際上就是給每個元素關聯了一個分數，分數可以相同。有序集合對象的編碼可以是ziplist或者skiplist。同時滿足以下條件時使用ziplist編碼：
元素數量小于128個
所有member的長度都小于64位元組
以上兩個條件的上限值可通過zset-max-ziplist-entries和zset-max-ziplist-value來修改。ziplist編碼的有序集合使用緊挨在一起的壓縮清單節點來儲存，第一個節點儲存member，第二個儲存score。ziplist内的集合元素按score從小到大排序，score較小的排在表頭位置。
skiplist編碼的有序集合底層是一個命名為zset的結構體，而一個zset結構同時包含一個字典和一個跳躍表。跳躍表按score從小到大儲存所有集合元素。而字典則儲存着從member到score的映射，這樣就可以用O(1)的複雜度來查找member對應的score值。雖然同時使用兩種結構，但它們會通過指針來共享相同元素的member和score，是以不會浪費額外的記憶體。
那麼什麼是skiplist？
跳表(skip List)是一種随機化的資料結構，基于并聯的連結清單，實作簡單，插入、删除、查找的複雜度均為O(logN)。簡單說來跳表也是連結清單的一種，隻不過它在連結清單的基礎上增加了跳躍功能，正是這個跳躍的功能，使得在查找元素時，跳表能夠提供O(logN)的時間複雜度。
在這樣一個連結清單中，如果我們要查找某個資料，那麼需要從頭開始逐個進行比較，直到找到包含資料的那個節點，或者找到第一個比給定資料大的節點為止（沒找到）。也就是說，時間複雜度為O(n)。同樣，當我們要插入新資料的時候，也要經曆同樣的查找過程，進而确定插入位置。
假如我們每相鄰兩個節點增加一個指針，讓指針指向下下個節點，如下圖：
這樣所有新增加的指針連成了一個新的連結清單，但它包含的節點個數隻有原來的一半（上圖中是7, 19, 26）。現在當我們想查找資料的時候，可以先沿着這個新連結清單進行查找。當碰到比待查資料大的節點時，再回到原來的連結清單中進行查找。比如，我們想查找23，查找的路徑是沿着下圖中标紅的指針所指向的方向進行的：
-
- 23首先和7比較，再和19比較，比它們都大，繼續向後比較。
- 但23和26比較的時候，比26要小，是以回到下面的連結清單（原連結清單），與22比較。
- 23比22要大，沿下面的指針繼續向後和26比較。23比26小，說明待查資料23在原連結清單中不存在，而且它的插入位置應該在22和26之間。
在這個查找過程中，由于新增加的指針，我們不再需要與連結清單中每個節點逐個進行比較了。需要比較的節點數大概隻有原來的一半。
利用同樣的方式，我們可以在上層新産生的連結清單上，繼續為每相鄰的兩個節點增加一個指針，進而産生第三層連結清單。如下圖：
在這個新的三層連結清單結構上，如果我們還是查找23，那麼沿着最上層連結清單首先要比較的是19，發現23比19大，接下來我們就知道隻需要到19的後面去繼續查找，進而一下子跳過了19前面的所有節點。可以想象，當連結清單足夠長的時候，這種多層連結清單的查找方式能讓我們跳過很多下層節點，大大加快查找的速度。
skiplist正是受這種多層連結清單的想法的啟發而設計出來的。實際上，按照上面生成連結清單的方式，上面每一層連結清單的節點個數，是下面一層的節點個數的一半，這樣查找過程就非常類似于一個二分查找，使得查找的時間複雜度可以降低到O(log n)。但是，這種方法在插入資料的時候有很大的問題。新插入一個節點之後，就會打亂上下相鄰兩層連結清單上節點個數嚴格的2:1的對應關系。如果要維持這種對應關系，就必須把新插入的節點後面的所有節點（也包括新插入的節點）重新進行調整，這會讓時間複雜度重新蛻化成O(n)。删除資料也有同樣的問題。
skiplist為了避免這一問題，它不要求上下相鄰兩層連結清單之間的節點個數有嚴格的對應關系，而是為每個節點随機出一個層數(level)。比如，一個節點随機出的層數是3，那麼就把它鍊入到第1層到第3層這三層連結清單中。為了表達清楚，下圖展示了如何通過一步步的插入操作進而形成一個skiplist的過程：
從上面skiplist的建立和插入過程可以看出，每一個節點的層數（level）是随機出來的，而且新插入一個節點不會影響其它節點的層數。是以，插入操作隻需要修改插入節點前後的指針，而不需要對很多節點都進行調整。這就降低了插入操作的複雜度。實際上，這是skiplist的一個很重要的特性，這讓它在插入性能上明顯優于平衡樹的方案。這在後面我們還會提到。
skiplist，指的就是除了最下面第1層連結清單之外，它會産生若幹層稀疏的連結清單，這些連結清單裡面的指針故意跳過了一些節點（而且越高層的連結清單跳過的節點越多）。這就使得我們在查找資料的時候能夠先在高層的連結清單中進行查找，然後逐層降低，最終降到第1層連結清單來精确地确定資料位置。在這個過程中，我們跳過了一些節點，進而也就加快了查找速度。
剛剛建立的這個skiplist總共包含4層連結清單，現在假設我們在它裡面依然查找23，下圖給出了查找路徑：
需要注意的是，前面示範的各個節點的插入過程，實際上在插入之前也要先經曆一個類似的查找過程，在确定插入位置後，再完成插入操作。
實際應用中的skiplist每個節點應該包含key和value兩部分。前面的描述中我們沒有具體區分key和value，但實際上清單中是按照key(score)進行排序的，查找過程也是根據key在比較。
執行插入操作時計算随機數的過程，是一個很關鍵的過程，它對skiplist的統計特性有着很重要的影響。這并不是一個普通的服從均勻分布的随機數，它的計算過程如下：
- 首先，每個節點肯定都有第1層指針（每個節點都在第1層連結清單裡）。
- 如果一個節點有第i層(i>=1)指針（即節點已經在第1層到第i層連結清單中），那麼它有第(i+1)層指針的機率為p。
- 節點最大的層數不允許超過一個最大值，記為MaxLevel。
skiplist與平衡樹、哈希表的比較
skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。是以，在哈希表上隻能做單個key的查找，不适宜做範圍查找。所謂範圍查找，指的是查找那些大小在指定的兩個值之間的所有節點。
在做範圍查找的時候，平衡樹比skiplist操作要複雜。在平衡樹上，我們找到指定範圍的小值之後，還需要以中序周遊的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這裡的中序周遊并不容易實作。而在skiplist上進行範圍查找就非常簡單，隻需要在找到小值之後，對第1層連結清單進行若幹步的周遊就可以實作。
平衡樹的插入和删除操作可能引發子樹的調整，邏輯複雜，而skiplist的插入和删除隻需要修改相鄰節點的指針，操作簡單又快速。
從記憶體占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節點包含2個指針（分别指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis裡的實作一樣，取p=1/4，那麼平均每個節點包含1.33個指針，比平衡樹更有優勢。
查找單個key，skiplist和平衡樹的時間複雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突機率的前提下，查找時間複雜度接近O(1)，性能更高一些。是以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實作的。
從算法實作難度上來比較，skiplist比平衡樹要簡單得多。
使用小結：
127.0.0.1:6379> zadd zset-key 728 members1
(integer) 1
127.0.0.1:6379> zadd zset-key 733 members2
(integer) 1
127.0.0.1:6379> zadd zset-key 299 members3
(integer) 1
127.0.0.1:6379> ZRANGE zset-key 0 -1
1) "members3"
2) "members1"
3) "members2"
127.0.0.1:6379> ZRANGEBYSCORE zset-key 0 500
1) "members3"
127.0.0.1:6379> ZREM zset-key members3
(integer) 1
參考：https://www.jianshu.com/p/cc379427ef9d
參考：https://blog.csdn.net/qq_35433716/article/details/82177585
參考：《Redis實戰》