作者 | 京東云開(kāi)發(fā)者-京東物流 紀(jì)卓志

目前市面上充斥著大量關(guān)于跳躍表結(jié)構(gòu)與 Redis 的源碼解析，但是經(jīng)過(guò)長(zhǎng)期觀察后發(fā)現(xiàn)大都只是在停留在代碼的表面，而沒(méi)有系統(tǒng)性地介紹跳躍表的由來(lái)以及各種常量的由來(lái)。作為一種概率數(shù)據(jù)結(jié)構(gòu)，理解各種常量的由來(lái)可以更好地進(jìn)行變化并應(yīng)用到高性能功能開(kāi)發(fā)中。本文沒(méi)有重復(fù)地以對(duì)現(xiàn)有優(yōu)秀實(shí)現(xiàn)進(jìn)行代碼分析，而是通過(guò)對(duì)跳躍表進(jìn)行了系統(tǒng)性地介紹與形式化分析，并給出了在特定場(chǎng)景下的跳躍表擴(kuò)展方式，方便讀者更好地理解跳躍表數(shù)據(jù)結(jié)構(gòu)。

跳躍表 [1,2,3] 是一種用于在大多數(shù)應(yīng)用程序中取代平衡樹(shù)的概率數(shù)據(jù)結(jié)構(gòu)。跳躍表?yè)碛信c平衡樹(shù)相同的期望時(shí)間上界，并且更簡(jiǎn)單、更快、是用更少的空間。在查找與列表的線性操作上，比平衡樹(shù)更快，并且更簡(jiǎn)單。

概率平衡也可以被用在基于樹(shù)的數(shù)據(jù)結(jié)構(gòu) [4] 上，例如樹(shù)堆（Treap）。與平衡二叉樹(shù)相同，跳躍表也實(shí)現(xiàn)了以下兩種操作

通過(guò)搜索引用 [5]，可以保證從任意元素開(kāi)始，搜索到在列表中間隔為 k 的元素的任意期望時(shí)間是 O (logk)

實(shí)現(xiàn)線性表的常規(guī)操作（例如_將元素插入到列表第 k 個(gè)元素后面_）

這幾種操作在平衡樹(shù)中也可以實(shí)現(xiàn)，但是在跳躍表中實(shí)現(xiàn)起來(lái)更簡(jiǎn)單而且非常的快，并且通常情況下很難在平衡樹(shù)中直接實(shí)現(xiàn)（樹(shù)的線索化可以實(shí)現(xiàn)與鏈表相同的效果，但是這使得實(shí)現(xiàn)變得更加復(fù)雜 [6]）

預(yù)覽

最簡(jiǎn)單的支持查找的數(shù)據(jù)結(jié)構(gòu)可能就是鏈表。Figure.1 是一個(gè)簡(jiǎn)單的鏈表。在鏈表中執(zhí)行一次查找的時(shí)間正比于必須考查的節(jié)點(diǎn)個(gè)數(shù)，這個(gè)個(gè)數(shù)最多是 N。

Figure.1 Linked List

Figure.2 表示一個(gè)鏈表，在該鏈表中，每個(gè)一個(gè)節(jié)點(diǎn)就有一個(gè)附加的指針指向它在表中的前兩個(gè)位置上的節(jié)點(diǎn)。正因?yàn)檫@個(gè)前向指針，在最壞情況下最多考查?N/2?+1 個(gè)節(jié)點(diǎn)。

Figure.2 Linked List with fingers to the 2nd forward elements

Figure.3 將這種想法擴(kuò)展，每個(gè)序數(shù)是 4 的倍數(shù)的節(jié)點(diǎn)都有一個(gè)指針指向下一個(gè)序數(shù)為 4 的倍數(shù)的節(jié)點(diǎn)。只有?N/4?+2 個(gè)節(jié)點(diǎn)被考查。

Figure.3 Linked List with fingers to the 4th forward elements

