[[410384]]

本文轉載自微信公眾號「JavaKeeper」，作者海星。轉載本文請聯(lián)系JavaKeeper公眾號。

干過服務端開發(fā)的應該都知道 Redis 的 ZSet 使用跳表實現(xiàn)的(當然還有壓縮列表、哈希表)，我就不從 1990 年的那個美國大佬 William Pugh 發(fā)表的那篇論文開始了，直接開跳

文章攏共兩部分

• 跳表是怎么搞的
• Redis 是怎么想的

一、跳表

跳表的簡歷

跳表，英文名：Skip List

父親：從英文名可以看出來，它首先是個 List，實際上，它是在有序鏈表的基礎上發(fā)展起來的

競爭對手：跳表(skip list)對標的是平衡樹(AVL Tree)

優(yōu)點：是一種 插入/刪除/搜索 都是 的數(shù)據(jù)結構。它最大的優(yōu)勢是原理簡單、容易實現(xiàn)、方便擴展、效率更高

跳表的基本思想

一如往常，采用循序漸進的手法帶你窺探 William Pugh 的小心思~

前提：跳表處理的是有序的鏈表，所以我們先看個不能再普通了的有序列表(一般是雙向鏈表)

如果我們想查找某個數(shù)，只能遍歷鏈表逐個比對，時間復雜度 ，插入和刪除操作都一樣。

為了提高查找效率，我們對鏈表做個”索引“

像這樣，我們每隔一個節(jié)點取一個數(shù)據(jù)作為索引節(jié)點(或者增加一個指針)，比如我們要找 31 直接在索引鏈表就找到了(遍歷 3 次)，如果找 16 的話，在遍歷到 31的時候，發(fā)現(xiàn)大于目標節(jié)點，就跳到下一層，接著遍歷~ (藍線表示搜索路徑)

恩，如果你數(shù)了下遍歷次數(shù)，沒錯，加不加索引都是 4 次遍歷才能找到 16，這是因為數(shù)據(jù)量太少，

數(shù)據(jù)量多的話，我們也可以多建幾層索引，如下 4 層索引，效果就比較明顯了

每加一層索引，我們搜索的時間復雜度就降為原來的

加了幾層索引，查找一個節(jié)點需要遍歷的節(jié)點個數(shù)明線減少了，效率提高不少，bingo~

有沒有似曾相識的感覺，像不像二分查找或者二叉搜索樹，通過索引來跳過大量的節(jié)點，從而提高搜索效率。

這樣的多層鏈表結構，就是『跳表』了~~

那到底提高了多少呢?

推理一番：

1. 如果一個鏈表有 n 個結點，如果每兩個結點抽取出一個結點建立索引的話，那么第一級索引的結點數(shù)大約就是 n/2，第二級索引的結點數(shù)大約為 n/4，以此類推第 m 級索引的節(jié)點數(shù)大約為 。
2. 假如一共有 m 級索引，第 m 級的結點數(shù)為兩個，通過上邊我們找到的規(guī)律，那么得出 ，從而求得 m=-1。如果加上原始鏈表，那么整個跳表的高度就是 。
3. 我們在查詢跳表的時候，如果每一層都需要遍歷 k 個結點，那么最終的時間復雜度就為 。
4. 那這個 k 值為多少呢，按照我們每兩個結點提取一個基點建立索引的情況，我們每一級最多需要遍歷兩個節(jié)點，所以 k=2。

為什么每一層最多遍歷兩個結點呢?

因為我們是每兩個節(jié)點提取一個節(jié)點建立索引，最高一級索引只有兩個節(jié)點，然后下一層索引比上一層索引兩個結點之間增加了一個結點，也就是上一層索引兩結點的中值，看到這里是不是想起了二分查找，每次我們只需要判斷要找的值在不在當前節(jié)點和下一個節(jié)點之間就可以了。

不信，你照著下圖比劃比劃，看看同一層能畫出 3 條線不~~

5.既然知道了每一層最多遍歷兩個節(jié)點，那跳表查詢數(shù)據(jù)的時間復雜度就是，常數(shù) 2 忽略不計，就是了。

空間換時間

跳表的效率比鏈表高了，但是跳表需要額外存儲多級索引，所以需要更多的內存空間。

