近幾年針對 Redis 面試時會涉及常見數(shù)據(jù)結構的底層設計，其中就有這么一道比較有意思的面試題：“Redis 的有序集合底層為什么要用跳表，而不用平衡樹、紅黑樹或者 B+樹？”。

本文就以這道大廠常問的面試題為切入點，帶大家詳細了解一下跳表這個數(shù)據(jù)結構。

本文整體脈絡如下圖所示，筆者會從有序集合的基本使用到跳表的源碼分析和實現(xiàn)，讓你會對 Redis 的有序集合底層實現(xiàn)的跳表有著更深刻的理解和掌握。

跳表在 Redis 中的運用

這里我們需要先了解一下 Redis 用到跳表的數(shù)據(jù)結構有序集合的使用，Redis 有個比較常用的數(shù)據(jù)結構叫**有序集合(sorted set，簡稱 zset)**，正如其名它是一個可以保證有序且元素唯一的集合，所以它經(jīng)常用于排行榜等需要進行統(tǒng)計排列的場景。

這里我們通過命令行的形式演示一下排行榜的實現(xiàn)，可以看到筆者分別輸入 3 名用戶：xiaoming、xiaohong、xiaowang，它們的score分別是 60、80、60，最終按照成績升級降序排列。

127.0.0.1:6379> zadd rankList 60 xiaoming
(integer) 1
127.0.0.1:6379> zadd rankList 80 xiaohong
(integer) 1
127.0.0.1:6379> zadd rankList 60 xiaowang
(integer) 1
# 返回有序集中指定區(qū)間內的成員，通過索引，分數(shù)從高到低
127.0.0.1:6379> ZREVRANGE rankList 0 100 WITHSCORES
1) "xiaohong"
2) "80"
3) "xiaowang"
4) "60"
5) "xiaoming"
6) "60"

此時我們通過 object 指令查看 zset 的數(shù)據(jù)結構，可以看到當前有序集合存儲的還是**ziplist(壓縮列表)**。

127.0.0.1:6379> object encoding rankList
"ziplist"

因為設計者考慮到 Redis 數(shù)據(jù)存放于內存，為了節(jié)約寶貴的內存空間，在有序集合元素小于 64 字節(jié)且個數(shù)小于 128 的時候，會使用 ziplist，而這個閾值的默認值的設置就來自下面這兩個配置項。

zset-max-ziplist-value 64
zset-max-ziplist-entries 128

一旦有序集合中的某個元素超出這兩個其中的一個閾值它就會轉為 skiplist（實際是 dict+skiplist，還會借用字典來提高獲取指定元素的效率）。

我們不妨在添加一個大于 64 字節(jié)的元素，可以看到有序集合的底層存儲轉為 skiplist。

127.0.0.1:6379> zadd rankList 90 yigemingzihuichaoguo64zijiedeyonghumingchengyongyuceshitiaobiaodeshijiyunyong
(integer) 1
# 超過閾值，轉為跳表
127.0.0.1:6379> object encoding rankList
"skiplist"

也就是說，ZSet 有兩種不同的實現(xiàn)，分別是 ziplist 和 skiplist，具體使用哪種結構進行存儲的規(guī)則如下：

• 當有序集合對象同時滿足以下兩個條件時，使用 ziplist：

• ZSet 保存的鍵值對數(shù)量少于 128 個；

  每個元素的長度小于 64 字節(jié)。

• 如果不滿足上述兩個條件，那么使用 skiplist 。

手寫一個跳表

為了更好的回答上述問題以及更好的理解和掌握跳表，這里可以通過手寫一個簡單的跳表的形式來幫助讀者理解跳表這個數(shù)據(jù)結構。

我們都知道有序鏈表在添加、查詢、刪除的平均時間復雜都都是O(n)即線性增長，所以一旦節(jié)點數(shù)量達到一定體量后其性能表現(xiàn)就會非常差勁。而跳表我們完全可以理解為在原始鏈表基礎上，建立多級索引，通過多級索引檢索定位將增刪改查的時間復雜度變?yōu)镺(log n)。