這種跳躍幅度的一般情況如 Figure.4 所示。每個(gè) 2i 節(jié)點(diǎn)就有一個(gè)指針指向下一個(gè) 2i 節(jié)點(diǎn)，前向指針的間隔最大為 N/2。可以證明總的指針最大不會(huì)超過(guò) 2N（見(jiàn)空間復(fù)雜度分析），但現(xiàn)在在一次查找中最多考查?logN?個(gè)節(jié)點(diǎn)。這意味著一次查找中總的時(shí)間消耗為 O (logN)，也就是說(shuō)在這種數(shù)據(jù)結(jié)構(gòu)中的查找基本等同于二分查找（binary search）。

Figure.4 Linked List with fingers to the 2ith forward elements

在這種數(shù)據(jù)結(jié)構(gòu)中，每個(gè)元素都由一個(gè)節(jié)點(diǎn)表示。每個(gè)節(jié)點(diǎn)都有一個(gè)高度（height）或級(jí)別（level），表示節(jié)點(diǎn)所擁有的前向指針數(shù)量。每個(gè)節(jié)點(diǎn)的第 i 個(gè)前向指針指向下一個(gè)級(jí)別為 i 或更高的節(jié)點(diǎn)。

在前面描述的數(shù)據(jù)結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)的級(jí)別都是與元素?cái)?shù)量有關(guān)的，當(dāng)插入或刪除時(shí)需要對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行調(diào)整來(lái)滿足這樣的約束，這是很呆板且低效的。為此，可以_將每個(gè) 2i 節(jié)點(diǎn)就有一個(gè)指針指向下一個(gè) 2i 節(jié)點(diǎn)_的限制去掉，當(dāng)新元素插入時(shí)為每個(gè)新節(jié)點(diǎn)分配一個(gè)隨機(jī)的級(jí)別而不用考慮數(shù)據(jù)結(jié)構(gòu)的元素?cái)?shù)量。

Figure.5 Skip List

數(shù)據(jù)結(jié)構(gòu)

到此為止，已經(jīng)得到了所有讓鏈表支持快速查找的充要條件，而這種形式的數(shù)據(jù)結(jié)構(gòu)就是跳躍表。接下來(lái)將會(huì)使用更正規(guī)的方式來(lái)定義跳躍表

所有元素在跳躍表中都是由一個(gè)節(jié)點(diǎn)表示。

每個(gè)節(jié)點(diǎn)都有一個(gè)高度或級(jí)別，有時(shí)候也可以稱之為階（step），節(jié)點(diǎn)的級(jí)別是一個(gè)與元素總數(shù)無(wú)關(guān)的隨機(jī)數(shù)。規(guī)定 NULL 的級(jí)別是∞。

每個(gè)級(jí)別為 k 的節(jié)點(diǎn)都有 k 個(gè)前向指針，且第 i 個(gè)前向指針指向下一個(gè)級(jí)別為 i 或更高的節(jié)點(diǎn)。

每個(gè)節(jié)點(diǎn)的級(jí)別都不會(huì)超過(guò)一個(gè)明確的常量 MaxLevel。整個(gè)跳躍表的級(jí)別是所有節(jié)點(diǎn)的級(jí)別的最高值。如果跳躍表是空的，那么跳躍表的級(jí)別就是 1。

存在一個(gè)頭節(jié)點(diǎn) head，它的級(jí)別是 MaxLevel，所有高于跳躍表的級(jí)別的前向指針都指向 NULL。

稍后將會(huì)提到，節(jié)點(diǎn)的查找過(guò)程是在頭節(jié)點(diǎn)從最高級(jí)別的指針開(kāi)始，沿著這個(gè)級(jí)別一直走，直到找到大于正在尋找的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（或者是 NULL），在此過(guò)程中除了頭節(jié)點(diǎn)外并沒(méi)有使用到每個(gè)節(jié)點(diǎn)的級(jí)別，因此每個(gè)節(jié)點(diǎn)無(wú)需存儲(chǔ)節(jié)點(diǎn)的級(jí)別。

