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中的随机数
• 多个节点可以包含相同的分值，但是成员对象必须是唯一的
• 节点按照分值大小排序，但分值相同时，按照成员对象的大小排序