點(diǎn)贊再看，養(yǎng)成習(xí)慣粥帚，公眾號搜一搜【一角錢技術(shù)】關(guān)注更多原創(chuàng)技術(shù)文章胰耗。本文 GitHub org_hejianhui/JavaStudy 已收錄，有我的系列文章芒涡。

前言

在這里我們先回憶一下普通鏈表的時(shí)間復(fù)雜度柴灯，可以看到除了 look up 操作是 的卖漫，其他操作都是 的時(shí)間復(fù)雜度。也就是說你需要隨機(jī)訪問里面的任何一個(gè)元素的話赠群，它的時(shí)間復(fù)雜度平均值是 的羊始，這也就是鏈表它的問題所在。從這里可以看到并沒有所謂完美的一種數(shù)據(jù)結(jié)構(gòu)查描，如果完美那就不需要 Array 或者 LInked List 這兩個(gè)數(shù)據(jù)結(jié)構(gòu)并存了店枣，就直接使用最牛逼的數(shù)據(jù)結(jié)構(gòu)即可。所以相當(dāng)于各有優(yōu)劣叹誉，看你的使用場景在什么地方鸯两，作為完整性比較，我這里把兩種時(shí)間復(fù)雜度都列出來长豁。

Linked List 的時(shí)間復(fù)雜度

Array 的時(shí)間復(fù)雜度

注意：正常情況下數(shù)組的 prepend 操作的時(shí)間復(fù)雜度是 O(n) 钧唐，但是可以進(jìn)行特殊優(yōu)化到 O(1)。采用的方式是申請稍微大一些的內(nèi)存空間匠襟，然后在數(shù)組開始預(yù)留一部分空間钝侠，然后 prepend 的操作則是把頭下標(biāo)前移一個(gè)位置即可。

跳表 Skip List

前面回顧了 Array 和 Linked List 的兩種結(jié)構(gòu)的時(shí)間復(fù)雜度酸舍，有一種情況下鏈表它的速度在 這一塊帅韧，就會覺得不太夠用，我們來看一下這種情況指的是什么啃勉？

鏈表元素有序的時(shí)候

一個(gè)有序的數(shù)組里面存在颗搂，那么問題來了，如果是有序的幕垦，但是是鏈表的情況下應(yīng)該怎樣有效地加速呢丢氢？于是在近代1990年前后傅联，一種新的數(shù)據(jù)結(jié)構(gòu)出現(xiàn)了，它的名字叫做 跳表疚察。

跳表的特點(diǎn)

注意：只能用于元素有序的情況蒸走。

所以，跳表（skip list）對表的是平衡樹（AVL Tree）和 二分查找貌嫡，是一種 插入/刪除/搜索 都是 的數(shù)據(jù)結(jié)構(gòu)比驻。1989 年出現(xiàn)。

不管是平衡樹岛抄、二叉搜索樹其他哪些樹的話都是在1960年和196幾年就已經(jīng)出現(xiàn)了别惦，它的出現(xiàn)比平衡樹和二分查找以及所謂的一些高級數(shù)據(jù)結(jié)構(gòu)出現(xiàn)的要晚。比其他的晚了接近30年夫椭，最后才出現(xiàn)掸掸，這就是為什么很多老的數(shù)據(jù)結(jié)構(gòu)的話，用平衡二叉樹會多一點(diǎn)蹭秋，而一些比較新的扰付，特別是在元素個(gè)數(shù)不多的情況的情況下，用的全部都是跳表仁讨，也就是說在更新?lián)Q代了羽莺。

它的最大優(yōu)勢是原理簡單、容易實(shí)現(xiàn)洞豁、方便擴(kuò)展盐固、效率更高。因此在一些熱門的項(xiàng)目里用來替代平衡樹族跛，如 Redis闰挡、LevelDB等。

跳躍表（skiplist）是一種隨機(jī)化的數(shù)據(jù)礁哄， 由 William Pugh 在論文《Skip lists: a probabilistic alternative to balanced trees》中提出， 跳躍表以有序的方式在層次化的鏈表中保存元素溪北， 效率和平衡樹媲美 —— 查找桐绒、刪除、添加等操作都可以在對數(shù)期望時(shí)間下完成之拨， 并且比起平衡樹來說茉继， 跳躍表的實(shí)現(xiàn)要簡單直觀得多。