跳表的空間復雜度分析并不難，如果一個鏈表有 n 個節(jié)點，每兩個節(jié)點抽取出一個節(jié)點建立索引的話，那么第一級索引的節(jié)點數(shù)大約就是 n/2，第二級索引的節(jié)點數(shù)大約為 n/4，以此類推第 m 級索引的節(jié)點數(shù)大約為，我們可以看出來這是一個等比數(shù)列。

這幾級索引的結點總和就是 n/2+n/4+n/8…+8+4+2=n-2，所以跳表的空間復雜度為。

實際上，在軟件開發(fā)中，我們不必太在意索引占用的額外空間。在講數(shù)據(jù)結構和算法時，我們習慣性地把要處理的數(shù)據(jù)看成整數(shù)，但是在實際的軟件開發(fā)中，原始鏈表中存儲的有可能是很大的對象，而索引結點只需要存儲關鍵值和幾個指針，并不需要存儲對象，所以當對象比索引結點大很多時，那索引占用的額外空間就可以忽略了。

插入數(shù)據(jù)

其實插入數(shù)據(jù)和查找一樣，先找到元素要插入的位置，時間復雜度也是，但有個問題就是如果一直往原始列表里加數(shù)據(jù)，不更新我們的索引層，極端情況下就會出現(xiàn)兩個索引節(jié)點中間數(shù)據(jù)非常多，相當于退化成了單鏈表，查找效率直接變成

跳表索引動態(tài)更新

我們上邊建立索引層都是下層節(jié)點個數(shù)的 1/2，最高層索引的節(jié)點數(shù)就是 2 個，但是我們隨意插入或者刪除一個原有鏈表的節(jié)點，這個比例就肯定會被破壞。

作為一種動態(tài)數(shù)據(jù)結構，我們需要某種手段來維護索引與原始鏈表大小之間的平衡，也就是說，如果鏈表中節(jié)點多了，索引節(jié)點就相應地增加一些，避免復雜度退化。

如果重建索引的話，效率就不能保證了。

如果你了解紅黑樹、AVL 樹這樣平衡二叉樹，你就知道它們是通過左右旋的方式保持左右子樹的大小平衡，而跳表是通過隨機函數(shù)來維護前面提到的“平衡性”。

所以跳表(skip list)索性就不強制要求 1:2 了，一個節(jié)點要不要被索引，建幾層的索引，就隨意點吧，都在節(jié)點插入時由拋硬幣決定。

比如我們要插入新節(jié)點 X，那要不要為 X 向上建索引呢，就是拋硬幣決定的，正面的話建索引，否則就不建了，就是這么隨意(比如一個節(jié)點隨機出的層數(shù)是 3，那就把它鏈入到第1 層到第 3 層鏈表中，也就是我們除了原鏈表的之外再往上 2 層索引都加上)。

其實是因為我們不能預測跳表的添加和刪除操作，很難用一種有效的算法保證索引部分始終均勻。學過概率論的我們都知道拋硬幣雖然不能讓索引位置絕對均勻，當數(shù)量足夠多的時候最起碼可以保證大體上相對均勻。

刪除節(jié)點相對來說就容易很多了，在索引層找到節(jié)點的話，就順藤摸瓜逐個往下刪除該索引節(jié)點和原鏈表上的節(jié)點，如果哪一層索引節(jié)點被刪的就剩 1 個節(jié)點的話，直接把這一層搞掉就可以了。

其實跳表的思想很容易理解，可是架不住實戰(zhàn)，我們接著看實戰(zhàn)

跳表的實現(xiàn)

差不多了解了跳表，其實就是加了幾層索引的鏈表，一共有 N 層，以 0 ~ N 層表示，設第 0 層是原鏈表，抽取其中部分元素，在第 1 層形成新的鏈表，上下層的相同元素之間連起來;再抽取第 1 層部分元素，構成第 2 層，以此類推。

