Redis 深度解析：跳躍表的原理與應用

一、跳躍表簡介

跳躍表SkipList是一種有序的數據結構，是 Redis 有序集合的底層實現之一。

跳躍表中，數據被存儲在節點中，每個節點包含一個數據元素和一組指向其他節點的指針。這些指針分佈在不同的層級，用於提升跳躍表的訪問性能。

跳躍表支持平均O(log N）、最壞O(N)複雜度的查找性能，並且支持通過順序性操作來批量處理節點。

在大部分情況下，跳躍表的效率可以和平衡樹相媲美，並且因爲眺躍表的實現比平衡樹 要來得更爲簡單，所以有不少程序都使用跳躍表來代替平衡樹。

二、跳躍表的原理

1. 跳躍表的數據結構

跳躍表是一種擴展的有序鏈表，它通過維護一個多級索引結構來實現快速查找。在跳躍表中，每個節點包含一個數據元素和一組指向其他節點的指針。這些指針分佈在不同的層級，每個層級的指針數量都比下一層級少。最底層（第 0 層）包含所有的元素，而最高層則只包含少數幾個元素。這樣，查找操作可以在高層級開始，快速跳過那些不需要的元素。

• 簡單的有序鏈表

在簡單的有序列表中，要訪問節點節點 3 需要經過節點 1、2、3 共 3 個節點；要訪問節點 9 需要經過節點 1、2、3…8、9 共 9 個節點

• 跳躍表

在跳躍表中，要訪問節點節點 3 需要經過節點 1、3 共 2 個節點（通過 L1 索引）；要訪問節點 9 需要經過節點 1、7、9 共 3 個節點（通過 L3 索引）。

可以看到查找的複雜度得到極大提升。

2. 跳躍表的查找、插入和刪除操作

• 查找操作

  從最高層索引的頭節點開始，

• 如果當前節點的下一個節點的值小於要查找的值，則向右移動；

• 如果當前節點的下一個節點的值大於要查找的值，則向下移動，

• 直到找到目標值或者確定目標值不存在。

• 插入操作

  首先進行查找操作，找到插入位置。然後隨機生成一個層數，根據這個層數在每一層插入新節點。

• 刪除操作：

  首先進行查找操作，找到要刪除的節點。然後在每一層刪除這個節點。

3. 跳躍表的時間複雜度分析

由於跳躍表的層級結構，查找、插入和刪除操作的平均時間複雜度和最壞時間複雜度都是 O(log n)，其中 n 是跳躍表中元素的數量。這使得跳躍表在處理大量數據時具有很高的效率。同時，跳躍表的空間複雜度是 O(n)，因爲每個元素都需要存儲在跳躍表中。

三、Redis 中的跳躍表

1. Redis 中跳躍表的實現

Redis 中的跳躍表實現與基本的跳躍表有一些不同。在 Redis 中，跳躍表的每個節點除了包含一個指向下一個節點的指針數組外，還包含一個反向指針，指向前一個節點。這樣，Redis 的跳躍表可以支持雙向遍歷。此外，Redis 的跳躍表還包含一個header節點和一個tail節點，分別指向跳躍表中的第一個節點和最後一個節點。

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

2. Redis 中跳躍表的特性

Redis 中的跳躍表具有以下特性：

• 支持快速查找：由於跳躍表的多級索引結構，Redis 可以在O(log N)的時間複雜度內查找到任意節點。

• 支持範圍查找：由於跳躍表的有序性，Redis 可以在O(log N)的時間複雜度內找到滿足特定範圍條件的所有節點。

• 支持雙向遍歷：由於每個節點都包含一個反向指針，Redis 的跳躍表可以支持從任意節點開始的雙向遍歷。

四、跳躍表與其他數據結構的比較

1. 跳躍表與平衡樹

平衡樹（如 AVL 樹、紅黑樹等）和跳躍表都是可以進行快速查找的數據結構，它們的查找、插入和刪除操作的時間複雜度都是O(log N)。然而，平衡樹的實現通常比跳躍表複雜，需要處理更多的旋轉和平衡操作。相比之下，跳躍表的實現更簡單，更易於理解和操作。

2. 跳躍表與哈希表

哈希表的查找、插入和刪除操作的平均時間複雜度是O(1)，優於跳躍表的O(log N)。然而，哈希表不支持有序操作，例如獲取最小值、最大值或者進行範圍查找。而跳躍表由於其有序性，可以很好地支持這些操作。

3. 跳躍表與鏈表

鏈表是一種基礎的數據結構，其查找、插入和刪除操作的時間複雜度是O(N)。而跳躍表是對鏈表的擴展，通過添加多級索引，將查找、插入和刪除操作的時間複雜度降低到O(log N)。同時，跳躍表保留了鏈表的有序性，可以支持一些鏈表無法支持的有序操作。

五、Redis 中跳躍表的應用場景

在 Redis 中，跳躍表主要被用於實現有序集合Sorted Set。

有序集合是 Redis 支持的一種數據類型，它不僅可以存儲一組元素，還可以爲每個元素關聯一個分數。通過這個分數，Redis 可以快速地獲取分數最高或最低的元素，或者獲取滿足特定分數範圍的所有元素。這些操作都是通過跳躍表來實現的。

跳躍表在 Redis 集羣節點中用作內部數據結構。

★

跳躍表在 Redis 中僅用於有序集合和集羣節點內部數據結構兩種場景。

”

六、跳躍表的優缺點小結

優點：

• 跳躍表的查找、插入和刪除操作的時間複雜度都是O(log N)，在處理大量數據時具有很高的效率。

• 跳躍表的實現相對簡單，比如相比於平衡樹，跳躍表不需要進行復雜的旋轉和平衡操作。

• 跳躍表支持有序操作，如獲取最小值、最大值或進行範圍查找。

缺點：

• 跳躍表的空間複雜度是O(N)，每個元素都需要存儲在跳躍表中，這可能會佔用較多的內存。

• 跳躍表的性能依賴於隨機數生成器，如果隨機數生成器的質量不高，可能會影響跳躍表的性能。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/adJJy-WM2jP9ArmXI3Y4bA