关于redis:深入理解跳表及其在Redis中的应用

前言

跳表能够达到和红黑树一样的工夫复杂度 O(logN)，且实现简略，Redis 中的有序汇合对象的底层数据结构就应用了跳表。其作者威廉·普评估：跳跃链表是在很多利用中有可能代替均衡树的一种数据结构。本篇文章将对跳表的实现及在Redis中的利用进行学习。**

一. 跳表的根底概念

跳表，即跳跃链表（Skip List），是基于并联的链表数据结构，操作效率能够达到O(logN)，对并发敌对，跳表的示意图如下所示。

跳表的特点，能够概括如下。

•跳表是多层（level）链表构造；

•跳表中的每一层都是一个有序链表，并且依照元素升序（默认）排列；

•跳表中的元素会在哪一层呈现是随机决定的，然而只有元素呈现在了第 k 层，那么 k 层以下的链表也会呈现这个元素；

•跳表的底层的链表蕴含所有元素；

•跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数；

•跳表中的节点蕴含两个指针，一个指针指向同层链表的后一节点，一个指针指向上层链表的同元素节点。

以上图中的跳表为例，如果要查找元素 71，那么查找流程如下图所示。

从顶层链表的头节点开始查找，查找到元素71的节点时，一共遍历了4个节点，然而如果依照传统链表的形式（即从跳表的底层链表的头节点开始向后查找），那么就须要遍历7个节点，所以跳表以空间换工夫，缩短了操作跳表所须要破费的工夫。跳跃列表的算法有同均衡树一样的渐进的预期工夫边界，并且更简略、更疾速和应用更少的空间。这种数据结构是由William Pugh(音译为威廉·普)创造的，最早呈现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。谷歌上找到一篇作者对于跳表的论文，感兴趣强烈建议下载浏览：

https://epaperpress.com/sorts...

跳表在动静查找过程中应用了一种非严格的均衡机制来让插入和删除都更加便当和快捷，这种非严格均衡是基于概率的，而不是均衡树的严格均衡。说到非严格均衡，首先想到的是红黑树RbTree，它同样采纳非严格均衡来防止像AVL那样调整树的构造，这里就不开展讲红黑树了，看来跳表也是相似的路子，然而是基于概率实现的。

二. 跳表的节点

已知跳表中的节点，须要有指向以后层链表后一节点的指针，和指向上层链表的同元素节点的指针，所以跳表中的节点，定义如下。

