Redis必知必会之zset底层—Skip List跳跃列表（面试加分项）

悠悠 2021-07-24 21:17 340阅读 0赞

### 一、简介 ###

> 跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

Skip List(跳跃列表)这种随机的数据结构，可以看做是一个二叉树的变种，它在性能上与红黑树、AVL树很相近；但是Skip List(跳跃列表)的实现相比前两者要简单很多，目前Redis的zset实现采用了Skip List(跳跃列表)（其它还有LevelDB等也使用了跳跃列表）。  
  
RBT红黑树与Skip List(跳跃列表)简单对比：  
RBT红黑树

1.  插入、查询时间复杂度O(logn)
2.  数据天然有序
3.  实现复杂，设计变色、左旋右旋平衡等操作
4.  需要加锁

Skip List跳跃列表

1.  插入、查询时间复杂度O(logn)
2.  数据天然有序
3.  实现简单，链表结构
4.  无需加锁

### 二、Skip List算法分析 ###

#### 2.1 Skip List论文 ####

这里贴出Skip List的论文，需要详细研究的请看论文，下文部分公式、代码、图片出自该论文。  
\_Skip Lists: A Probabilistic Alternative to Balanced Trees \_

> [https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf][https_www.cl.cam.ac.uk_teaching_2005_Algorithms_skiplists.pdf]

#### 2.2 Skip List动态图 ####

先通过一张动图来了解Skip List的插入节点元素的流程，此图来自维基百科。  
![在这里插入图片描述][20210706233840101.gif]

#### 2.3 Skip List算法性能分析 ####

##### 2.3.1 计算随机层数算法 #####

首先分析的是执行插入操作时计算随机数的过程，这个过程会涉及层数的计算，所以十分重要。对于节点他有如下特性：

*  节点都有第一层的指针
 *  节点有第i层指针，那么第i+1层出现的概率为p
 *  节点有最大层数限制，MaxLevel

计算随机层数的伪代码：  
**论文中的示例**  
![在这里插入图片描述][20210706233905456.png]

**Java版本**

public int randomLevel(){ 
        int level = 1;
        // random()返回一个[0...1)的随机数
        while (random() < p && level < MaxLevel){  
            level += 1;
        }
        return level;
    }

代码中包含两个变量P和MaxLevel，在Redis中这两个参数的值分别是：

p = 1/4
    MaxLevel = 64

##### 2.3.2 节点包含的平均指针数目 #####

Skip List属于空间换时间的数据结构，这里的空间指的就是每个节点包含的指针数目，这一部分是额外的内内存开销，可以用来度量空间复杂度。random()是个随机数，因此产生越高的节点层数，概率越低（Redis标准源码中的晋升率数据1/4，相对来说Skip List的结构是比较扁平的，层高相对较低）。其定量分析如下：

*  level = 1 概率为1-p
 *  level >=2 概率为p
 *  level = 2 概率为p(1-p)
 *  level >= 3 概率为p^2
 *  level = 3 概率为p^2(1-p)
 *  level >=4 概率为p^3
 *  level = 4 概率为p^3(1-p)
 *  ……

得出节点的平均层数（节点包含的平均指针数目）：  
![在这里插入图片描述][20210706233954778.png]  
所以Redis中p=1/4计算的平均指针数目为1.33

##### 2.3.3 时间复杂度计算 #####

以下推算来自论文内容  
假设p=1/2，在以p=1/2生成的16个元素的跳过列表中，我们可能碰巧具有9个元素，1级3个元素，3个元素3级元素和1个元素14级（这不太可能，但可能会发生）。我们该怎么处理这种情况？如果我们使用标准算法并在第14级开始我们的搜索，我们将会做很多无用的工作。那么我们应该从哪里开始搜索？此时我们假设SkipList中有n个元素，第L层级元素个数的期望是1/p个；每个元素出现在L层的概率是p^(L-1), 那么第L层级元素个数的期望是 n \* (p^L-1)；得到1 / p =n \* (p^L-1)

1 / p = n * (p^L-1)
    n = (1/p)^L
    L = log(1/p)^n

所以我们应该选择MaxLevel = log(1/p)^n  
定义：MaxLevel = L(n) = log(1/p)^n

推算Skip List的时间复杂度，可以用逆向思维，从层数为i的节点x出发，返回起点的方式来回溯时间复杂度，节点x点存在两种情况：

*  节点x存在(i+1)层指针，那么向上爬一级，概率为p，对应下图situation c.
 *  节点x不存在(i+1)层指针，那么向左爬一级，概率为1-p，对应下图situation b.  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70]

设C(k) = 在无限列表中向上攀升k个level的搜索路径的预期成本（即长度）那么推演如下：

C(0)=0
    C(k)=(1-p)×(情况b的查找长度) + p×(情况c的查找长度)
    C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)
    C(k)=1/p+C(k-1)
    C(k)=k/p

