手记

redis笔记:跳跃表

  1. 通过在每个节点中维持多个只想其他节点的指针,从而达到快速访问节点的目的。

  2. 作为redis有序集合键的底层实现之一(数量多,元素字符长)

  3. 跳跃表的原理可参考: http://www.cnblogs.com/acfox/p/3688607.html

  4. 不同的是:先从上层插入的,而不是底层,先随机判断插入的层数。

redis跳跃表的实现

/*
 * 跳跃表节点
 */typedef struct zskiplistNode {

    // 成员对象
    robj *obj;    // 分值
    double score;    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;/*
 * 跳跃表
 */typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;    // 表中层数最大的节点的层数
    int level;

} zskiplist;
  • 创建新跳跃表节点时,根据幂次定律随机生成一个介于1——32之间的值作为level高度的大小。类似与 http://www.cnblogs.com/acfox/p/3688607.html 中的抛硬币

  • 每个节点的高度都是1-32中的随机数

  • 多个节点可以包含相同的分值,但是成员对象必须是唯一的

  • 节点按照分值大小排序,但分值相同时,按照成员对象的大小排序



作者:峰巢
链接:https://www.jianshu.com/p/667cb880a5ae


0人推荐
随时随地看视频
慕课网APP