如何給有序的鏈表加速

假設(shè)有一個(gè)有序的鏈表蚀乔，1 3 4 5 7 8 9 10 這么一個(gè)原始的鏈表烁竭。它的時(shí)間復(fù)雜度查詢肯定是 的，那么問一下如何優(yōu)化吉挣？如何進(jìn)行簡單優(yōu)化派撕？可以讓它的查詢時(shí)間復(fù)雜度變低婉弹，也就是加速它的查詢。

我們可以思考一些终吼，如果你來比如說我要很快地查到 7 镀赌，有沒有在鏈表中存在和它的位置在哪兒的話，你能夠非臣使颍快的查詢出來嗎商佛？

• 時(shí)間復(fù)雜度：查詢 O(n)
• 簡單優(yōu)化：添加頭尾指針

上面這么一個(gè)結(jié)構(gòu)，它是一維的數(shù)據(jù)結(jié)構(gòu)姆打，現(xiàn)在它是有序了良姆，也就是說我們有附加的信息了，那么如何加速對吧幔戏？一般來說這種加速的方式的話玛追，就類似于星際穿越里面這有點(diǎn)玄學(xué)，但是你一定要記住一個(gè)概念就行了评抚，一維的數(shù)據(jù)結(jié)構(gòu)要加速的話豹缀，經(jīng)常采用的方式就是升維也就是說變成二維。為什么要多一層維度慨代，因?yàn)槟愣嗔艘粋€(gè)維度之后邢笙，就會有多一級的信息在里面，這樣多一級的信息就可以幫助你可以很快地得到一維里面你必須挨個(gè)走才能走到的那些元素

添加第一級索引

如何提高鏈表線性查找的效率侍匙？

具體我們來看上圖氮惯，在原始鏈表的情況下，我們再增加一個(gè)維度想暗，也就是在上面再增加一層索引妇汗，我們叫做第一級索引，那么第一級索引的話就不是指向它元素的 next 元素了说莫，而是指向它的 next next 杨箭，也就是說你可以理解為 next + 1 就行了，所以第一級索引的話就是第一個(gè)元素储狭，馬上第三個(gè)元素互婿、第五個(gè)元素、第七個(gè)元素辽狈。

• 這里你就會發(fā)現(xiàn)如果你要找7的話慈参，我們怎么辦？我們這么查找刮萌，先查找第一級索引看有沒有1 4 7 驮配，如果有那就說明 7 存在這個(gè)鏈表里面是存在的，說明我們查詢到了。
• 我們再看要查另一個(gè)元素壮锻，比如說 8琐旁，我們怎么走？還是先找第一級躯保，8是大于 1 的睬关，所以后繼往后到達(dá) 4 索引的值专执，8 是大于 4的坑匠，繼續(xù)往后到了7吭服，8 也大于7的，再繼續(xù)往后發(fā)現(xiàn) 9 大于 8 了尸变。說明 8 是存在于 7 和 9 這兩個(gè)索引之間的元素里面的义图，那么這個(gè)時(shí)候從第一級元素向下走到原始的鏈表了，從對應(yīng)的位置挨個(gè)找就會發(fā)現(xiàn) 8 找到了召烂，說明 8 也是存在的碱工。

添加第二級索引

那么有的朋友可能就會想了，你加一級索引的話奏夫，每次相當(dāng)于步伐加 2 了怕篷，但是它的速度的話也就是比原來稍微快了一點(diǎn)，能不能更快呢酗昼？對你這個(gè)想法是非常有道理的廊谓，也是很好的。

那么在一級索引的基礎(chǔ)上麻削，我們可以再加索引就行了蒸痹，也就是說同理可得，在第一級索引的基礎(chǔ)上呛哟，我們把它當(dāng)作是一個(gè)原始鏈表一樣叠荠，往上再加一級索引，也就是說每次針對第一級索引走兩步扫责。那么它相等于原始鏈表相當(dāng)于每次就走了四步榛鼎。對不對，就乘于 2鳖孤，那這樣的話借帘，速度就更加高效了。

