深入理解跳表及其在Redis中的應(yīng)用

作者：京東云開發(fā)者 2023-03-02 08:26:36

跳表的時間復(fù)雜度與AVL樹和紅黑樹相同，可以達(dá)到O(logN)，但是AVL樹要維持高度的平衡，紅黑樹要維持高度的近似平衡，這都會導(dǎo)致插入或者刪除節(jié)點(diǎn)時的一些時間開銷，所以跳表相較于AVL樹和紅黑樹來說，省去了維持高度的平衡的時間開銷，但是相應(yīng)的也付出了更多的空間來存儲多個層的節(jié)點(diǎn)，所以跳表是用空間換時間的數(shù)據(jù)結(jié)構(gòu)。

前言

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

一. 跳表的基礎(chǔ)概念

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

跳表的特點(diǎn)，可以概括如下。

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

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

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

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

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

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

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

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

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

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

二. 跳表的節(jié)點(diǎn)

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

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é)點(diǎn)的最簡單的定義方式，存儲的元素 data 為整數(shù)，節(jié)點(diǎn)之間進(jìn)行比較時直接比較元素 data 的大小。

三. 跳表的初始化

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

??跳表初始化的相關(guān)代碼如下所示。

public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;

public int curLevel;

public Random random;

public Skiplist() {
    random = new Random();

    //headNodes用于存儲每一層的頭節(jié)點(diǎn)
    headNodes = new LinkedList<>();
    //tailNodes用于存儲每一層的尾節(jié)點(diǎn)
    tailNodes = new LinkedList<>();

    //初始化跳表時，跳表的層數(shù)隨機(jī)指定
    curLevel = getRandomLevel();
    //指定了跳表的初始的隨機(jī)層數(shù)后，就需要將每一層的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)創(chuàng)建出來并構(gòu)建好關(guān)系
    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;
    }
}

四. 跳表的添加方法

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

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

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

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

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

