redis數(shù)據(jù)結(jié)構(gòu)中跳躍表的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)redis數(shù)據(jù)結(jié)構(gòu)中跳躍表的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

跳躍表定義:

跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點(diǎn)中維持多個指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。

跳躍表支持平均O（logN）、最壞O（N）復(fù)雜度的節(jié)點(diǎn)查找，還可以通過順序性操作來批量處理節(jié)點(diǎn)。

跳躍表使用場景:

Redis使用跳躍表作為有序集合鍵的底層實(shí)現(xiàn)之一，如果一個有序集合包含的元素數(shù)量比較多，又或者有序集合中元素的成員（member）是比較長的字符串時，Redis就會使用跳躍表來作為有序集合鍵的底層實(shí)現(xiàn), 和鏈表、字典等數(shù)據(jù)結(jié)構(gòu)被廣泛地應(yīng)用在Redis內(nèi)部不同，Redis只在兩個地方用到了跳躍表，一個是實(shí)現(xiàn)有序集合鍵，另一個是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)，除此之外，跳躍表在Redis里面沒有其他用途。

跳躍表構(gòu)成:

Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結(jié)構(gòu)定義。

zskiplistNode結(jié)構(gòu)用于表示跳躍表節(jié)點(diǎn):

?層（level）：節(jié)點(diǎn)中用L1、L2、L3等字樣標(biāo)記節(jié)點(diǎn)的各個層，L1代表第一層，L2代表第二層，以此類推。每個層都帶有兩個屬性：前進(jìn)指針和跨度。前進(jìn)指針用于訪問位于表尾方向的其他節(jié)點(diǎn)，而跨度則記錄了前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離。在上面的圖片中，連線上帶有數(shù)字的箭頭就代表前進(jìn)指針，而那個數(shù)字就是跨度。當(dāng)程序從表頭向表尾進(jìn)行遍歷時，訪問會沿著層的前進(jìn)指針進(jìn)行。?后退（backward）指針：節(jié)點(diǎn)中用BW字樣標(biāo)記節(jié)點(diǎn)的后退指針，它指向位于當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)。后退指針在程序從表尾向表頭遍歷時使用。?分值（score）：各個節(jié)點(diǎn)中的1.0、2.0和3.0是節(jié)點(diǎn)所保存的分值。在跳躍表中，節(jié)點(diǎn)按各自所保存的分值從小到大排列。?成員對象（obj）：各個節(jié)點(diǎn)中的o1、o2和o3是節(jié)點(diǎn)所保存的成員對象。

zskiplist結(jié)構(gòu):用于保存跳躍表節(jié)點(diǎn)的相關(guān)信息，比如節(jié)點(diǎn)的數(shù)量，以及指向表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的指針等等。

?header：指向跳躍表的表頭節(jié)點(diǎn)。?tail：指向跳躍表的表尾節(jié)點(diǎn)?level：記錄目前跳躍表內(nèi)，層數(shù)最大的那個節(jié)點(diǎn)的層數(shù)（表頭節(jié)點(diǎn)的層數(shù)不計算在內(nèi)）?length：記錄跳躍表的長度，也即是，跳躍表目前包含節(jié)點(diǎn)的數(shù)量（表頭節(jié)點(diǎn)不計算在內(nèi)

跳躍表展示圖:

zskiplistNod 結(jié)構(gòu)詳細(xì)介紹：

?結(jié)構(gòu)定義：

跳躍表節(jié)點(diǎn)的level數(shù)組可以包含多個元素，每個元素都包含一個指向其他節(jié)點(diǎn)的指針，程序可以通過這些層來加快訪問其他節(jié)點(diǎn)的速度，一般來說，層的數(shù)量越多，訪問其他節(jié)點(diǎn)的速度就越快

查詢遍歷過程：

?1）迭代程序首先訪問跳躍表的第一個節(jié)點(diǎn)（表頭），然后從第四層的前進(jìn)指針移動到表中的第二個節(jié)點(diǎn)。?2）在第二個節(jié)點(diǎn)時，程序沿著第二層的前進(jìn)指針移動到表中的第三個節(jié)點(diǎn)。?3）在第三個節(jié)點(diǎn)時，程序同樣沿著第二層的前進(jìn)指針移動到表中的第四個節(jié)點(diǎn)。?4）當(dāng)程序再次沿著第四個節(jié)點(diǎn)的前進(jìn)指針移動時，它碰到一個NULL，程序知道這時已經(jīng)到達(dá)了跳躍表的表尾，于是結(jié)束這次遍歷。

舉個查詢例子：

假如要查詢 數(shù)值為3.0的位置，從頭節(jié)點(diǎn)出發(fā)遍歷到3.0, 沿途經(jīng)歷的層：查找的過程只經(jīng)過了一個層，并且層的跨度為3，所以目標(biāo)節(jié)點(diǎn)在跳躍表中的位置為3。是不是很快！

zskiplist 結(jié)構(gòu)詳細(xì)介紹：

?結(jié)構(gòu)定義：

通過使用一個zskiplist結(jié)構(gòu)來持有這些節(jié)點(diǎn)，程序可以更方便地對整個跳躍表進(jìn)行處理，比如快速訪問跳躍表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)，或者快速地獲取跳躍表節(jié)點(diǎn)的數(shù)量（也即是跳躍表的長度）等信息

跳躍表常見api

關(guān)于“redis數(shù)據(jù)結(jié)構(gòu)中跳躍表的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。