• 比如我舉個(gè)例子要查8淌铐，先找 1，8 比 1要大蔫缸，再找 7 腿准，這時(shí)候你會發(fā)現(xiàn) 8 也是比 7 大的，再找，假設(shè)這個(gè)元素后面的話是 11 或者 12 好了吐葱，這時(shí)候你會發(fā)現(xiàn) 8 是小于它后面的元素街望，所以 7 這里的話就必須向下再走一級索引了，走到第一級索引的 7 來弟跑，再類似于之前 7 和 9 之間灾前，然后再走到8 這樣一直走下來。

添加多級索引

以此類推孟辑，增加多級索引

假設(shè)有五級索引的這么一個(gè)原始鏈表哎甲，那么我們要查一個(gè)元素，比如說要查 62 元素或者中間元素饲嗽，就類似于下圖炭玫，一級一級一級一級走下來，最后的話就可以查到我們需要的62這個(gè)元素貌虾。當(dāng)然的話你最后查到原始鏈表吞加，你會發(fā)現(xiàn)比如說是我們要查63或者61，原始鏈表里面沒有尽狠，我們就說元素不存在衔憨，在我們這個(gè)有序的鏈表里面，也就是說在跳表里面查不到這么一個(gè)元素袄膏，最后也可以得出這樣的結(jié)論践图。

跳表查詢的時(shí)間復(fù)雜度分析

跳表的時(shí)間復(fù)雜度計(jì)算

• n/2、n/4哩陕、n/8平项、第 k 級索引結(jié)點(diǎn)的個(gè)數(shù)就是 n/(2^k)
• 假設(shè)索引有 h 級，最高級的索引有 2 個(gè)結(jié)點(diǎn)悍及。n/(2^h) = 2闽瓢，從而求得 h = log2(n)-1

舉一個(gè)例子，跳表在查詢的時(shí)候心赶，假設(shè)索引的高度：logn扣讼，每層索引遍歷的結(jié)點(diǎn)個(gè)數(shù)：3，假設(shè)要走到第 8 個(gè)節(jié)點(diǎn)缨叫。

每層要遍歷的元素總共是3個(gè)椭符，所以這里的話 log28 的話，就是它的時(shí)間復(fù)雜度耻姥。最后的話得出證明出來：時(shí)間復(fù)雜度為log2n销钝。也就是從最樸素的原始鏈表的話，它的 O(n) 的時(shí)間復(fù)雜度降到 log2n 的時(shí)間復(fù)雜度琐簇。這已經(jīng)是一個(gè)很大的改進(jìn)了蒸健。假設(shè)是1024的話座享，你會發(fā)現(xiàn)原始鏈表要查1024次最后得到這個(gè)元素，那么這里的話就只需要查（2的10次方是1024次）十次這樣一個(gè)數(shù)量級似忧。

現(xiàn)實(shí)中跳表的形態(tài)

在現(xiàn)實(shí)中我們在用跳表的情況下渣叛，它會由于這個(gè)元素的增加和刪除而導(dǎo)致的它的索引的話，有些數(shù)它并不是完全非常工整的盯捌，最后經(jīng)過多次改動(dòng)后淳衙，它最后索引有些地方會跨幾步，有些地方會少只跨兩步饺著，這是因?yàn)槔锩娴囊恍┰貢辉黾雍蛣h除了箫攀，而且它的維護(hù)成本相對較高，也是說當(dāng)你增加一個(gè)元素瓶籽，你會把它的索引要更新一遍匠童，你要?jiǎng)h除一個(gè)元素，也需要把它的索引更新一遍塑顺。在這種過程中它在增加和刪除的話汤求，它的時(shí)間復(fù)雜度就會變成 了。

在跳表中查詢?nèi)我鈹?shù)據(jù)的時(shí)平均時(shí)間復(fù)雜度就是 O(logn)严拒。

跳表查詢的空間復(fù)雜度分析

在這里的話扬绪，我們假設(shè)它的長度為 n，然后按照之前的例子裤唠，每兩個(gè)節(jié)點(diǎn)抽一個(gè)做成一個(gè)索引的話挤牛，那么它的一級索引為二分之 n 對吧。最后如下：

