主頁 > 知識庫 > 為何Redis使用跳表而非紅黑樹實(shí)現(xiàn)SortedSet

為何Redis使用跳表而非紅黑樹實(shí)現(xiàn)SortedSet
熱門標(biāo)簽：Linux服務(wù)器 呼叫中心市場需求 AI電銷 服務(wù)外包 地方門戶網(wǎng)站 網(wǎng)站排名優(yōu)化 鐵路電話系統(tǒng) 百度競價排名

知道跳表（Skip List）是在看關(guān)于Redis的書的時候，Redis中的有序集合使用了跳表數(shù)據(jù)結(jié)構(gòu)。接著就查了一些博客，來學(xué)習(xí)一下跳表。后面會使用Java代碼來簡單實(shí)現(xiàn)跳表。

什么是跳表

跳表由William Pugh發(fā)明，他在論文《Skip lists: a probabilistic alternative to balanced trees》中詳細(xì)介紹了跳表的數(shù)據(jù)結(jié)構(gòu)和插入刪除等操作，論文是這么介紹跳表的：

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ù)，使得插入、刪除操作更簡單、更快。先來看論文里的一張圖：


觀察上圖

  • a：已排好序的鏈表，查找一個結(jié)點(diǎn)最多需要比較N個結(jié)點(diǎn)。
  • b：每隔2個結(jié)點(diǎn)增加一個指針，指向該結(jié)點(diǎn)間距為2的后續(xù)結(jié)點(diǎn)，那么查找一個結(jié)點(diǎn)最多需要比較ceil(N/2)+1個結(jié)點(diǎn)。
  • c，每隔4個結(jié)點(diǎn)增加一個指針，指向該結(jié)點(diǎn)間距為4的后續(xù)結(jié)點(diǎn)，那么查找一個結(jié)點(diǎn)最多需要比較ceil(N/4)+1個結(jié)點(diǎn)。
  • 若每第2^i 個結(jié)點(diǎn)都有一個指向間距為 2^i的后續(xù)結(jié)點(diǎn)的指針，這樣不斷增加指針，比較次數(shù)會降為log(N)。這樣的話，搜索會很快，但插入和刪除會很困難。

一個擁有k個指針的結(jié)點(diǎn)稱為一個k層結(jié)點(diǎn)（level k node）。按照上面的邏輯，50%的結(jié)點(diǎn)為1層，25%的結(jié)點(diǎn)為2層，12.5%的結(jié)點(diǎn)為3層…如果每個結(jié)點(diǎn)的層數(shù)隨機(jī)選取，但仍服從這樣的分布呢（上圖e，對比上圖d）？

使一個k層結(jié)點(diǎn)的第i個指針指向第i層的下一個結(jié)點(diǎn)，而不是它后面的第2^(i-1)個結(jié)點(diǎn)，那么結(jié)點(diǎn)的插入和刪除只需要原地修改操作；一個結(jié)點(diǎn)的層數(shù)，是在它被插入的時候隨機(jī)選取的，并且永不改變。因?yàn)檫@樣的數(shù)據(jù)結(jié)構(gòu)是基于鏈表的，并且額外的指針會跳過中間結(jié)點(diǎn)，所以作者稱之為跳表（Skip Lists）。

二分查找底層依賴數(shù)組隨機(jī)訪問的特性，所以只能用數(shù)組實(shí)現(xiàn)。若數(shù)據(jù)存儲在鏈表，就沒法用二分搜索了？

其實(shí)只需稍微改造下鏈表，就能支持類似“二分”的搜索算法，即跳表（Skip list），支持快速的新增、刪除、搜索操作。

Redis中的有序集合（Sorted Set）就是用跳表實(shí)現(xiàn)的。我們知道紅黑樹也能實(shí)現(xiàn)快速的插入、刪除和查找操作。那Redis 為何不選擇紅黑樹來實(shí)現(xiàn)呢？

跳表的意義究竟在于何處？

單鏈表即使存儲的數(shù)據(jù)有序，若搜索某數(shù)據(jù)，也只能從頭到尾遍歷，搜索效率很低，平均時間復(fù)雜度是O(n)。

追求極致的程序員就開始想了，那這該如何提高鏈表結(jié)構(gòu)的搜索效率呢？
若如下圖，對鏈表建立一級“索引”，每兩個結(jié)點(diǎn)提取一個結(jié)點(diǎn)到上一級，把抽出來的那級叫作索引或索引層。圖中的down表示down指針，指向下一級結(jié)點(diǎn)。


比如要搜索16：