可能這里說的有些抽象，我們舉個例子，以下圖跳表為例，其原始鏈表存儲按序存儲 1-10，有 2 級索引，每級索引的索引個數(shù)都是基于下層元素個數(shù)的一半。

假如我們需要查詢元素 6，其工作流程如下：

• 從 2 級索引開始，先來到節(jié)點 4。
• 查看 4 的后繼節(jié)點，是 8 的 2 級索引，這個值大于 6，說明 2 級索引后續(xù)的索引都是大于 6 的，沒有再往后搜尋的必要，我們索引向下查找。
• 來到 4 的 1 級索引，比對其后繼節(jié)點為 6，查找結束。

相較于原始有序鏈表需要 6 次，我們的跳表通過建立多級索引，我們只需兩次就直接定位到了目標元素，其查尋的復雜度被直接優(yōu)化為**O(log n)**。

對應的添加也是一個道理，假如我們需要在這個有序集合中添加一個元素 7，那么我們就需要通過跳表找到小于元素 7 的最大值，也就是下圖元素 6 的位置，將其插入到元素 6 的后面，讓元素 6 的索引指向新插入的節(jié)點 7，其工作流程如下：

• 從 2 級索引開始定位到了元素 4 的索引。
• 查看索引 4 的后繼索引為 8，索引向下推進。
• 來到 1 級索引，發(fā)現(xiàn)索引 4 后繼索引為 6，小于插入元素 7，指針推進到索引 6 位置。
• 繼續(xù)比較 6 的后繼節(jié)點為索引 8，大于元素 7，索引繼續(xù)向下。
• 最終我們來到 6 的原始節(jié)點，發(fā)現(xiàn)其后繼節(jié)點為 7，指針沒有繼續(xù)向下的空間，自此我們可知元素 6 就是小于插入元素 7 的最大值，于是便將元素 7 插入。

這里我們又面臨一個問題，我們是否需要為元素 7 建立索引，索引多高合適？

我們上文提到，理想情況是每一層索引是下一層元素個數(shù)的二分之一，假設我們的總共有 16 個元素，對應各級索引元素個數(shù)應該是：

1. 一級索引:16/2=8
2. 二級索引:8/2 =4
3. 三級索引:4/2=2

由此我們用數(shù)學歸納法可知：

1. 一級索引:16/2=16/2^1=8
2. 二級索引:8/2 => 16/2^2 =4
3. 三級索引:4/2=>16/2^3=2

假設元素個數(shù)為 n，那么對應 k 層索引的元素個數(shù) r 計算公式為:

r=n/2^k

同理我們再來推斷以下索引的最大高度，一般來說最高級索引的元素個數(shù)為 2，我們設元素總個數(shù)為 n，索引高度為 h，代入上述公式可得：

2= n/2^h
=> 2*2^h=n
=> 2^(h+1)=n
=> h+1=log2^n
=> h=log2^n -1

而 Redis 又是內存數(shù)據(jù)庫，我們假設元素最大個數(shù)是65536，我們把65536代入上述公式可知最大高度為 16。所以我們建議添加一個元素后為其建立的索引高度不超過 16。

因為我們要求盡可能保證每一個上級索引都是下級索引的一半，在實現(xiàn)高度生成算法時，我們可以這樣設計：

• 跳表的高度計算從原始鏈表開始，即默認情況下插入的元素的高度為 1，代表沒有索引，只有元素節(jié)點。
• 設計一個為插入元素生成節(jié)點索引高度 level 的方法。
• 進行一次隨機運算，隨機數(shù)值范圍為 0-1 之間。
• 如果隨機數(shù)大于 0.5 則為當前元素添加一級索引，自此我們保證生成一級索引的概率為50%，這也就保證了 1 級索引理想情況下只有一半的元素會生成索引。
• 同理后續(xù)每次隨機算法得到的值大于 0.5 時，我們的索引高度就加 1，這樣就可以保證節(jié)點生成的 2 級索引概率為25%，3 級索引為 12.5%**……