上面推演的结果可知，爬升k个level的预期长度为k/p，爬升一个level的长度为1/p。

由于MaxLevel = L(n)， C(k) = k / p，因此期望值为：(L(n) – 1) / p；将L(n) = log(1/p)^n 代入可得：(log(1/p)^n - 1) / p；将p = 1 / 2 代入可得：2 \* log2^n - 2，即O(logn)的时间复杂度。

### 三、Skip List特性及其实现 ###

#### 2.1 Skip List特性 ####

Skip List跳跃列表通常具有如下这些特性

1.  Skip List包含多个层，每层称为一个level，level从0开始递增
2.  Skip List 0层，也就是最底层，应该包含所有的元素
3.  每一个level/层都是一个有序的列表
4.  level小的层包含level大的层的元素，也就是说元素A在X层出现，那么 想X>Z>=0的level/层都应该包含元素A
5.  每个节点元素由节点key、节点value和指向当前节点所在level的指针数组组成

#### 2.2 Skip List查询 ####

假设初始Skip List跳跃列表中已经存在这些元素，他们分布的结构如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70 1]  
此时查询节点88，它的查询路线如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70 2]

1.  从Skip List跳跃列表最顶层level3开始，往后查询到10 < 88 && 后续节点值为null && 存在下层level2
2.  level2 10往后遍历，27 < 88 && 后续节点值为null && 存在下层level1
3.  level1 27往后遍历，88 = 88，查询命中

#### 2.3 Skip List插入 ####

Skip List的初始结构与2.3中的初始结构一致，此时假设插入的新节点元素值为90，插入路线如下所示：

1.  查询插入位置，与Skip List查询方式一致，这里需要查询的是第一个比90大的节点位置，插入在这个节点的前面， 88 < 90 < 100
2.  构造一个新的节点Node(90)，为插入的节点Node(90)计算一个随机level，这里假设计算的是1，这个level时随机计算的，可能时1、2、3、4…均有可能，level越大的可能越小，主要看随机因子x ，层数的概率大致计算为 (1/x)^level ，如果level大于当前的最大level3，需要新增head和tail节点
3.  节点构造完毕后，需要将其插入列表中，插入十分简单步骤 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70 3]

#### 2.4 Skip List删除 ####

删除的流程就是查询到节点，然后删除，重新将删除节点左右两边的节点以链表的形式组合起来即可，这里不再画图

### 四、手写实现一个简单Skip List ###

实现一个Skip List比较简单，主要分为两个步骤：

1.  定义Skip List的节点Node，节点之间以链表的形式存储，因此节点持有相邻节点的指针，其中prev与next是同一level的前后节点的指针，down与up是同一节点的多个level的上下节点的指针
2.  定义Skip List的实现类，包含节点的插入、删除、查询，其中查询操作分为升序查询和降序查询（往后和往前查询），这里实现的Skip List默认节点之间的元素是升序链表

####  ####

#### 3.1 定义Node节点 ####

Node节点类主要包括如下重要属性：

1.  score -> 节点的权重，这个与Redis中的score相同，用来节点元素的排序作用
2.  value -> 节点存储的真实数据，只能存储String类型的数据
3.  prev -> 当前节点的前驱节点，同一level
4.  next -> 当前节点的后继节点，同一level
5.  down -> 当前节点的下层节点，同一节点的不同level
6.  up -> 当前节点的上层节点，同一节点的不同level

package com.liziba.skiplist;
    
    /** * <p> * 跳表节点元素 * </p> * * @Author: Liziba * @Date: 2021/7/5 21:01 */
    public class Node { 
    
        /** 节点的分数值，根据分数值来排序 */
        public Double score;
        /** 节点存储的真实数据 */
        public String value;
        /** 当前节点的 前、后、下、上节点的引用 */
        public Node prev, next, down, up;
    
        public Node(Double score) { 
            this.score = score;
            prev = next = down = up = null;
        }
    
        public Node(Double score, String value) { 
            this.score = score;
            this.value = value;
        }
    }

#### 3.2 SkipList节点元素的操作类 ####

SkipList主要包括如下重要属性：

1.  head -> SkipList中的头节点的最上层头节点（level最大的层的头节点），这个节点不存储元素，是为了构建列表和查询时做查询起始位置的，具体的结构请看2.3中的结构
2.  tail -> SkipList中的尾节点的最上层尾节点（level最大的层的尾节点），这个节点也不存储元素，是查询某一个level的终止标志
3.  level -> 总层数
4.  size -> Skip List中节点元素的个数
5.  random -> 用于随机计算节点level，如果 random.nextDouble() < 1/2则需要增加当前节点的level，如果当前节点增加的level超过了总的level则需要增加head和tail(总level)

