SkipList详解

[toc]

SkipList是一个链表

  • 元素按照升序排列
  • 一个节点可能包含多个级别不同的指针，它们的跨度不同
    • 最多允许32级指针

image-20240921123854120

源码分析

以下是zset中使用的skiplist源码及示例图：

image-20240921124750028

1
2
3
4
5
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;		// 头尾节点指针
    unsigned long length;						// 节点数量
    int level;									// 最大的索引层级，默认为1
} zskiplist;
1
2
3
4
5
6
7
8
9
typedef struct zskiplistNode {
    sds ele;									// 节点存储的值
    double score;								// 节点的分数，用于排序和查找
    struct zskiplistNode *backward;				// 前一个节点的指针
    struct zskiplistLevel {						
        struct zskiplistNode *forward;			// 下一个节点指针
        unsigned long span;						// 索引跨度
    } level[];									// 多级索引数组
} zskiplistNode;
SkipList特点总结
  • 是一个双向链表，每个节点都有ele和score值，分别用于存储数据和打分排序查找
  • 节点按照score排序，score值相同时按照ele字典序
  • 每个节点可能包含多个指针，层数为1到32
  • 不同层级指针跨越的距离不同，层级越高跨度越大
  • 增删改查效率较高，与红黑树类似，但实现简单