我們回過頭，上述插入 7 之后，我們通過隨機算法得到 2，即要為其建立 1 級索引：

最后我們再來說說刪除，假設我們這里要刪除元素 10，我們必須定位到當前跳表各層元素小于 10 的最大值，索引執(zhí)行步驟為：

• 2 級索引 4 的后繼節(jié)點為 8，指針推進。
• 索引 8 無后繼節(jié)點，該層無要刪除的元素，指針直接向下。
• 1 級索引 8 后繼節(jié)點為 10，說明 1 級索引 8 在進行刪除時需要將自己的指針和 1 級索引 10 斷開聯(lián)系，將 10 刪除。
• 1 級索引完成定位后，指針向下，后繼節(jié)點為 9，指針推進。
• 9 的后繼節(jié)點為 10，同理需要讓其指向 null，將 10 刪除。

模板定義

有了整體的思路之后，我們可以開始實現(xiàn)一個跳表了，首先定義一下跳表中的節(jié)點Node，從上文的演示中可以看出每一個Node它都包含以下幾個元素：

• 存儲的value值。
• 后繼節(jié)點的地址。
• 多級索引。

為了更方便統(tǒng)一管理Node后繼節(jié)點地址和多級索引指向的元素地址，筆者在Node中設置了一個forwards數(shù)組，用于記錄原始鏈表節(jié)點的后繼節(jié)點和多級索引的后繼節(jié)點指向。

以下圖為例，我們forwards數(shù)組長度為 5，其中索引 0記錄的是原始鏈表節(jié)點的后繼節(jié)點地址，而其余自底向上表示從 1 級索引到 4 級索引的后繼節(jié)點指向。

于是我們的就有了這樣一個代碼定義，可以看出筆者對于數(shù)組的長度設置為固定的 16**(上文的推算最大高度建議是 16)，默認data為-1，節(jié)點最大高度maxLevel初始化為 1，注意這個maxLevel**的值代表原始鏈表加上索引的總高度。

/**
 * 跳表索引最大高度為16
 */
private static final int MAX_LEVEL = 16;
class Node {
    private int data = -1;
    private Node[] forwards = new Node[MAX_LEVEL];
    private int maxLevel = 0;
}

元素添加

定義好節(jié)點之后，我們先實現(xiàn)以下元素的添加，添加元素時首先自然是設置data這一步我們直接根據(jù)將傳入的value設置到data上即可。

然后就是高度maxLevel的設置 ，我們在上文也已經(jīng)給出了思路，默認高度為 1，即只有一個原始鏈表節(jié)點，通過隨機算法每次大于 0.5 索引高度加 1，由此我們得出高度計算的算法randomLevel()：

/**
 * 理論來講，一級索引中元素個數(shù)應該占原始數(shù)據(jù)的 50%，二級索引中元素個數(shù)占 25%，三級索引12.5% ，一直到最頂層。
 * 因為這里每一層的晉升概率是 50%。對于每一個新插入的節(jié)點，都需要調用 randomLevel 生成一個合理的層數(shù)。
 * 該 randomLevel 方法會隨機生成 1~MAX_LEVEL 之間的數(shù)，且 ：
 * 50%的概率返回 1
 * 25%的概率返回 2
 *  12.5%的概率返回 3 ...
 * @return
 */
private int randomLevel() {
    int level = 1;
    while (Math.random() > PROB && level < MAX_LEVEL) {
        ++level;
    }
    return level;
}

然后再設置當前要插入的Node和Node索引的后繼節(jié)點地址，這一步稍微復雜一點，我們假設當前節(jié)點的高度為 4，即 1 個節(jié)點加 3 個索引，所以我們創(chuàng)建一個長度為 4 的數(shù)組maxOfMinArr ，遍歷各級索引節(jié)點中小于當前value的最大值。

假設我們要插入的value為 5，我們的數(shù)組查找結果當前節(jié)點的前驅節(jié)點和 1 級索引、2 級索引的前驅節(jié)點都為 4，三級索引為空。

