Redis跳躍表的基本原理和實現

2022-06-09 14:04:27

一、概述

跳躍表（skiplist）是一種有序資料結構，它通過在每個節點中維持多個指向其他節點的指標，從而達到快速存取節點的目的。

如下，對於單個連結串列來講，即便連結串列中儲存的資料是有序的，如果我們要向在其中查詢某個資料，它只能從頭到尾遍歷連結串列。這樣查詢效率就會很低，時間複雜度會很高，達到了O(n)。

如果我們想要提高其查詢效率，可以考慮在連結串列上構建索引的方式，每兩個節點提取一個節點到上級，我們把抽出來的那一級就叫做索引，如下：

此時，我們假設要查詢節點8，我們可以先在索引層遍歷，當遍歷到索引層中值為7的節點時，發現下一個節點是9，那麼要查詢的節點肯定在這兩個節點之間，我們下降到連結串列層繼續遍歷就找到了8這個節點。原來我們在單連結串列中找到8這個節點要遍歷8個節點，而現在有了一級索引後，只需要遍歷5個節點。

從上個例子中，我們可以看出，加來一層索引後，查詢一個節點需要遍歷的節點個數減少了，也就是說查詢效率得到了提升，同理我們在一級索引的基礎上，在加二級索引。

從圖中我們可以看出，查詢效率又有了提升，因為在這裡例子中我們的資料量很少，當有大量的資料時，我們可以增加多級索引，在查詢時，效率可以得到明顯的提升。像這種連結串列增加多種索引的結構，就是跳躍表。

Redis使用跳躍表作為有序集合鍵的底層實現之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員（member）是比較長的字串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現。

二、跳躍表的實現

Redis的跳躍表由zskiplistNode和zskiplist兩個結構定義，其中zskiplistNode結構用於表示跳躍表節點，而zskiplist結構則用於儲存跳躍表節點的相關資訊，比如節點的數量，以及指向表頭節點和表尾節點的指標等等，如下，是一個跳躍表的結構：

上圖片最左邊的是zskiplist結構，該結構包含以下屬性：

header：指向跳躍表的表頭節點，通過這個指標程式定位表頭節點的時間複雜度就為O(1)；
tail：指向跳躍表的表尾節點，通過這個指標程式定位表尾節點的時間複雜度就為O(1)；
level：記錄目前跳躍表內，層數最大的那個節點的層數（表頭節點的層數不計算在內）；通過這個屬性可以再O(1)的時間複雜度內獲取層高最高的節點的層數
length：記錄跳躍表的長度，也即是，跳躍表目前包含節點的數量（表頭節點不計算在內）通過這個屬性，程式可以再O(1)的時間複雜度內返回跳躍表的長度

上圖位於zskiplist結構右方的是四個zskiplistNode結構，該結構包含以下屬性：

層（level）：節點中用L1、L2、L3等字樣標記節點的各個層，L1代表第一層，L2代表第二層，以此類推。每個層都帶有兩個屬性：前進指標和跨度。前進指標用於存取位於表尾方向的其他節點，而跨度則記錄了前進指標所指向節點和當前節點的距離（跨度越大，距離越遠）。在上面的圖片中，連線上帶有數位的箭頭就代表前進指標，而那個數位就是跨度。當程式從表頭向表尾進行遍歷時，存取會沿著層的前進指標進行。
後退（backward）指標：節點中用BW字樣標記節點的後退指標，它指向位於當前節點的前一個節點。後退指標在程式從表尾向表頭遍歷時使用
分值（score）：各個節點中的1.0、2.0和3.0是節點所儲存的分值。在跳躍表中，節點按各自所儲存的分值從小到大排列。
成員物件（obj）：各個節點中的o1、o2和o3是節點所儲存的成員物件

2.1 跳躍表節點的zskiplisNode結構定義

typedef struct zskiplistNode {
    // 層
    struct zskiplistLevel {
        // 前進指標
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
    // 後退指標
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成員物件
    robj *obj;
} zskiplistNode;

層：跳躍表節點的level陣列可以包含多個元素，每個元素都包含一個指向其他節點的指標，程式可以通過這些層來加快存取其他節點的速度，一般來說，層的數量越多，存取其他節點的速度就越快。
每個層都有一個指向表尾方向的前進指標（level[i].forward屬性），用於從表頭向表尾方向存取節點
層的跨度（level[i].span屬性）用於記錄兩個節點之間的距離。
節點的後退指標（backward屬性）用於從表尾向表頭方向存取節點：跟可以一次跳過多個節點的前進指標不同，因為每個節點只有一個後退指標，所以每次只能後退至前一個節點
節點的分值（score屬性）是一個double型別的浮點數，跳躍表中的所有節點都按分值從小到大來排序；
節點的成員物件（obj屬性）是一個指標，它指向一個字串物件，而字串物件則儲存著一個SDS值

2.2 zskiplist結構的定義

typedef struct zskiplist {
    // 表頭節點和表尾節點
    structz skiplistNode *header, *tail;
    // 表中節點的數量
    unsigned long length;
    // 表中層數最大的節點的層數
    int level;
} zskiplist;

header和tail指標分別指向跳躍表的表頭和表尾節點，通過這兩個指標，程式定位表頭節點和表尾節點的複雜度為O(1)。

通過使用length屬性來記錄節點的數量，程式可以在O(1)複雜度內返回跳躍表的長度。

三、結束

Redis使用跳躍表作為有序集合鍵的底層實現之一，如果一個有序集合包含的元素數量比較多，又或者有序集合中元素的成員（member）是比較長的字串時，Redis就會使用跳躍表來作為有序集合鍵的底層實現。之所以如此，是因為跳躍表在連結串列的基礎上增加了多級索引以提升查詢的效率，但其是一個空間換時間的方案，必然會帶來一個問題——索引是佔記憶體的。原始連結串列中儲存的有可能是很大的物件，而索引結點只需要儲存關鍵值值和幾個指標，並不需要儲存物件，因此當節點本身比較大或者元素數量比較多的時候，其優勢必然會被放大，而缺點則可以忽略。

到此這篇關於Redis跳躍表的基本原理和實現的文章就介紹到這了,更多相關Redis跳躍表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！