先遍歷索引層，當(dāng)遍歷到索引層的13時，發(fā)現(xiàn)下一個結(jié)點(diǎn)是17，說明目標(biāo)結(jié)點(diǎn)位于這倆結(jié)點(diǎn)中間

然后通過down指針，下降到原始鏈表層，繼續(xù)遍歷
此時只需再遍歷2個結(jié)點(diǎn)，即可找到16！

原先單鏈表結(jié)構(gòu)需遍歷10個結(jié)點(diǎn)，現(xiàn)在只需遍歷7個結(jié)點(diǎn)即可?？梢姡右粚铀饕?，所需遍歷的結(jié)點(diǎn)個數(shù)就減少了，搜索效率提升。

若再加層索引，搜索效率是不是更高？于是每兩個結(jié)點(diǎn)再抽出一個結(jié)點(diǎn)到第二級索引?，F(xiàn)在搜索16，只需遍歷6個結(jié)點(diǎn)了！


這里數(shù)據(jù)量不大，可能你也沒感覺到搜索效率ROI高嗎。

那數(shù)據(jù)量就變大一點(diǎn)，現(xiàn)有一64結(jié)點(diǎn)鏈表，給它建立五級的索引。


原來沒有索引時，單鏈表搜索62需遍歷62個結(jié)點(diǎn)！
現(xiàn)在呢？只需遍歷11個！所以你現(xiàn)在能體會到了，當(dāng)鏈表長度n很大時，建立索引后，搜索性能顯著提升。

這種有多級索引的，可以提高查詢效率的鏈表就是最近火遍面試圈的跳表。
作為嚴(yán)謹(jǐn)?shù)某绦騿T，我們又開始好奇了

跳表的搜索時間復(fù)雜度

我們都知道單鏈表搜索時間復(fù)雜度O(n)，那如此快的跳表呢？

若鏈表有n個結(jié)點(diǎn)，會有多少級索引呢？假設(shè)每兩個結(jié)點(diǎn)抽出一個結(jié)點(diǎn)作為上級索引，則：

  • 第一級索引結(jié)點(diǎn)個數(shù)是n/2
  • 第二級n/4第
  • 三級n/8
  • …
  • 第k級就是n/(2^k)

假設(shè)索引有h級，最高級索引有2個結(jié)點(diǎn)，可得：n/(2h) = 2

所以：h = log2n-1

若包含原始鏈表這一層，整個跳表的高度就是log2 n。我們在跳表中查詢某個數(shù)據(jù)的時候，如果每一層都要遍歷m個結(jié)點(diǎn)，那在跳表中查詢一個數(shù)據(jù)的時間復(fù)雜度就是O(m*logn)。

那這個m的值是多少呢？按照前面這種索引結(jié)構(gòu)，我們每一級索引都最多只需要遍歷3個結(jié)點(diǎn)，也就是說m=3，為什么是3呢？我來解釋一下。

假設(shè)我們要查找的數(shù)據(jù)是x，在第k級索引中，我們遍歷到y(tǒng)結(jié)點(diǎn)之后，發(fā)現(xiàn)x大于y，小于后面的結(jié)點(diǎn)z，所以我們通過y的down指針，從第k級索引下降到第k-1級索引。在第k-1級索引中，y和z之間只有3個結(jié)點(diǎn)（包含y和z），所以，我們在K-1級索引中最多只需要遍歷3個結(jié)點(diǎn)，依次類推，每一級索引都最多只需要遍歷3個結(jié)點(diǎn)。

通過上面的分析，我們得到m=3，所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時間復(fù)雜度就是O(logn)。這個查找的時間復(fù)雜度跟二分查找是一樣的。換句話說，我們其實(shí)是基于單鏈表實(shí)現(xiàn)了二分查找，是不是很神奇？不過，天下沒有免費(fèi)的午餐，這種查詢效率的提升，前提是建立了很多級索引，也就是我們在第6節(jié)講過的空間換時間的設(shè)計(jì)思路。

跳表是不是很費(fèi)內(nèi)存？

由于跳表要存儲多級索引，勢必比單鏈表消耗更多存儲空間。那到底是多少呢？
若原始鏈表大小為n：

  • 第一級索引大約有n/2個結(jié)點(diǎn)
  • 第二級索引大約有n/4個結(jié)點(diǎn)
  • …
  • 最后一級2個結(jié)點(diǎn)

多級結(jié)點(diǎn)數(shù)的總和就是：

n/2+n/4+n/8…+8+4+2=n-2

