1傅蹂、ziplist 壓縮列表
1.1 概述
壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)兵迅，是一塊連續(xù)的內(nèi)存空間甜紫，元素之間緊挨著存儲(chǔ)，沒有任何冗余空間艘狭。
Redis 為了節(jié)約內(nèi)存空間使用挎扰，zset 和 hash 容器對象在元素個(gè)數(shù)較少的時(shí)候，采用壓縮列表 (ziplist) 進(jìn)行存儲(chǔ)巢音。3.2.0版本之前, 當(dāng) List 容器對象在元素個(gè)數(shù)較少的時(shí)候遵倦，也采用壓縮列表 (ziplist) 進(jìn)行存儲(chǔ), 3.2.0之后 List 全部使用 quickList(快速列表)
1.2 數(shù)據(jù)結(jié)構(gòu)
struct ziplist<T> {
int32 zlbytes; // 4 byte, 記錄整個(gè)壓縮列表占用內(nèi)存字節(jié)數(shù),在內(nèi)存分配或者計(jì)算 zlend 的位置時(shí)使用
int32 zltail_offset; // 4 byte, 最后一個(gè)元素距離壓縮列表起始位置的偏移量，用于快速定位到最后一個(gè)節(jié)點(diǎn)
int16 zllength; // 2 byte, 元素個(gè)數(shù)當(dāng)屬性值 < 65535 時(shí), 屬性值表示節(jié)點(diǎn)個(gè)數(shù), 當(dāng)屬性值 = 65535 時(shí), 真實(shí)節(jié)點(diǎn)個(gè)數(shù)需要遍歷壓縮列表才能計(jì)算得出
T[] entries; // 元素節(jié)點(diǎn)列表官撼，節(jié)點(diǎn)之間挨個(gè)緊湊存儲(chǔ),無冗余空間
int8 zlend; // 1 byte,標(biāo)志壓縮列表的結(jié)束梧躺，值恒為 0xFF
}
真正保存的數(shù)據(jù)是在元素節(jié)點(diǎn)entries中的content，每個(gè)壓縮列表的節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值
struct entry {
// 前一個(gè) entry 的字節(jié)長度,
// 前一個(gè)節(jié)點(diǎn)長度小于254字節(jié),則該屬性用一個(gè)字節(jié)表示, 否則(大于等于254字節(jié))用五個(gè)字節(jié)表示,第一個(gè)字節(jié)被設(shè)置為0xFE(254), 后四個(gè)字節(jié)表示前一個(gè)節(jié)點(diǎn)長度
int<var> prevlen;
// 記錄了節(jié)點(diǎn)的 content 屬性所保存的數(shù)據(jù)的類型及長度
//當(dāng)屬性長度為 1 2 5 字節(jié),值最高位為 00 01 10 時(shí)表示為字節(jié)數(shù)組, 數(shù)組長度有編碼去除最高2位之后的其他位記錄, 當(dāng)屬性長度為 1 字節(jié)長, 最高位以 11 開頭表示是整數(shù)編碼,整數(shù)的類型和長度有編碼去除最高2位的其他位表示
int<var> encoding;
// 保存節(jié)點(diǎn)的值, 可以是一個(gè)字節(jié)數(shù)組或者整數(shù)
optional byte[] content;
}
2傲绣、quicklist 快速列表
2.1 概述
我們知道掠哥，鏈表中每個(gè)節(jié)點(diǎn)都會(huì)有prev 和 next 指針巩踏，每個(gè)指針占用8個(gè)字節(jié)，同時(shí)续搀，其每個(gè)節(jié)點(diǎn)的內(nèi)存都是單獨(dú)分配的塞琼，這會(huì)加劇內(nèi)存的碎片化，影響內(nèi)存管理效率目代。對于redis來說屈梁，內(nèi)存是相當(dāng)寶貴的。所以有了quicklist榛了。
2.2 數(shù)據(jù)結(jié)構(gòu)
從上面可以看出在讶，quicklist其實(shí)就是ziplist作為節(jié)點(diǎn)元素組成的鏈表。
// 快速列表
struct quicklist {
quicklistNode* head;
quicklistNode* tail;
long count; // 元素總數(shù)
int nodes; // ziplist 節(jié)點(diǎn)的個(gè)數(shù)
int compressDepth; // LZF 算法壓縮深度
...
}
// 快速列表節(jié)點(diǎn)
struct quicklistNode {
quicklistNode* prev;
quicklistNode* next;
ziplist* zl; // 指向壓縮列表
int32 size; // ziplist 的字節(jié)總數(shù)
int16 count; // ziplist 中的元素?cái)?shù)量
int2 encoding; // 存儲(chǔ)形式 2bit霜大，原生字節(jié)數(shù)組還是 LZF 壓縮存儲(chǔ)
...
}
2.3 zipList 長度
quicklist 內(nèi)部默認(rèn)單個(gè) ziplist 長度為 8k 字節(jié)构哺，超出了這個(gè)字節(jié)數(shù)，就會(huì)新起一個(gè) ziplist战坤。
ziplist 的長度由配置參數(shù) list-max-ziplist-size 決定曙强。
3、zskiplist
3.1 概述
跳躍表是一種有序的數(shù)據(jù)結(jié)構(gòu)途茫，通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針碟嘴，從而達(dá)到快速訪問節(jié)點(diǎn)的目的
大部分情況下, 跳躍表的效率可以和平衡樹相媲美
Redis中只在兩處用到了跳躍表，一個(gè)是實(shí)現(xiàn)有序集合囊卜，另一個(gè)是 集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)
3.2 數(shù)據(jù)結(jié)構(gòu)
typedef struct zset {
dict *dict; // 字典
zskiplist *zsl; // 跳躍表
} zset;
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 頭節(jié)點(diǎn) 尾節(jié)點(diǎn)
unsigned long length; // 節(jié)點(diǎn)個(gè)數(shù)
int level; // 最高層數(shù)
} zskiplist;
typedef struct zskiplistNode {
sds ele; //成員
double score; // 分值
struct zskiplistNode *backward; // 后退指針
struct zskiplistLevel {
struct zskiplistNode *forward; // 前進(jìn)指針
unsigned long span; // 跨度
} level[]; // 多層連接指針
} zskiplistNode;
每個(gè)跳躍表節(jié)點(diǎn)都保存一個(gè)元素娜扇，并按分值從小到大排列；節(jié)點(diǎn)的object屬性保存了元素的成員栅组，score屬性保存分值雀瓢；
字典的每個(gè)鍵值對保存一個(gè)元素，字典的鍵保存元素的成員玉掸，字典的值保存分值
4刃麸、總結(jié)
在Redis的五大數(shù)據(jù)對象中，string對象是唯一個(gè)可以被其他四種數(shù)據(jù)對象作為內(nèi)嵌對象的司浪；
列表（list）泊业、哈希（hash）、集合（set）啊易、有序集合（zset）底層實(shí)現(xiàn)都用到了壓縮列表結(jié)構(gòu)脱吱，并且使用壓縮列表結(jié)構(gòu)的條件都是在元素個(gè)數(shù)比較少、字節(jié)長度較短的情況下认罩；
四種數(shù)據(jù)對象使用壓縮列表的優(yōu)點(diǎn)：
節(jié)約內(nèi)存，減少內(nèi)存開銷续捂，Redis是內(nèi)存型數(shù)據(jù)庫垦垂，所以一定情況下減少內(nèi)存開銷是非常有必要的宦搬。
減少內(nèi)存碎片，壓縮列表的內(nèi)存塊是連續(xù)的劫拗，并分配內(nèi)存的次數(shù)一次即可间校。
壓縮列表的新增、刪除页慷、查找操作的平均時(shí)間復(fù)雜度是O(N)憔足，在N再一定的范圍內(nèi)，這個(gè)時(shí)間幾乎是可以忽略的酒繁，并且N的上限值是可以配置的滓彰。
四種數(shù)據(jù)對象都有兩種編碼結(jié)構(gòu)，靈活性增加州袒。
