Redis五種基本數(shù)據(jù)結構：String茵休、List、Set映挂、Hash泽篮、Zset
一、Redis對象基本結構
Redis是鍵值對方式的存儲柑船，每一個Redis存儲對象都包括兩個對象帽撑，一個是Key,一個是Value。
Redisc創(chuàng)建的對象RedisObject數(shù)據(jù)結構如下：
unsigned type: 4? // 類型鞍时，其中type的值對應5中redis數(shù)據(jù)類型的類型常量
unsigned encoding: 4 // 編碼亏拉，encoding則記錄了底層實現(xiàn)所用的數(shù)據(jù)結構
void *ptr // 指向底層數(shù)據(jù)結構指針
二扣蜻、內部數(shù)據(jù)結構
2.1 簡單動態(tài)字符串
redis實現(xiàn)了一個SDS結構(簡單動態(tài)字符串)類型來替代C語言中的原生字符串, 結構如下
struct sdshdr {
? ? int len; //記錄buf中字符串的實際長度
? ? int free; //記錄buf數(shù)組空閑長度
? ? char buf[];//字節(jié)數(shù)組,用于保存字符串
};
和C語言原生字符串相比, 其有一下優(yōu)點:
1、因為存儲了字符串長度及塘，可以在長量時間內獲取字符串長度莽使。
2、同樣由于存儲了字符串實際長度和buff空閑長度,字符串變化時不需要每次都重新分配內存笙僚；同時也避免了字符串長度變化可能導致的緩沖區(qū)溢出和內存泄漏芳肌。
3、SDS的設計由于根據(jù)字符串長度來判斷字符串的末尾,因此中間可以存儲任何數(shù)據(jù)包括空字符
2.2 雙向鏈表
redis中的鏈表類型就是最常用的雙向鏈表,涉及數(shù)據(jù)結構如下
//鏈表類型
typedef struct list {
listNode * head;//表頭節(jié)點
listNode * tail;//表未節(jié)點,方便逆向遍歷
unsigned long len;//節(jié)點數(shù)目, 優(yōu)化鏈表求長度
}list;
2.3肋层、Hash表
redis中的字典類型也就是基本的hash表
redis中的rehash就是通過創(chuàng)建一個臨時的字典,將正在使用的字典中的所有鍵值對復制到臨時字典中(這個過程需要重新計算hash值和索引值,因此稱為rehash),最后釋放老的字典,并將其指針指向臨時字典亿笤。
當數(shù)據(jù)量比較小的時候,這個過程可以一次性完成，但是數(shù)據(jù)量大的時候,龐大的計算量可能導致整個服務停止,因此redis采用了漸進式rehash:
1栋猖、同時維護兩個hash表hd[0]和hd[1]
2净薛、設置rehash_idx設置為0，在0< rehash_idx < 槽位數(shù)組長度時, 對hash表的任何操作除了執(zhí)行正常的操作過程以外蒲拉，還會將hd[0]槽位數(shù)組rehash_idx索引上的所有鍵值對rehash到hd[1]
3肃拜、同時所有的添加鍵值對操作只會在hd[1]上進行,保證了hd[0]只減不增。
4雌团、rehash完成后,hash表指針指向hd[1],釋放hd[0]內存燃领。
2.4 跳躍表
跳躍表是一種有序的數(shù)據(jù)結構，支持平均O(logN)復雜度的節(jié)點查找,其效率可以和平衡樹媲美辱姨，同時實現(xiàn)簡單,而且由于不需要reblance操作,在高并發(fā)情況下表現(xiàn)更加出色柿菩。redis中的跳躍表也就是基本的跳躍表實現(xiàn), 涉及數(shù)據(jù)結構如下。
typedef struct zskiplistNode{
? ? struct zskiplistLevel{? ?// 層數(shù)組雨涛，相當于索引枢舶，其中包括了當前節(jié)點砸每一層的前進指針以及到下一節(jié)點的跨度
? ? ? ? ? ?struct zskiplistNode *forward; // 本層節(jié)點中的下一節(jié)點
? ? ? ? ? ? unsinged int span; // 跨度，用于計算節(jié)點的排位替久。
? ?} level[]
? ?struct zskiplistNode *backWard; //指向前一個節(jié)點
? ?duble score; // 所有節(jié)點按分值排序
? ? robj *obj // 成員對象
}?
typedef struct zskiplist {
? ? struct zskiplistNode *header ,*tail;
? ? unsigned long length; // 表中節(jié)點數(shù)
? ? in level; 最大層數(shù)
}
實際上對有序鏈表稍加改造凉泄，我們就可以對鏈表進行二分查找。這就是我們要說的跳表蚯根。下面我們來看一下后众，跳表是怎么跳的。
上圖是一個簡單的有序的單鏈表颅拦，如果要查找某個數(shù)據(jù)蒂誉，只能從頭至尾遍歷鏈表，查找到值與給定元素時返回該結點距帅，這樣的查詢效率很低右锨，時間復雜度是為O(n)。
假如對鏈表進行改造碌秸，先對鏈表中每兩個節(jié)點建立第一級索引绍移，再對第一級索引每兩個節(jié)點建立第二級索引悄窃。如下圖所示：
對于上圖中的帶二級索引的鏈表中，我們查詢元素 16蹂窖，先從第二級索引查詢 1 -> 7->13轧抗，發(fā)現(xiàn)16大于13 ，然后通過 13 的 down 指針找到第一級索引的 17瞬测，發(fā)現(xiàn) 16 小于17 横媚，再通過13 的 down 指針找到鏈表中的 16，只需要遍歷 6 個節(jié)點就完成 16 的查找涣楷。如果在單鏈表中直接查找 16 的話分唾，只能順序遍歷，需要遍歷 10 個節(jié)點狮斗，是不是效率上有所提升呢，由于數(shù)據(jù)量較小弧蝇，遍歷 10 個節(jié)點到遍歷 6 個節(jié)點你可能覺得沒有提升多少性能碳褒。
所以，當鏈表的長度 n 比較大時看疗，比如 1000沙峻、10000 的時候，在構建索引之后两芳，查找效率的提升就會非常明顯摔寨。
跳表有多占內存？
假如有 n 個元素的鏈表怖辆，第一級索引為 n/2 個是复，第二級為 n/4 個，第三級為 n/8 個竖螃，......淑廊，最后一級為 2 個。這幾級索引的結點總和就是n/2+n/4+n/8…+8+4+2=n-2特咆。所以季惩，跳表的空間復雜度是 O(n)。也就是說腻格，如果將包含 n 個結點的單鏈表構造成跳表画拾，我們需要額外再用接近 n 個結點的存儲空間。那我們有沒有辦法降低索引占用的內存空間呢菜职？
其實 redis 中有序集合支持的核心操作也就是這幾個青抛。這里說下為什么 redis 使用跳表而不使用紅黑樹。
1些楣、紅黑樹在查找區(qū)間元素的效率沒有跳表高脂凶，其他操作時間復雜度一致宪睹。
2、相比紅黑樹蚕钦，跳表的實現(xiàn)還是簡單的亭病，簡單就意味著不容易出錯，bug 少嘶居，穩(wěn)定罪帖，易讀，易維護邮屁。
3整袁、跳表更加靈活，通過改變索引構建策略佑吝，有效平衡效率和內存消耗
2.5 壓縮表
壓縮列表是Redis為了節(jié)約內存而開發(fā)的, 是由一系列特殊編碼的連續(xù)內存塊組成的順序型數(shù)據(jù)結構,每個壓縮列表節(jié)點可以保存一個字節(jié)數(shù)組或一個整數(shù)值坐昙。其由三部分構成,如下所示:
zlbytes?表示的是整個壓縮列表使用的內存字節(jié)數(shù)
zltail?指定了壓縮列表的尾節(jié)點的偏移量
zllen?是壓縮列表 entry 的數(shù)量
entry?就是 ziplist 的節(jié)點
zlend?標記壓縮列表的末端
再看看一個 entry 的結構
typedef struct zlentry {?
// prevrawlen 前置節(jié)點的長度 ；prevrawlensize 編碼 prevrawlen 所需的字節(jié)大小
?unsigned int prevrawlensize, prevrawlen;
?// len 當前節(jié)點值的長度 芋忿，lensize 編碼 len 所需的字節(jié)大小
? unsigned int lensize, len;?
// 當前節(jié)點 header 的大小? 等于 prevrawlensize + lensize?
unsigned int headersize;? ? ?
?// 當前節(jié)點值所使用的編碼類型?
unsigned char encoding;?
// 指向當前節(jié)點的指針?
unsigned char *p;
?} zlentry;??????
prevrawlen?前置節(jié)點的長度炸客，這里多了一個 size，其實是記錄了 prevrawlen 的尺寸戈钢。Redis 為了節(jié)約內存并不是直接使用默認的 int 的長度痹仙，而是逐漸升級的。
同理?len?記錄的是當前節(jié)點的長度殉了，lensize?記錄的是 len 的長度开仰。
三、數(shù)據(jù)類型
String類型
String類型在Redis底層可以是int,raw和embstr薪铜。
如果一個String對象保存的是整數(shù)值众弓，并且可以使用long來表示,那么將會以整數(shù)形式保存。
如果一個String對象保存的是字符串值痕囱，并且其長度大于32字節(jié)田轧，那么就直接使用SDS結構來保存，其encoding標記為raw鞍恢。
如果一個String對象保存的字符串長度小于32字節(jié)傻粘，那么會使用embstr編碼，embstr是一種短字符串的優(yōu)化帮掉，其存儲還是使用SDS結構弦悉，但raw編碼會調用兩次內存分配函數(shù)來分別創(chuàng)建redisObject結構和SDS結構，而embstr編碼則通過調用一次內存分配函數(shù)來分配 一塊連續(xù)的空間蟆炊，空間中依次包含redisObject和SDS結構稽莉。
List類型
List類型在Redis底層可以是ziplist(壓縮列表)或linkedlist(雙向列表)。
Hash類型
Hash類型在Redis底層可以是ziplist(壓縮列表)或hashtable(Hash表)涩搓，ziplist編碼的哈希對象每當 有新的鍵值對要插入時,會將保存了鍵和值的節(jié)點依次推入到壓縮列表表尾,因此同一鍵值對順序存放在一起污秆。
Set類型
Set類型在Redis底層可以是intset(整數(shù)集合)或hashtable(Hash表)劈猪，只有當Set中的所有元素均為整數(shù)類型時才會使用intset。
Zset類型
Zset類型在Redis底層可以是ziplist(壓縮列表)或skiplist(跳躍
