五種數(shù)據(jù)類型

• string字符串
• hash 哈希
• list 列表
• set 無序集合
• zset 有序集合

string字符串類型實(shí)現(xiàn)

redis的字符串類型是由一種叫做簡單動(dòng)態(tài)字符串(SDS)的數(shù)據(jù)類型來實(shí)現(xiàn)

struct sdshdr {
  int len;          //buf中已占用空間的長度
  int free;        //buf中剩余空間的長度
  char buf[];    //數(shù)據(jù)空間
}

SDC和C語言字符串的區(qū)別：
1：SDS保存了字符串的長度烹卒，而C語言不保存，只能遍歷找到第一個(gè)\0的結(jié)束符才能確定字符串的長度
2：修改SDS贸宏，會(huì)檢查空間是否足夠丈探，不足會(huì)先擴(kuò)展空間妇拯，防止緩沖區(qū)溢出蛛芥，C字符串不會(huì)檢查
3：SDS的預(yù)分配空間機(jī)制商膊，可以減少為字符串重新分配空間的次數(shù)
備注：重新分配空間方式饶囚，小于1M的數(shù)據(jù) 翻倍+1帕翻，例如：13K+13K+1，如果大于1M萝风，每次多分配1M嘀掸，例如：10M+1M+1,如果字符串變短，并不會(huì)立即縮短规惰，而是采用惰性空間釋放睬塌，有專門的API可以釋放多余空間

hash哈希

hash結(jié)構(gòu)里其實(shí)是一個(gè)字典，有許多的鍵值對(duì)
redis的哈希表是一個(gè)dictht結(jié)構(gòu)體：

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

哈希表節(jié)點(diǎn)的結(jié)構(gòu)體如下：

typedef struct dictEntry{
  void *key;  //鍵
  union {      //不同鍵對(duì)飲的值得類型可能不同揩晴，使用union來處理這個(gè)問題
    void *val;
    uint64_tu64;
    int64_ts64;
  }
  struct dictEntry *next;
}

hash算法：
當(dāng)要將一個(gè)新的鍵值對(duì)添加到字典里面時(shí)， 程序需要先根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值贪磺， 然后再根據(jù)索引值硫兰， 將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組的指定索引上面。

# 使用字典設(shè)置的哈希函數(shù)寒锚，計(jì)算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 屬性和哈希值劫映，計(jì)算出索引值
# 根據(jù)情況不同违孝， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

hash沖突解決方式：鏈表法，后入的放到最前面
rehash：
鍵值數(shù)據(jù)量變動(dòng)時(shí)泳赋，時(shí)為了讓哈希表的負(fù)載因子（load factor）維持在一個(gè)合理的范圍之內(nèi)雌桑， 當(dāng)哈希表保存的鍵值對(duì)數(shù)量太多或者太少時(shí)， 程序需要對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮祖今。
如果是擴(kuò)充筹燕，新數(shù)組的空間大小為 大于2*used的2的n次方，比如：used=5,則去大于10的第一個(gè)2的n次方衅鹿，為16
如果是縮小撒踪，新數(shù)組的空間大小為第一個(gè)不大于used的2的n次方，比如：used=5,則新大小為4

list列表類型實(shí)現(xiàn)

redis的list列表是使用雙向鏈表來實(shí)現(xiàn)的
···
typedef struct listNode {
struct listNode * pre; //前置節(jié)點(diǎn)
struct listNode * next; //后置節(jié)點(diǎn)
void * value; //節(jié)點(diǎn)的值
}

typedef struct list {
listNode *head; //表頭節(jié)點(diǎn)
listNode tail; //表尾節(jié)點(diǎn)
unsigned long len; //鏈表所包含的節(jié)點(diǎn)數(shù)量
void (dup) (void ptr); //節(jié)點(diǎn)值賦值函數(shù) 這里有問題
void (free) (void ptr); //節(jié)點(diǎn)值釋放函數(shù)
int (match) (void *ptr, void *key) //節(jié)點(diǎn)值對(duì)比函數(shù)
}
···

zset有序集合

1：有序集合的底層實(shí)現(xiàn)之一是跳表大渤， 除此之外跳表它在 Redis 中沒有其他應(yīng)用制妄。
2：整數(shù)集合（intset）是集合鍵的底層實(shí)現(xiàn)之一： 當(dāng)一個(gè)集合只包含整數(shù)值元素， 并且這個(gè)集合的元素?cái)?shù)量不多時(shí)泵三， Redis 就會(huì)使用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)耕捞。
3：數(shù)據(jù)少是，使用ziplist(壓縮列表)烫幕，占用連續(xù)內(nèi)存俺抽，每項(xiàng)元素都是(數(shù)據(jù)+score)的方式連續(xù)存儲(chǔ)，按照score從小到大排序较曼。ziplist為了節(jié)省內(nèi)存磷斧，每個(gè)元素占用的空間可以不同，對(duì)于大數(shù)據(jù)(long long),就多用一些字節(jié)存儲(chǔ)捷犹，而對(duì)于小的數(shù)據(jù)(short)弛饭，就少用一些字節(jié)來存儲(chǔ)。因此查找的時(shí)候需要按順序遍歷萍歉。ziplist省內(nèi)存但是查找效率低侣颂。

set無序集合

無序集合可以用整數(shù)集合(intset)或者字典實(shí)現(xiàn)

Stream

