string
string表示的是一個(gè)可變的字節(jié)數(shù)組云挟，內(nèi)部結(jié)構(gòu)實(shí)現(xiàn)上類似于Java的ArrayList转质，采用預(yù)分配冗余空間的方式來(lái)減少內(nèi)存的頻繁分配。
如圖沸枯，內(nèi)部為當(dāng)前字符串實(shí)際分配的空間capacity一般要高于實(shí)際字符串長(zhǎng)度len赂弓。
當(dāng)字符串長(zhǎng)度小于1M時(shí)拣展，擴(kuò)容都是加倍現(xiàn)有的空間缔逛，如果超過(guò)1M，擴(kuò)容時(shí)一次只會(huì)多擴(kuò)1M的空間按脚。需要注意的是字符串最大長(zhǎng)度為512M敦冬。
list
Redis將列表數(shù)據(jù)結(jié)構(gòu)命名為list而不是array，是因?yàn)榱斜淼拇鎯?chǔ)結(jié)構(gòu)用的是鏈表而不是數(shù)組堪遂，而且鏈表還是雙向鏈表。因?yàn)樗擎湵肀揖桑噪S機(jī)定位性能較弱O(n)猿妈，首尾插入刪除性能較優(yōu)O(1)。如果list的列表長(zhǎng)度很長(zhǎng)鳍刷，使用時(shí)我們一定要關(guān)注鏈表相關(guān)操作的時(shí)間復(fù)雜度俯抖。
快速列表
如果再深入一點(diǎn)芬萍，你會(huì)發(fā)現(xiàn)Redis底層存儲(chǔ)的還不是一個(gè)簡(jiǎn)單的linkedlist，而是稱之為快速鏈表quicklist的一個(gè)結(jié)構(gòu)担忧。
首先在列表元素較少的情況下會(huì)使用一塊連續(xù)的內(nèi)存存儲(chǔ)瓶盛，這個(gè)結(jié)構(gòu)是ziplist，也即是壓縮列表惩猫。它將所有的元素緊挨著一起存儲(chǔ)轧房，分配的是一塊連續(xù)的內(nèi)存。當(dāng)數(shù)據(jù)量比較多的時(shí)候才會(huì)改成quicklist奶镶。因?yàn)槠胀ǖ逆湵硇枰母郊又羔樋臻g太大厂镇，會(huì)比較浪費(fèi)空間。比如這個(gè)列表里存的只是int類型的數(shù)據(jù)捺信，結(jié)構(gòu)上還需要兩個(gè)額外的指針prev和next。所以Redis將鏈表和ziplist結(jié)合起來(lái)組成了quicklist秒咨。也就是將多個(gè)ziplist使用雙向指針串起來(lái)使用雨席。這樣既滿足了快速的插入刪除性能，又不會(huì)出現(xiàn)太大的空間冗余舅世。
hash
hash 的實(shí)現(xiàn)類似java的HashMap雏亚。
它使用二維結(jié)構(gòu)，第一維是數(shù)組罢低，第二維是鏈表网持，hash的內(nèi)容key和value存放在鏈表中，數(shù)組里存放的是鏈表的頭指針功舀。通過(guò)key查找元素時(shí)辟汰，先計(jì)算key的hashcode，然后用hashcode對(duì)數(shù)組的長(zhǎng)度進(jìn)行取模定位到鏈表的表頭帖汞，再對(duì)鏈表進(jìn)行遍歷獲取到相應(yīng)的value值翩蘸，鏈表的作用就是用來(lái)將產(chǎn)生了「hash碰撞」的元素串起來(lái)，也就是拉鏈法解決hash沖突問(wèn)題催首。哈希的第一維數(shù)組的長(zhǎng)度也是2^n翅帜。
set
類似java的HashSet的內(nèi)部實(shí)現(xiàn)使用的是HashMap。Redis的set結(jié)構(gòu)也是一樣，它的內(nèi)部也使用hash結(jié)構(gòu)歼疮，所有的value都指向同一個(gè)內(nèi)部值。
sorted set
Redis 的 zset 是一個(gè)復(fù)合結(jié)構(gòu)韩脏，第一個(gè)是hash赡矢，第二個(gè)是跳躍列表skiplist。hash 結(jié)構(gòu)來(lái)存儲(chǔ) value 和 score 的對(duì)應(yīng)關(guān)系吹散，保障元素value的唯一性空民，可以通過(guò)元素value找到相應(yīng)的score值。跳躍列表的目的在于給按照score排序画饥，根據(jù)score的范圍獲取value列表浊猾。
跳躍列表
跳表(skip List)是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表单山，實(shí)現(xiàn)簡(jiǎn)單幅疼，插入、刪除悴晰、查找的復(fù)雜度均為O(logN)逐工。簡(jiǎn)單說(shuō)來(lái)跳表也是鏈表的一種，只不過(guò)它在鏈表的基礎(chǔ)上增加了跳躍功能棕硫，正是這個(gè)跳躍的功能袒啼，使得在查找元素時(shí)，跳表能夠提供O(logN)的時(shí)間復(fù)雜度滑肉。
因?yàn)?zset 要支持隨機(jī)的插入和刪除，所以它不好使用數(shù)組來(lái)表示问畅。而如果我們用一個(gè)有序鏈表來(lái)實(shí)現(xiàn)六荒，那么我們要查找某個(gè)數(shù)據(jù)掏击，就需要從頭開(kāi)始逐個(gè)進(jìn)行比較（二分查找的對(duì)象必須是數(shù)組，只有數(shù)組才可以支持快速位置定位铐料，鏈表做不到）钠惩，也就是說(shuō)，時(shí)間復(fù)雜度為O(n)膝捞。同樣愧沟，當(dāng)我們要插入新數(shù)據(jù)的時(shí)候，也要經(jīng)歷同樣的查找過(guò)程林艘，從而確定插入位置混坞。
假如我們每相鄰兩個(gè)節(jié)點(diǎn)增加一個(gè)指針究孕，讓指針指向下下個(gè)節(jié)點(diǎn)，如下圖：
現(xiàn)在當(dāng)我們想查找數(shù)據(jù)的時(shí)候镶殷，可以先沿著這個(gè)新鏈表進(jìn)行查找微酬。當(dāng)碰到比待查數(shù)據(jù)大的節(jié)點(diǎn)時(shí)颤陶，再回到原來(lái)的鏈表中進(jìn)行查找指郁。比如拷呆，我們想查找23疫粥，查找的路徑是沿著下圖中標(biāo)紅的指針?biāo)赶虻姆较蜻M(jìn)行的：
- 23首先和7比較，再和19比較项秉，比它們都大慷彤，繼續(xù)向后比較。
- 但23和26比較的時(shí)候岁诉，比26要小跋选，因此回到下面的鏈表（原鏈表），與22比較坠韩。
- 23比22要大炼列，沿下面的指針繼續(xù)向后和26比較俭尖。23比26小，說(shuō)明待查數(shù)據(jù)23在原鏈表中不存在目溉，而且它的插入位置應(yīng)該在22和26之間明肮。
利用同樣的方式，我們可以在上層新產(chǎn)生的鏈表上缭付，繼續(xù)為每相鄰的兩個(gè)節(jié)點(diǎn)增加一個(gè)指針柿估，從而產(chǎn)生第三層鏈表。如下圖：
skiplist正是受這種多層鏈表的想法的啟發(fā)而設(shè)計(jì)出來(lái)的陷猫。實(shí)際上秫舌，按照上面生成鏈表的方式的妖，上面每一層鏈表的節(jié)點(diǎn)個(gè)數(shù)，是下面一層的節(jié)點(diǎn)個(gè)數(shù)的一半足陨，這樣查找過(guò)程就非常類似于一個(gè)二分查找，使得查找的時(shí)間復(fù)雜度可以降低到O(log n)墨缘。但是星虹，這種方法在插入數(shù)據(jù)的時(shí)候有很大的問(wèn)題。新插入一個(gè)節(jié)點(diǎn)之后镊讼，就會(huì)打亂上下相鄰兩層鏈表上節(jié)點(diǎn)個(gè)數(shù)嚴(yán)格的2:1的對(duì)應(yīng)關(guān)系宽涌。如果要維持這種對(duì)應(yīng)關(guān)系，就必須把新插入的節(jié)點(diǎn)后面的所有節(jié)點(diǎn)（也包括新插入的節(jié)點(diǎn)）重新進(jìn)行調(diào)整蝶棋，這會(huì)讓時(shí)間復(fù)雜度重新蛻化成O(n)卸亮。刪除數(shù)據(jù)也有同樣的問(wèn)題。
skiplist為了避免這一問(wèn)題玩裙，它不要求上下相鄰兩層鏈表之間的節(jié)點(diǎn)個(gè)數(shù)有嚴(yán)格的對(duì)應(yīng)關(guān)系兼贸，而是為每個(gè)節(jié)點(diǎn)隨機(jī)出一個(gè)層數(shù)(level)。比如吃溅，一個(gè)節(jié)點(diǎn)隨機(jī)出的層數(shù)是3溶诞，那么就把它鏈入到第1層到第3層這三層鏈表中。為了表達(dá)清楚罕偎，下圖展示了如何通過(guò)一步步的插入操作從而形成一個(gè)skiplist的過(guò)程：
實(shí)際應(yīng)用中的skiplist每個(gè)節(jié)點(diǎn)應(yīng)該包含key和value兩部分很澄。前面的描述中我們沒(méi)有具體區(qū)分key和value，但實(shí)際上列表中是按照key(score)進(jìn)行排序的颜及，查找過(guò)程也是根據(jù)key在比較甩苛。
執(zhí)行插入操作時(shí)計(jì)算隨機(jī)數(shù)的過(guò)程，是一個(gè)很關(guān)鍵的過(guò)程俏站，它對(duì)skiplist的統(tǒng)計(jì)特性有著很重要的影響讯蒲。這并不是一個(gè)普通的服從均勻分布的隨機(jī)數(shù)，它的計(jì)算過(guò)程如下：
- 首先肄扎，每個(gè)節(jié)點(diǎn)肯定都有第1層指針（每個(gè)節(jié)點(diǎn)都在第1層鏈表里）墨林。
- 如果一個(gè)節(jié)點(diǎn)有第i層(i>=1)指針（即節(jié)點(diǎn)已經(jīng)在第1層到第i層鏈表中），那么它有第(i+1)層指針的概率為p（redis中為25%）犯祠。
- 節(jié)點(diǎn)最大的層數(shù)不允許超過(guò)一個(gè)最大值旭等，記為MaxLevel（redis中為64）。
計(jì)算隨機(jī)層數(shù)的偽碼如下所示：
randomLevel()
level := 1
// random()返回一個(gè)[0...1)的隨機(jī)數(shù)
while random() < p and level < MaxLevel do
level := level + 1
return level
因?yàn)槊繉拥臅x升的概率都只有25%衡载，所以官方的跳躍列表更加的扁平化搔耕，層高相對(duì)較低，在單個(gè)層上需要遍歷的節(jié)點(diǎn)數(shù)量會(huì)稍多一點(diǎn)痰娱。也正是因?yàn)閷訑?shù)一般不高弃榨，所以遍歷的時(shí)候從頂層開(kāi)始往下遍歷會(huì)非常浪費(fèi)菩收。跳躍列表會(huì)記錄一下當(dāng)前的最高層數(shù)maxLevel，遍歷時(shí)從這個(gè) maxLevel 開(kāi)始遍歷性能就會(huì)提高很多
在一個(gè)極端的情況下鲸睛，zset 中所有的 score 值都是一樣的娜饵，zset 的查找性能會(huì)退化為 O(n) 么？Redis 作者自然考慮到了這一點(diǎn)官辈，所以 zset 的排序元素不只看 score 值箱舞，如果 score 值相同還需要再比較 value 值 (字符串比較)。
元素排名
如果僅僅使用上面的結(jié)構(gòu)钧萍，rank 是不能算出來(lái)的褐缠。Redis 在 skiplist 的 forward 指針上進(jìn)行了優(yōu)化政鼠，給每一個(gè) forward 指針都增加了 span 屬性风瘦，span 是「跨度」的意思，表示從前一個(gè)節(jié)點(diǎn)沿著當(dāng)前層的 forward 指針跳到當(dāng)前這個(gè)節(jié)點(diǎn)中間會(huì)跳過(guò)多少個(gè)節(jié)點(diǎn)公般。Redis 在插入刪除操作時(shí)會(huì)小心翼翼地更新 span 值的大小万搔。這樣當(dāng)我們要計(jì)算一個(gè)元素的排名時(shí)，只需要將「搜索路徑」上的經(jīng)過(guò)的所有節(jié)點(diǎn)的跨度 span 值進(jìn)行疊加就可以算出元素的最終 rank 值官帘。
skiplist與平衡樹(shù)的比較：
- 查找單個(gè)key瞬雹，skiplist和平衡樹(shù)的時(shí)間復(fù)雜度都為O(log n)。
- 在做范圍查找的時(shí)候刽虹，平衡樹(shù)比skiplist操作要復(fù)雜酗捌。
- 平衡樹(shù)的插入和刪除操作可能引發(fā)子樹(shù)的調(diào)整，邏輯復(fù)雜涌哲，而skiplist的插入和刪除只需要修改相鄰節(jié)點(diǎn)的指針胖缤，操作簡(jiǎn)單又快速。
- 從內(nèi)存占用上來(lái)說(shuō)阀圾，skiplist比平衡樹(shù)更靈活一些哪廓。一般來(lái)說(shuō)，平衡樹(shù)每個(gè)節(jié)點(diǎn)包含2個(gè)指針（分別指向左右子樹(shù)）初烘，
- 從算法實(shí)現(xiàn)難度上來(lái)比較涡真，skiplist比平衡樹(shù)要簡(jiǎn)單得多。
參考文章：https://zsr.github.io/2017/07/03/redis-zset%E5%86%85%E9%83%A8%E5%AE%9E%E7%8E%B0/
