Redis底層探秘（二）：連結清單和跳躍表
連結清單簡介
連結清單提供了高效的節點重排能力，以及順序性的節點通路方式，并且可以通過增删節點來靈活地跳轉連結清單的長度。
作為一種常用資料結構，連結清單内置在很多進階的程式設計語言裡面，因為Redis使用C語言并沒有内置這種資料結構，是以Redis建構了自己的連結清單實作。
連結清單在Redis中的應用非常多，比如清單鍵的底層實作之一就是連結清單，釋出與訂閱、慢查詢、螢幕等功能也用到了連結清單，Redis伺服器本身還是用連結清單來儲存多個用戶端的狀态資訊，以及使用連結清單來建構用戶端輸出緩沖區(output buffer)。
連結清單和連結清單節點的實作
每個連結清單的節點都是一個adlist.h/ listNode結構
typedef struct listNode {
struct listNode *prev;//前置節點
struct listNode *next;//後置節點
void *value;//節點的值
} listNode; 
雖然使用多個listNode結構就可以組成連結清單，但使用adlist.h/ list來持有連結清單的話，操作起來會更友善。
typedef struct list {
//表頭節點
listNode *head;
//表尾節點
listNode *tail;
//節點值複制函數
void *(*dup)(void *ptr);
//節點值釋放制函數
void (*free)(void *ptr);
//節點值對比函數
int (*match)(void *ptr, void *key);
//連結清單所包含的節點數量
unsigned long len;
} list; 
Redis的連結清單特性總結
1、 雙端：連結清單節點帶有prev和next指針，擷取某個節點的前置節點和後置節點的複雜度都是O(1)。
2、 無環：表頭節點的prev指針和表位節點的next指針都指向null，對連結清單的通路以null為終點。
3、 帶表頭指針和表尾指針：通過list結構的head指針和tail指針，程式擷取連結清單的表頭節點和表尾節點的複雜度為O(1)。
4、 帶連結清單長度計數器：程式使用list結構的len屬性來對list持有的連結清單節點進行計數，是以擷取節點數量的複雜度為O(1)。
5、 多态：連結清單節點使用void *指針來儲存節點值，并且可以通過list結構的dup、free、match三個屬性為節點設定類型特定函數，是以連結清單可以用于儲存各種不同類型的值。
連結清單和連結清單節點的API
跳躍表(skipList)簡介
跳躍表(skipList)是一種有序資料結構，他通過在每個節點中維持多個指向其他節點的指針，進而達到快速通路節點的目的。
跳躍表支援評價O(logN)、最壞O(N)複雜度的節點查找，還可以通過順序性操作來批量處理節點。
在大部分情況下，跳躍表的效率可以和平衡樹相媲美，并且因為跳躍表的實作比平衡樹來得更簡單，是以有不少程式都是用跳躍表來代替平衡樹。
具體關于跳躍表的原理，可檢視這個《漫畫算法：什麼是跳躍表》http://blog.jobbole.com/111731/。
Redis使用跳躍表作為有序結合鍵的底層實作之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員時比較長的字元串時，redis就會使用跳躍表來作為有序集合鍵的底層實作。
Redis在兩個地方用到了跳躍表，一個是實作有序集合鍵，另一個是在叢集節點中用作内部資料結構。
跳躍表的實作
Redis的跳躍表由redis.h\zskiplistNode和redis.h/zskiplist兩個結構定義（最新版已經移動到server.h），其中zskiplistNode結構用于表示跳躍表節點，而zskiplist結構則用于儲存跳躍表節點的相關資訊，比如節點數量，以及指向表頭界定啊和表尾節點的指針等等。
上圖最左邊的就是zskiplist結構，該結構包含以下屬性：
1 header：指向跳躍表的表頭表頭節點。
2 tail：指向跳躍表的表尾節點。
3 level：記錄目前跳躍表内，層數最大的那個節點的層數（表頭節點的層數不計算在内）。
4 length：記錄跳躍表的長度，也即是，跳躍表目前包含節點的數量（表頭節點不計算在内）。
位于zskiplist結構右方的四個zskiplistNode結構，該結構包含一下屬性：
1 層（level）：節點中用L1、L2、L3等字樣标記節點的各個層，L1代表第一層，L2代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用于通路位于表尾方向的其他節點，而跨度則記錄了前進指針所指向節點和目前節點的舉例。在上圖中，連線上帶有數字的箭頭就代表前進指針，而那個數字就是跨度。當程式從表頭向表尾進行周遊時，通路會沿着層的前進指針進行。
2 後退指針：節點中用BW（backward）字樣标記節點的後退指針，他指向位于目前節點的前一個節點。後退指針在程式從表尾向表頭周遊時使用。
3 分值（score）：各個節點中的1.0、2.0和3.0是節點所儲存的分值。在跳躍表中，節點按各自所儲存的分值從小到大排量。
4 成員對象（obj）：各個節點中o1、o2和o3是節點所儲存的成員對象。
注意：表頭節點和其他節點的構造是一樣的；表頭節點也有後退指針、分值和成員對象，不過表頭節點的這些屬性不會被用到，是以圖中省略了。
跳躍表節點zskiplistNode
跳躍表節點由server.h\zskiplistNode結構定義
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
//成員對象
robj *obj;
//分值
double score;
//後退指針
struct zskiplistNode *backward;
//層
struct zskiplistLevel {
struct zskiplistNode *forward;//前進指針
unsigned int span;//跨度
} level[];
} zskiplistNode; 1、 層
跳躍表節點的level數組可以包含多個元素，每個元素都包含一個指向其他節點的指針，程式可以通這些層來加快通路其他節點的速度，一般來說，層數越多，通路其他節點的速度就越快。
每次建立一個新的跳躍表節點的時候，程式都根據幂次定律（power law，越大的數出現的機率越小）随機生成一個介于1和32之間的值作為level數組的大小，這個大小就是層的“高度”。下圖就是帶有不同層高的節點。
2、 前進指針
每個層都有一個指向表尾方向的前進指針，用于從表頭向表尾方向通路節點。下圖用虛線表示出了程式從表頭向表尾方向，周遊跳躍表中所有節點的路徑：
a 疊代程式首先通路跳躍表的第一個節點（表頭），然後從第四層的前進指針移動到表中的第二個節點。
b 在第二個節點時，程式沿着第二層的前進指針移動到表中第三個節點。
c 在第三個節點時，程式同樣沿着第二層的前進指針移動到表中的第四個節點。
d 當程式再次沿着第四個節點的前進指針移動式，他碰到一個null，程式知道這時已經到達了跳躍表的表尾，于是結束這次周遊。
3、跨度
層的跨度用于記錄兩個節點之間的距離：
a 兩個節點之間的跨度越大，他們相距得就越遠。
b 指向null的所有前進指針的跨度都為0，因為他們沒有連向任何節點。
初看上去，很容易以為跨度和周遊操作有關，但實際上并不是這樣，周遊操作隻使用前進指針就可以完成了，寬度實際上是用來計算排位（rank）的：在查找某個節點的過程中，将沿途通路過的所有層的跨度累計起來，得到的結果就是目标節點在跳躍表中的排位。
舉個例子，下圖用虛線标記了在跳躍表中查找分值為3.0、成員對象為o3的節點時，沿途經曆的層：查找的過程隻經過了一個層，并且層的跨度為3，是以目标節點在跳躍表中的排位為3。
再舉個例子，下圖用虛線标記了在跳躍表中查找分值為2.0、成員對象為o2的節點時，沿途經曆的層：在查找節點的過程中，程式經過了兩個跨度為1的節點，是以可以計算出，目标節點在跳躍表中的排位為2。
4、後退指針
節點的後退指針用于從表尾向表頭方向通路節點：跟可以一次跳過多個節點的前進指針不同，因為每個節點隻有一個後退指針，是以每次隻能後退至前一個節點。
下圖用虛線表示了如果從表尾向表頭周遊跳躍表中的所有節點。
5、分值和成員
節點的分值（score屬性）是一個double類型的浮點數，跳躍表中的所有節點都按照分值從小到大來排序。
節點的成員對象是一個指針，他指向一個字元串對象，而字元串對象則儲存着一個SDS值。
在同一個跳躍表中，各個節點儲存的成員對象必須是唯一的，但是多個節點儲存的分值卻可以是相同的：分值相同的節點按照成員對象在字典中的大小來進行排序，成員對象較小的節點會排在前面（靠近表頭方向），而成員對象較大的節點則會排在後面（靠近表尾的方向）。
舉個例子，在下圖所示的跳躍表中，三個跳躍表節點都儲存了相同的分值10086.0，但儲存成員對象o1的節點卻排在儲存成員對象o2和o3的節點之前，由順序可知，三個對象在字典中的排序哦o1<=o2<=o3。
跳躍表zskiplist
緊靠多個跳躍表節點就可以組成一個跳躍表，如下圖。
但通過使用一個zskiplist結構來持有這些節點，程式可以更友善地對整個跳躍表進行處理，比如快速通路跳躍表的表頭節點和表尾節點，或者快速地擷取跳躍表節點的數量等資訊。
typedef struct zskiplist {
//表頭節點和表尾節點
struct zskiplistNode *header, *tail;
//表中節點的的數量
unsigned long length;
//表中層數最大的節點層數
int level;
} zskiplist; header和tail指針分别指向跳躍表的表頭和表尾節點，通過這兩個指針，程式定位表頭及诶點和表尾節點的複雜度為O(1)。
通過使用length屬性來記錄節點的數量，程式可以在O(1)複雜度内傳回跳躍表的長度。
level屬性則用于在O(1)複雜度内擷取跳躍表中層高最大的那個節點的層數量，注意表頭節點的層高并不計算在内。
跳躍表API