Redis的5.0版本中，放出一個(gè)新的數(shù)據(jù)結(jié)構(gòu)Stream枪孩。其實(shí)也是一個(gè)隊(duì)列憔晒，沒一個(gè)不同的key對(duì)應(yīng)的是不同的隊(duì)列，沒個(gè)隊(duì)列的元素蔑舞，也就是消息拒担，都有一個(gè)msgid，并且需要保證msgid是嚴(yán)格遞增的斗幼。在Stream當(dāng)中澎蛛，消息是默認(rèn)持久化的，即便是Redis重啟蜕窿，也能夠讀取到信息谋逻。
Stream的多播呆馁，與其它隊(duì)列系統(tǒng)相似，對(duì)不同的消費(fèi)者毁兆，也有消費(fèi)者Group這樣的概念浙滤，不同的消費(fèi)組，可以消費(fèi)通一個(gè)消息气堕，對(duì)于不同的消費(fèi)組纺腊，都維護(hù)一個(gè)Idx下標(biāo)，表示這一個(gè)消費(fèi)群組費(fèi)到了哪里茎芭，每次進(jìn)行消費(fèi)揖膜，都會(huì)更新一下這個(gè)下標(biāo)，往后面一位進(jìn)行偏移梅桩。

其它

一壹粟、 跳躍表

跳躍表是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其它節(jié)點(diǎn)的指針宿百，從而大道快速訪問節(jié)點(diǎn)的目的趁仙，具有以下性質(zhì)：
1：有很多層結(jié)構(gòu)組成
2：每一層都是一個(gè)有序的鏈表，排列順序?yàn)橛筛叩降涂岩常贾辽侔瑑蓚€(gè)鏈表節(jié)點(diǎn)雀费，分別是前面的head節(jié)點(diǎn)和后面的nil節(jié)點(diǎn)
3：最底層的鏈表包含了所有的元素
4：如果一個(gè)元素出現(xiàn)在某一層的鏈表中，那么在該層之下的鏈表也全部都會(huì)出現(xiàn)
5：鏈表中的每個(gè)節(jié)點(diǎn)都包含兩個(gè)指針痊焊，一個(gè)指向同一層的下一個(gè)鏈表節(jié)點(diǎn)盏袄，另一個(gè)指向下一層的通一個(gè)鏈表節(jié)點(diǎn)

image.png

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

多個(gè)跳躍表節(jié)點(diǎn)構(gòu)成一個(gè)跳躍表

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;
}

跳表操作

1：搜索，從最高層的鏈表節(jié)點(diǎn)開始宋光，如果比當(dāng)前節(jié)點(diǎn)要大和比當(dāng)前層的下一個(gè)節(jié)點(diǎn)要小貌矿，那么則往下找炭菌，也及時(shí)和當(dāng)前層的下一層的節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)
2：插入罪佳，首先確定插入的層數(shù)，有一種方法是拋一個(gè)硬幣黑低，如果是正面就累加赘艳，直到遇到反面為止，最后記錄正面的次數(shù)作為插入的層數(shù)克握，當(dāng)確定插入的層數(shù)K后蕾管，則需要將新元素插入從底層到K層
3：刪除，在各個(gè)層中找到包含指定值得節(jié)點(diǎn)菩暗，然后將節(jié)點(diǎn)從鏈表中刪除即可掰曾，如果刪除以后只剩下頭尾兩個(gè)節(jié)點(diǎn)，則刪除這一層停团。

二旷坦、整數(shù)集合

整數(shù)集合是Redis用于保存整數(shù)值集合的抽象數(shù)據(jù)類型掏熬，它可以保存int16_t、int32_t秒梅、int64_t的整數(shù)值旗芬，并且保證集合中不會(huì)出現(xiàn)重復(fù)元素。

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

整數(shù)集合的每個(gè)元素都是contents數(shù)組的一個(gè)數(shù)據(jù)項(xiàng)捆蜀，他們按照從小到大的順序排列疮丛，并且不包含任何重復(fù)項(xiàng)。
length屬性記錄了contents數(shù)組的大小辆它。
需要注意的是雖然contents數(shù)組聲明為int8_t類型誊薄，但是實(shí)際上contents數(shù)組并不保存任何int8_t類型的值，其真正類型由encoding來決定锰茉。

• 升級(jí)
  當(dāng)我們新增元素類型比原集合元素類型的長度要大時(shí)暇屋，需要對(duì)整數(shù)集合進(jìn)行升級(jí)，才能將新元素放入整數(shù)集合中洞辣，具體步驟：
  1：根據(jù)新元素類型咐刨，擴(kuò)展整數(shù)集合底層數(shù)組的大小，并為新元素分配空間
  2：將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)成與新元素相同類型的元素扬霜，并將轉(zhuǎn)換后的元素放到正確的位置定鸟，放置過程中，維持整個(gè)元素順序都是有序的著瓶。
  3：將新元素添加到整數(shù)集合中(保證有序)
• 降級(jí)
  整數(shù)集合不支持降級(jí)联予，一旦對(duì)數(shù)組進(jìn)行了升級(jí)，編碼就會(huì)一直保存升級(jí)后的狀態(tài)

三材原、壓縮列表

壓縮列表(ziplist)是Redis為了節(jié)省內(nèi)存而開發(fā)的沸久，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)(entry)余蟹，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或一個(gè)整數(shù)值卷胯。
壓縮列表的原理：壓縮列表并不是對(duì)數(shù)據(jù)利用某種算法進(jìn)行壓縮的，而是將數(shù)據(jù)按照一定規(guī)則編碼在一塊連續(xù)的內(nèi)存區(qū)域威酒，目的是節(jié)省內(nèi)存窑睁。

image.png

壓縮列表的每個(gè)節(jié)點(diǎn)構(gòu)成如下：

image.png