跳表是一种有序的数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。平均O(logN)、最坏O(N)复杂度。跳表由跳表节点zskiplistNode 和 跳表zskiplist 两个结构定义

跳表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//跳表节点
typedef struct zskiplistNode{
//层
struct zskiplistLevel {
//前进指针
struct zskiplistNode * forward;
//跨度
unsigned int span
} level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
} zskiplistNode;
  • level: 层数组,每个层带有两个属性。一般来说,层数越多,访问其他节点的速度就越快
    • forward 前进指针:用于访问位于表尾方向的其他跳表节点
    • span 跨度:记录了前进指针指向的节点和当前节点的距离,跨度越大,节点距离就越远。
  • 后退指针:指向当前节点的前一个节点。从表尾向表头遍历时使用
  • score: 分值,节点按分值从小到大排列
  • obj: 成员对象(Redis对象 redisObject 结构后续介绍

跳表

1
2
3
4
5
6
7
8
typedef struct zskiplist {
//表头、表尾节点
struct zskiplistNode *header, *tail;
//表中节点的数量
unsigned long length;
//表中层数最大的节点的层数
int level;
} zskiplist;
  • header : 指向跳表的表头节点。定位表头节点的复杂度为O(1)
  • tail: 指向跳表的表尾节点。定位表尾节点的复杂度为O(1)
  • length: 记录跳表的长度。即跳表中目前包含节点的数量(表头不算在内)。获取跳表长度的复杂度为O(1)
  • level: 记录目前跳表内,层数最大的那个节点的层数(表头节点的层数不算在内)

注:表头节点和其他节点的构造是一样的,也有后退指针、分值及成员对象。不过表头节点的这些属性不会被用到