Redis中的zset幸逆，首先它是一個set棍辕，set中的元素具有不可重復(fù)性暮现，其次它也是一個有序集合，其中的元素按照一定的評分進(jìn)行排序楚昭。Set的內(nèi)部結(jié)構(gòu)我們就不說了栖袋，可以參考上一節(jié)的內(nèi)容《Redis筆記（三）- 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)_Hash和Set》，我們這次主要探討一下zset中元素是怎么實(shí)現(xiàn)有序的抚太。
概括
實(shí)際上zset對于排序有兩種結(jié)構(gòu)實(shí)現(xiàn)塘幅，一種是在元素個數(shù)比較少且總長度比較短的時候使用壓縮列表（ziplist，參考《Redis筆記（二）- 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)_List》中的部分內(nèi)容）凭舶，另一種是不符合上述條件時使用跳躍列表（skiplist）晌块。
ziplist使用條件：
- 元素?cái)?shù)量小于128個爱沟。
- 所有元素成員的長度小于64字節(jié)帅霜。
zset中的壓縮列表ziplist
先來回顧一下ziplist的結(jié)構(gòu)
struct ziplist<T> {
int32 zlbytes; // 整個壓縮列表占用字節(jié)數(shù)
int32 zltail_offset; // 最后一個元素距離壓縮列表起始位置的偏移量，用于快速定位到最后一個節(jié)點(diǎn)
int16 zllength; // 元素個數(shù)
T[] entries; // 元素內(nèi)容列表呼伸，緊湊的連續(xù)內(nèi)存空間
int8 zlend; // 標(biāo)志壓縮列表的結(jié)束身冀，值恒為 0xFF
}
每一個entry的結(jié)構(gòu)：
struct entry {
int<var> prevlen; // 前一個 entry 的字節(jié)長度
int<var> encoding; // 元素類型編碼
optional byte[] content; // 元素內(nèi)容
}
zset中的ziplist元素是怎樣存的呢？entries中每兩個連續(xù)entry為一組括享，表示一個元素搂根，第一個entry保存的是其元素的值，第二個entry保存的是其評分铃辖，評分低的排在entries數(shù)組的前面剩愧，評分高的排在entries數(shù)組的后面。
zset中的跳躍列表skiplist
先來張圖解釋下跳躍列表：
最底層是一個有序的鏈表娇斩，查找一個元素仁卷，需要O(n)的時間復(fù)雜度，但是如果從這個鏈表抽出一部分元素犬第，形成一個新的鏈表锦积，把這個鏈表當(dāng)做粗略的索引，遍歷索引的次數(shù)要比遍歷原始鏈表的次數(shù)大大降低歉嗓。典型的空間換時間的思維丰介。
檢索過程
舉個例子，如果我要查找"13"這個元素鉴分，首先從最高的第二級索引層遍歷哮幢，當(dāng)遍歷過元素"7"之后，發(fā)現(xiàn)我要找的"13"這個元素是小于下一個元素"14"的志珍，因此家浇，進(jìn)入第一級索引層繼續(xù)從"7"遍歷到"14",當(dāng)遍歷過元素"10"之后，要找的"13"這個元素還是小于下一個元素"14"的碴裙，于是繼續(xù)在下一級的原始鏈表中從"10"遍歷到"14"钢悲，最后就能在這個范圍中找到"13"這個元素点额。
插入過程
redis的跳躍列表并不是按照嚴(yán)格的"上一層的索引節(jié)點(diǎn)數(shù)是下一層的二分之一"這樣的規(guī)則進(jìn)行構(gòu)造的，因?yàn)榧偃绨凑者@個規(guī)則進(jìn)行插入莺琳，則插入元素的左右節(jié)點(diǎn)的層數(shù)都要調(diào)整还棱。而實(shí)際上每插入一個元素，這個元素所擁有的層數(shù)是隨機(jī)的惭等≌涫郑看個插入過程的例子：
每插入一個元素隨機(jī)層數(shù)的計(jì)算方法如下：
- 首先，每個節(jié)點(diǎn)肯定都有第1層指針（每個節(jié)點(diǎn)都在第1層鏈表里）辞做。
- 如果一個節(jié)點(diǎn)有第i層(i>=1)指針（即節(jié)點(diǎn)已經(jīng)在第1層到第i層鏈表中）琳要，那么它有第(i+1)層指針的概率為p^(i-1)，p默認(rèn)1/4秤茅。
- 節(jié)點(diǎn)最大的層數(shù)不允許超過一個最大值稚补，記為MaxLevel。
總結(jié)
- 查詢元素的分?jǐn)?shù)值框喳，是用zset中的hash結(jié)構(gòu)來查的课幕。
- 范圍查詢或者獲取元素的排名是根據(jù)skiplist來查的。這里skiplist做了一點(diǎn)小優(yōu)化五垮，就是在元素的每層索引的指針擴(kuò)展了一個屬性乍惊，這個屬性存儲了這個元素到指針指向的下一個元素之前有多少個節(jié)點(diǎn)，又稱跨度放仗，這樣在檢索一個元素的時候就可以很方便的知道在這個元素在整個鏈表的排名润绎。
