第3章
跳 躍 表
有序集合在生活中較常見，如根據成績對學生進行排名、根據得分對遊戲玩家進行排名等。對于有序集合的底層實作，我們可以使用數組、連結清單、平衡樹等結構。數組不便于元素的插入和删除；連結清單的查詢效率低，需要周遊所有元素；平衡樹或者紅黑樹等結構雖然效率高但實作複雜。Redis采用了一種新型的資料結構——跳躍表。跳躍表的效率堪比紅黑樹，然而其實作卻遠比紅黑樹簡單。
3.1 簡介
在了解跳躍表之前，我們先了解一下有序連結清單。有序連結清單是所有元素以遞增或遞減方式有序排列的資料結構，其中每個節點都有指向下個節點的next指針，最後一個節點的next指針指向NULL。遞增有序連結清單舉例如圖3-1所示。
如圖3-1所示的有序連結清單，如果要查詢值為51的元素，需要從第一個元素開始依次向後查找、比較才可以找到，查找順序為1→11→21→31→41→51，共6次比較，時間複雜度為O(N)。有序連結清單的插入和删除操作都需要先找到合适的位置再修改next指針，修改操作基本不消耗時間，是以插入、删除、修改有序連結清單的耗時主要在查找元素上。
如果我們将有序連結清單中的部分節點分層，每一層都是一個有序連結清單。在查找時優先從最高層開始向後查找，當到達某節點時，如果next節點值大于要查找的值或next指針指向NULL，則從目前節點下降一層繼續向後查找，這樣是否可以提升查找效率呢？
分層有序連結清單如圖3-2所示，我們再次查找值為51的節點，查找步驟如下。
1）從第2層開始，1節點比51節點小，向後比較。
2）21節點比51節點小，繼續向後比較。第2層21節點的next指針指向NULL，是以從21節點開始需要下降一層到第1層繼續向後比較。
3）第1層中，21節點的next節點為41節點，41節點比51節點小，繼續向後比較。第1層41節點的next節點為61節點，比要查找的51節點大，是以從41節點開始下降一層到第0層繼續向後比較。
4）在第0層，51節點為要查詢的節點，節點被找到。
采用圖3-2所示的資料結構後，總共查找4次就可以找到51節點，比有序連結清單少2次。當資料量大時，優勢會更明顯。
綜上所述，通過将有序集合的部分節點分層，由最上層開始依次向後查找，如果本層的next節點大于要查找的值或next節點為NULL，則從本節點開始，降低一層繼續向後查找，依次類推，如果找到則傳回節點；否則傳回NULL。采用該原理查找節點，在節點數量比較多時，可以跳過一些節點，查詢效率大大提升，這就是跳躍表的基本思想。
跳躍表的實作過程如圖3-3所示。
從圖3-3中我們可以看出跳躍表有如下性質。
1）跳躍表由很多層構成。
2）跳躍表有一個頭（header）節點，頭節點中有一個64層的結構，每層的結構包含指向本層的下個節點的指針, 指向本層下個節點中間所跨越的節點個數為本層的跨度（span）。
3）除頭節點外，層數最多的節點的層高為跳躍表的高度（level），圖3-3中跳躍表的高度為3。
4）每層都是一個有序連結清單，資料遞增。
5）除header節點外，一個元素在上層有序連結清單中出現，則它一定會在下層有序連結清單中出現。
6）跳躍表每層最後一個節點指向NULL，表示本層有序連結清單的結束。
7）跳躍表擁有一個tail指針，指向跳躍表最後一個節點。
8）最底層的有序連結清單包含所有節點，最底層的節點個數為跳躍表的長度（length）（不包括頭節點），圖3-3中跳躍表的長度為7。
9）每個節點包含一個後退指針，頭節點和第一個節點指向NULL；其他節點指向最底層的前一個節點。
跳躍表每個節點維護了多個指向其他節點的指針，是以在跳躍表進行查找、插入、删除操作時可以跳過一些節點，快速找到操作需要的節點。歸根結底，跳躍表是以犧牲空間的形式來達到快速查找的目的。跳躍表與平衡樹相比，實作方式更簡單，隻要熟悉有序連結清單，就可以輕松地掌握跳躍表。
3.2 跳躍表節點與結構
由3.1節我們知道，跳躍表由多個節點構成，每個節點由很多層構成，每層都有指向本層下個節點的指針。那麼，Redis中的跳躍表是如何實作的呢？
3.2.1 跳躍表節點
下面我們來看跳躍表節點的zskiplistNode結構體。
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode; 該結構體包含如下屬性。
1）ele：用于存儲字元串類型的資料。
2）score：用于存儲排序的分值。
3）backward：後退指針，隻能指向目前節點最底層的前一個節點，頭節點和第一個節點—backward指向NULL，從後向前周遊跳躍表時使用。
4）level：為柔性數組。每個節點的數組長度不一樣，在生成跳躍表節點時，随機生成一個1～64的值，值越大出現的機率越低。
level數組的每項包含以下兩個元素。
- forward：指向本層下一個節點，尾節點的forward指向NULL。
- span：forward指向的節點與本節點之間的元素個數。span值越大，跳過的節點個數越多。
跳躍表是Redis有序集合的底層實作方式之一，是以每個節點的ele存儲有序集合的成員member值，score存儲成員score值。所有節點的分值是按從小到大的方式排序的，當有序集合的成員分值相同時，節點會按member的字典序進行排序。
3.2.2 跳躍表結構
除了跳躍表節點外，還需要一個跳躍表結構來管理節點，Redis使用zskiplist結構體，定義如下：
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist; 1）header：指向跳躍表頭節點。頭節點是跳躍表的一個特殊節點，它的level數組元素個數為64。頭節點在有序集合中不存儲任何member和score值，ele值為NULL，score值為0；也不計入跳躍表的總長度。頭節點在初始化時，64個元素的forward都指向NULL，span值都為0。
2）tail：指向跳躍表尾節點。
3）length：跳躍表長度，表示除頭節點之外的節點總數。
4）level：跳躍表的高度。
通過跳躍表結構體的屬性我們可以看到，程式可以在O(1)的時間複雜度下, 快速擷取到跳躍表的頭節點、尾節點、長度和高度。
3.3 基本操作
我們已經知道了跳躍表節點和跳躍表結構體的定義，下面我們分别介紹跳躍表的建立、插入、查找和删除操作。
3.3.1 建立跳躍表
1．節點層高
節點層高的最小值為1，最大值是ZSKIPLIST_MAXLEVEL，Redis5中節點層高的值為64。
#define ZSKIPLIST_MAXLEVEL 64 Redis通過zslRandomLevel函數随機生成一個1～64的值，作為建立節點的高度，值越大出現的機率越低。節點層高确定之後便不會再修改。生成随機層高的代碼如下。
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
} 上述代碼中，level的初始值為1，通過while循環，每次生成一個随機值，取這個值的低16位作為x，當x小于0.25倍的0xFFFF時，level的值加1；否則退出while循環。最終傳回level和ZSKIPLIST_MAXLEVEL兩者中的最小值。
下面計算節點的期望層高。假設p=ZSKIPLIST_P：
1）節點層高為1的機率為(1-p)。
2）節點層高為2的機率為p(1-p)。
3）節點層高為3的機率為p2(1-p)。
4）……
5）節點層高為n的機率為pn-1(1-p)。
是以節點的期望層高為
E＝1×(1-p)＋2×p(1-p)＋3×p2(1-p)＋…
＝(1-p)∑+∞i=1ipi-1
＝1/(1-p) 當p＝0.25時，跳躍表節點的期望層高為1/(1-0.25)≈1.33。
2.建立跳躍表節點
跳躍表的每個節點都是有序集合的一個元素，在建立跳躍表節點時，待建立節點的層高、分值、member等都已确定。對于跳躍表的每個節點，我們需要申請記憶體來存儲，代碼如下。
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel)); zskiplistNode結構體的最後一個元素為柔性數組，申請記憶體時需要指定柔性數組的大小，一個節點占用的記憶體大小為zskiplistNode的記憶體大小與level個zskiplistLevel的記憶體大小之和。
配置設定好空間之後，進行節點變量初始化。代碼如下。
zn->score = score;
zn->ele = ele;
return zn; 3.頭節點
頭節點是一個特殊的節點，不存儲有序集合的member資訊。頭節點是跳躍表中第一個插入的節點，其level數組的每項forward都為NULL，span值都為0。
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
} 4.建立跳躍表的步驟
建立完頭節點後，就可以建立跳躍表。建立跳躍表的步驟如下。
1）建立跳躍表結構體對象zsl。
2）将zsl的頭節點指針指向新建立的頭節點。
3）跳躍表層高初始化為1，長度初始化為0，尾節點指向NULL。
相關代碼如下。
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
zsl->header->backward = NULL;
zsl->level = 1;
zsl->length = 0;
zsl->tail = NULL; 3.3.2 插入節點
插入節點的步驟：① 查找要插入的位置；② 調整跳躍表高度；③ 插入節點；④ 調整backward。
1.查找要插入的位置
查找是跳躍表操作中使用最多的操作，無論是擷取、插入還是删除，都需要查找到指定的節點位置。通過3.1節内容，我們已經大概知道了跳躍表查找的基本邏輯，下面借助跳躍表的插入節點的過程深入了解跳躍表的查找過程。
如圖3-4所示的跳躍表，長度為3，高度為2。若要插入一個節點，分值為31，層高為3，則插入節點時查找被更新節點的代碼如下。
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
} 為了找到要更新的節點，我們需要以下兩個長度為64的數組來輔助操作。
update[]：插入節點時，需要更新被插入節點每層的前一個節點。由于每層更新的節點不一樣，是以将每層需要更新的節點記錄在update[i]中。
rank[]：記錄目前層從header節點到update[i]節點所經曆的步長，在更新update[i]的span和設定新插入節點的span時用到。
查找節點（score=31，level=3）的插入位置，邏輯如下。
1）第一次for循環，i=1。x為跳躍表的頭節點。
2）此時i的值與zsl->level-1相等，是以rank[1]的值為0。
3）header->level[1].forward存在，并且header->level[1].forward->score==1小于要插入的score，是以可以進入while循環，rank[1]=1，x為第一個節點。
4）第一個節點的第1層的forward指向NULL，是以不會再進入while循環。經過第一次for循環，rank[1]=1。x和update[1]都為第一個節點（score=1）。
5）經過第二次for循環，i=0。x為跳躍表的第一個節點（score=1）。
6）此時i的值與zsl->level-1不相等，是以rank[0]等于rank[1]的值，值為1。
7）x->level[0]->forward存在，并且x->level[0].foreard->score==21小于要插入的score，是以可以進入while循環，rank[0]=2。x為第二個節點（score=21）。
8）x->level[0]->forward存在，并且x->level[0].foreard->score==41大于要插入的score，是以不會再進入while，經過第二次for循環，rank[0]=2。x和update[0]都為第二個節點（score=21）。
update和rank指派後的跳躍表如圖3-5所示。
2.調整跳躍表高度
由上文可知，插入節點的高度是随機的，假設要插入節點的高度為3，大于跳躍表的高度2，是以我們需要調整跳躍表的高度。代碼如下。
level = zslRandomLevel();
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level; 此時，i的值為2，level的值為3，是以隻能進入一次for循環。由于header的第0層到第1層的forward都已經指向了相應的節點，而新添加的節點的高度大于跳躍表的原高度，是以第2層隻需要更新header節點即可。前面我們介紹過，rank是用來更新span的變量，其值是頭節點到update[i]所經過的節點數，而此次修改的是頭節點，是以rank[2]為0，update[2]一定為頭節點。update[2]->level[2].span的值先指派為跳躍表的總長度，後續在計算新插入節點level[2]的span時會用到此值。在更新完新插入節點level[2]的span之後會對update[2]->level[2].span的值進行重新計算指派。
調整高度後的跳躍表如圖3-6所示。
3.插入節點
當update和rank都指派且節點已建立好後，便可以插入節點了。代碼如下。
x = zslCreateNode(level,score,ele);
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
} level的值為3，是以可以執行三次for循環，插入過程如下。
（1）第一次for循環
1）x的level[0]的forward為update[0]的level[0]的forward節點，即x->level[0].forward為score=41的節點。
2）update[0]的level[0]的下一個節點為新插入的節點。
3）rank[0]-rank[0]＝0，update[0]->level[0].span=1，是以x->level[0].span=1。
4）update[0]->level[0].span=0+1=1。
插入節點并更新第0層後的跳躍表如圖3-7所示。
（2）第2次for循環
1）x的level[1]的forward為update[1]的level[1]的forward節點，即x->level[1].forward為NULL。
2）update[1]的level[1]的下一個節點為新插入的節點。
3）rank[0]-rank[1]=1，update[1]->level[1].span=2，是以x->level[1].span=1。
4）update[1]->level[1].span=1+1=2。
插入節點并更新第1層後的跳躍表如圖3-8所示。
（3）第3次for循環
1）x的level[2]的forward為update[2]的level[2]的forward節點，即x->level[2].forward為NULL。
2）update[2]的level[2]的下一個節點為新插入的節點。
3）rank[0]-rank[2]=2，因為update[2]->level[2].span=3，是以x->level[2].span=1。
4）update[2]->level[2].span=2+1=3。
插入節點并更新第2層後的跳躍表如圖3-9所示。
新插入節點的高度大于原跳躍表高度，是以下面代碼不會運作。但如果新插入節點的高度小于原跳躍表高度，則從level到zsl->level-1層的update[i]節點forward不會指向新插入的節點，是以不用更新update[i]的forward指針，隻将這些level層的span加1即可。代碼如下。
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
} 4.調整backward
根據update的指派過程，新插入節點的前一個節點一定是update[0]，由于每個節點的後退指針隻有一個，與此節點的層數無關，是以當插入節點不是最後一個節點時，需要更新被插入節點的backward指向update[0]。如果新插入節點是最後一個節點，則需要更新跳躍表的尾節點為新插入節點。插入節點後，更新跳躍表的長度加1。代碼如下。
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x; 插入新節點後的跳躍表如圖3-10所示。
3.3.3 删除節點
删除節點的步驟：1）查找需要更新的節點；2）設定span和forward。
圖3-10中的跳躍表的長度為3，高度為3，此時删除score=31的節點，将此節點記錄為x。
1.查找需要更新的節點
查找需要更新的節點要借助update數組，數組的指派方式與3.3.2中update的指派方式相同，不再贅述。查找完畢之後，update[2]=header，update[1]為score=1的節點，update[0]為score=21的節點。删除節點前的跳躍表如圖3-11所示。
2.設定span和forward
删除節點需要設定update數組中每個節點的span和forward。
假設x的第i層的span值為a，update[i]第i層的span值為b，由于删除了一個節點，是以a+b-1的值就是update[i]第i層的span新值。update[i]的第i的新forward就是x節點第i層的forward，這個類似連結清單删除元素的操作。
如果update[i]第i層的forward不為x，說明update[i]的層高大于x的層高，即update[i]第i層指向了指向了x的後續節點或指向NULL。由于删除了一個節點，是以update[i]的leve[i]的span需要減1。
如果update[i]的forward不為x，在要删除的節點的高度小于跳躍表高度的情況下出現，i大于x高度的節點的forward與x無關，是以這些節點隻需更新其span減1即可。
設定span和forward的代碼如下。
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].span += x->level[i].span - 1;
update[i]->level[i].forward = x->level[i].forward;
} else {
update[i]->level[i].span -= 1;
}
}
} 設定span和forward後的跳躍表如圖3-12所示。
update節點更新完畢之後，需要更新backward指針、跳躍表高度和長度。如果x不為最後一個節點，直接将第0層後一個節點的backward指派為x的backward即可；否則，将跳躍表的尾指針指向x的backward節點即可。代碼如下。
if (x->level[0].forward) {
x->level[0].forward->backward = x->backward;
else {
zsl->tail = x->backward;
}
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--; 當删除的x節點是跳躍表的最高節點，并且沒有其他節點與x節點的高度相同時，需要将跳躍表的高度減1。
由于删除了一個節點，跳躍表的長度需要減1。
删除節點後的跳躍表如圖3-13所示。
3.3.4 删除跳躍表
擷取到跳躍表對象之後，從頭節點的第0層開始，通過forward指針逐漸向後周遊，每遇到一個節點便将釋放其記憶體。當所有節點的記憶體都被釋放之後，釋放跳躍表對象，即完成了跳躍表的删除操作。代碼如下。
void zslFree(zskiplist *zsl) {
zskiplistNode *node = zsl->header->level[0].forward, *next;
zfree(zsl->header);
while(node) {
next = node->level[0].forward;
zslFreeNode(node);
node = next;
}
zfree(zsl);
} 3.4 跳躍表的應用
在Redis中，跳躍表主要應用于有序集合的底層實作（有序集合的另一種實作方式為壓縮清單）。
Redis的配置檔案中關于有序集合底層實作的兩個配置。
1）zset-max-ziplist-entries 128：zset采用壓縮清單時，元素個數最大值。預設值為128。
2）zset-max-ziplist-value 64：zset采用壓縮清單時，每個元素的字元串長度最大值。預設值為64。
zset添加元素的主要邏輯位于t_zset.c的zaddGenericCommand函數中。zset插入第一個元素時，會判斷下面兩種條件：
- zset-max-ziplist-entries的值是否等于0；
- zset-max-ziplist-value小于要插入元素的字元串長度。
滿足任一條件Redis就會采用跳躍表作為底層實作，否則采用壓縮清單作為底層實作方式。
if (server.zset_max_ziplist_entries == 0 ||
server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
{
zobj = createZsetObject();//建立跳躍表結構
} else {
zobj = createZsetZiplistObject();//建立壓縮清單結構
} 一般情況下，不會将zset-max-ziplist-entries配置成0，元素的字元串長度也不會太長，是以在建立有序集合時，預設使用壓縮清單的底層實作。zset新插入元素時，會判斷以下兩種條件：
- zset中元素個數大于zset_max_ziplist_entries；
- 插入元素的字元串長度大于zset_max_ziplist_value。
當滿足任一條件時，Redis便會将zset的底層實作由壓縮清單轉為跳躍表。代碼如下。
if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries)
zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
if (sdslen(ele) > server.zset_max_ziplist_value)
zsetConvert(zobj,OBJ_ENCODING_SKIPLIST); 值得注意的是，zset在轉為跳躍表之後，即使元素被逐漸删除，也不會重新轉為壓縮清單。
3.5 本章小結
本章介紹了跳躍表的基本原理和實作過程。跳躍表的原理簡單，其查詢、插入、删除的平均複雜度都為O(logN)。跳躍表主要應用于有序集合的底層實作。