Redis 四 - 跳跃表

Redis 四 - 跳跃表

跳跃表实现比平衡树简单,效率可以和平衡树相媲美。主要涉及文件 redis.h

定义

zskiplistNode 用于跳跃表节点:

1
2
3
4
5
6
7
8
9
10
11
12
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
/* forward pointer */
struct zskiplistNode *forward;
/* spacing */
unsigned int span;
} level[];
} zskiplistNode;

zskiplist 用于保存跳跃表节点的相关信息

1
2
3
4
5
6
7
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
/* The count of node */
unsigned long length;
/* the max level */
int level;
} zskiplist;

跳跃表结构如下:

推荐文章