本文是對(duì)redis系統(tǒng)中用到的基本數(shù)據(jù)結(jié)構(gòu)的梳理
1.sds 字符串
redis 中字符串?dāng)?shù)據(jù)結(jié)構(gòu)如下
struct sdshdr{
int len; //已用長(zhǎng)度
int free; //未使用數(shù)據(jù)長(zhǎng)度
char buf[]; //數(shù)據(jù)指針
};
可以看到,在字符串的頭部,記錄了字符串對(duì)象當(dāng)前
使用的長(zhǎng)度以及剩余的空間大小尿赚。有了這個(gè)長(zhǎng)度可以杜絕字符串的溢出裸卫，也能基于len和free字段做字符串空間的預(yù)分配。
2.鏈表
struct list{
listNode* head;
listNode * tail;
int len;
void *(*dup)(void *ptr);//節(jié)點(diǎn)復(fù)制函數(shù)
void(*free)(void *prt); //節(jié)點(diǎn)釋放函數(shù)
void （*match）（void*ptr,void *key）//節(jié)點(diǎn)比對(duì)函數(shù)
}
雙向鏈表的實(shí)現(xiàn)沒有特別的地方淑蔚，這里值得借鑒的是，把函數(shù)指針當(dāng)做結(jié)構(gòu)體成員，這個(gè)就是c語(yǔ)言編寫面向?qū)ο蟪绦虻姆椒ā?/p>
3.字典
字典數(shù)據(jù)結(jié)構(gòu)示意圖：
redis的字典結(jié)構(gòu)底層是一個(gè)拉鏈法實(shí)現(xiàn)的哈希表。
值得注意的是一個(gè)字典結(jié)構(gòu)里實(shí)際上有兩個(gè)哈希表結(jié)構(gòu)象迎。目的是用來(lái)做rehash。
當(dāng)哈希表中元素過多或過少時(shí)呛踊，就需要對(duì)原來(lái)這個(gè)哈希表做rehash操作砾淌。
rehash本質(zhì)上是開一個(gè)新hash表,其空間是原先空間的指數(shù)倍放大或縮小。將原表上的每一個(gè)元素取出,重新hash并放入到新表中的過程谭网。
如果一次性將表中所有元素都rehash掉汪厨，其代價(jià)較大,redis 這里采用的方式是，每次訪問一個(gè)key時(shí)愉择，將val = hash（key）上的所有元素rehash掉劫乱。
4.跳躍表
跳躍表在redis 中用于解決zset的排序問題。
跳躍表的平均時(shí)間復(fù)雜度O(logn)锥涕，其空間復(fù)雜度為O(n)衷戈。
跳躍表的原理見:
https://www.cnblogs.com/George1994/p/7635731.html
5.整數(shù)集合
整數(shù)集合是redis set 類型的底層的實(shí)現(xiàn),當(dāng)一個(gè)集合中只包含整數(shù)值元素，并且這個(gè)集合的元素?cái)?shù)量不多時(shí)层坠，redis就會(huì)用整數(shù)集合作為底層實(shí)現(xiàn)殖妇。
目的在于：節(jié)省內(nèi)存
整數(shù)集合的數(shù)據(jù)結(jié)構(gòu)如下：
struct intset {
uint32_t encoding;//說(shuō)明一個(gè)元素占多少空間。
uint32_t length //元素個(gè)數(shù);
int8_t contents[];
};
可以看到破花，實(shí)際上就是一個(gè)整數(shù)數(shù)組谦趣。數(shù)組中的值從小到大排序。
如果添加的新元素類型比當(dāng)前整數(shù)集合保存值的類型長(zhǎng)時(shí)需要做升級(jí)處理旧乞。
升級(jí)步驟：
- 擴(kuò)展數(shù)組空間
- 將已有元素?cái)U(kuò)展為新類型
- 放入新元素
6.壓縮列表
壓縮列表是列表和哈希表的底層實(shí)現(xiàn)之一蔚润。
當(dāng)列表/哈希表包含的對(duì)象較少磅氨，切對(duì)象是整數(shù)或者短字符串時(shí)尺栖，采用壓縮列表作為底層實(shí)現(xiàn)。
壓縮列表目的在于：節(jié)省內(nèi)存
