深入理解跳表及其在Redis中的應用

2023-03-02 08:58:20來源：今日頭條

前言

跳表可以達到和紅黑樹一樣的時間復雜度 O(logN)，且實現(xiàn)簡單，Redis 中的有序集合對象的底層數(shù)據(jù)結(jié)構就使用了跳表。其作者威廉·普評價：跳躍鏈表是在很多應用中有可能替代平衡樹的一種數(shù)據(jù)結(jié)構。本篇文章將對跳表的實現(xiàn)及在Redis中的應用進行學習。

(資料圖)

一. 跳表的基礎概念

跳表，即跳躍鏈表（Skip List），是基于并聯(lián)的鏈表數(shù)據(jù)結(jié)構，操作效率可以達到O(logN)，對并發(fā)友好，跳表的示意圖如下所示。

跳表的特點，可以概括如下。

?跳表是多層（level）鏈表結(jié)構；

?跳表中的每一層都是一個有序鏈表，并且按照元素升序（默認）排列；

?跳表中的元素會在哪一層出現(xiàn)是隨機決定的，但是只要元素出現(xiàn)在了第 k 層，那么 k 層以下的鏈表也會出現(xiàn)這個元素；

?跳表的底層的鏈表包含所有元素；

?跳表頭節(jié)點和尾節(jié)點不存儲元素，且頭節(jié)點和尾節(jié)點的層數(shù)就是跳表的最大層數(shù)；

?跳表中的節(jié)點包含兩個指針，一個指針指向同層鏈表的后一節(jié)點，一個指針指向下層鏈表的同元素節(jié)點。

以上圖中的跳表為例，如果要查找元素 71，那么查找流程如下圖所示。

??從頂層鏈表的頭節(jié)點開始查找，查找到元素71的節(jié)點時，一共遍歷了4個節(jié)點，但是如果按照傳統(tǒng)鏈表的方式（即從跳表的底層鏈表的頭節(jié)點開始向后查找），那么就需要遍歷7個節(jié)點，所以跳表以空間換時間，縮短了操作跳表所需要花費的時間。跳躍列表的算法有同平衡樹一樣的漸進的預期時間邊界，并且更簡單、更快速和使用更少的空間。這種數(shù)據(jù)結(jié)構是由William Pugh(音譯為威廉·普)發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。谷歌上找到一篇作者關于跳表的論文，感興趣強烈建議下載閱讀：

?https://epaperpress.com/sortsearch/download/skiplist.pdf?

跳表在動態(tài)查找過程中使用了一種非嚴格的平衡機制來讓插入和刪除都更加便利和快捷，這種非嚴格平衡是基于概率的，而不是平衡樹的嚴格平衡。說到非嚴格平衡，首先想到的是紅黑樹RbTree，它同樣采用非嚴格平衡來避免像AVL那樣調(diào)整樹的結(jié)構，這里就不展開講紅黑樹了，看來跳表也是類似的路子，但是是基于概率實現(xiàn)的。

二. 跳表的節(jié)點

已知跳表中的節(jié)點，需要有指向當前層鏈表后一節(jié)點的指針，和指向下層鏈表的同元素節(jié)點的指針，所以跳表中的節(jié)點，定義如下。