然后我們基于這個數(shù)組maxOfMinArr 定位到各級的后繼節(jié)點，讓插入的元素 5 指向這些后繼節(jié)點，而maxOfMinArr指向 5，結果如下圖：

轉化成代碼就是下面這個形式，是不是很簡單呢？我們繼續(xù)：

/**
 * 默認情況下的高度為1，即只有自己一個節(jié)點
 */
private int levelCount = 1;
/**
 * 跳表最底層的節(jié)點，即頭節(jié)點
 */
private Node h = new Node();
public void add(int value) {
    //隨機生成高度
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    //創(chuàng)建一個node數(shù)組，用于記錄小于當前value的最大值
    Node[] maxOfMinArr = new Node[level];
    //默認情況下指向頭節(jié)點
    for (int i = 0; i < level; i++) {
        maxOfMinArr[i] = h;
    }
    //基于上述結果拿到當前節(jié)點的后繼節(jié)點
    Node p = h;
    for (int i = level - 1; i >= 0; i--) {
        while (p.forwards[i] != null && p.forwards[i].data < value) {
            p = p.forwards[i];
        }
        maxOfMinArr[i] = p;
    }
    //更新前驅節(jié)點的后繼節(jié)點為當前節(jié)點newNode
    for (int i = 0; i < level; i++) {
        newNode.forwards[i] = maxOfMinArr[i].forwards[i];
        maxOfMinArr[i].forwards[i] = newNode;
    }
    //如果當前newNode高度大于跳表最高高度則更新levelCount
    if (levelCount < level) {
        levelCount = level;
    }
}

元素查詢

查詢邏輯比較簡單，從跳表最高級的索引開始定位找到小于要查的 value 的最大值，以下圖為例，我們希望查找到節(jié)點 8：

• 跳表的 3 級索引首先找找到 5 的索引，5 的 3 級索引forwards[3]指向空，索引直接向下。
• 來到 5 的 2 級索引，其后繼forwards[2]指向 8，繼續(xù)向下。
• 5 的 1 級索引forwards[1]指向索引 6，繼續(xù)向前。
• 索引 6 的forwards[1]指向索引 8，繼續(xù)向下。
• 我們在原始節(jié)點向前找到節(jié)點 7。
• 節(jié)點 7 后續(xù)就是節(jié)點 8，繼續(xù)向前為節(jié)點 8，無法繼續(xù)向下，結束搜尋。
• 判斷 7 的前驅，等于 8，查找結束。

所以我們的代碼實現(xiàn)也很上述步驟差不多，從最高級索引開始向前查找，如果不為空且小于要查找的值，則繼續(xù)向前搜尋，遇到不小于的節(jié)點則繼續(xù)向下，如此往復，直到得到當前跳表中小于查找值的最大節(jié)點，查看其前驅是否等于要查找的值：

public Node get(int value) {
    Node p = h;
    //找到小于value的最大值
    for (int i = levelCount - 1; i >= 0; i--) {
        while (p.forwards[i] != null && p.forwards[i].data < value) {
            p = p.forwards[i];
        }
    }
    //如果p的前驅節(jié)點等于value則直接返回
    if (p.forwards[0] != null && p.forwards[0].data == value) {
        return p.forwards[0];
    }
    return null;
}

元素刪除

最后是刪除邏輯，需要查找各層級小于要刪除節(jié)點的最大值，假設我們要刪除 10：

• 3 級索引得到小于 10 的最大值為 5，繼續(xù)向下。
• 2 級索引從索引 5 開始查找，發(fā)現(xiàn)小于 10 的最大值為 8，繼續(xù)向下。
• 同理 1 級索引得到 8，繼續(xù)向下。
• 原始節(jié)點找到 9。
• 從最高級索引開始，查看每個小于 10 的節(jié)點后繼節(jié)點是否為 10，如果等于 10，則讓這個節(jié)點指向 10 的后繼節(jié)點，將節(jié)點 10 及其索引交由 GC 回收。

/**
 * 刪除
 *
 * @param value
 */