package com.liziba.skiplist;
    
    import java.util.Random;
    
    /** * <p> * 跳表实现 * </p> * * @Author: Liziba */
    public class SkipList { 
    
        /** 最上层头节点 */
        public Node head;
        /** 最上层尾节点 */
        public Node tail;
        /** 总层数 */
        public int level;
        /** 元素个数 */
        public int size;
        public Random random;
    
        public SkipList() { 
            level = size = 0;
            head = new Node(null);
            tail = new Node(null);
            head.next = tail;
            tail.prev = head;
        }
    
        /** * 查询插入节点的前驱节点位置 * * @param score * @return */
        public Node fidePervNode(Double score) { 
            Node p = head;
            for(;;) { 
                // 当前层(level)往后遍历，比较score，如果小于当前值，则往后遍历
                while (p.next.value == null && p.prev.score <= score)
                    p = p.next;
                // 遍历最右节点的下一层(level)
                if (p.down != null)
                    p = p.down;
                else
                    break;
            }
            return p;
        }
    
        /** * 插入节点，插入位置为fidePervNode(Double score)前面 * * @param score * @param value */
        public void insert(Double score, String value) { 
    
            // 当前节点的前置节点
            Node preNode = fidePervNode(score);
            // 当前新插入的节点
            Node curNode = new Node(score, value);
            // 分数和值均相等则直接返回
            if (curNode.value != null && preNode.value != null && preNode.value.equals(curNode.value)
                      && curNode.score.equals(preNode.score)) { 
                return;
            }
    
            preNode.next = curNode;
            preNode.next.prev = curNode;
            curNode.next = preNode.next;
            curNode.prev = preNode;
    
            int curLevel = 0;
            while (random.nextDouble() < 1/2) { 
                // 插入节点层数(level)大于等于层数(level)，则新增一层(level)
                if (curLevel >= level) { 
                    Node newHead = new Node(null);
                    Node newTail = new Node(null);
                    newHead.next = newTail;
                    newHead.down = head;
                    newTail.prev = newHead;
                    newTail.down = tail;
                    head.up = newHead;
                    tail.up = newTail;
                    // 头尾节点指针修改为新的，确保head、tail指针一直是最上层的头尾节点
                    head = newHead;
                    tail = newTail;
                    ++level;
                }
    
                while (preNode.up == null)
                    preNode = preNode.prev;
    
                preNode = preNode.up;
    
                Node copy = new Node(null);
                copy.prev = preNode;
                copy.next = preNode.next;
                preNode.next.prev = copy;
                preNode.next = copy;
                copy.down = curNode;
                curNode.up = copy;
                curNode = copy;
    
                ++curLevel;
            }
            ++size;
        }
    
        /** * 查询指定score的节点元素 * @param score * @return */
        public Node search(double score) { 
            Node p = head;
            for (;;) { 
                while (p.next.score != null && p.next.score <= score)
                    p = p.next;
                if (p.down != null)
                    p = p.down;
                else // 遍历到最底层
                    if (p.score.equals(score))
                        return p;
                    return null;
            }
        }
    
        /** * 升序输出Skip List中的元素 （默认升序存储，因此从列表head往tail遍历） */
        public void dumpAllAsc() { 
            Node p = head;
            while (p.down != null) { 
                p = p.down;
            }
            while (p.next.score != null) { 
                System.out.println(p.next.score + "-->" + p.next.value);
                p = p.next;
            }
        }
    
        /** * 降序输出Skip List中的元素 */
        public void dumpAllDesc() { 
            Node p = tail;
            while (p.down != null) { 
                p = p.down;
            }
            while (p.prev.score != null) { 
                System.out.println(p.prev.score + "-->" + p.prev.value);
                p = p.prev;
            }
        }
    
    
        /** * 删除Skip List中的节点元素 * @param score */
        public void delete(Double score) { 
            Node p = search(score);
            while (p != null) { 
                p.prev.next = p.next;
                p.next.prev = p.prev;
                p = p.up;
            }
        }
    
    
    }

[https_www.cl.cam.ac.uk_teaching_2005_Algorithms_skiplists.pdf]: https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf
[20210706233840101.gif]: /images/20210724/35c263d1364441aea70ee729062f6c96.png
[20210706233905456.png]: /images/20210724/15c858c895cb4d4d83ecc6266aa9d641.png
[20210706233954778.png]: /images/20210724/32afacc02537467082ea6756c6076ae8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70]: /images/20210724/6f43c2da01da4634997c212601974035.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70 1]: /images/20210724/b502299b442847cf87dfb5d420f0cc94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70 2]: /images/20210724/a7faeec80e5446b888a7b3a4393d8315.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTI1MjE5_size_16_color_FFFFFF_t_70 3]: /images/20210724/4fa45c2c9fe44952bd393f0cd9d02070.png