Redis(版本4.0)日记20210809--跳表(SkipList)

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode { // 跳表的节点
    sds ele; // 元素是一个简单动态字符串
    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; // 除了header节点外所有节点中层数的最大值
} zskiplist;

/* Create a new skiplist. */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;


    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    // header 头节点初始化开始
    // 确定头节点有ZSKIPLIST_MAXLEVEL层
    // ZSKIPLIST_MAXLEVEL = 32 可以在server.h中找到
    // #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    // 然后遍历层，将每层的后继节点置为null,span置为0
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    // 将头节点的前躯节点置为null
    zsl->header->backward = NULL;
    // header 头节点初始化结束
    zsl->tail = NULL;
    return zsl;
}

/* Insert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The skiplist takes ownership
 * of the passed SDS string 'ele'. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    ... 省略其他代码
    level = zslRandomLevel();
    ... 省略其他代码
    return x;
}

/* 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. 
 * 为即将创建的跳表节点返回一个随机的level
 * 返回值将在1～ZSKIPLIST_MAXLEVEL之间（包含1和32）
 * 该方法使用powerlaw-alike distribution（google翻译为：幂律分布）
 * 这种概率的方式使level返回的尽量小
 */
int zslRandomLevel(void) {
    int level = 1;
    // ZSKIPLIST_P = 0.25 可以在server.h中找到
    // #define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
    // level 有四分之一的概率往上进行l累加
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}