public class SkiplistNode {    public int data;    public SkiplistNode next;    public SkiplistNode down;    public int level;    public SkiplistNode(int data, int level) {        this.data = data;        this.level = level;    }

上述是跳表中的节点的最简略的定义形式，存储的元素 data 为整数，节点之间进行比拟时间接比拟元素 data 的大小。

三. 跳表的初始化

跳表初始化时，将每一层链表的头尾节点创立进去并应用汇合将头尾节点进行存储，头尾节点的层数随机指定，且头尾节点的层数就代表以后跳表的层数。初始化后，跳表构造如下所示。

跳表初始化的相干代码如下所示。

public LinkedList<SkiplistNode> headNodes;public LinkedList<SkiplistNode> tailNodes;public int curLevel;public Random random;public Skiplist() {    random = new Random();    //headNodes用于存储每一层的头节点    headNodes = new LinkedList<>();    //tailNodes用于存储每一层的尾节点    tailNodes = new LinkedList<>();    //初始化跳表时，跳表的层数随机指定    curLevel = getRandomLevel();    //指定了跳表的初始的随机层数后，就须要将每一层的头节点和尾节点创立进去并构建好关系    SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);    SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);    for (int i = 0; i <= curLevel; i++) {        head.next = tail;        headNodes.addFirst(head);        tailNodes.addFirst(tail);        SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);        SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);        headNew.down = head;        tailNew.down = tail;        head = headNew;        tail = tailNew;    }}

四. 跳表的增加办法

每一个元素增加到跳表中时，首先须要随机指定这个元素在跳表中的层数，如果随机指定的层数大于了跳表的层数，则在将元素增加到跳表中之前，还须要扩充跳表的层数，而扩充跳表的层数就是将头尾节点的层数扩充。上面给出须要扩充跳表层数的一次增加的过程。

初始状态时，跳表的层数为 2，如下图所示。

当初要往跳表中增加元素 120，并且随机指定的层数为 3，大于了以后跳表的层数 2，此时须要先扩充跳表的层数，2如下图所示。

将元素 120 插入到跳表中时，从顶层开始，逐层向下插入，如下图所示。

跳表的增加办法的代码如下所示。

public void add(int num) {    //获取本次增加的值的层数    int level = getRandomLevel();    //如果本次增加的值的层数大于以后跳表的层数    //则须要在增加以后值前先将跳表层数裁减    if (level > curLevel) {        expanLevel(level - curLevel);    }    //curNode示意num值在以后层对应的节点    SkiplistNode curNode = new SkiplistNode(num, level);    //preNode示意curNode在以后层的前一个节点    SkiplistNode preNode = headNodes.get(curLevel - level);    for (int i = 0; i <= level; i++) {        //从以后层的head节点开始向后遍历，直到找到一个preNode        //使得preNode.data < num <= preNode.next.data        while (preNode.next.data < num) {            preNode = preNode.next;        }        //将curNode插入到preNode和preNode.next两头        curNode.next = preNode.next;        preNode.next = curNode;        //如果以后并不是0层，则持续向上层增加节点        if (curNode.level > 0) {            SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);            //curNode指向下一层的节点            curNode.down = downNode;            //curNode向下挪动一层            curNode = downNode;        }        //preNode向下挪动一层        preNode = preNode.down;    }}private void expanLevel(int expanCount) {    SkiplistNode head = headNodes.getFirst();    SkiplistNode tail = tailNodes.getFirst();    for (int i = 0; i < expanCount; i++) {        SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);        SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);        headNew.down = head;        tailNew.down = tail;        head = headNew;        tail = tailNew;        headNodes.addFirst(head);        tailNodes.addFirst(tail);    }}

五. 跳表的搜寻办法

在跳表中搜寻一个元素时，须要从顶层开始，逐层向下搜寻。搜寻时遵循如下规定。

•目标值大于以后节点的后一节点值时，持续在本层链表上向后搜寻；

•目标值大于以后节点值，小于以后节点的后一节点值时，向下挪动一层，从上层链表的同节点地位向后搜寻；

•目标值等于以后节点值，搜寻完结。

•下图是一个搜寻过程的示意图。

•跳表的搜寻的代码如下所示。

public boolean search(int target) {    //从顶层开始寻找，curNode示意以后遍历到的节点    SkiplistNode curNode = headNodes.getFirst();    while (curNode != null) {        if (curNode.next.data == target) {            //找到了目标值对应的节点，此时返回true            return true;        } else if (curNode.next.data > target) {            //curNode的后一节点值大于target            //阐明指标节点在curNode和curNode.next之间            //此时须要向上层寻找            curNode = curNode.down;        } else {            //curNode的后一节点值小于target            //阐明指标节点在curNode的后一节点的前面            //此时在本层持续向后寻找            curNode = curNode.next;        }    }    return false;}

六. 跳表的删除办法

当在跳表中须要删除某一个元素时，则须要将这个元素在所有层的节点都删除，具体的删除规定如下所示。

•首先依照跳表的搜寻的形式，搜寻待删除节点，如果可能搜寻到，此时搜寻到的待删除节点位于该节点层数的最高层；

•从待删除节点的最高层往下，将每一层的待删除节点都删除掉，删除形式就是让待删除节点的前一节点间接指向待删除节点的后一节点。

•下图是一个删除过程的示意图。

•跳表的删除的代码如下所示。

public boolean erase(int num) {    //删除节点的遍历过程与寻找节点的遍历过程是雷同的    //不过在删除节点时如果找到指标节点，则须要执行节点删除的操作    SkiplistNode curNode = headNodes.getFirst();    while (curNode != null) {        if (curNode.next.data == num) {            //preDeleteNode示意待删除节点的前一节点            SkiplistNode preDeleteNode = curNode;            while (true) {                //删除以后层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点                preDeleteNode.next = curNode.next.next;                //以后层删除完后，须要持续删除下一层的待删除节点                //这里让preDeleteNode向下挪动一层                //向下挪动一层后，preDeleteNode就不肯定是待删除节点的前一节点了                preDeleteNode = preDeleteNode.down;                //如果preDeleteNode为null，阐明曾经将底层的待删除节点删除了                //此时就完结删除流程，并返回true                if (preDeleteNode == null) {                    return true;                }                //preDeleteNode向下挪动一层后，须要持续从以后地位向后遍历                //直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值                //此时preDeleteNode就又变成了待删除节点的前一节点                while (preDeleteNode.next.data != num) {                    preDeleteNode = preDeleteNode.next;                }            }        } else if (curNode.next.data > num) {            curNode = curNode.down;        } else {            curNode = curNode.next;        }    }    return false;}

七. 跳表残缺代码

跳表残缺代码如下所示。

public class Skiplist {    public LinkedList<SkiplistNode> headNodes;    public LinkedList<SkiplistNode> tailNodes;    public int curLevel;    public Random random;    public Skiplist() {        random = new Random();        //headNodes用于存储每一层的头节点        headNodes = new LinkedList<>();        //tailNodes用于存储每一层的尾节点        tailNodes = new LinkedList<>();        //初始化跳表时，跳表的层数随机指定        curLevel = getRandomLevel();        //指定了跳表的初始的随机层数后，就须要将每一层的头节点和尾节点创立进去并构建好关系        SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);        SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);        for (int i = 0; i <= curLevel; i++) {            head.next = tail;            headNodes.addFirst(head);            tailNodes.addFirst(tail);            SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);            SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);            headNew.down = head;            tailNew.down = tail;            head = headNew;            tail = tailNew;        }    }    public boolean search(int target) {        //从顶层开始寻找，curNode示意以后遍历到的节点        SkiplistNode curNode = headNodes.getFirst();        while (curNode != null) {            if (curNode.next.data == target) {                //找到了目标值对应的节点，此时返回true                return true;            } else if (curNode.next.data > target) {                //curNode的后一节点值大于target                //阐明指标节点在curNode和curNode.next之间                //此时须要向上层寻找                curNode = curNode.down;            } else {                //curNode的后一节点值小于target                //阐明指标节点在curNode的后一节点的前面                //此时在本层持续向后寻找                curNode = curNode.next;            }        }        return false;    }    public void add(int num) {        //获取本次增加的值的层数        int level = getRandomLevel();        //如果本次增加的值的层数大于以后跳表的层数        //则须要在增加以后值前先将跳表层数裁减        if (level > curLevel) {            expanLevel(level - curLevel);        }        //curNode示意num值在以后层对应的节点        SkiplistNode curNode = new SkiplistNode(num, level);        //preNode示意curNode在以后层的前一个节点        SkiplistNode preNode = headNodes.get(curLevel - level);        for (int i = 0; i <= level; i++) {            //从以后层的head节点开始向后遍历，直到找到一个preNode            //使得preNode.data < num <= preNode.next.data            while (preNode.next.data < num) {                preNode = preNode.next;            }            //将curNode插入到preNode和preNode.next两头            curNode.next = preNode.next;            preNode.next = curNode;            //如果以后并不是0层，则持续向上层增加节点            if (curNode.level > 0) {                SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);                //curNode指向下一层的节点                curNode.down = downNode;                //curNode向下挪动一层                curNode = downNode;            }            //preNode向下挪动一层            preNode = preNode.down;        }    }    public boolean erase(int num) {        //删除节点的遍历过程与寻找节点的遍历过程是雷同的        //不过在删除节点时如果找到指标节点，则须要执行节点删除的操作        SkiplistNode curNode = headNodes.getFirst();        while (curNode != null) {            if (curNode.next.data == num) {                //preDeleteNode示意待删除节点的前一节点                SkiplistNode preDeleteNode = curNode;                while (true) {                    //删除以后层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点                    preDeleteNode.next = curNode.next.next;                    //以后层删除完后，须要持续删除下一层的待删除节点                    //这里让preDeleteNode向下挪动一层                    //向下挪动一层后，preDeleteNode就不肯定是待删除节点的前一节点了                    preDeleteNode = preDeleteNode.down;                    //如果preDeleteNode为null，阐明曾经将底层的待删除节点删除了                    //此时就完结删除流程，并返回true                    if (preDeleteNode == null) {                        return true;                    }                    //preDeleteNode向下挪动一层后，须要持续从以后地位向后遍历                    //直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值                    //此时preDeleteNode就又变成了待删除节点的前一节点                    while (preDeleteNode.next.data != num) {                        preDeleteNode = preDeleteNode.next;                    }                }            } else if (curNode.next.data > num) {                curNode = curNode.down;            } else {                curNode = curNode.next;            }        }        return false;    }    private void expanLevel(int expanCount) {        SkiplistNode head = headNodes.getFirst();        SkiplistNode tail = tailNodes.getFirst();        for (int i = 0; i < expanCount; i++) {            SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);            SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);            headNew.down = head;            tailNew.down = tail;            head = headNew;            tail = tailNew;            headNodes.addFirst(head);            tailNodes.addFirst(tail);        }    }    private int getRandomLevel() {        int level = 0;        while (random.nextInt(2) > 1) {            level++;        }        return level;    }}

八. 跳表在Redis中的利用

ZSet构造同时蕴含一个字典和一个跳跃表，跳跃表按score从小到大保留所有汇合元素。字典保留着从member到score的映射。这两种构造通过指针共享雷同元素的member和score，不会节约额定内存。

typedef struct zset {    dict *dict;    zskiplist *zsl;} zset;

ZSet中的字典和跳表布局：

1.ZSet中跳表的实现细节

随机层数的实现原理：

跳表是一个概率型的数据结构，元素的插入层数是随机指定的。Willam Pugh在论文中形容了它的计算过程如下：指定节点最大层数 MaxLevel，指定概率 p，默认层数 lvl 为1；

生成一个0~1的随机数r，若r<p，且lvl<MaxLevel ，则lvl ++；

反复第 2 步，直至生成的r >p 为止，此时的 lvl 就是要插入的层数。

论文中生成随机层数的伪码：

在Redis中对跳表的实现基本上也是遵循这个思维的，只不过有渺小差别，看下Redis对于跳表层数的随机源码src/z_set.c：

/* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */int zslRandomLevel(void) {    int level = 1;    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))        level += 1;    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;}

其中两个宏的定义在redis.h中：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

能够看到while中的：

(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)

第一眼看到这个公式，因为波及位运算有些惊讶，须要钻研一下Antirez为什么应用位运算来这么写？

最开始的猜想是random()返回的是浮点数[0-1]，于是乎在线找了个浮点数转二进制的工具，输出0.5看了下后果：

能够看到0.5的32bit转换16进制后果为0x3f000000，如果与0xFFFF做与运算后果还是0，不合乎预期。

理论利用时对于随机层数的实现并不对立，重要的是随机数的生成，在LevelDB中对跳表层数的生成代码是这样的：

template <typename Key, typename Value>int SkipList<Key, Value>::randomLevel() {  static const unsigned int kBranching = 4;  int height = 1;  while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {    height++;  }  assert(height > 0);  assert(height <= kMaxLevel);  return height;}uint32_t Next( uint32_t& seed) {  seed = seed & 0x7fffffffu;  if (seed == 0 || seed == 2147483647L) {     seed = 1;  }  static const uint32_t M = 2147483647L;  static const uint64_t A = 16807;  uint64_t product = seed * A;  seed = static_cast<uint32_t>((product >> 31) + (product & M));  if (seed > M) {    seed -= M;  }  return seed;}

能够看到leveldb应用随机数与kBranching取模，如果值为0就减少一层，这样尽管没有应用浮点数，然而也实现了概率均衡。

2.跳表结点的均匀层数

咱们很容易看出，产生越高的节点层数呈现概率越低，无论如何层数总是满足幂次定律越大的数呈现的概率越小。

如果某件事的产生频率和它的某个属性成幂关系，那么这个频率就能够称之为合乎幂次定律。
幂次定律的体现是少数几个事件的产生频率占了整个产生频率的大部分，而其余的大多数事件只占整个产生频率的一个小局部。

幂次定律利用到跳表的随机层数来说就是大部分的节点层数都是黄色局部，只有多数是绿色局部，并且概率很低。

定量的剖析如下：

•节点层数至多为1，大于1的节点层数满足一个概率分布。

•节点层数恰好等于1的概率为p^0(1-p)

•节点层数恰好等于2的概率为p^1(1-p)

•节点层数恰好等于3的概率为p^2(1-p)

•节点层数恰好等于4的概率为p^3(1-p)

顺次递推节点层数恰好等于K的概率为p^(k-1)(1-p)

因而如果咱们要求节点的均匀层数，那么也就转换成了求概率分布的冀望问题了：

表中P为概率，V为对应取值，给出了所有取值和概率的可能，因而就能够求这个概率分布的冀望了。方括号外面的式子其实就是高一年级学的等比数列，罕用技巧错位相减求和，从中能够看到结点层数的期望值与1-p成反比。对于Redis而言，当p=0.25时结点层数的冀望是1.33。

总结

跳表的工夫复杂度与AVL树和红黑树雷同，能够达到O(logN)，然而AVL树要维持高度的均衡，红黑树要维持高度的近似均衡，这都会导致插入或者删除节点时的一些工夫开销，所以跳表相较于AVL树和红黑树来说，省去了维持高度的均衡的工夫开销，然而相应的也付出了更多的空间来存储多个层的节点，所以跳表是用空间换工夫的数据结构。以Redis中底层的数据结构zset作为典型利用来开展，进一步看到跳跃链表的理论利用。