Leetcode 的題目：設計跳表(https://leetcode-cn.com/problems/design-skiplist/)

既然是鏈表結構，先搞個 Node

class Node{ 
    Integer value; //節(jié)點值 
    Node[] next; // 節(jié)點在不同層的下一個節(jié)點 
 
    public Node(Integer value,int size) { // 用size表示當前節(jié)點在跳表中索引幾層 
        this.value = value; 
        this.next = new Node[size]; 
    } 
} 

增刪改查來一套，先看下增加節(jié)點，上邊我們已經知道了，新增時候會隨機生成一個層數(shù)，看下網上大佬的解釋

執(zhí)行插入操作時計算隨機數(shù)的過程，是一個很關鍵的過程，它對 skiplist 的統(tǒng)計特性有著很重要的影響。這并不是一個普通的服從均勻分布的隨機數(shù)，它的計算過程如下：

首先，每個節(jié)點肯定都有第 1 層指針(每個節(jié)點都在第 1 層鏈表里)。

如果一個節(jié)點有第 i 層(i>=1)指針(即節(jié)點已經在第 1 層到第 i 層鏈表中)，那么它有第(i+1)層指針的概率為 p。

節(jié)點最大的層數(shù)不允許超過一個最大值，記為 MaxLevel。

這個計算隨機層數(shù)的代碼如下所示：

int randomLevel() 
    int level = 1; 
    while (Math.random()<p && level<MaxLevel){ 
        level ++ ; 
    } 
    return level; 

randomLevel() 包含兩個參數(shù)，一個是 p，一個是 MaxLevel。在 Redis 的 skiplist 實現(xiàn)中，這兩個參數(shù)的取值為：

p = 1/4 
MaxLevel = 32(5.0版本以后是64) 

所以我們和 Redis 一樣的設置

/** 
 * 最大層數(shù) 
 */ 
private static int DEFAULT_MAX_LEVEL = 32; 
 
/** 
 * 隨機層數(shù)概率，也就是隨機出的層數(shù)，在 第1層以上(不包括第一層)的概率，層數(shù)不超過maxLevel，層數(shù)的起始號為1 
 */ 
private static double DEFAULT_P_FACTOR = 0.25; 
 
/** 
 * 頭節(jié)點 
 */ 
Node head = new Node(null, DEFAULT_MAX_LEVEL);  
 
/** 
 * 表示當前nodes的實際層數(shù)，它從1開始 
 */ 
int currentLevel = 1;  

增

我覺得我寫的注釋還挺通俗易懂的(代碼參考了 leetcode 和 王爭老師的實現(xiàn))

public void add(int num) { 
  int level = randomLevel(); 
  Node newNode = new Node(num,level); 
 
  Node updateNode = head; 
 
  // 計算出當前num 索引的實際層數(shù)，從該層開始添加索引，逐步向下 
  for (int i = currentLevel-1; i>=0; i--) { 
    //找到本層最近離num最近的節(jié)點(剛好比它小的節(jié)點) 
    while ((updateNode.next[i])!=null && updateNode.next[i].value < num){ 
      updateNode = updateNode.next[i]; 
    } 
    //本次隨機的最高層才設值，如果是最后一個直接指向newNode,否則將newNode 鏈入鏈表 
    if (i<level){ 
      if (updateNode.next[i]==null){ 
        updateNode.next[i] = newNode; 
      }else{ 
        Node temp = updateNode.next[i]; 
        updateNode.next[i] = newNode; 
        newNode.next[i] = temp; 
      } 
    } 
  } 
  //如果隨機出來的層數(shù)比當前的層數(shù)還大，那么超過currentLevel的head 直接指向newNode 
  if (level > currentLevel){ 
    for (int i = currentLevel; i < level; i++) { 
      head.next[i] = newNode; 
    } 
    //更新層數(shù) 
    currentLevel = level; 
  } 
} 

刪

public boolean erase(int num) { 
  boolean flag = false; 
  Node searchNode = head; 
  //從最高層開始遍歷找 
  for (int i = currentLevel-1; i >=0; i--) { 
    //和新增一樣也需要找到離要刪除節(jié)點最近的辣個 
    while ((searchNode.next[i])!=null && searchNode.next[i].value < num){ 
      searchNode = searchNode.next[i]; 
    } 
    //如果有這樣的數(shù)值 
    if (searchNode.next[i]!=null && searchNode.next[i].value == num){ 
      //找到該層中該節(jié)點，把下一個節(jié)點過來，就刪除了 
      searchNode.next[i] = searchNode.next[i].next[i]; 
      flag = true; 
    } 
  } 
  return flag; 
} 

查

public Node search(int target) { 
  Node searchNode = head; 
  for (int i = currentLevel - 1; i >= 0; i--) { 
    while ((head.next[i]) != null && searchNode.next[i].value < target) { 
      searchNode = searchNode.next[i]; 
    } 
  } 
  if (searchNode.next[0] != null && searchNode.next[0].value == target) { 
    return searchNode.next[0]; 
  } else { 
    return null; 
  } 
} 

二、Redis 為什么選擇跳表?

跳表本質上也是一種查找結構，我們經常遇到的查找問題最常見的就是哈希表，還有就是各種平衡樹，跳表又不屬于這兩大陣營，那問題來了：

為什么 Redis 要用跳表來實現(xiàn)有序集合，而不是哈希表或者平衡樹(AVL、紅黑樹等)?

Redis 中的有序集合是通過跳表來實現(xiàn)的，嚴格點講，其實還用到了壓縮列表、哈希表。

Redis 提供了兩種編碼的選擇，根據(jù)數(shù)據(jù)量的多少進行對應的轉化 (源碼地址 )

• 當數(shù)據(jù)較少時，ZSet 是由一個 ziplist 來實現(xiàn)的
• 當數(shù)據(jù)多的時候，ZSet 是由一個 dict + 一個 skiplist 來實現(xiàn)的。簡單來講，dict 用來查詢數(shù)據(jù)到分數(shù)的對應關系，而 skiplist 用來根據(jù)分數(shù)查詢數(shù)據(jù)(可能是范圍查找)。

Redis 的跳躍表做了些修改

• 允許有重復的分值
• 對元素的比對不僅要比對他們的分值，還要比對他們的對象
• 每個跳躍表節(jié)點都帶有一個后退指針，它允許程序在執(zhí)行像 ZREVRANGE 這樣的命令時，從表尾向表頭遍歷跳躍表。

我們先看下 ZSet 常用的一些命令

主要操作就是增刪查一個數(shù)據(jù)，迭代數(shù)據(jù)、按區(qū)間查數(shù)據(jù)，看下原因

• 哈希表是無序的，且只能查找單個 key，不適宜范圍查找
• 插入、刪除、查找以及迭代輸出有序序列這幾個操作，紅黑樹也可以完成，時間復雜度跟跳表是一樣的。但是，按照區(qū)間來查找數(shù)據(jù)這個操作，紅黑樹的效率沒有跳表高(跳表只需要定位區(qū)間的起點，然后遍歷就行了)
• Redis 選跳表實現(xiàn)有序集合，還有其他各種原因，比如代碼實現(xiàn)相對簡單些，且更加靈活，它可以通過改變索引構建策略，有效平衡執(zhí)行效率和內存消耗。

扯點別的 | 這又是為什么?

有序集合的英文全稱明明是sorted sets，為啥叫 zset 呢?

Redis官網上沒有解釋，但是在 Github 上有人向作者提問了。作者是這么回答的哈哈哈

Hello. Z is as in XYZ, so the idea is, sets with another dimension: the order. It’s a far association… I know ??

原來前面的 Z 代表的是 XYZ 中的Z，最后一個英文字母，zset 是在說這是比 set 有更多一個維度的 set ??

是不沒道理?

更沒道理的還有，Redis 默認端口 6379 ，因為作者喜歡的一個叫 Merz 的女明星，其名字在手機上輸入正好對應號碼 6379，索性就把 Redis 的默認端口叫 6379 了…

小結

跳表使用空間換時間的設計思路，通過構建多級索引來提高查詢的效率，實現(xiàn)了基于鏈表的“二分查找”。

跳表是一種動態(tài)數(shù)據(jù)結構，支持快速地插入、刪除、查找操作，時間復雜度都是 。

Redis 的 zset 是一個復合結構，一方面它需要一個 hash 結構來存儲 value 和 score 的對應關系，另一方面需要提供按照 score 來排序的功能，還需要能夠指定 score 的范圍來獲取 value 列表的功能

Redis 中的有序集合是通過壓縮列表、哈希表和跳表的組合來實現(xiàn)的，當數(shù)據(jù)較少時，ZSet 是由一個 ziplist 來實現(xiàn)的。當數(shù)據(jù)多的時候，ZSet 是由一個dict + 一個 skiplist 來實現(xiàn)的

后續(xù)：MySQL 的 Innodb ，為什么不用 skiplist，而用 B+ Tree ?

參考

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf 原論文

Redis內部數(shù)據(jù)結構詳解(6)——skiplist 圖文并茂講解 skip list

https://leetcode-cn.com/problems/design-skiplist/

https://lotabout.me/2018/skip-list/

https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html

https://redisbook.readthedocs.io/en/latest/datatype/sorted_set.html#sorted-set-chapter