所以空間復(fù)雜度是O(n)。這個量還是挺大的，能否再稍微降低索引占用的內(nèi)存空間呢？
若每三五個結(jié)點(diǎn)才抽取一個到上級索引呢？

  • 第一級索引需要大約n/3個結(jié)點(diǎn)
  • 第二級索引需要大約n/9個結(jié)點(diǎn)
  • 每往上一級，索引結(jié)點(diǎn)個數(shù)都除以3

假設(shè)最高級索引結(jié)點(diǎn)個數(shù)為1，總索引結(jié)點(diǎn)數(shù)：n/3+n/9+n/27+…+9+3+1=n/2

盡管空間復(fù)雜度還是O(n)，但比上面的每兩個結(jié)點(diǎn)抽一個結(jié)點(diǎn)的索引構(gòu)建方法，要減少了一半的索引結(jié)點(diǎn)存儲空間。

我們大可不必過分在意索引占用的額外空間，實(shí)際開發(fā)中，原始鏈表中存儲的有可能是很大的對象，而索引結(jié)點(diǎn)只需存儲關(guān)鍵值和幾個指針，無需存儲對象，所以當(dāng)對象比索引結(jié)點(diǎn)大很多時，那索引占用的額外空間可忽略。

插入和刪除的時間復(fù)雜度

插入

在跳表中插入一個數(shù)據(jù)，只需O(logn)時間復(fù)雜度。
單鏈表中，一旦定位好要插入的位置，插入的時間復(fù)雜度是O(1)。但這里為了保證原始鏈表中數(shù)據(jù)的有序性，要先找到插入位置，所以這個過程中的查找操作比較耗時。

單純的單鏈表，需遍歷每個結(jié)點(diǎn)以找到插入的位置。但跳表搜索某結(jié)點(diǎn)的的時間復(fù)雜度是O(logn)，所以搜索某數(shù)據(jù)應(yīng)插入的位置的時間復(fù)雜度也是O(logn)。

刪除

如果這個結(jié)點(diǎn)在索引中也有出現(xiàn)，除了要刪除原始鏈表的結(jié)點(diǎn)，還要刪除索引中的。
因?yàn)閱捂湵韯h除操作需拿到要刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后通過指針完成刪除。所以查找要刪除結(jié)點(diǎn)時，一定要獲取前驅(qū)結(jié)點(diǎn)。若是雙向鏈表，就沒這個問題了。

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

當(dāng)不停往跳表插入數(shù)據(jù)時，若不更新索引，就可能出現(xiàn)某2個索引結(jié)點(diǎn)之間數(shù)據(jù)非常多。極端情況下，跳表還會退化成單鏈表。


作為一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，我們需要某種手段來維護(hù)索引與原始鏈表大小之間的平衡，也就是說，如果鏈表中結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加一些，避免復(fù)雜度退化，以及查找、插入、刪除操作性能下降。

像紅黑樹、AVL樹這樣的平衡二叉樹通過左右旋保持左右子樹的大小平衡，而跳表是通過隨機(jī)函數(shù)維護(hù)前面提到的“平衡性”。

往跳表插入數(shù)據(jù)時，可以選擇同時將這個數(shù)據(jù)插入到部分索引層中。

那如何選擇加入哪些索引層呢？

通過一個隨機(jī)函數(shù)決定將這個結(jié)點(diǎn)插入到哪幾級索引中，比如隨機(jī)函數(shù)生成了值K，那就把這個結(jié)點(diǎn)添加到第一級到第K級這K級索引中。

為何Redis要用跳表來實(shí)現(xiàn)有序集合，而不是紅黑樹？

Redis中的有序集合支持的核心操作主要支持：

  • 插入一個數(shù)據(jù)
  • 刪除一個數(shù)據(jù)
  • 查找一個數(shù)據(jù)
  • 迭代輸出有序序列：以上操作，紅黑樹也能完成，時間復(fù)雜度跟跳表一樣。
  • 按照區(qū)間查找數(shù)據(jù)：紅黑樹的效率低于跳表。跳表可以做到O(logn)定位區(qū)間的起點(diǎn)，然后在原始鏈表順序往后遍歷即可。

除了性能，還有其它原因：

  • 代碼實(shí)現(xiàn)比紅黑樹好懂、好寫多了，因?yàn)楹唵尉痛砜勺x性好，不易出錯
  • 跳表更靈活，可通過改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗

因?yàn)榧t黑樹比跳表誕生更早，很多編程語言中的Map類型（比如JDK 的 HashMap）都是通過紅黑樹實(shí)現(xiàn)的。業(yè)務(wù)開發(fā)時，直接從JDK拿來用，但跳表沒有一個現(xiàn)成的實(shí)現(xiàn)，只能自己實(shí)現(xiàn)。

跳表的代碼實(shí)現(xiàn)（Java 版）

數(shù)據(jù)結(jié)構(gòu)定義

表中的元素使用結(jié)點(diǎn)來表示，結(jié)點(diǎn)的層數(shù)在它被插入時隨機(jī)計(jì)算決定（與表中已有結(jié)點(diǎn)數(shù)目無關(guān)）。

一個i層的結(jié)點(diǎn)有i個前向指針（java中使用結(jié)點(diǎn)對象數(shù)組forward來表示），索引為從1到i。用MaxLevel來記錄跳表的最大層數(shù)。

跳表的層數(shù)為當(dāng)前所有結(jié)點(diǎn)中的最大層數(shù)（如果list為空，則層數(shù)為1）。

列表頭header擁有從1到MaxLevel的前向指針：

public class SkipListT> {

    // 最高層數(shù)
    private final int MAX_LEVEL;
    // 當(dāng)前層數(shù)
    private int listLevel;
    // 表頭
    private SkipListNodeT> listHead;
    // 表尾
    private SkipListNodeT> NIL;
    // 生成randomLevel用到的概率值
    private final double P;
    // 論文里給出的最佳概率值
    private static final double OPTIMAL_P = 0.25;
    
    public SkipList() {
        // 0.25, 15
        this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
    }

    public SkipList(double probability, int maxLevel) {
        P = probability;
        MAX_LEVEL = maxLevel;

        listLevel = 1;
        listHead = new SkipListNodeT>(Integer.MIN_VALUE, null, maxLevel);
        NIL = new SkipListNodeT>(Integer.MAX_VALUE, null, maxLevel);
        for (int i = listHead.forward.length - 1; i >= 0; i--) {
            listHead.forward[i] = NIL;
        }
    }

    // 內(nèi)部類
    class SkipListNodeT> {
        int key;
        T value;
        SkipListNode[] forward;
        
        public SkipListNode(int key, T value, int level) {
            this.key = key;
            this.value = value;
            this.forward = new SkipListNode[level];
        }
    }
}

搜索算法

按key搜索，找到返回該key對應(yīng)的value，未找到則返回null。

通過遍歷forward數(shù)組來需找特定的searchKey。假設(shè)skip list的key按照從小到大的順序排列，那么從跳表的當(dāng)前最高層listLevel開始尋找searchKey。在某一層找到一個非小于searchKey的結(jié)點(diǎn)后，跳到下一層繼續(xù)找，直到最底層為止。那么根據(jù)最后搜索停止位置的下一個結(jié)點(diǎn)，就可以判斷searchKey在不在跳表中。

在跳表中找8的過程：

 

插入和刪除算法

都是通過查找與連接（search and splice）：


維護(hù)一個update數(shù)組，在搜索結(jié)束之后，update[i]保存的是待插入/刪除結(jié)點(diǎn)在第i層的左側(cè)結(jié)點(diǎn)。

插入

若key不存在，則插入該key與對應(yīng)的value；若key存在，則更新value。

如果待插入的結(jié)點(diǎn)的層數(shù)高于跳表的當(dāng)前層數(shù)listLevel，則更新listLevel。

選擇待插入結(jié)點(diǎn)的層數(shù)randomLevel：

randomLevel只依賴于跳表的最高層數(shù)和概率值p。

另一種實(shí)現(xiàn)方法為，如果生成的randomLevel大于當(dāng)前跳表的層數(shù)listLevel，那么將randomLevel設(shè)置為listLevel+1，這樣方便以后的查找，在工程上是可以接受的，但同時也破壞了算法的隨機(jī)性。

刪除

刪除特定的key與對應(yīng)的value。如果待刪除的結(jié)點(diǎn)為跳表中層數(shù)最高的結(jié)點(diǎn)，那么刪除之后，要更新listLevel。

public class SkipListT> {

    // 最高層數(shù)
    private final int MAX_LEVEL;
    // 當(dāng)前層數(shù)
    private int listLevel;
    // 表頭
    private SkipListNodeT> listHead;
    // 表尾
    private SkipListNodeT> NIL;
    // 生成randomLevel用到的概率值
    private final double P;
    // 論文里給出的最佳概率值
    private static final double OPTIMAL_P = 0.25;

    public SkipList() {
        // 0.25, 15
        this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
    }