在跳躍表中，級(jí)別為 1 的前向指針與原始的鏈表結(jié)構(gòu)中 next 指針的作用完全相同，因此跳躍表支持所有鏈表支持的算法。

對(duì)應(yīng)到高級(jí)語(yǔ)言中的結(jié)構(gòu)定義如下所示（后續(xù)所有代碼示例都將使用 C 語(yǔ)言描述）

#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;
}

從前面的預(yù)覽章節(jié)中，不難看出 MaxLevel 的選值影響著跳躍表的查詢性能，關(guān)于 MaxLevel 的選值將會(huì)在后續(xù)章節(jié)中進(jìn)行介紹。在此先將 MaxLevel 定義為 32，這對(duì)于 232 個(gè)元素的跳躍表是足夠的。延續(xù)預(yù)覽章節(jié)中的描述，跳躍表的概率被定義為 0.5，關(guān)于這個(gè)值的選取問(wèn)題將會(huì)在后續(xù)章節(jié)中進(jìn)行詳細(xì)介紹。

算法

搜索

在跳躍表中進(jìn)行搜索的過(guò)程，是通過(guò) Z 字形遍歷所有沒(méi)有超過(guò)要尋找的目標(biāo)元素的前向指針來(lái)完成的。在當(dāng)前級(jí)別沒(méi)有可以移動(dòng)的前向指針時(shí)，將會(huì)移動(dòng)到下一級(jí)別進(jìn)行搜索。直到在級(jí)別為 1 的時(shí)候且沒(méi)有可以移動(dòng)的前向指針時(shí)停止搜索，此時(shí)直接指向的節(jié)點(diǎn)（級(jí)別為 1 的前向指針）就是包含目標(biāo)元素的節(jié)點(diǎn)（如果目標(biāo)元素在列表中的話）。在 Figure.6 中展示了在跳躍表中搜索元素 17 的過(guò)程。


Figure.6 A search path to find element 17 in Skip List 整個(gè)過(guò)程的示例代碼如下所示，因?yàn)楦呒?jí)語(yǔ)言中的數(shù)組下標(biāo)從 0 開(kāi)始，因此 forwards [0] 表示節(jié)點(diǎn)的級(jí)別為 1 的前向指針，依此類(lèi)推

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;
  }
}

插入和刪除

在插入和刪除節(jié)點(diǎn)的過(guò)程中，需要執(zhí)行和搜索相同的邏輯。在搜索的基礎(chǔ)上，需要維護(hù)一個(gè)名為 update 的向量，它維護(hù)的是搜索過(guò)程中跳躍表每個(gè)級(jí)別上遍歷到的最右側(cè)的值，表示插入或刪除的節(jié)點(diǎn)的左側(cè)直接直接指向它的節(jié)點(diǎn)，用于在插入或刪除后調(diào)整節(jié)點(diǎn)所在所有級(jí)別的前向指針（與樸素的鏈表節(jié)點(diǎn)插入或刪除的過(guò)程相同）。 當(dāng)新插入節(jié)點(diǎn)的級(jí)別超過(guò)當(dāng)前跳躍表的級(jí)別時(shí)，需要增加跳躍表的級(jí)別并將 update 向量中對(duì)應(yīng)級(jí)別的節(jié)點(diǎn)修改為 head 節(jié)點(diǎn)。 Figure.7 和 Figure.8 展示了在跳躍表中插入元素 16 的過(guò)程。首先，在 Figure.7 中執(zhí)行與搜索相同的查詢過(guò)程，在每個(gè)級(jí)別遍歷到的最后一個(gè)元素在對(duì)應(yīng)層級(jí)的前向指針被標(biāo)記為灰色，表示稍后將會(huì)對(duì)齊進(jìn)行調(diào)整。接下來(lái)在 Figure.8 中，在元素為 13 的節(jié)點(diǎn)后插入元素 16，元素 16 對(duì)應(yīng)的節(jié)點(diǎn)的級(jí)別是 5，這比跳躍表當(dāng)前級(jí)別要高，因此需要增加跳躍表的級(jí)別到 5，并將 head 節(jié)點(diǎn)對(duì)應(yīng)級(jí)別的前向指針標(biāo)記為灰色。Figure.8 中所有虛線部分都表示調(diào)整后的效果。

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;
}