public void delete(int value) {
    Node p = h;
    //找到各級節(jié)點小于value的最大值
    Node[] updateArr = new Node[levelCount];
    for (int i = levelCount - 1; i >= 0; i--) {
        while (p.forwards[i] != null && p.forwards[i].data < value) {
            p = p.forwards[i];
        }
        updateArr[i] = p;
    }
    //查看原始層節(jié)點前驅是否等于value，若等于則說明存在要刪除的值
    if (p.forwards[0] != null && p.forwards[0].data == value) {
        //從最高級索引開始查看其前驅是否等于value，若等于則將當前節(jié)點指向value節(jié)點的后繼節(jié)點
        for (int i = levelCount - 1; i >= 0; i--) {
            if (updateArr[i].forwards[i] != null && updateArr[i].forwards[i].data == value) {
                updateArr[i].forwards[i] = updateArr[i].forwards[i].forwards[i];
            }
        }
    }
    //從最高級開始查看是否有一級索引為空，若為空則層級減1
    while (levelCount > 1 && h.forwards[levelCount - 1] == null) {
        levelCount--;
    }
}

完整代碼以及測試

完整代碼如下，讀者可自行參閱:

public class SkipList {
    /**
     * 跳表索引最大高度為16
     */
    private static final int MAX_LEVEL = 16;
    /**
     * 每個節(jié)點添加一層索引高度的概率為二分之一
     */
    private static final float PROB = 0.5 f;
    /**
     * 默認情況下的高度為1，即只有自己一個節(jié)點
     */
    private int levelCount = 1;
    /**
     * 跳表最底層的節(jié)點，即頭節(jié)點
     */
    private Node h = new Node();
    public SkipList() {}
    public class Node {
        private int data = -1;
        /**
         *
         */
        private Node[] forwards = new Node[MAX_LEVEL];
        private int maxLevel = 0;
        @Override
        public String toString() {
            return "Node{" +
                "data=" + data +
                ", maxLevel=" + maxLevel +
                '}';
        }
    }
    public void add(int value) {
        //隨機生成高度
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;
        //創(chuàng)建一個node數(shù)組，用于記錄小于當前value的最大值
        Node[] maxOfMinArr = new Node[level];
        //默認情況下指向頭節(jié)點
        for (int i = 0; i < level; i++) {
            maxOfMinArr[i] = h;
        }
        //基于上述結果拿到當前節(jié)點的后繼節(jié)點
        Node p = h;
        for (int i = level - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            maxOfMinArr[i] = p;
        }
        //更新前驅節(jié)點的后繼節(jié)點為當前節(jié)點newNode
        for (int i = 0; i < level; i++) {
            newNode.forwards[i] = maxOfMinArr[i].forwards[i];
            maxOfMinArr[i].forwards[i] = newNode;
        }
        //如果當前newNode高度大于跳表最高高度則更新levelCount
        if (levelCount < level) {
            levelCount = level;
        }
    }
    /**
     * 理論來講，一級索引中元素個數(shù)應該占原始數(shù)據(jù)的 50%，二級索引中元素個數(shù)占 25%，三級索引12.5% ，一直到最頂層。
     * 因為這里每一層的晉升概率是 50%。對于每一個新插入的節(jié)點，都需要調用 randomLevel 生成一個合理的層數(shù)。
     * 該 randomLevel 方法會隨機生成 1~MAX_LEVEL 之間的數(shù)，且 ：
     * 50%的概率返回 1
     * 25%的概率返回 2
     *  12.5%的概率返回 3 ...
     * @return
     */
    private int randomLevel() {
        int level = 1;
        while (Math.random() > PROB && level < MAX_LEVEL) {
            ++level;
        }
        return level;
    }
    public Node get(int value) {
        Node p = h;
        //找到小于value的最大值
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
        }
        //如果p的前驅節(jié)點等于value則直接返回
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        }
        return null;
    }
    /**
     * 刪除
     *
     * @param value
     */
    public void delete(int value) {
        Node p = h;
        //找到各級節(jié)點小于value的最大值
        Node[] updateArr = new Node[levelCount];
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            updateArr[i] = p;
        }
        //查看原始層節(jié)點前驅是否等于value，若等于則說明存在要刪除的值
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            //從最高級索引開始查看其前驅是否等于value，若等于則將當前節(jié)點指向value節(jié)點的后繼節(jié)點
            for (int i = levelCount - 1; i >= 0; i--) {
                if (updateArr[i].forwards[i] != null && updateArr[i].forwards[i].data == value) {
                    updateArr[i].forwards[i] = updateArr[i].forwards[i].forwards[i];
                }
            }
        }
        //從最高級開始查看是否有一級索引為空，若為空則層級減1
        while (levelCount > 1 && h.forwards[levelCount - 1] == null) {
            levelCount--;
        }
    }
    public void printAll() {
        Node p = h;
        //基于最底層的非索引層進行遍歷，只要后繼節(jié)點不為空，則速速出當前節(jié)點，并移動到后繼節(jié)點
        while (p.forwards[0] != null) {
            System.out.println(p.forwards[0]);
            p = p.forwards[0];
        }
    }
}

對應測試代碼和輸出結果如下：

public static void main(String[] args) {
        SkipList skipList = new SkipList();
        for (int i = 0; i < 24; i++) {
            skipList.add(i);
        }
        System.out.println("**********輸出添加結果**********");
        skipList.printAll();
        SkipList.Node node = skipList.get(22);
        System.out.println("**********查詢結果:" + node+" **********");
        skipList.delete(22);
        System.out.println("**********刪除結果**********");
        skipList.printAll();
    }

輸出結果:

**********輸出添加結果**********
Node{data=0, maxLevel=2}
Node{data=1, maxLevel=3}
Node{data=2, maxLevel=1}
Node{data=3, maxLevel=1}
Node{data=4, maxLevel=2}
Node{data=5, maxLevel=2}
Node{data=6, maxLevel=2}
Node{data=7, maxLevel=2}
Node{data=8, maxLevel=4}
Node{data=9, maxLevel=1}
Node{data=10, maxLevel=1}
Node{data=11, maxLevel=1}
Node{data=12, maxLevel=1}
Node{data=13, maxLevel=1}
Node{data=14, maxLevel=1}
Node{data=15, maxLevel=3}
Node{data=16, maxLevel=4}
Node{data=17, maxLevel=2}
Node{data=18, maxLevel=1}
Node{data=19, maxLevel=1}
Node{data=20, maxLevel=1}
Node{data=21, maxLevel=3}
Node{data=22, maxLevel=1}
Node{data=23, maxLevel=1}
**********查詢結果:Node{data=22, maxLevel=1} **********
**********刪除結果**********
Node{data=0, maxLevel=2}
Node{data=1, maxLevel=3}
Node{data=2, maxLevel=1}
Node{data=3, maxLevel=1}
Node{data=4, maxLevel=2}
Node{data=5, maxLevel=2}
Node{data=6, maxLevel=2}
Node{data=7, maxLevel=2}
Node{data=8, maxLevel=4}
Node{data=9, maxLevel=1}
Node{data=10, maxLevel=1}
Node{data=11, maxLevel=1}
Node{data=12, maxLevel=1}
Node{data=13, maxLevel=1}
Node{data=14, maxLevel=1}
Node{data=15, maxLevel=3}
Node{data=16, maxLevel=4}
Node{data=17, maxLevel=2}
Node{data=18, maxLevel=1}
Node{data=19, maxLevel=1}
Node{data=20, maxLevel=1}
Node{data=21, maxLevel=3}
Node{data=23, maxLevel=1}

和其余三種數(shù)據(jù)結構的比較

最后，我們再來回答一下文章開頭的那道面試題: “Redis 的有序集合底層為什么要用跳表，而不用平衡樹、紅黑樹或者 B+樹？”。

平衡樹 vs 跳表

先來說說它和平衡樹的比較，平衡樹我們又會稱之為 AVL 樹，是一個嚴格的平衡二叉樹，平衡條件必須滿足（所有節(jié)點的左右子樹高度差不超過 1，即平衡因子為范圍為 [-1,1]）。平衡樹的插入、刪除和查詢的時間復雜度和跳表一樣都是 O(log n)。

對于范圍查詢來說，它也可以通過中序遍歷的方式達到和跳表一樣的效果。但是它的每一次插入或者刪除操作都需要保證整顆樹左右節(jié)點的絕對平衡，只要不平衡就要通過旋轉操作來保持平衡，這個過程是比較耗時的。

跳表誕生的初衷就是為了克服平衡樹的一些缺點，跳表的發(fā)明者在論文《Skip lists: a probabilistic alternative to balanced trees》中有詳細提到：

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

跳表是一種可以用來代替平衡樹的數(shù)據(jù)結構。跳表使用概率平衡而不是嚴格強制的平衡，因此，跳表中的插入和刪除算法比平衡樹的等效算法簡單得多，速度也快得多。

筆者這里也貼出了 AVL 樹插入操作的核心代碼，可以看出每一次添加操作都需要進行一次遞歸定位插入位置，然后還需要根據(jù)回溯到根節(jié)點檢查沿途的各層節(jié)點是否失衡，再通過旋轉節(jié)點的方式進行調整。

// 向二分搜索樹中添加新的元素(key, value)
public void add(K key, V value) {
    root = add(root, key, value);
}
// 向以node為根的二分搜索樹中插入元素(key, value)，遞歸算法
// 返回插入新節(jié)點后二分搜索樹的根
private Node add(Node node, K key, V value) {
    if (node == null) {
        size++;
        return new Node(key, value);
    }
    if (key.compareTo(node.key) < 0)
        node.left = add(node.left, key, value);
    else if (key.compareTo(node.key) > 0)
        node.right = add(node.right, key, value);
    else // key.compareTo(node.key) == 0
        node.value = value;
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    int balanceFactor = getBalanceFactor(node);
    // LL型需要右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);
    }
    //RR型失衡需要左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
        return leftRotate(node);
    }
    //LR需要先左旋成LL型，然后再右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    //RL
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

紅黑樹 vs 跳表

紅黑樹（Red Black Tree）也是一種自平衡二叉查找樹，它的查詢性能略微遜色于 AVL 樹，但插入和刪除效率更高。紅黑樹的插入、刪除和查詢的時間復雜度和跳表一樣都是 O(log n)。

紅黑樹是一個黑平衡樹，即從任意節(jié)點到另外一個葉子葉子節(jié)點，它所經(jīng)過的黑節(jié)點是一樣的。當對它進行插入操作時，需要通過旋轉和染色（紅黑變換）來保證黑平衡。不過，相較于 AVL 樹為了維持平衡的開銷要小一些。關于紅黑樹的詳細介紹，可以查看這篇文章：紅黑樹。

相比較于紅黑樹來說，跳表的實現(xiàn)也更簡單一些。并且，按照區(qū)間來查找數(shù)據(jù)這個操作，紅黑樹的效率沒有跳表高。

對應紅黑樹添加的核心代碼如下，讀者可自行參閱理解：

private Node < K, V > add(Node < K, V > node, K key, V val) {
    if (node == null) {
        size++;
        return new Node(key, val);
    }
    if (key.compareTo(node.key) < 0) {
        node.left = add(node.left, key, val);
    } else if (key.compareTo(node.key) > 0) {
        node.right = add(node.right, key, val);
    } else {
        node.val = val;
    }
    //左節(jié)點不為紅，右節(jié)點為紅，左旋
    if (isRed(node.right) && !isRed(node.left)) {
        node = leftRotate(node);
    }
    //左鏈右旋
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rightRotate(node);
    }
    //顏色翻轉
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }
    return node;
}

B+樹 vs 跳表

想必使用 MySQL 的讀者都知道 B+樹這個數(shù)據(jù)結構，B+樹是一種常用的數(shù)據(jù)結構，具有以下特點：

• 多叉樹結構：它是一棵多叉樹，每個節(jié)點可以包含多個子節(jié)點，減小了樹的高度，查詢效率高。
• 存儲效率高:其中非葉子節(jié)點存儲多個 key，葉子節(jié)點存儲 value，使得每個節(jié)點更夠存儲更多的鍵，根據(jù)索引進行范圍查詢時查詢效率更高。-
• 平衡性：它是絕對的平衡，即樹的各個分支高度相差不大，確保查詢和插入時間復雜度為O(log n)。
• 順序訪問：葉子節(jié)點間通過鏈表指針相連，范圍查詢表現(xiàn)出色。
• 數(shù)據(jù)均勻分布：B+樹插入時可能會導致數(shù)據(jù)重新分布，使得數(shù)據(jù)在整棵樹分布更加均勻，保證范圍查詢和刪除效率。

所以，B+樹更適合作為數(shù)據(jù)庫和文件系統(tǒng)中常用的索引結構之一，它的核心思想是通過可能少的 IO 定位到盡可能多的索引來獲得查詢數(shù)據(jù)。對于 Redis 這種內存數(shù)據(jù)庫來說，它對這些并不感冒，因為 Redis 作為內存數(shù)據(jù)庫它不可能存儲大量的數(shù)據(jù)，所以對于索引不需要通過 B+樹這種方式進行維護，只需按照概率進行隨機維護即可，節(jié)約內存。而且使用跳表實現(xiàn) zset 時相較前者來說更簡單一些，在進行插入時只需通過索引將數(shù)據(jù)插入到鏈表中合適的位置再隨機維護一定高度的索引即可，也不需要像 B+樹那樣插入時發(fā)現(xiàn)失衡時還需要對節(jié)點分裂與合并。

Redis 作者給出的理由

當然我們也可以通過 Redis 的作者自己給出的理由:

There are a few reasons: 1、They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees. 2、A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees. 3、They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

翻譯過來的意思就是:

有幾個原因：

1、它們不是很占用內存。這主要取決于你。改變節(jié)點擁有給定層數(shù)的概率的參數(shù)，會使它們比 B 樹更節(jié)省內存。

2、有序集合經(jīng)常是許多 ZRANGE 或 ZREVRANGE 操作的目標，也就是說，以鏈表的方式遍歷跳表。通過這種操作，跳表的緩存局部性至少和其他類型的平衡樹一樣好。

3、它們更容易實現(xiàn)、調試等等。例如，由于跳表的簡單性，我收到了一個補丁（已經(jīng)在 Redis 主分支中），用增強的跳表實現(xiàn)了 O(log(N))的 ZRANK。它只需要對代碼做很少的修改。

小結

本文通過大量篇幅介紹跳表的工作原理和實現(xiàn)，幫助讀者更進一步的熟悉跳表這一數(shù)據(jù)結構的優(yōu)劣，最后再結合各個數(shù)據(jù)結構操作的特點進行比對，從而幫助讀者更好的理解這道面試題，建議讀者實現(xiàn)理解跳表時，盡可能配合執(zhí)筆模擬來了解跳表的增刪改查詳細過程。

參考資料

• 為啥 redis 使用跳表(skiplist)而不是使用 red-black？:https://www.zhihu.com/question/20202931/answer/16086538
• Skip List--跳表（全網(wǎng)最詳細的跳表文章沒有之一）:https://www.jianshu.com/p/9d8296562806
• Redis 對象與底層數(shù)據(jù)結構詳解:https://blog.csdn.net/shark_chili3007/article/details/104171986
• Redis 有序集合(sorted set):https://www.runoob.com/redis/redis-sorted-sets.html
• 紅黑樹和跳表比較:https://zhuanlan.zhihu.com/p/576984787
• 為什么 redis 的 zset 用跳躍表而不用 b+ tree？:https://blog.csdn.net/f80407515/article/details/129136998

到此這篇關于Redis 為什么用跳表實現(xiàn)有序集合的文章就介紹到這了,更多相關Redis 有序集合內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！