小白也能看懂的Redis教学基础篇——朋友面试被Skiplist跳跃表拦住了

2020 年 10 月 1 日
筆記
Redis, Redis基础, 数据结构

各位看官大大们，双节快乐！！！

这是本系列博客的第二篇，主要讲的是Redis基础数据结构中ZSet(有序集合)底层实现之一的Skiplist跳跃表。

不知道那些是Redis基础数据结构的看官们，可以翻阅我的上一篇文章：

小白也能看懂的REDIS教学基础篇——REDIS基础数据结构

今天我朋友突然找到我，说他面试被刷了。

我一脸吃惊，忙问到：怎么了，倒在什么题上了。

朋友说：面试官说，你说你了解Redis的基础数据结构，那我问问你，你知道什么是Skiplist跳跃表吗？讲讲它是一种什么样的数据结构。它有什么优势和缺陷，它是如何插入和删除的？

我：那你怎么回答的？

我朋友：我就说Redis不是只有五种基本数据结构 字符串（strings），列表（lists）， 字典（dictht），集合（sets），有序集合（ZSet）吗？然后人家就让我回家等通知了。

我：…

我朋友：怎么了，你怎么一副无语的表情。

我：哎，还是由我来给你科普一下吧。

Skiplist 跳跃表是跳表出自 William Pugh 于1989年发表的论文《Skip Lists: A Probabilistic Alternative toBalanced Trees 》。

在论文中 William Pugh 写到；

译文大意为：

跳跃表：平衡树的概率替代方案

跳跃列表是一种可以代替平衡树的数据结构。跳跃列表使用概率平衡，而不是严格的强制平衡，因此在跳跃列表中插入和删除的算法比平衡树的算法简单得多，速度也快得多。

注：平衡树(Balance Tree) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）。

看到这里，看官们是不是一头雾水？先不要急，让我们来看看跳跃表的完整结构图。

看到这的看官是不有种想骂人的冲动？心里在想，这是个什么玩意，比平衡树还复杂。

//跳表
typedef struct zskiplist{
    //头结点和尾节点的指针
    struct skiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点层数
    int level;
};

//跳表节点
typedef struct zskiplistNode{
    //后退指针
    struct zskiplistNode *backward;
    //分值
    double score;
    //成员对象
    robj *obj;
    //层
    struct zskiplistLevel{
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
};

skiplistNode *header, *tail 指向首尾节点的指针。
long length 　表中节点的总数。
int level 所有节点中层数最高的节点的层数。
zskiplistNode *backward 后退指针，用来从尾部开始遍历到首节点。
double score 分值，元素的排位分值。
robj *obj 元素的对象指针。
zskiplistNode *forward 前进指针指向该层下一个元素的指针。
int span 跨度，用于记录两个节点之间的距离，跨度越大证明两个节点离得越远，在查找某个节点的过程中，将跨度累加，就是这个节点在跳跃表中的排位rank。

层是跳跃表节点的精髓和核心所在，跳跃表节点的level数组可以包含多个层元素。每个层元素都包含一个指向其他节点的指针，程序可以通过这些层来快速查找其他节点。一般来说，层数量越多，查找其他元素的速度就越快。

但是一个元素在插入时，他的层是怎么获得的呢？我们来看下面这个方法（此方法是仿照论文中的描述，用java实现的）。

    /**
     * 获取层级
     * @param maxLevel 最大支持的层级数
     * @return
     */
    private int randomLevel(int maxLevel){
        int lvl = 1;
        /**
         * 这里是关键 Math.random() > (0.5D) 等于true 的概率是 1/2 
         * 所以 lvl = 1 的概率是 1/2 lvl = 2 的概率 是 (1/2)*(1/2) = 1/4
         * lvl = 3 的概率是 (1/2)*(1/2)*(1/2) = 1/8 从这里可以看出 lvl 越大概率越低
         */
        for(;Math.random() > (0.5D) && lvl < maxLevel;){
            lvl += 1;
        }
        return lvl;
    }