Redis 使用跳表實(shí)現(xiàn)有序集合的方法

更新時(shí)間：2024年09月28日 11:03:43 作者：yeye19891224

Redis有序集合底層為什么使用跳表而非其他數(shù)據(jù)結(jié)構(gòu)如平衡樹、紅黑樹或B+樹的原因在于其特殊的設(shè)計(jì)和應(yīng)用場(chǎng)景,跳表提供了與平衡樹類似的效率,同時(shí)實(shí)現(xiàn)更簡(jiǎn)單,調(diào)試和修改也更加容易,感興趣的朋友一起看看吧

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

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

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ū)間內(nèi)的成員，通過索引，分?jǐn)?shù)從高到低
127.0.0.1:6379> ZREVRANGE rankList 0 100 WITHSCORES
1) "xiaohong"
2) "80"
3) "xiaowang"
4) "60"
5) "xiaoming"
6) "60"

此時(shí)我們通過 object 指令查看 zset 的數(shù)據(jù)結(jié)構(gòu)，可以看到當(dāng)前有序集合存儲(chǔ)的還是**ziplist(壓縮列表)**。

127.0.0.1:6379> object encoding rankList
"ziplist"

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

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

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

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

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

也就是說，ZSet 有兩種不同的實(shí)現(xiàn)，分別是 ziplist 和 skiplist，具體使用哪種結(jié)構(gòu)進(jìn)行存儲(chǔ)的規(guī)則如下：

當(dāng)有序集合對(duì)象同時(shí)滿足以下兩個(gè)條件時(shí)，使用 ziplist：

ZSet 保存的鍵值對(duì)數(shù)量少于 128 個(gè)；

每個(gè)元素的長(zhǎng)度小于 64 字節(jié)。

如果不滿足上述兩個(gè)條件，那么使用 skiplist 。

手寫一個(gè)跳表

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

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

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

假如我們需要查詢?cè)?6，其工作流程如下：

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

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

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

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

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

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

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

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

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

假設(shè)元素個(gè)數(shù)為 n，那么對(duì)應(yīng) k 層索引的元素個(gè)數(shù) r 計(jì)算公式為:

r=n/2^k

同理我們?cè)賮硗茢嘁韵滤饕淖畲蟾叨?，一般來說最高級(jí)索引的元素個(gè)數(shù)為 2，我們?cè)O(shè)元素總個(gè)數(shù)為 n，索引高度為 h，代入上述公式可得：

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

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

因?yàn)槲覀円蟊M可能保證每一個(gè)上級(jí)索引都是下級(jí)索引的一半，在實(shí)現(xiàn)高度生成算法時(shí)，我們可以這樣設(shè)計(jì)：

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

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

最后我們?cè)賮碚f說刪除，假設(shè)我們這里要?jiǎng)h除元素 10，我們必須定位到當(dāng)前跳表各層元素小于 10 的最大值，索引執(zhí)行步驟為：

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

模板定義

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

存儲(chǔ)的value值。
后繼節(jié)點(diǎn)的地址。
多級(jí)索引。

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

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

于是我們的就有了這樣一個(gè)代碼定義，可以看出筆者對(duì)于數(shù)組的長(zhǎng)度設(shè)置為固定的 16**(上文的推算最大高度建議是 16)，默認(rèn)data為-1，節(jié)點(diǎn)最大高度maxLevel初始化為 1，注意這個(gè)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é)點(diǎn)之后，我們先實(shí)現(xiàn)以下元素的添加，添加元素時(shí)首先自然是設(shè)置data這一步我們直接根據(jù)將傳入的value設(shè)置到data上即可。

然后就是高度maxLevel的設(shè)置，我們?cè)谏衔囊惨呀?jīng)給出了思路，默認(rèn)高度為 1，即只有一個(gè)原始鏈表節(jié)點(diǎn)，通過隨機(jī)算法每次大于 0.5 索引高度加 1，由此我們得出高度計(jì)算的算法randomLevel()：