public class SkiplistNode {    public int data;    public SkiplistNode next;    public SkiplistNode down;    public int level;    public SkiplistNode(int data, int level) {        this.data = data;        this.level = level;    }

上述是跳表中的節(jié)點的最簡單的定義方式，存儲的元素 data 為整數(shù)，節(jié)點之間進行比較時直接比較元素 data 的大小。

三. 跳表的初始化

跳表初始化時，將每一層鏈表的頭尾節(jié)點創(chuàng)建出來并使用集合將頭尾節(jié)點進行存儲，頭尾節(jié)點的層數(shù)隨機指定，且頭尾節(jié)點的層數(shù)就代表當前跳表的層數(shù)。初始化后，跳表結(jié)構如下所示。

??跳表初始化的相關代碼如下所示。

public LinkedList headNodes;public LinkedList tailNodes;public int curLevel;public Random random;public Skiplist() {    random = new Random();    //headNodes用于存儲每一層的頭節(jié)點    headNodes = new LinkedList<>();    //tailNodes用于存儲每一層的尾節(jié)點    tailNodes = new LinkedList<>();    //初始化跳表時，跳表的層數(shù)隨機指定    curLevel = getRandomLevel();    //指定了跳表的初始的隨機層數(shù)后，就需要將每一層的頭節(jié)點和尾節(jié)點創(chuàng)建出來并構建好關系    SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);    SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);    for (int i = 0; i <= curLevel; i++) {        head.next = tail;        headNodes.addFirst(head);        tailNodes.addFirst(tail);        SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);        SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);        headNew.down = head;        tailNew.down = tail;        head = headNew;        tail = tailNew;    }}

四. 跳表的添加方法

每一個元素添加到跳表中時，首先需要隨機指定這個元素在跳表中的層數(shù)，如果隨機指定的層數(shù)大于了跳表的層數(shù)，則在將元素添加到跳表中之前，還需要擴大跳表的層數(shù)，而擴大跳表的層數(shù)就是將頭尾節(jié)點的層數(shù)擴大。下面給出需要擴大跳表層數(shù)的一次添加的過程。

初始狀態(tài)時，跳表的層數(shù)為 2，如下圖所示。

現(xiàn)在要往跳表中添加元素 120，并且隨機指定的層數(shù)為 3，大于了當前跳表的層數(shù) 2，此時需要先擴大跳表的層數(shù)，2如下圖所示。

??將元素 120 插入到跳表中時，從頂層開始，逐層向下插入，如下圖所示。

??跳表的添加方法的代碼如下所示。

public void add(int num) {    //獲取本次添加的值的層數(shù)    int level = getRandomLevel();    //如果本次添加的值的層數(shù)大于當前跳表的層數(shù)    //則需要在添加當前值前先將跳表層數(shù)擴充    if (level > curLevel) {        expanLevel(level - curLevel);    }    //curNode表示num值在當前層對應的節(jié)點    SkiplistNode curNode = new SkiplistNode(num, level);    //preNode表示curNode在當前層的前一個節(jié)點    SkiplistNode preNode = headNodes.get(curLevel - level);    for (int i = 0; i <= level; i++) {        //從當前層的head節(jié)點開始向后遍歷，直到找到一個preNode        //使得preNode.data < num <= preNode.next.data        while (preNode.next.data < num) {            preNode = preNode.next;        }        //將curNode插入到preNode和preNode.next中間        curNode.next = preNode.next;        preNode.next = curNode;        //如果當前并不是0層，則繼續(xù)向下層添加節(jié)點        if (curNode.level > 0) {            SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);            //curNode指向下一層的節(jié)點            curNode.down = downNode;            //curNode向下移動一層            curNode = downNode;        }        //preNode向下移動一層        preNode = preNode.down;    }}private void expanLevel(int expanCount) {    SkiplistNode head = headNodes.getFirst();    SkiplistNode tail = tailNodes.getFirst();    for (int i = 0; i < expanCount; i++) {        SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);        SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);        headNew.down = head;        tailNew.down = tail;        head = headNew;        tail = tailNew;        headNodes.addFirst(head);        tailNodes.addFirst(tail);    }}

五. 跳表的搜索方法

在跳表中搜索一個元素時，需要從頂層開始，逐層向下搜索。搜索時遵循如下規(guī)則。

?目標值大于當前節(jié)點的后一節(jié)點值時，繼續(xù)在本層鏈表上向后搜索；

?目標值大于當前節(jié)點值，小于當前節(jié)點的后一節(jié)點值時，向下移動一層，從下層鏈表的同節(jié)點位置向后搜索；

?目標值等于當前節(jié)點值，搜索結(jié)束。

?下圖是一個搜索過程的示意圖。

?跳表的搜索的代碼如下所示。

public boolean search(int target) {    //從頂層開始尋找，curNode表示當前遍歷到的節(jié)點    SkiplistNode curNode = headNodes.getFirst();    while (curNode != null) {        if (curNode.next.data == target) {            //找到了目標值對應的節(jié)點，此時返回true            return true;        } else if (curNode.next.data > target) {            //curNode的后一節(jié)點值大于target            //說明目標節(jié)點在curNode和curNode.next之間            //此時需要向下層尋找            curNode = curNode.down;        } else {            //curNode的后一節(jié)點值小于target            //說明目標節(jié)點在curNode的后一節(jié)點的后面            //此時在本層繼續(xù)向后尋找            curNode = curNode.next;        }    }    return false;}

六. 跳表的刪除方法

當在跳表中需要刪除某一個元素時，則需要將這個元素在所有層的節(jié)點都刪除，具體的刪除規(guī)則如下所示。

?首先按照跳表的搜索的方式，搜索待刪除節(jié)點，如果能夠搜索到，此時搜索到的待刪除節(jié)點位于該節(jié)點層數(shù)的最高層；

?從待刪除節(jié)點的最高層往下，將每一層的待刪除節(jié)點都刪除掉，刪除方式就是讓待刪除節(jié)點的前一節(jié)點直接指向待刪除節(jié)點的后一節(jié)點。

?下圖是一個刪除過程的示意圖。

?跳表的刪除的代碼如下所示。

public boolean erase(int num) {    //刪除節(jié)點的遍歷過程與尋找節(jié)點的遍歷過程是相同的    //不過在刪除節(jié)點時如果找到目標節(jié)點，則需要執(zhí)行節(jié)點刪除的操作    SkiplistNode curNode = headNodes.getFirst();    while (curNode != null) {        if (curNode.next.data == num) {            //preDeleteNode表示待刪除節(jié)點的前一節(jié)點            SkiplistNode preDeleteNode = curNode;            while (true) {                //刪除當前層的待刪除節(jié)點，就是讓待刪除節(jié)點的前一節(jié)點指向待刪除節(jié)點的后一節(jié)點                preDeleteNode.next = curNode.next.next;                //當前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點                //這里讓preDeleteNode向下移動一層                //向下移動一層后，preDeleteNode就不一定是待刪除節(jié)點的前一節(jié)點了                preDeleteNode = preDeleteNode.down;                //如果preDeleteNode為null，說明已經(jīng)將底層的待刪除節(jié)點刪除了                //此時就結(jié)束刪除流程，并返回true                if (preDeleteNode == null) {                    return true;                }                //preDeleteNode向下移動一層后，需要繼續(xù)從當前位置向后遍歷                //直到找到一個preDeleteNode，使得preDeleteNode.next的值等于目標值                //此時preDeleteNode就又變成了待刪除節(jié)點的前一節(jié)點                while (preDeleteNode.next.data != num) {                    preDeleteNode = preDeleteNode.next;                }            }        } else if (curNode.next.data > num) {            curNode = curNode.down;        } else {            curNode = curNode.next;        }    }    return false;}

七. 跳表完整代碼

跳表完整代碼如下所示。

public class Skiplist {    public LinkedList headNodes;    public LinkedList tailNodes;    public int curLevel;    public Random random;    public Skiplist() {        random = new Random();        //headNodes用于存儲每一層的頭節(jié)點        headNodes = new LinkedList<>();        //tailNodes用于存儲每一層的尾節(jié)點        tailNodes = new LinkedList<>();        //初始化跳表時，跳表的層數(shù)隨機指定        curLevel = getRandomLevel();        //指定了跳表的初始的隨機層數(shù)后，就需要將每一層的頭節(jié)點和尾節(jié)點創(chuàng)建出來并構建好關系        SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);        SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);        for (int i = 0; i <= curLevel; i++) {            head.next = tail;            headNodes.addFirst(head);            tailNodes.addFirst(tail);            SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);            SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);            headNew.down = head;            tailNew.down = tail;            head = headNew;            tail = tailNew;        }    }    public boolean search(int target) {        //從頂層開始尋找，curNode表示當前遍歷到的節(jié)點        SkiplistNode curNode = headNodes.getFirst();        while (curNode != null) {            if (curNode.next.data == target) {                //找到了目標值對應的節(jié)點，此時返回true                return true;            } else if (curNode.next.data > target) {                //curNode的后一節(jié)點值大于target                //說明目標節(jié)點在curNode和curNode.next之間                //此時需要向下層尋找                curNode = curNode.down;            } else {                //curNode的后一節(jié)點值小于target                //說明目標節(jié)點在curNode的后一節(jié)點的后面                //此時在本層繼續(xù)向后尋找                curNode = curNode.next;            }        }        return false;    }    public void add(int num) {        //獲取本次添加的值的層數(shù)        int level = getRandomLevel();        //如果本次添加的值的層數(shù)大于當前跳表的層數(shù)        //則需要在添加當前值前先將跳表層數(shù)擴充        if (level > curLevel) {            expanLevel(level - curLevel);        }        //curNode表示num值在當前層對應的節(jié)點        SkiplistNode curNode = new SkiplistNode(num, level);        //preNode表示curNode在當前層的前一個節(jié)點        SkiplistNode preNode = headNodes.get(curLevel - level);        for (int i = 0; i <= level; i++) {            //從當前層的head節(jié)點開始向后遍歷，直到找到一個preNode            //使得preNode.data < num <= preNode.next.data            while (preNode.next.data < num) {                preNode = preNode.next;            }            //將curNode插入到preNode和preNode.next中間            curNode.next = preNode.next;            preNode.next = curNode;            //如果當前并不是0層，則繼續(xù)向下層添加節(jié)點            if (curNode.level > 0) {                SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);                //curNode指向下一層的節(jié)點                curNode.down = downNode;                //curNode向下移動一層                curNode = downNode;            }            //preNode向下移動一層            preNode = preNode.down;        }    }    public boolean erase(int num) {        //刪除節(jié)點的遍歷過程與尋找節(jié)點的遍歷過程是相同的        //不過在刪除節(jié)點時如果找到目標節(jié)點，則需要執(zhí)行節(jié)點刪除的操作        SkiplistNode curNode = headNodes.getFirst();        while (curNode != null) {            if (curNode.next.data == num) {                //preDeleteNode表示待刪除節(jié)點的前一節(jié)點                SkiplistNode preDeleteNode = curNode;                while (true) {                    //刪除當前層的待刪除節(jié)點，就是讓待刪除節(jié)點的前一節(jié)點指向待刪除節(jié)點的后一節(jié)點                    preDeleteNode.next = curNode.next.next;                    //當前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點                    //這里讓preDeleteNode向下移動一層                    //向下移動一層后，preDeleteNode就不一定是待刪除節(jié)點的前一節(jié)點了                    preDeleteNode = preDeleteNode.down;                    //如果preDeleteNode為null，說明已經(jīng)將底層的待刪除節(jié)點刪除了                    //此時就結(jié)束刪除流程，并返回true                    if (preDeleteNode == null) {                        return true;                    }                    //preDeleteNode向下移動一層后，需要繼續(xù)從當前位置向后遍歷                    //直到找到一個preDeleteNode，使得preDeleteNode.next的值等于目標值                    //此時preDeleteNode就又變成了待刪除節(jié)點的前一節(jié)點                    while (preDeleteNode.next.data != num) {                        preDeleteNode = preDeleteNode.next;                    }                }            } else if (curNode.next.data > num) {                curNode = curNode.down;            } else {                curNode = curNode.next;            }        }        return false;    }    private void expanLevel(int expanCount) {        SkiplistNode head = headNodes.getFirst();        SkiplistNode tail = tailNodes.getFirst();        for (int i = 0; i < expanCount; i++) {            SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);            SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);            headNew.down = head;            tailNew.down = tail;            head = headNew;            tail = tailNew;            headNodes.addFirst(head);            tailNodes.addFirst(tail);        }    }    private int getRandomLevel() {        int level = 0;        while (random.nextInt(2) > 1) {            level++;        }        return level;    }}

八. 跳表在Redis中的應用

ZSet結(jié)構同時包含一個字典和一個跳躍表，跳躍表按score從小到大保存所有集合元素。字典保存著從member到score的映射。這兩種結(jié)構通過指針共享相同元素的member和score，不會浪費額外內(nèi)存。

typedef struct zset {    dict *dict;    zskiplist *zsl;} zset;

ZSet中的字典和跳表布局：

1.ZSet中跳表的實現(xiàn)細節(jié)

隨機層數(shù)的實現(xiàn)原理：

跳表是一個概率型的數(shù)據(jù)結(jié)構，元素的插入層數(shù)是隨機指定的。Willam Pugh在論文中描述了它的計算過程如下：指定節(jié)點最大層數(shù) MaxLevel，指定概率 p，默認層數(shù) lvl 為1；

生成一個0~1的隨機數(shù)r，若r

重復第 2 步，直至生成的r >p 為止，此時的 lvl 就是要插入的層數(shù)。

論文中生成隨機層數(shù)的偽碼：

在Redis中對跳表的實現(xiàn)基本上也是遵循這個思想的，只不過有微小差異，看下Redis關于跳表層數(shù)的隨機源碼src/z_set.c：

/* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */int zslRandomLevel(void) {    int level = 1;    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))        level += 1;    return (level其中兩個宏的定義在redis.h中：
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
可以看到while中的：
(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)
第一眼看到這個公式，因為涉及位運算有些詫異，需要研究一下Antirez為什么使用位運算來這么寫？
最開始的猜測是random()返回的是浮點數(shù)[0-1]，于是乎在線找了個浮點數(shù)轉(zhuǎn)二進制的工具，輸入0.5看了下結(jié)果：
可以看到0.5的32bit轉(zhuǎn)換16進制結(jié)果為0x3f000000，如果與0xFFFF做與運算結(jié)果還是0，不符合預期。
實際應用時對于隨機層數(shù)的實現(xiàn)并不統(tǒng)一，重要的是隨機數(shù)的生成，在LevelDB中對跳表層數(shù)的生成代碼是這樣的：
template int SkipList::randomLevel() {  static const unsigned int kBranching = 4;  int height = 1;  while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {    height++;  }  assert(height > 0);  assert(height <= kMaxLevel);  return height;}uint32_t Next( uint32_t& seed) {  seed = seed & 0x7fffffffu;  if (seed == 0 || seed == 2147483647L) {     seed = 1;  }  static const uint32_t M = 2147483647L;  static const uint64_t A = 16807;  uint64_t product = seed * A;  seed = static_cast((product >> 31) + (product & M));  if (seed > M) {    seed -= M;  }  return seed;}
可以看到leveldb使用隨機數(shù)與kBranching取模，如果值為0就增加一層，這樣雖然沒有使用浮點數(shù)，但是也實現(xiàn)了概率平衡。
2.跳表結(jié)點的平均層數(shù)我們很容易看出，產(chǎn)生越高的節(jié)點層數(shù)出現(xiàn)概率越低，無論如何層數(shù)總是滿足冪次定律越大的數(shù)出現(xiàn)的概率越小。
如果某件事的發(fā)生頻率和它的某個屬性成冪關系，那么這個頻率就可以稱之為符合冪次定律。
冪次定律的表現(xiàn)是少數(shù)幾個事件的發(fā)生頻率占了整個發(fā)生頻率的大部分， 而其余的大多數(shù)事件只占整個發(fā)生頻率的一個小部分。
冪次定律應用到跳表的隨機層數(shù)來說就是大部分的節(jié)點層數(shù)都是黃色部分，只有少數(shù)是綠色部分，并且概率很低。
定量的分析如下：
?節(jié)點層數(shù)至少為1，大于1的節(jié)點層數(shù)滿足一個概率分布。
?節(jié)點層數(shù)恰好等于1的概率為p^0(1-p)
?節(jié)點層數(shù)恰好等于2的概率為p^1(1-p)
?節(jié)點層數(shù)恰好等于3的概率為p^2(1-p)
?節(jié)點層數(shù)恰好等于4的概率為p^3(1-p)
依次遞推節(jié)點層數(shù)恰好等于K的概率為p^(k-1)(1-p)
因此如果我們要求節(jié)點的平均層數(shù)，那么也就轉(zhuǎn)換成了求概率分布的期望問題了：
??表中P為概率，V為對應取值，給出了所有取值和概率的可能，因此就可以求這個概率分布的期望了。方括號里面的式子其實就是高一年級學的等比數(shù)列，常用技巧錯位相減求和，從中可以看到結(jié)點層數(shù)的期望值與1-p成反比。對于Redis而言，當p=0.25時結(jié)點層數(shù)的期望是1.33。
總結(jié)跳表的時間復雜度與AVL樹和紅黑樹相同，可以達到O(logN)，但是AVL樹要維持高度的平衡，紅黑樹要維持高度的近似平衡，這都會導致插入或者刪除節(jié)點時的一些時間開銷，所以跳表相較于AVL樹和紅黑樹來說，省去了維持高度的平衡的時間開銷，但是相應的也付出了更多的空間來存儲多個層的節(jié)點，所以跳表是用空間換時間的數(shù)據(jù)結(jié)構。以Redis中底層的數(shù)據(jù)結(jié)構zset作為典型應用來展開，進一步看到跳躍鏈表的實際應用。 
		         
關鍵詞：         
       刪除節(jié)點 
              
       向下移動 
              
       數(shù)據(jù)結(jié)構 
              
       找到一個