• 原始鏈表大小為 n种蘸，每 2 個(gè)結(jié)點(diǎn)抽 1 個(gè)墓赴，每層索引的結(jié)點(diǎn)數(shù):

• 原始鏈表大小為 n，每 3 個(gè)結(jié)點(diǎn)抽 1 個(gè)航瞭，每層索引的結(jié)點(diǎn)數(shù):

• 空間復(fù)雜度是

跳躍表的構(gòu)成

以下是個(gè)典型的跳躍表例子：

從圖中可以看到诫硕， 跳躍表主要由以下部分構(gòu)成：

• 表頭（head）：負(fù)責(zé)維護(hù)跳躍表的節(jié)點(diǎn)指針。
• 跳躍表節(jié)點(diǎn)：保存著元素值刊侯，以及多個(gè)層章办。
• 層：保存著指向其他元素的指針。高層的指針越過的元素?cái)?shù)量大于等于低層的指針滨彻，為了提高查找的效率藕届，程序總是從高層先開始訪問，然后隨著元素值范圍的縮小亭饵，慢慢降低層次休偶。
• 表尾：全部由 NULL 組成，表示跳躍表的末尾辜羊。

Redis 跳躍表的實(shí)現(xiàn)

Redis 的跳躍表由 redis.h/zskiplistNode 和 redis.h/zskiplist 兩個(gè)結(jié)構(gòu)定義椅贱， 其中 zskiplistNode 結(jié)構(gòu)用于表示跳躍表節(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ù)最大的那個(gè)節(jié)點(diǎn)的層數(shù)（表頭節(jié)點(diǎn)的層數(shù)不計(jì)算在內(nèi)）萌衬。
• length ：記錄跳躍表的長度饮醇，也即是，跳躍表目前包含節(jié)點(diǎn)的數(shù)量（表頭節(jié)點(diǎn)不計(jì)算在內(nèi)）秕豫。

位于 zskiplist 結(jié)構(gòu)右方的是四個(gè) zskiplistNode 結(jié)構(gòu)朴艰， 該結(jié)構(gòu)包含以下屬性：

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

注意：表頭節(jié)點(diǎn)和其他節(jié)點(diǎn)的構(gòu)造是一樣的： 表頭節(jié)點(diǎn)也有后退指針槽片、分值和成員對象何缓， 不過表頭節(jié)點(diǎn)的這些屬性都不會被用到， 所以圖中省略了這些部分还栓， 只顯示了表頭節(jié)點(diǎn)的各個(gè)層碌廓。

跳躍表節(jié)點(diǎn)

跳躍表節(jié)點(diǎn)的實(shí)現(xiàn)由 redis.h/zskiplistNode 結(jié)構(gòu)定義：

typedef struct zskiplistNode {
    // 后退指針
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成員對象
    robj *obj;
    // 層
    struct zskiplistLevel {
        // 前進(jìn)指針
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

層

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

每次創(chuàng)建一個(gè)新跳躍表節(jié)點(diǎn)的時(shí)候， 程序都根據(jù)冪次定律 （power law跟匆，越大的數(shù)出現(xiàn)的概率越幸彀馈） 隨機(jī)生成一個(gè)介于 1 和 32 之間的值作為 level 數(shù)組的大小， 這個(gè)大小就是層的“高度”玛臂。

下圖分別展示了三個(gè)高度為 1 層烤蜕、 3 層和 5 層的節(jié)點(diǎn)， 因?yàn)?C 語言的數(shù)組索引總是從 0 開始的垢揩， 所以節(jié)點(diǎn)的第一層是 level[0] 玖绿， 而第二層是 level[1] ， 以此類推叁巨。

前進(jìn)指針

每個(gè)層都有一個(gè)指向表尾方向的前進(jìn)指針（level[i].forward 屬性）斑匪， 用于從表頭向表尾方向訪問節(jié)點(diǎn)。

1. 迭代程序首先訪問跳躍表的第一個(gè)節(jié)點(diǎn)（表頭）蚀瘸， 然后從第四層的前進(jìn)指針移動(dòng)到表中的第二個(gè)節(jié)點(diǎn)。
2. 在第二個(gè)節(jié)點(diǎn)時(shí)庶橱， 程序沿著第二層的前進(jìn)指針移動(dòng)到表中的第三個(gè)節(jié)點(diǎn)贮勃。
3. 在第三個(gè)節(jié)點(diǎn)時(shí)， 程序同樣沿著第二層的前進(jìn)指針移動(dòng)到表中的第四個(gè)節(jié)點(diǎn)苏章。
4. 當(dāng)程序再次沿著第四個(gè)節(jié)點(diǎn)的前進(jìn)指針移動(dòng)時(shí)寂嘉， 它碰到一個(gè) NULL ， 程序知道這時(shí)已經(jīng)到達(dá)了跳躍表的表尾枫绅， 于是結(jié)束這次遍歷泉孩。

跨度

層的跨度（level[i].span 屬性）用于記錄兩個(gè)節(jié)點(diǎn)之間的距離：

• 兩個(gè)節(jié)點(diǎn)之間的跨度越大， 它們相距得就越遠(yuǎn)并淋。
• 指向 NULL 的所有前進(jìn)指針的跨度都為 0 寓搬， 因?yàn)樗鼈儧]有連向任何節(jié)點(diǎn)。