/**
 * 理論來講，一級(jí)索引中元素個(gè)數(shù)應(yīng)該占原始數(shù)據(jù)的 50%，二級(jí)索引中元素個(gè)數(shù)占 25%，三級(jí)索引12.5% ，一直到最頂層。
 * 因?yàn)檫@里每一層的晉升概率是 50%。對(duì)于每一個(gè)新插入的節(jié)點(diǎn)，都需要調(diào)用 randomLevel 生成一個(gè)合理的層數(shù)。
 * 該 randomLevel 方法會(huì)隨機(jī)生成 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;
}

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

假設(shè)我們要插入的value為 5，我們的數(shù)組查找結(jié)果當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和 1 級(jí)索引、2 級(jí)索引的前驅(qū)節(jié)點(diǎn)都為 4，三級(jí)索引為空。

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

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

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

元素查詢

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

跳表的 3 級(jí)索引首先找找到 5 的索引，5 的 3 級(jí)索引forwards[3]指向空，索引直接向下。
來到 5 的 2 級(jí)索引，其后繼forwards[2]指向 8，繼續(xù)向下。
5 的 1 級(jí)索引forwards[1]指向索引 6，繼續(xù)向前。
索引 6 的forwards[1]指向索引 8，繼續(xù)向下。
我們?cè)谠脊?jié)點(diǎn)向前找到節(jié)點(diǎn) 7。
節(jié)點(diǎn) 7 后續(xù)就是節(jié)點(diǎn) 8，繼續(xù)向前為節(jié)點(diǎn) 8，無法繼續(xù)向下，結(jié)束搜尋。
判斷 7 的前驅(qū)，等于 8，查找結(jié)束。

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

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的前驅(qū)節(jié)點(diǎn)等于value則直接返回
    if (p.forwards[0] != null && p.forwards[0].data == value) {
        return p.forwards[0];
    }
    return null;
}

元素刪除

最后是刪除邏輯，需要查找各層級(jí)小于要?jiǎng)h除節(jié)點(diǎn)的最大值，假設(shè)我們要?jiǎng)h除 10：

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

/**
 * 刪除
 *
 * @param value
 */
public void delete(int value) {
    Node p = h;
    //找到各級(jí)節(jié)點(diǎn)小于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é)點(diǎn)前驅(qū)是否等于value，若等于則說明存在要?jiǎng)h除的值
    if (p.forwards[0] != null && p.forwards[0].data == value) {
        //從最高級(jí)索引開始查看其前驅(qū)是否等于value，若等于則將當(dāng)前節(jié)點(diǎn)指向value節(jié)點(diǎn)的后繼節(jié)點(diǎn)
        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];
            }
        }
    }
    //從最高級(jí)開始查看是否有一級(jí)索引為空，若為空則層級(jí)減1
    while (levelCount > 1 && h.forwards[levelCount - 1] == null) {
        levelCount--;
    }
}

完整代碼以及測(cè)試

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

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

對(duì)應(yīng)測(cè)試代碼和輸出結(jié)果如下：

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

輸出結(jié)果:

**********輸出添加結(jié)果**********
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}
**********查詢結(jié)果:Node{data=22, maxLevel=1} **********
**********刪除結(jié)果**********
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ù)結(jié)構(gòu)的比較

最后，我們?cè)賮砘卮鹨幌挛恼麻_頭的那道面試題: “Redis 的有序集合底層為什么要用跳表，而不用平衡樹、紅黑樹或者 B+樹？”。

平衡樹 vs 跳表

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

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

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

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ù)結(jié)構(gòu)。跳表使用概率平衡而不是嚴(yán)格強(qiáng)制的平衡，因此，跳表中的插入和刪除算法比平衡樹的等效算法簡(jiǎn)單得多，速度也快得多。

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

// 向二分搜索樹中添加新的元素(key, value)
public void add(K key, V value) {
    root = add(root, key, value);
}
// 向以node為根的二分搜索樹中插入元素(key, value)，遞歸算法
// 返回插入新節(jié)點(diǎn)后二分搜索樹的根
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 樹，但插入和刪除效率更高。紅黑樹的插入、刪除和查詢的時(shí)間復(fù)雜度和跳表一樣都是 O(log n)。

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

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

對(duì)應(yīng)紅黑樹添加的核心代碼如下，讀者可自行參閱理解：

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é)點(diǎn)不為紅，右節(jié)點(diǎn)為紅，左旋
    if (isRed(node.right) && !isRed(node.left)) {
        node = leftRotate(node);
    }
    //左鏈右旋
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rightRotate(node);
    }
    //顏色翻轉(zhuǎn)
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }
    return node;
}

B+樹 vs 跳表

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

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

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

Redis 作者給出的理由

當(dāng)然我們也可以通過 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.

翻譯過來的意思就是:

有幾個(gè)原因：

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

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

3、它們更容易實(shí)現(xiàn)、調(diào)試等等。例如，由于跳表的簡(jiǎn)單性，我收到了一個(gè)補(bǔ)?。ㄒ呀?jīng)在 Redis 主分支中），用增強(qiáng)的跳表實(shí)現(xiàn)了 O(log(N))的 ZRANK。它只需要對(duì)代碼做很少的修改。

小結(jié)

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

參考資料

為啥 redis 使用跳表(skiplist)而不是使用 red-black？:https://www.zhihu.com/question/20202931/answer/16086538
Skip List--跳表（全網(wǎng)最詳細(xì)的跳表文章沒有之一）:https://www.jianshu.com/p/9d8296562806
Redis 對(duì)象與底層數(shù)據(jù)結(jié)構(gòu)詳解: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

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

您可能感興趣的文章: