ASP源码.NET源码PHP源码JSP源码JAVA源码DELPHI源码PB源码VC源码VB源码Android源码
当前位置:首页 >> 数据库 >> 其他数据库 >> 跳跃表在 Redis 中的应用

跳跃表在 Redis 中的应用

来源:网络整理     时间:2018-08-23     关键词:

本篇文章主要介绍了" 跳跃表在 Redis 中的应用",主要涉及到方面的内容,对于其他数据库感兴趣的同学可以参考一下: 前提申明,因篇幅有限,本文只介绍跳跃表在 Redis 中的应用,而关于跳跃表的原理性介绍,还请参考其他相关书籍,或参考博文跳跃表 SkipList【数据...

    前提申明,因篇幅有限,本文只介绍跳跃表在 Redis 中的应用,而关于跳跃表的原理性介绍,还请参考其他相关书籍,或参考博文跳跃表 SkipList【数据结构】原理及实现。
    跳跃表是一种有序数据结构,它实现了同二分查找一样的平均 O(logN)、最坏 O(N) 复杂度的节点查找。由于它的效率可以和平衡树相媲美,而实现又比平衡树简单,因此很多情况下可以用来代替平衡树。
    跳跃表在 Redis 中不如链表和字典等数据结构的应用广泛,只有两个地方用到。一是实现有序集合键,另一个是在集群节点中用作内部数据结构。
    Redis 中的跳跃表节点的实现如下:
typedef struct zskiplistNode{
    struct zskiplistLevel{                // 层数组
        struct zskiplistNode *forward;            // 前进指针
        unsigned int span;                        // 跨度
    }level[];
    struct zskiplistNode *backward;       // 后退指针
    double score;                         // 成员分数
    robj *obj;                            // 成员对象
}zskiplistNode;

    关于该结构中的成员需要作如下说明:
    * 层数组 level:其中的每个 zskiplistLevel 结构元素都表示一层,该结构中包含一个指向同层中下一个链表节点的指针 forward,称为前进指针,以及一个称为跨度的属性 span,表示前进指针指向的下一个节点与当前节点的距离。跨度主要是用来计算目标节点的排位(rank,即相当于在底层整个有序链表中的索引位置):在查找某个节点的过程中,将沿途访问过的所有层的跨度累计起来,得到的结果就是目标节点在跳跃表中的排位。层就如同于对一个普通有序链表建立起了多级索引,所以一般层的数量越多,访问相应节点的速度就越快。每次创建一个新跳跃表节点的时候,Redis 都会根据幂次定律(即越大的数出现的概率越小)随机生成一个介于 1 到 32 之间的数作为 level 数组的大小,也就是层的“高度”。
    * 后退指针 backward:主要用于从表尾向表头方向访问节点。它不能像前进指针一样可以一次跳过多个中间节点,因为每个节点只有一个后退指针,所以每次只能后退至前一个节点。
    * 成员分值 score 和成员对象 obj:这两个属性就是每个节点中保存的真正的数据值。跳跃表中的所有节点都按分值从小到大来排序。成员分值可以相同,但成员对象必须唯一:分值相同的成员将按照成员对象的字典序来进行排序。
    虽然通过多个跳跃表节点就可以组成一个跳跃表,不过 Redis 使用了如下的 zskiplist 结构来持有这些节点,这样就能更方便地对整个跳跃表进行处理,比如快速访问跳跃表的表头节点和表尾节点,或者快速地获取跳跃表的节点数量等。
typedef struct zskiplist{
    struct zskiplistNode *header, *tail;    // 表头节点和表尾节点指针
    unsigned long length;                   // 节点的数量
    int level;                      // 节点的最大层数(表头节点的层数不计算在内)
}zskiplist;

    下图是 Redis 中的一个跳跃表示例。

    图中的 L1、L2 等字样表示节点的各个层,连线上带有数字的箭头代表前进指针,而那个数字就是跨度,后退指针用 BW 字样表示。另外,由于表头节点的后退指针、成员分值和成员对象都不会被用到,所以图中只显示了表头节点的各个层。

以上就介绍了 跳跃表在 Redis 中的应用,包括了方面的内容,希望对其他数据库有兴趣的朋友有所帮助。

本文网址链接:http://www.codes51.com/article/detail_4586375.html

相关图片

相关文章