作者：京東物流 紀卓志
目前市面上充斥著大量關于跳躍表結構與Redis的源碼解析，但是經過長期觀察后發現大都只是在停留在代碼的表面，而沒有系統性地介紹跳躍表的由來以及各種常量的由來。作為一種概率數據結構，理解各種常量的由來可以更好地進行變化并應用到高性能功能開發中。本文沒有重復地以對現有優秀實現進行代碼分析，而是通過對跳躍表進行了系統性地介紹與形式化分析，并給出了在特定場景下的跳躍表擴展方式，方便讀者更好地理解跳躍表數據結構。
?
跳躍表[1,2,3]是一種用于在大多數應用程序中取代平衡樹的概率數據結構。跳躍表擁有與平衡樹相同的期望時間上界，并且更簡單、更快、是用更少的空間。在查找與列表的線性操作上，比平衡樹更快，并且更簡單。
概率平衡也可以被用在基于樹的數據結構[4]上，例如樹堆（Treap）。與平衡二叉樹相同，跳躍表也實現了以下兩種操作
- 通過搜索引用[5]，可以保證從任意元素開始，搜索到在列表中間隔為k的元素的任意期望時間是O(logk)
- 實現線性表的常規操作（例如將元素插入到列表第k個元素后面）
這幾種操作在平衡樹中也可以實現，但是在跳躍表中實現起來更簡單而且非常的快，并且通常情況下很難在平衡樹中直接實現（樹的線索化可以實現與鏈表相同的效果，但是這使得實現變得更加復雜[6]）
預覽
最簡單的支持查找的數據結構可能就是鏈表。Figure.1是一個簡單的鏈表。在鏈表中執行一次查找的時間正比于必須考查的節點個數，這個個數最多是N。
?
Figure.1 Linked List
Figure.2表示一個鏈表，在該鏈表中，每個一個節點就有一個附加的指針指向它在表中的前兩個位置上的節點。正因為這個前向指針，在最壞情況下最多考查?N/2?+1個節點。
?
Figure.2 Linked List with fingers to the 2nd forward elements
Figure.3將這種想法擴展，每個序數是4的倍數的節點都有一個指針指向下一個序數為4的倍數的節點。只有?N/4?+2個節點被考查。
?
Figure.3 Linked List with fingers to the 4th forward elements
這種跳躍幅度的一般情況如Figure.4所示。每個2i節點就有一個指針指向下一個2i節點，前向指針的間隔最大為N/2?？梢宰C明總的指針最大不會超過2N（見空間復雜度分析），但現在在一次查找中最多考查?logN?個節點。這意味著一次查找中總的時間消耗為O(logN)，也就是說在這種數據結構中的查找基本等同于二分查找（binary search）。
?
Figure.4 Linked List with fingers to the 2ith forward elements
在這種數據結構中，每個元素都由一個節點表示。每個節點都有一個高度（height）或級別（level），表示節點所擁有的前向指針數量。每個節點的第i個前向指針指向下一個級別為i或更高的節點。
在前面描述的數據結構中，每個節點的級別都是與元素數量有關的，當插入或刪除時需要對數據結構進行調整來滿足這樣的約束，這是很呆板且低效的。為此，可以將每個2i節點就有一個指針指向下一個2i節點的限制去掉，當新元素插入時為每個新節點分配一個隨機的級別而不用考慮數據結構的元素數量。
雖然無法通過元素數量來確定每個節點的級別，但是通過考查Figure.1到Figure.4中的節點分布規律不難發現，隨著級別的增加，當前級別的節點數量成比例減少。在Figure.1到Figure.4中，這個比例是12，也就是說只有12i個節點的級別是i，隨機選擇節點的級別的概率分布遵循P(X)=(12)X。所以Figure.5也可以認為是這種數據結構的一個實例。
?
Figure.5 Skip List
數據結構
到此為止，已經得到了所有讓鏈表支持快速查找的充要條件，而這種形式的數據結構就是跳躍表。接下來將會使用更正規的方式來定義跳躍表
- 所有元素在跳躍表中都是由一個節點表示。
- 每個節點都有一個高度或級別，有時候也可以稱之為階（step），節點的級別是一個與元素總數無關的隨機數。規定NULL的級別是∞。
- 每個級別為k的節點都有k個前向指針，且第i個前向指針指向下一個級別為i或更高的節點。
- 每個節點的級別都不會超過一個明確的常量MaxLevel。整個跳躍表的級別是所有節點的級別的最高值。如果跳躍表是空的，那么跳躍表的級別就是1。
- 存在一個頭節點head，它的級別是MaxLevel，所有高于跳躍表的級別的前向指針都指向NULL。
稍后將會提到，節點的查找過程是在頭節點從最高級別的指針開始，沿著這個級別一直走，直到找到大于正在尋找的節點的下一個節點（或者是NULL），在此過程中除了頭節點外并沒有使用到每個節點的級別，因此每個節點無需存儲節點的級別。
在跳躍表中，級別為1的前向指針與原始的鏈表結構中next指針的作用完全相同，因此跳躍表支持所有鏈表支持的算法。
對應到高級語言中的結構定義如下所示（后續所有代碼示例都將使用C語言描述）
#define SKIP_LIST_KEY_TYPE int #define SKIP_LIST_VALUE_TYPE int #define SKIP_LIST_MAX_LEVEL 32 #define SKIP_LIST_P 0.5 struct Node { SKIP_LIST_KEY_TYPE key; SKIP_LIST_VALUE_TYPE value; struct Node *forwards[]; // flexible array member }; struct SkipList { struct Node *head; int level; }; struct Node *CreateNode(int level) { struct Node *node; assert(level > 0); node = malloc(sizeof(struct Node) + sizeof(struct Node *) * level); return node; } struct SkipList *CreateSkipList() { struct SkipList *list; struct Node *head; int i; list = malloc(sizeof(struct SkipList)); head = CreateNode(SKIP_LIST_MAX_LEVEL); for (i = 0; i < SKIP_LIST_MAX_LEVEL; i++) { head->forwards[i] = NULL; } list->head = head; list->level = 1; return list; }
?
從前面的預覽章節中，不難看出MaxLevel的選值影響著跳躍表的查詢性能，關于MaxLevel的選值將會在后續章節中進行介紹。在此先將MaxLevel定義為32，這對于232個元素的跳躍表是足夠的。延續預覽章節中的描述，跳躍表的概率被定義為0.5，關于這個值的選取問題將會在后續章節中進行詳細介紹。
算法
搜索
在跳躍表中進行搜索的過程，是通過Z字形遍歷所有沒有超過要尋找的目標元素的前向指針來完成的。在當前級別沒有可以移動的前向指針時，將會移動到下一級別進行搜索。直到在級別為1的時候且沒有可以移動的前向指針時停止搜索，此時直接指向的節點（級別為1的前向指針）就是包含目標元素的節點（如果目標元素在列表中的話）。在Figure.6中展示了在跳躍表中搜索元素17的過程。
?
Figure.6 A search path to find element 17 in Skip List
整個過程的示例代碼如下所示，因為高級語言中的數組下標從0開始，因此forwards[0]表示節點的級別為1的前向指針，依此類推
struct Node *SkipListSearch(struct SkipList *list, SKIP_LIST_KEY_TYPE target) { struct Node *current; int i; current = list->head; for (i = list->level - 1; i >= 0; i--) { while (current->forwards[i] && current->forwards[i]->key < target) { current = current->forwards[i]; } } current = current->forwards[0]; if (current->key == target) { return current; } else { return NULL; } }
?
插入和刪除
在插入和刪除節點的過程中，需要執行和搜索相同的邏輯。在搜索的基礎上，需要維護一個名為update的向量，它維護的是搜索過程中跳躍表每個級別上遍歷到的最右側的值，表示插入或刪除的節點的左側直接直接指向它的節點，用于在插入或刪除后調整節點所在所有級別的前向指針（與樸素的鏈表節點插入或刪除的過程相同）。
當新插入節點的級別超過當前跳躍表的級別時，需要增加跳躍表的級別并將update向量中對應級別的節點修改為head節點。
Figure.7和Figure.8展示了在跳躍表中插入元素16的過程。首先，在Figure.7中執行與搜索相同的查詢過程，在每個級別遍歷到的最后一個元素在對應層級的前向指針被標記為灰色，表示稍后將會對齊進行調整。接下來在Figure.8中，在元素為13的節點后插入元素16，元素16對應的節點的級別是5，這比跳躍表當前級別要高，因此需要增加跳躍表的級別到5，并將head節點對應級別的前向指針標記為灰色。Figure.8中所有虛線部分都表示調整后的效果。
?
Figure.7 Search path for inserting element 16
?
Figure.8 Insert element 16 and adjust forward pointers
struct Node *SkipListInsert(struct SkipList *list, SKIP_LIST_KEY_TYPE key, SKIP_LIST_VALUE_TYPE value) { struct Node *update[SKIP_LIST_MAX_LEVEL]; struct Node *current; int i; int level; current = list->head; for (i = list->level - 1; i >= 0; i--) { while (current->forwards[i] && current->forwards[i]->key < target) { current = current->forwards[i]; } update[i] = current; } current = current->forwards[0]; if (current->key == target) { current->value = value; return current; } level = SkipListRandomLevel(); if (level > list->level) { for (i = list->level; i < level; i++) { update[i] = list->header; } } current = CreateNode(level); current->key = key; current->value = value; for (i = 0; i < level; i++) { current->forwards[i] = update[i]->forwards[i]; update[i]->forwards[i] = current; } return current; }
?
在刪除節點后，如果刪除的節點是跳躍表中級別最大的節點，那么需要降低跳躍表的級別。
Figure.9和Figure.10展示了在跳躍表中刪除元素19的過程。首先，在Figure.9中執行與搜索相同的查詢過程，在每個級別遍歷到的最后一個元素在對應層級的前向指針被標記為灰色，表示稍后將會對齊進行調整。接下來在Figure.10中，首先通過調整前向指針將元素19對應的節點從跳躍表中卸載，因為元素19對應的節點是級別最高的節點，因此將其從跳躍表中移除后需要調整跳躍表的級別。Figure.10中所有虛線部分都表示調整后的效果。
?
Figure.9 Search path for deleting element 19
?
Figure.10 Delete element 19 and adjust forward pointers
struct Node *SkipListDelete(struct SkipList *list, SKIP_LIST_KEY_TYPE key) { struct Node *update[SKIP_LIST_MAX_LEVEL]; struct Node *current; int i; current = list->head; for (i = list->level - 1; i >= 0; i--) { while (current->forwards[i] && current->forwards[i]->key < key) { current = current->forwards[i]; } update[i] = current; } current = current->forwards[0]; if (current && current->key == key) { for (i = 0; i < list->level; i++) { if (update[i]->forwards[i] == current) { update[i]->forwards[i] = current->forwards[i]; } else { break; } } while (list->level > 1 && list->head->forwards[list->level - 1] == NULL) { list->level--; } } return current; }
?
生成隨機級別
在前面提到過，隨機選擇節點的級別的概率分布遵循概率為12的指數分布，也就是說第i+1層的節點數量是第i層的一半。為了避免使用魔法值，定義一個分數p代表節點同時帶有第i層前向指針和第i+1層前向指針的概率（在之前的討論中，p=12）。節點的級別可以使用如下方法隨機生成，在這個算法中節點的級別可以在不依賴跳躍表元素數量的前提下生成
int SkipListRandomLevel() { int level; level = 1; while (random() < RAND_MAX * SKIP_LIST_P && level <= SKIP_LIST_MAX_LEVEL) { level++; } return level; }
?
以下表格為按上面算法執行232次后，所生成的隨機級別的分布情況。
MaxLevel的選擇
在Figure.4中曾給出過對于10個元素的跳躍表最理想的分布情況，其中5個節點的級別是1，3個節點的級別是2，1個節點的級別是3，1個節點的級別是4。
這引申出一個問題：既然相同元素數量下，跳躍表的級別不同會有不同的性能，那么跳躍表的級別為多少才合適？
經過分析得出，跳躍表在級別L上期望的節點數量是1p，當L=log1pn時這是成立的[1]。在此可以定義L(n)來代表log1pn。
由于級別可以安全地限定在L(n)，可以選擇MaxLevel=L(N)（N是跳躍表中元素數量的上限）。如果p=12，那么MaxLevel=32就可以安全地包含最多232個元素。
分析
空間復雜度分析
前面提到過，分數p代表節點同時帶有第i層前向指針和第i+1層前向指針的概率，而每個節點的級別最少是1，因此級別為i的前向指針數為npi?1。定義S(n)表示所有前向指針的總量，由等比數列求和公式可得
S(n)=n?(1+p+p2+...+pL(n)?1)=n?1?pL(n)?11?p=n?1?plog1pn?11?p
對S(n)求極限，有
limn→+∞S(n)=n?11?p=n1?p
易證，這是一個關于p的單調遞增函數，因此p的值越大，跳躍表中前向指針的總數越多。因為1?p是已知的常數，所以說跳躍表的空間復雜度是O(n)。
時間復雜度分析
非形式化分析
延續前面的定義，分數p代表節點同時帶有第i層前向指針和第i+1層前向指針的概率，也就是說相鄰兩個級別為i+k(k>0)的節點中間期望有1p?1個級別為i的節點。
而通過考查Figure.6搜索路徑，不難發現，在級別i的搜索永遠不會觸達級別大于i的節點（因為級別大于i的節點已經在級別i+k(k>0)的搜索中被否決），因此可以認為在理想情況下每一層最多只需要訪問1p個節點。
由搜索是通過Z字形遍歷所有沒有超過要尋找的目標元素的前向指針來完成的，因此搜索總是需要經過L(n)層。所以期望的訪問次數是1pL(n)，因為L(n)=log1pn，所以期望的訪問次數是1plog1pn，因為1/p是可以確定的常數，因此跳躍表的搜索、插入和刪除的時間復雜度都是O(logn)
形式化分析
定義1. $={prob} and \le{prob}：定義：定義X和和Y是兩個非負的無關的隨機變量（通常來說，是兩個非負的無關的隨機變量（通常來說，X和和Y表示算法表示算法A_X和和A_Y的執行時間）。定義的執行時間）。定義X\le_{prob}Y當且僅當對于任意當且僅當對于任意t，，t在在X中出現的概率總是小于中出現的概率總是小于t在在Y$中出現的概率時為真。更加形式化的定義
X=probY if ?t,Prob{X>t}=Prob{Y>t}
X≤probYif?t,Prob{X>t}≤Prob{Y>t}
定義2. 負二項分布（NB(s,p)）[7]）：定義s為一個非負整數，并且p是概率。NB(s,p)表示一個在成功概率為p的情況下，重復執行隨機獨立試驗在第s次成功前的失敗次數的隨機變量。NB(s,p)的數學期望是s(1?p)/p，而方差是s(1?p)/p2。
延續分數p代表節點同時帶有第i層前向指針和第i+1層前向指針的概率的定義，考慮反方向分析搜索路徑。
搜索的路徑總是小于必須執行的比較的次數的。首先需要考查從級別1（在搜索到元素前遍歷的最后一個節點）爬升到級別L(n)所需要反向跟蹤的指針數量。雖然在搜索時可以確定每個節點的級別都是已知且確定的，在這里仍認為只有當整個搜索路徑都被反向追蹤后才能被確定，并且在爬升到級別L(n)之前都不會接觸到head節點。
在爬升過程中任何特定的點，都認為是在元素x的第i個前向指針，并且不知道元素x左側所有元素的級別或元素x的級別，但是可以知道元素x的級別至少是i。元素x的級別大于i的概率是p，可以通過考慮視認為這個反向爬升的過程是一系列由成功的爬升到更高級別或失敗地向左移動的隨機獨立實驗。
在爬升到級別L(n)過程中，向左移動的次數等于在連續隨機試驗中第L(n)?1次成功前的失敗的次數，這符合負二項分布。期望的向上移動次數一定是L(n)?1。因此可以得到無限列表中爬升到L(n)的代價C C=prob(L(n)?1)+NB(L(n)?1,p) 列表長度無限大是一個悲觀的假設。當反向爬升的過程中接觸到head節點時，可以直接向上爬升而不需要任何向左移動。因此可以得到n個元素列表中爬升到L(n)的代價C(n)
C(n)≤probC=prob(L(n)?1)+NB(L(n)?1,p)
因此n個元素列表中爬升到L(n)的代價C(n)的數學期望和方差為
?
因為1/p是已知常數，因此跳躍表的搜索、插入和刪除的時間復雜度都是O(logn)。
P的選擇
得到搜索代價為E(C(n))<1plog1pn后，可以分析p的選擇對E(C(n))的影響。為了更好的分析p對搜索時間的影響，需要對E(C(n))進行等價變換
E(C(n))<1plog1pn=ln(n)pln(1p)
不難看出，對于任意確定的n，ln(n)都是確定的，因此只需要分析1pln(1p)的變化趨勢就可以。為了更好的進行對比，以p=12為基礎值進行標準化，Figure.11就是隨著p的變化，搜索時間的變化趨勢，其中p=1e的點是搜索時間最好的點，但是二的整數次冪可以更好地進行隨機級別的生成。
?
Figure.11 Normalized search times
而前面分析空間復雜度時也確定了n1?p，空間用量隨著p減小而降低，因此p=14是優于p=12的，這也是Redis中使用p=0.25而不是p=0.5的一個原因。
擴展
快速隨機訪問
在跳躍表中通過前向引用實現了O(log1pn)時間復雜度的搜索、插入與刪除算法，但是對于隨機訪問數組中第i個元素操作仍需要O(i)時間。通過觀察Figure.7中的Z字形搜索路徑，不難發現，從頭節點到某個節點的路徑中所有前向指針的跨度的和，就是這個節點在跳躍表中的位置。那么通過在前向指針中維護當前節點到目標節點的跨度，就可以保證隨機訪問的時間復雜度也是O(log1pn)。
首先，需要對數據結構重新進行定義，在前向指針中增加跨度相關的記錄，并將其初始設置為0。此外，可以認為NULL在跳躍表中的位置永遠是跳躍表的長度（從0開始），因此需要在跳躍表中記錄總長度。
本節中的代碼參考自Redis的跳躍表實現[8], 為了與前面的代碼風格保持一致，進行了適當的修改
#define SKIP_LIST_KEY_TYPE int #define SKIP_LIST_VALUE_TYPE int #define SKIP_LIST_MAX_LEVEL 32 #define SKIP_LIST_P 0.5 struct Node; // forward definition struct Forward { struct Node *forward; int span; } struct Node { SKIP_LIST_KEY_TYPE key; SKIP_LIST_VALUE_TYPE value; struct Forward forwards[]; // flexible array member }; struct SkipList { struct Node *head; int level; int length; }; struct Node *CreateNode(int level) { struct Node *node; assert(level > 0); node = malloc(sizeof(struct Node) + sizeof(struct Forward) * level); return node; } struct SkipList *CreateSkipList() { struct SkipList *list; struct Node *head; int i; list = malloc(sizeof(struct SkipList)); head = CreateNode(SKIP_LIST_MAX_LEVEL); for (i = 0; i < SKIP_LIST_MAX_LEVEL; i++) { head->forwards[i].forward = NULL; head->forwards[i].span = 0; } list->head = head; list->level = 1; return list; }
?
接下來需要修改插入和刪除操作，來保證在跳躍表修改后跨度的數據完整性。
需要注意的是，在插入過程中需要使用indices記錄在每個層級遍歷到的最后一個元素的位置，這樣通過做簡單的減法操作就可以知道每個層級遍歷到的最后一個元素到新插入節點的跨度。
struct Node *SkipListInsert(struct SkipList *list, SKIP_LIST_KEY_TYPE key, SKIP_LIST_VALUE_TYPE value) { struct Node *update[SKIP_LIST_MAX_LEVEL]; struct Node *current; int indices[SKIP_LIST_MAX_LEVEL]; int i; int level; current = list->head; for (i = list->level - 1; i >= 0; i--) { if (i == list->level - 1) { indices[i] = 0; } else { indices[i] = indices[i + 1]; } while (current->forwards[i].forward && current->forwards[i].forward->key < target) { indices[i] += current->forwards[i].span; current = current->forwards[i].forward; } update[i] = current; } current = current->forwards[0].forward; if (current->key == target) { current->value = value; return current; } level = SkipListRandomLevel(); if (level > list->level) { for (i = list->level; i < level; i++) { indices[i] = 0; update[i] = list->header; update[i]->forwards[i].span = list->length; } } current = CreateNode(level); current->key = key; current->value = value; for (i = 0; i < level; i++) { current->forwards[i].forward = update[i]->forwards[i].forward; update[i]->forwards[i].forward = current; current->forwards[i].span = update[i]->forwards[i].span - (indices[0] - indices[i]); update[i]->forwards[i].span = (indices[0] - indices[i]) + 1; } list.length++; return current; } struct Node *SkipListDelete(struct SkipList *list, SKIP_LIST_KEY_TYPE key) { struct Node *update[SKIP_LIST_MAX_LEVEL]; struct Node *current; int i; current = list->head; for (i = list->level - 1; i >= 0; i--) { while (current->forwards[i].forward && current->forwards[i].forward->key < key) { current = current->forwards[i].forward; } update[i] = current; } current = current->forwards[0].forward; if (current && current->key == key) { for (i = 0; i < list->level; i++) { if (update[i]->forwards[i].forward == current) { update[i]->forwards[i].forward = current->forwards[i]; update[i]->forwards[i].span += current->forwards[i].span - 1; } else { break; } } while (list->level > 1 && list->head->forwards[list->level - 1] == NULL) { list->level--; } } return current; }
?
當實現了快速隨機訪問之后，通過簡單的指針操作即可實現區間查詢功能。
參考文獻
- Pugh, W. (1989). A skip list cookbook. Tech. Rep. CS-TR-2286.1, Dept. of Computer Science, Univ. of Maryland, College Park, MD [July 1989]
- Pugh, W. (1989). Skip lists: A probabilistic alternative to balanced trees. Lecture Notes in Computer Science, 437–449. https://doi.org/10.1007/3-540-51542-9_36
- Weiss, M. A. (1996).?Data Structures and Algorithm Analysis in C (2nd Edition)?(2nd ed.). Pearson.
- Aragon, Cecilia & Seidel, Raimund. (1989). Randomized Search Trees. 540-545. 10.1109/SFCS.1989.63531.
- Wikipedia contributors. (2022b, November 22).?Finger search. Wikipedia. https://en.wikipedia.org/wiki/Finger_search
- Wikipedia contributors. (2022a, October 24).?Threaded binary tree. Wikipedia. https://en.wikipedia.org/wiki/Threaded_binary_tree
- Wikipedia contributors. (2023, January 4).?Negative binomial distribution. Wikipedia. https://en.wikipedia.org/wiki/Negative_binomial_distribution
- Redis contributors.?Redis ordered set implementation. GitHub. https://github.com/redis/redis
后續工作
- 確定性跳躍表
- 無鎖并發安全跳躍表
?