初看上去县耽， 很容易以為跨度和遍歷操作有關(guān)句喷， 但實(shí)際上并不是這樣 —— 遍歷操作只使用前進(jìn)指針就可以完成了镣典， 跨度實(shí)際上是用來計(jì)算排位（rank）的： 在查找某個(gè)節(jié)點(diǎn)的過程中， 將沿途訪問過的所有層的跨度累計(jì)起來唾琼， 得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳躍表中的排位兄春。

舉個(gè)例子， 如下用虛線標(biāo)記了在跳躍表中查找分值為 3.0 父叙、 成員對象為 o3 的節(jié)點(diǎn)時(shí)神郊， 沿途經(jīng)歷的層： 查找的過程只經(jīng)過了一個(gè)層， 并且層的跨度為 3 趾唱， 所以目標(biāo)節(jié)點(diǎn)在跳躍表中的排位為 3 。

再舉個(gè)例子蜻懦， 如下用虛線標(biāo)記了在跳躍表中查找分值為 2.0 甜癞、 成員對象為 o2 的節(jié)點(diǎn)時(shí)， 沿途經(jīng)歷的層： 在查找節(jié)點(diǎn)的過程中宛乃， 程序經(jīng)過了兩個(gè)跨度為 1 的節(jié)點(diǎn)悠咱， 因此可以計(jì)算出， 目標(biāo)節(jié)點(diǎn)在跳躍表中的排位為 2 征炼。

后退指針

節(jié)點(diǎn)的后退指針（backward 屬性）用于從表尾向表頭方向訪問節(jié)點(diǎn)： 跟可以一次跳過多個(gè)節(jié)點(diǎn)的前進(jìn)指針不同析既， 因?yàn)槊總€(gè)節(jié)點(diǎn)只有一個(gè)后退指針， 所以每次只能后退至前一個(gè)節(jié)點(diǎn)谆奥。

分值和成員

• 節(jié)點(diǎn)的分值（score 屬性）是一個(gè) double 類型的浮點(diǎn)數(shù)魄懂， 跳躍表中的所有節(jié)點(diǎn)都按分值從小到大來排序沿侈。
• 節(jié)點(diǎn)的成員對象（obj 屬性）是一個(gè)指針， 它指向一個(gè)字符串對象市栗， 而字符串對象則保存著一個(gè) SDS（簡單動(dòng)態(tài)字符串） 值缀拭。

在同一個(gè)跳躍表中， 各個(gè)節(jié)點(diǎn)保存的成員對象必須是唯一的填帽， 但是多個(gè)節(jié)點(diǎn)保存的分值卻可以是相同的： 分值相同的節(jié)點(diǎn)將按照成員對象在字典序中的大小來進(jìn)行排序蛛淋， 成員對象較小的節(jié)點(diǎn)會排在前面（靠近表頭的方向）， 而成員對象較大的節(jié)點(diǎn)則會排在后面（靠近表尾的方向）盲赊。

