跳跃表(skiplist)是一种有序数据结果,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。
跳跃表的实现
由zskiplistNode和zskiplist两个结构定义
zskiplist的组成:
header:指向跳跃表的表头节点。
tail:指向跳跃表的表尾节点。
level:记录目前跳跃表内,成熟最大的那个节点的层数。
length:记录跳跃表的长度。
typedef struct zskiplist{
//表头节点和表尾节点
structz skiplistNode *header, *tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点层数
int level;
}
zskiplistNode的组成:
level:跳跃表节点的level数组可以包含多个元素,每个元素都包含一个指向其他节点的指针。
forward:前进指针,指向下一层级的指针。
span:跨度,用于记录两个节点之间的距离。
backward:后退指针,用于逆向遍历的指针。
分值:节点的分值是一个都变了类型的浮点数,跳跃表中的所有节点都按分值从小到大排序。
成员:节点的成员对象,指向一个保存的字符串对象,而字符串对象则保存着SDS值。
typedef struct zskiplistNode{
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
}
}
总结
跳跃表是有序集合的底层实现之一。
redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistNode则用于表示跳跃表节点。
每个跳跃表节点的层高都是1至32之间的随机数
在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。
跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。