public void add(int num) {
    //獲取本次添加的值的層數(shù)
    int level = getRandomLevel();
    //如果本次添加的值的層數(shù)大于當(dāng)前跳表的層數(shù)
    //則需要在添加當(dāng)前值前先將跳表層數(shù)擴(kuò)充
    if (level > curLevel) {
        expanLevel(level - curLevel);
    }

    //curNode表示num值在當(dāng)前層對應(yīng)的節(jié)點(diǎn)
    SkiplistNode curNode = new SkiplistNode(num, level);
    //preNode表示curNode在當(dāng)前層的前一個節(jié)點(diǎn)
    SkiplistNode preNode = headNodes.get(curLevel - level);
    for (int i = 0; i <= level; i++) {
        //從當(dāng)前層的head節(jié)點(diǎn)開始向后遍歷，直到找到一個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;

        //如果當(dāng)前并不是0層，則繼續(xù)向下層添加節(jié)點(diǎn)
        if (curNode.level > 0) {
            SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
            //curNode指向下一層的節(jié)點(diǎn)
            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ī)則。

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

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

?目標(biāo)值等于當(dāng)前節(jié)點(diǎn)值，搜索結(jié)束。

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

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

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

六. 跳表的刪除方法

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

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

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

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

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

public boolean erase(int num) {
    //刪除節(jié)點(diǎn)的遍歷過程與尋找節(jié)點(diǎn)的遍歷過程是相同的
    //不過在刪除節(jié)點(diǎn)時如果找到目標(biāo)節(jié)點(diǎn)，則需要執(zhí)行節(jié)點(diǎn)刪除的操作
    SkiplistNode curNode = headNodes.getFirst();
    while (curNode != null) {
        if (curNode.next.data == num) {
            //preDeleteNode表示待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
            SkiplistNode preDeleteNode = curNode;
            while (true) {
                //刪除當(dāng)前層的待刪除節(jié)點(diǎn)，就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)
                preDeleteNode.next = curNode.next.next;
                //當(dāng)前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點(diǎn)
                //這里讓preDeleteNode向下移動一層
                //向下移動一層后，preDeleteNode就不一定是待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)了
                preDeleteNode = preDeleteNode.down;

                //如果preDeleteNode為null，說明已經(jīng)將底層的待刪除節(jié)點(diǎn)刪除了
                //此時就結(jié)束刪除流程，并返回true
                if (preDeleteNode == null) {
                    return true;
                }

                //preDeleteNode向下移動一層后，需要繼續(xù)從當(dāng)前位置向后遍歷
                //直到找到一個preDeleteNode，使得preDeleteNode.next的值等于目標(biāo)值
                //此時preDeleteNode就又變成了待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
                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<SkiplistNode> headNodes;
    public LinkedList<SkiplistNode> tailNodes;

    public int curLevel;

    public Random random;

    public Skiplist() {
        random = new Random();

        //headNodes用于存儲每一層的頭節(jié)點(diǎn)
        headNodes = new LinkedList<>();
        //tailNodes用于存儲每一層的尾節(jié)點(diǎn)
        tailNodes = new LinkedList<>();

        //初始化跳表時，跳表的層數(shù)隨機(jī)指定
        curLevel = getRandomLevel();
        //指定了跳表的初始的隨機(jī)層數(shù)后，就需要將每一層的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)創(chuàng)建出來并構(gòu)建好關(guān)系
        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表示當(dāng)前遍歷到的節(jié)點(diǎn)
        SkiplistNode curNode = headNodes.getFirst();
        while (curNode != null) {
            if (curNode.next.data == target) {
                //找到了目標(biāo)值對應(yīng)的節(jié)點(diǎn)，此時返回true
                return true;
            } else if (curNode.next.data > target) {
                //curNode的后一節(jié)點(diǎn)值大于target
                //說明目標(biāo)節(jié)點(diǎn)在curNode和curNode.next之間
                //此時需要向下層尋找
                curNode = curNode.down;
            } else {
                //curNode的后一節(jié)點(diǎn)值小于target
                //說明目標(biāo)節(jié)點(diǎn)在curNode的后一節(jié)點(diǎn)的后面
                //此時在本層繼續(xù)向后尋找
                curNode = curNode.next;
            }
        }
        return false;
    }

    public void add(int num) {
        //獲取本次添加的值的層數(shù)
        int level = getRandomLevel();
        //如果本次添加的值的層數(shù)大于當(dāng)前跳表的層數(shù)
        //則需要在添加當(dāng)前值前先將跳表層數(shù)擴(kuò)充
        if (level > curLevel) {
            expanLevel(level - curLevel);
        }

        //curNode表示num值在當(dāng)前層對應(yīng)的節(jié)點(diǎn)
        SkiplistNode curNode = new SkiplistNode(num, level);
        //preNode表示curNode在當(dāng)前層的前一個節(jié)點(diǎn)
        SkiplistNode preNode = headNodes.get(curLevel - level);
        for (int i = 0; i <= level; i++) {
            //從當(dāng)前層的head節(jié)點(diǎn)開始向后遍歷，直到找到一個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;

            //如果當(dāng)前并不是0層，則繼續(xù)向下層添加節(jié)點(diǎn)
            if (curNode.level > 0) {
                SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
                //curNode指向下一層的節(jié)點(diǎn)
                curNode.down = downNode;
                //curNode向下移動一層
                curNode = downNode;
            }
            //preNode向下移動一層
            preNode = preNode.down;
        }
    }

    public boolean erase(int num) {
        //刪除節(jié)點(diǎn)的遍歷過程與尋找節(jié)點(diǎn)的遍歷過程是相同的
        //不過在刪除節(jié)點(diǎn)時如果找到目標(biāo)節(jié)點(diǎn)，則需要執(zhí)行節(jié)點(diǎn)刪除的操作
        SkiplistNode curNode = headNodes.getFirst();
        while (curNode != null) {
            if (curNode.next.data == num) {
                //preDeleteNode表示待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
                SkiplistNode preDeleteNode = curNode;
                while (true) {
                    //刪除當(dāng)前層的待刪除節(jié)點(diǎn)，就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)
                    preDeleteNode.next = curNode.next.next;
                    //當(dāng)前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點(diǎn)
                    //這里讓preDeleteNode向下移動一層
                    //向下移動一層后，preDeleteNode就不一定是待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)了
                    preDeleteNode = preDeleteNode.down;

                    //如果preDeleteNode為null，說明已經(jīng)將底層的待刪除節(jié)點(diǎn)刪除了
                    //此時就結(jié)束刪除流程，并返回true
                    if (preDeleteNode == null) {
                        return true;
                    }

                    //preDeleteNode向下移動一層后，需要繼續(xù)從當(dāng)前位置向后遍歷
                    //直到找到一個preDeleteNode，使得preDeleteNode.next的值等于目標(biāo)值
                    //此時preDeleteNode就又變成了待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
                    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中的應(yīng)用

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

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

ZSet中的字典和跳表布局：

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

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

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

生成一個0~1的隨機(jī)數(shù)r，若r<p，且lvl<MaxLevel ，則lvl ++；

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

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

在Redis中對跳表的實(shí)現(xiàn)基本上也是遵循這個思想的，只不過有微小差異，看下Redis關(guān)于跳表層數(shù)的隨機(jī)源碼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<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

其中兩個宏的定義在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)

第一眼看到這個公式，因?yàn)樯婕拔贿\(yùn)算有些詫異，需要研究一下Antirez為什么使用位運(yùn)算來這么寫？

最開始的猜測是random()返回的是浮點(diǎn)數(shù)[0-1]，于是乎在線找了個浮點(diǎn)數(shù)轉(zhuǎn)二進(jìn)制的工具，輸入0.5看了下結(jié)果：

可以看到0.5的32bit轉(zhuǎn)換16進(jìn)制結(jié)果為0x3f000000，如果與0xFFFF做與運(yùn)算結(jié)果還是0，不符合預(yù)期。

實(shí)際應(yīng)用時對于隨機(jī)層數(shù)的實(shí)現(xiàn)并不統(tǒng)一，重要的是隨機(jī)數(shù)的生成，在LevelDB中對跳表層數(shù)的生成代碼是這樣的：

template <typename Key, typename Value>
int SkipList<Key, Value>::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<uint32_t>((product >> 31) + (product & M));
  if (seed > M) {
    seed -= M;
  }
  return seed;
}

可以看到leveldb使用隨機(jī)數(shù)與kBranching取模，如果值為0就增加一層，這樣雖然沒有使用浮點(diǎn)數(shù)，但是也實(shí)現(xiàn)了概率平衡。

2.跳表結(jié)點(diǎn)的平均層數(shù)

我們很容易看出，產(chǎn)生越高的節(jié)點(diǎn)層數(shù)出現(xiàn)概率越低，無論如何層數(shù)總是滿足冪次定律越大的數(shù)出現(xiàn)的概率越小。

如果某件事的發(fā)生頻率和它的某個屬性成冪關(guān)系，那么這個頻率就可以稱之為符合冪次定律。
冪次定律的表現(xiàn)是少數(shù)幾個事件的發(fā)生頻率占了整個發(fā)生頻率的大部分，而其余的大多數(shù)事件只占整個發(fā)生頻率的一個小部分。

冪次定律應(yīng)用到跳表的隨機(jī)層數(shù)來說就是大部分的節(jié)點(diǎn)層數(shù)都是黃色部分，只有少數(shù)是綠色部分，并且概率很低。

定量的分析如下：

?節(jié)點(diǎn)層數(shù)至少為1，大于1的節(jié)點(diǎn)層數(shù)滿足一個概率分布。

?節(jié)點(diǎn)層數(shù)恰好等于1的概率為p^0(1-p)

?節(jié)點(diǎn)層數(shù)恰好等于2的概率為p^1(1-p)

?節(jié)點(diǎn)層數(shù)恰好等于3的概率為p^2(1-p)

?節(jié)點(diǎn)層數(shù)恰好等于4的概率為p^3(1-p)

依次遞推節(jié)點(diǎn)層數(shù)恰好等于K的概率為p^(k-1)(1-p)

因此如果我們要求節(jié)點(diǎn)的平均層數(shù)，那么也就轉(zhuǎn)換成了求概率分布的期望問題了：

??表中P為概率，V為對應(yīng)取值，給出了所有取值和概率的可能，因此就可以求這個概率分布的期望了。方括號里面的式子其實(shí)就是高一年級學(xué)的等比數(shù)列，常用技巧錯位相減求和，從中可以看到結(jié)點(diǎn)層數(shù)的期望值與1-p成反比。對于Redis而言，當(dāng)p=0.25時結(jié)點(diǎn)層數(shù)的期望是1.33。

總結(jié)

責(zé)任編輯：武曉燕來源：今日頭條