在刪除節(jié)點(diǎn)后，如果刪除的節(jié)點(diǎn)是跳躍表中級(jí)別最大的節(jié)點(diǎn)，那么需要降低跳躍表的級(jí)別。 Figure.9 和 Figure.10 展示了在跳躍表中刪除元素 19 的過(guò)程。首先，在 Figure.9 中執(zhí)行與搜索相同的查詢過(guò)程，在每個(gè)級(jí)別遍歷到的最后一個(gè)元素在對(duì)應(yīng)層級(jí)的前向指針被標(biāo)記為灰色，表示稍后將會(huì)對(duì)齊進(jìn)行調(diào)整。接下來(lái)在 Figure.10 中，首先通過(guò)調(diào)整前向指針將元素 19 對(duì)應(yīng)的節(jié)點(diǎn)從跳躍表中卸載，因?yàn)樵?19 對(duì)應(yīng)的節(jié)點(diǎn)是級(jí)別最高的節(jié)點(diǎn)，因此將其從跳躍表中移除后需要調(diào)整跳躍表的級(jí)別。Figure.10 中所有虛線部分都表示調(diào)整后的效果。 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;
}

生成隨機(jī)級(jí)別

int SkipListRandomLevel() {
  int level;
  level = 1;
  while (random() < RAND_MAX * SKIP_LIST_P && level <= SKIP_LIST_MAX_LEVEL) {
    level++;
  }
  return level;
}

以下表格為按上面算法執(zhí)行 232 次后，所生成的隨機(jī)級(jí)別的分布情況。

1	2	3	4	5	6	7	8
2147540777	1073690199	536842769	268443025	134218607	67116853	33563644	16774262
9	10	11	12	13	14	15	16
8387857	4193114	2098160	1049903	523316	262056	131455	65943
17	18	19	20	21	22	23	24
32611	16396	8227	4053	2046	1036	492	249
25	26	27	28	29	30	31	32
121	55	34	16	7	9	2	1

MaxLevel 的選擇

在 Figure.4 中曾給出過(guò)對(duì)于 10 個(gè)元素的跳躍表最理想的分布情況，其中 5 個(gè)節(jié)點(diǎn)的級(jí)別是 1，3 個(gè)節(jié)點(diǎn)的級(jí)別是 2，1 個(gè)節(jié)點(diǎn)的級(jí)別是 3，1 個(gè)節(jié)點(diǎn)的級(jí)別是 4。 這引申出一個(gè)問(wèn)題：既然相同元素?cái)?shù)量下，跳躍表的級(jí)別不同會(huì)有不同的性能，那么跳躍表的級(jí)別為多少才合適？

分析

空間復(fù)雜度分析

前面提到過(guò)，分?jǐn)?shù) p 代表節(jié)點(diǎn)同時(shí)帶有第 i 層前向指針和第 i+1 層前向指針的概率，而每個(gè)節(jié)點(diǎn)的級(jí)別最少是 1，因此級(jí)別為 i 的前向指針數(shù)為 npi?1。定義 S (n) 表示所有前向指針的總量，由等比數(shù)列求和公式可得 對(duì) S (n) 求極限，有 易證，這是一個(gè)關(guān)于 p 的單調(diào)遞增函數(shù)，因此 p 的值越大，跳躍表中前向指針的總數(shù)越多。因?yàn)?1?p 是已知的常數(shù)，所以說(shuō)跳躍表的空間復(fù)雜度是 O (n)。

時(shí)間復(fù)雜度分析

非形式化分析

形式化分析

延續(xù)_分?jǐn)?shù) p 代表節(jié)點(diǎn)同時(shí)帶有第 i 層前向指針和第 i+1 層前向指針的概率_的定義，考慮反方向分析搜索路徑。 搜索的路徑總是小于必須執(zhí)行的比較的次數(shù)的。首先需要考查從級(jí)別 1（在搜索到元素前遍歷的最后一個(gè)節(jié)點(diǎn)）爬升到級(jí)別 L (n) 所需要反向跟蹤的指針數(shù)量。雖然在搜索時(shí)可以確定每個(gè)節(jié)點(diǎn)的級(jí)別都是已知且確定的，在這里仍認(rèn)為只有當(dāng)整個(gè)搜索路徑都被反向追蹤后才能被確定，并且在爬升到級(jí)別 L (n) 之前都不會(huì)接觸到 head 節(jié)點(diǎn)。 在爬升過(guò)程中任何特定的點(diǎn)，都認(rèn)為是在元素 x 的第 i 個(gè)前向指針，并且不知道元素 x 左側(cè)所有元素的級(jí)別或元素 x 的級(jí)別，但是可以知道元素 x 的級(jí)別至少是 i。元素 x 的級(jí)別大于 i 的概率是 p，可以通過(guò)考慮視認(rèn)為這個(gè)反向爬升的過(guò)程是一系列由成功的爬升到更高級(jí)別或失敗地向左移動(dòng)的隨機(jī)獨(dú)立實(shí)驗(yàn)。 在爬升到級(jí)別 L (n) 過(guò)程中，向左移動(dòng)的次數(shù)等于在連續(xù)隨機(jī)試驗(yàn)中第 L (n)?1 次成功前的失敗的次數(shù)，這符合負(fù)二項(xiàng)分布。期望的向上移動(dòng)次數(shù)一定是 L (n)?1。因此可以得到無(wú)限列表中爬升到 L (n) 的代價(jià) C C=prob (L (n)?1)+NB (L (n)?1,p) 列表長(zhǎng)度無(wú)限大是一個(gè)悲觀的假設(shè)。當(dāng)反向爬升的過(guò)程中接觸到 head 節(jié)點(diǎn)時(shí)，可以直接向上爬升而不需要任何向左移動(dòng)。因此可以得到 n 個(gè)元素列表中爬升到 L (n) 的代價(jià) C (n) C(n)≤probC=prob(L(n)?1)+NB(L(n)?1,p) 因此 n 個(gè)元素列表中爬升到 L (n) 的代價(jià) C (n) 的數(shù)學(xué)期望和方差為

因?yàn)?1/p 是已知常數(shù)，因此跳躍表的搜索、插入和刪除的時(shí)間復(fù)雜度都是 O (logn)。

P 的選擇

Figure.11 Normalized search times

擴(kuò)展

快速隨機(jī)訪問(wèn)

#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;
}

接下來(lái)需要修改插入和刪除操作，來(lái)保證在跳躍表修改后跨度的數(shù)據(jù)完整性。

需要注意的是，在插入過(guò)程中需要使用 indices 記錄在每個(gè)層級(jí)遍歷到的最后一個(gè)元素的位置，這樣通過(guò)做簡(jiǎn)單的減法操作就可以知道每個(gè)層級(jí)遍歷到的最后一個(gè)元素到新插入節(jié)點(diǎn)的跨度。

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;
}

當(dāng)實(shí)現(xiàn)了快速隨機(jī)訪問(wèn)之后，通過(guò)簡(jiǎn)單的指針操作即可實(shí)現(xiàn)區(qū)間查詢功能。

審核編輯：湯梓紅