数据结构-Skiplist

基本概念

跳表是可以实现二分查找的有序链表，实现原理是将多个链表在纵向串起来，在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

主要用于有序集合 Zset 结构里，按 score 排序 member

设计

1. 最低层包含所有的元素

2. 每个索引节点包含两个指针，一个向下，一个向右

3. 插入元素时，先插入最底层，然后以 1/4 的概率插入上层（最大层高 = 32）。这样随机生成它的最高层高

4. 跳表查询、插入、删除的时间复杂度为 O(log n)，与平衡二叉树接近

img

跳表 VS 二叉树

1. 范围查找更快。二叉树需要不断的中序遍历，性能较差。

2. 跳表更紧凑，省空间。每个节点平均 1 + 0.25 + 0.25² + ... + 0.25^31 = 1.33 个指针。二叉树是 2 个指针。

3. 跳表实现更简单。二叉树增删元素时可能需要调整多层节点；跳表只需调整前后的邻节点。

跳表 VS B+树

1. 跳表写数据时只需生成随机层数，没有旋转和维持树平衡的开销，因此写入性能优于B+树

2. 同样量级的数据，B+树层高比跳表矮，因此查询比B+树快

   1. facebook 的 rocksDB 用了B+树，就是写性能贼强，读性能差点

3. Redis 的数据都存在内存，不需要像 MySQL 一样按页从磁盘加载数据到内存，因此层高不再是跳表的劣势

实现

跳表节点 zskiplistNode

// src/t_zset.c
typedef struct zskiplistNode {  
    robj *obj;     // 元素 
    double score;  // 分值用于排序 
    struct zskiplistNode *backward;     // 前驱节点
    struct zskiplistLevel {  
        struct zskiplistNode *forward;  // 后继节点
        unsigned int span;              // 层跨度，记录本节点到下个节点跨过了几个元素
    } level[];                          // 分层数组
} zskiplistNode;

插入

插入前由 hashmap 来防重

// src/t_zset.c

// zadd key field score，参数里的 ele 是 field
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { 
	for (i = zsl->level-1; i >= 0; i--) { // 从最上层开始，遍历每层
         while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0))) // scrore相同的，比较字符串值
        {
            x = x->level[i].forward;
        }
        update[i] = x; // 使用 update 数组记录每层 x 插入位置的前驱节点
    }
    
    level = zslRandomLevel(); // 随机生成本次插入的层数，每多一层，概率*0.25
    
    x = zslCreateNode(level,score,ele);                   // 新建层数=level 的 entry 节点
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward; // 将 x.forward 指向原下一个节点
        update[i]->level[i].forward = x;  
    }
}

// 随机生成层数
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) // 等价于 while (random() < 0.25)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

// new 一个跳表 node 结构
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}

问题

随机层数的概率为什么是 p=0.25?

这个值是对空间和时间的权衡。p 值太大的话，上层索引节点数量太多，上层几乎退化成顺序遍历，相当于没有索引；p 值太小，上层索引过于稀疏，起不到作用，最后也只能到最下层顺序遍历。

为什么使用跳表而不用二叉树?

见上面

手绘一个跳表看看？

head         5                  tail
head 1       5       9       12 tail
head 1 2 3 4 5 6 7 8 9 10 11 12 tail

比如要查找分值 [6 ~ 8] 的元素，第一层查到 [5, tail)，第二层查到 [5, 9]，第三层就在 [5,6,7,8,9] 里遍历查找

参考

lz710117239 - redis(五)跳跃表

Why use skip list instead of binary tree?