記錄閱讀這本書時(shí)覺得有用的東西幔崖，也許很零散食店。(第一部分)
字符串
redis的字符串底層實(shí)現(xiàn)為簡(jiǎn)單動(dòng)態(tài)字符串simple-dynamic-string。
struct sdshdr{
int len; 字符個(gè)數(shù)赏寇，不包括‘/0’
int free; 沒有使用的字符個(gè)數(shù)
char buf[]; 字符數(shù)組
}
空間預(yù)分配
空間預(yù)分配用于優(yōu)化SDS的字符串增長(zhǎng)操作吉嫩。
- 如果對(duì)sds修改后，len小于1MB嗅定，那么分配與len同樣大小的未使用空間自娩。buf的長(zhǎng)度變?yōu)?code>len+buf+1
- 如果修改后，lend大于等于1MB,那么分配1MB的未使用空間渠退。buf的長(zhǎng)度變?yōu)?code>len+1MB+1byte
惰性空間釋放
用于優(yōu)化SDS的字符串縮短操作
- 進(jìn)行縮短操作時(shí)忙迁，不減少buf的長(zhǎng)度，將縮短的部分加入free碎乃。
- 同時(shí)提供了真正釋放未使用空間的API姊扔，不用擔(dān)心內(nèi)存浪費(fèi)
C字符串與SDS對(duì)比
| C字符串 | SDS |
|---|---|
| 獲取字符串長(zhǎng)度復(fù)雜度O(n) | 復(fù)雜度O(1) |
| API不安全，可能緩沖區(qū)溢出 | API安全 |
| 修改字符串長(zhǎng)度N次必然需要執(zhí)行N次內(nèi)存重分配 | 修改字符串長(zhǎng)度N次最多需要N次內(nèi)存重分配 |
| 只能保存文本數(shù)據(jù) | 可以保存文本或者二進(jìn)制數(shù)據(jù) |
| 可以使用所有<string.h>庫(kù)中的函數(shù) | 可以使用部分 |
鏈表
鏈表在redis中應(yīng)用廣泛梅誓，當(dāng)一個(gè)列表鍵包含了數(shù)量較多的元素恰梢，又或者列表包含的元素都是比較長(zhǎng)的字符串時(shí)，redis就會(huì)用鏈表作為列表鍵的底層實(shí)現(xiàn)梗掰。
特性
- 雙向嵌言， 無環(huán)
- 有表頭，表尾指針
- 帶鏈表長(zhǎng)度計(jì)數(shù)器
- 多態(tài)及穗，可以保存不同類型的值
字典
應(yīng)用廣泛摧茴。整個(gè)數(shù)據(jù)庫(kù)就是一個(gè)kv數(shù)據(jù)庫(kù)，其次哈希鍵這個(gè)數(shù)據(jù)結(jié)構(gòu)的底層也是字典埂陆。
哈希表結(jié)構(gòu)
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼苛白，用于計(jì)算索引值，總是等于size-1
unsigned long sizemask;
// 該哈希表已有節(jié)點(diǎn)數(shù)量
unsigned long used;
} dictht;
哈希表節(jié)點(diǎn)結(jié)構(gòu)
typedef struct dictEntry {
void *key;
union(
void *val;
uint64_tu64;
int64_ts64;
) v;
struvt dictEntry *next;
} dictEntry;
字典結(jié)構(gòu)
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引焚虱， 當(dāng)rehash不在進(jìn)行時(shí)丸氛，值為-1
int trehashidx;
} dict;
字典保存在ht[0]中，ht[1]用來對(duì)哈希表進(jìn)行rehash著摔。使用MurmueHash算法缓窜。數(shù)組+鏈表的方式解決哈希沖突。
rehash優(yōu)化-漸進(jìn)式rehash
如果字典表過大谍咆，一次完成rehash會(huì)造成數(shù)據(jù)庫(kù)在一段時(shí)間停止服務(wù)禾锤。步驟如下：
- 為ht[1]分配空間
- 在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將值置為0
- 在rehash期間摹察，每次對(duì)字典進(jìn)行添加刪除恩掷，查找或者更新操作時(shí)，順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]供嚎，完成后rehashidx+1
- 最終全部rehash到ht[1]黄娘， 將rehashidx設(shè)為-1表示完成峭状。把ht[0]的哈希表指向ht[1]的哈希表，ht[1]指向null逼争。
壓縮列表
壓縮列表是列表和哈希的底層實(shí)現(xiàn)之一优床，當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，并且是小整數(shù)值或短字符串誓焦。同時(shí)滿足以下兩點(diǎn)胆敞，使用壓縮鏈表。
- 列表對(duì)象保存的所有字符串長(zhǎng)度都小于64字節(jié)
- 列表對(duì)象保存的元素?cái)?shù)量小于512個(gè)
跳躍表
redis使用跳躍表作為有序集合的底層實(shí)現(xiàn)之一杂伟，同時(shí)也用在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)移层。可以參考網(wǎng)上跳表數(shù)據(jù)結(jié)構(gòu)分析赫粥。（個(gè)人感覺與二分的思想是一致的观话，有序情況下降低復(fù)雜度）
set
集合數(shù)據(jù)結(jié)構(gòu)靠字典實(shí)現(xiàn)，集合的值為字典的鍵越平，對(duì)應(yīng)的值為null匪燕。