    public SkipList(double probability, int maxLevel) {
        P = probability;
        MAX_LEVEL = maxLevel;

        listLevel = 1;
        listHead = new SkipListNodeT>(Integer.MIN_VALUE, null, maxLevel);
        NIL = new SkipListNodeT>(Integer.MAX_VALUE, null, maxLevel);
        for (int i = listHead.forward.length - 1; i >= 0; i--) {
            listHead.forward[i] = NIL;
        }
    }

    // 內(nèi)部類
    class SkipListNodeT> {
        int key;
        T value;
        SkipListNode[] forward;
        
        public SkipListNode(int key, T value, int level) {
            this.key = key;
            this.value = value;
            this.forward = new SkipListNode[level];
        }
    }

    public T search(int searchKey) {
        SkipListNodeT> curNode = listHead;

        for (int i = listLevel; i > 0; i--) {
            while (curNode.forward[i].key  searchKey) {
                curNode = curNode.forward[i];
            }
        }

        if (curNode.key == searchKey) {
            return curNode.value;
        } else {
            return null;
        }
    }

    public void insert(int searchKey, T newValue) {
        SkipListNodeT>[] update = new SkipListNode[MAX_LEVEL];
        SkipListNodeT> curNode = listHead;

        for (int i = listLevel - 1; i >= 0; i--) {
            while (curNode.forward[i].key  searchKey) {
                curNode = curNode.forward[i];
            }
            // curNode.key  searchKey = curNode.forward[i].key
            update[i] = curNode;
        }

        curNode = curNode.forward[0];

        if (curNode.key == searchKey) {
            curNode.value = newValue;
        } else {
            int lvl = randomLevel();

            if (listLevel  lvl) {
                for (int i = listLevel; i  lvl; i++) {
                    update[i] = listHead;
                }
                listLevel = lvl;
            }

            SkipListNodeT> newNode = new SkipListNodeT>(searchKey, newValue, lvl);

            for (int i = 0; i  lvl; i++) {
                newNode.forward[i] = update[i].forward[i];
                update[i].forward[i] = newNode;
            }
        }
    }

    public void delete(int searchKey) {
        SkipListNodeT>[] update = new SkipListNode[MAX_LEVEL];
        SkipListNodeT> curNode = listHead;

        for (int i = listLevel - 1; i >= 0; i--) {
            while (curNode.forward[i].key  searchKey) {
                curNode = curNode.forward[i];
            }
            // curNode.key  searchKey = curNode.forward[i].key
            update[i] = curNode;
        }

        curNode = curNode.forward[0];

        if (curNode.key == searchKey) {
            for (int i = 0; i  listLevel; i++) {
                if (update[i].forward[i] != curNode) {
                    break;
                }
                update[i].forward[i] = curNode.forward[i];
            }

            while (listLevel > 0  listHead.forward[listLevel - 1] == NIL) {
                listLevel--;
            }
        }
    }

    private int randomLevel() {
        int lvl = 1;
        while (lvl  MAX_LEVEL  Math.random()  P) {
            lvl++;
        }
        return lvl;
    }

    public void print() {
    for (int i = listLevel - 1; i >= 0; i--) {
            SkipListNodeT> curNode = listHead.forward[i];
            while (curNode != NIL) {
                System.out.print(curNode.key + "->");
                curNode = curNode.forward[i];
            }
            System.out.println("NIL");
        }
    }

    public static void main(String[] args) {
        SkipListInteger> sl = new SkipListInteger>();
        sl.insert(20, 20);
        sl.insert(5, 5);
        sl.insert(10, 10);
        sl.insert(1, 1);
        sl.insert(100, 100);
        sl.insert(80, 80);
        sl.insert(60, 60);
        sl.insert(30, 30);
        sl.print();
        System.out.println("---");
        sl.delete(20);
        sl.delete(100);
        sl.print();
    }
}

到此這篇關(guān)于為何Redis使用跳表而非紅黑樹實(shí)現(xiàn)SortedSet的文章就介紹到這了,更多相關(guān)Redis跳表實(shí)現(xiàn)SortedSet內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:
  • 簡單談?wù)凪ysql索引與redis跳表

標(biāo)簽：黃山 衡水 蘭州 銅川 湘潭 湖南 仙桃 崇左

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《為何Redis使用跳表而非紅黑樹實(shí)現(xiàn)SortedSet》，本文關(guān)鍵詞  ；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請?zhí)峁┫嚓P(guān)信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 收縮
    • 微信客服
    • 微信二維碼

    • 電話咨詢

    • 400-1100-266