舉個(gè)例子铣鹏， 在下圖所示的跳躍表中， 三個(gè)跳躍表節(jié)點(diǎn)都保存了相同的分值 10086.0 哀蘑， 但保存成員對象 o1 的節(jié)點(diǎn)卻排在保存成員對象 o2 和 o3 的節(jié)點(diǎn)之前诚卸， 而保存成員對象 o2 的節(jié)點(diǎn)又排在保存成員對象 o3 的節(jié)點(diǎn)之前葵第， 由此可見， o1 合溺、 o2 卒密、 o3 三個(gè)成員對象在字典中的排序?yàn)?o1 <= o2 <= o3 。

跳躍表

雖然僅靠多個(gè)跳躍表節(jié)點(diǎn)就可以組成一個(gè)跳躍表棠赛， 如下圖 所示：

typedef struct zskiplist {

    // 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
    struct zskiplistNode *header, *tail;

    // 表中節(jié)點(diǎn)的數(shù)量
    unsigned long length;

    // 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
    int level;

} zskiplist;

• header 和 tail 指針分別指向跳躍表的表頭和表尾節(jié)點(diǎn)， 通過這兩個(gè)指針辩涝， 程序定位表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的復(fù)雜度為 O(1) 贸伐。
• 通過使用 length 屬性來記錄節(jié)點(diǎn)的數(shù)量， 程序可以在 O(1) 復(fù)雜度內(nèi)返回跳躍表的長度怔揩。
• level 屬性則用于在 O(1) 復(fù)雜度內(nèi)獲取跳躍表中層高最大的那個(gè)節(jié)點(diǎn)的層數(shù)量捉邢， 注意表頭節(jié)點(diǎn)的層高并不計(jì)算在內(nèi)。

跳躍表API

列出了跳躍表的所有操作 API 商膊。

面試：為啥 redis 使用跳表(skiplist)而不是使用 red-black右核？

1. skiplist的復(fù)雜度和紅黑樹一樣，而且實(shí)現(xiàn)起來更簡單渺绒。
2. 在并發(fā)環(huán)境下skiplist有另外一個(gè)優(yōu)勢贺喝，紅黑樹在插入和刪除的時(shí)候可能需要做一些rebalance的操作，這樣的操作可能會涉及到整個(gè)樹的其他部分宗兼，而skiplist的操作顯然更加局部性一些躏鱼，鎖需要盯住的節(jié)點(diǎn)更少，因此在這樣的情況下性能好一些殷绍。

具體可以參考Herb Sutter寫的Choose Concurrency-Friendly Data Structures.

另外這篇論文里有更詳細(xì)的說明和對比染苛，page50~53：
http://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf

附：開發(fā)者說的為什么選用skiplist The Skip list

There are a few reasons:

1. They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
   About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.

About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.

總結(jié)

• 跳躍表是有序集合的底層實(shí)現(xiàn)之一， 除此之外它在 Redis 中沒有其他應(yīng)用主到。
• Redis 的跳躍表實(shí)現(xiàn)由 zskiplist 和 zskiplistNode 兩個(gè)結(jié)構(gòu)組成茶行， 其中 zskiplist 用于保存跳躍表信息（比如表頭節(jié)點(diǎn)躯概、表尾節(jié)點(diǎn)、長度）拢军， 而 zskiplistNode 則用于表示跳躍表節(jié)點(diǎn)楞陷。
• 每個(gè)跳躍表節(jié)點(diǎn)的層高都是 1 至 32 之間的隨機(jī)數(shù)。
• 在同一個(gè)跳躍表中茉唉， 多個(gè)節(jié)點(diǎn)可以包含相同的分值固蛾， 但每個(gè)節(jié)點(diǎn)的成員對象必須是唯一的。
• 跳躍表中的節(jié)點(diǎn)按照分值大小進(jìn)行排序度陆， 當(dāng)分值相同時(shí)艾凯， 節(jié)點(diǎn)按照成員對象的大小進(jìn)行排序。

參考資料

• 跳躍表

文章持續(xù)更新懂傀，可以公眾號搜一搜「 一角錢技術(shù) 」第一時(shí)間閱讀趾诗， 本文 GitHub org_hejianhui/JavaStudy 已經(jīng)收錄，歡迎 Star蹬蚁。