redis中跳跃表

原创
2020/11/08 15:10
阅读数 340

跳跃表

 

定义:有序数据结构,在每一个节点中维护多个指向其他节点指针,从而能够达到快速访问节点得目的。

使用:redis中有序集合得实现之一为跳跃表,节点数比较多或者成员是比较长得字符串时,就使用跳跃表来作为有序集合键得底层实现;

另一个用到跳跃表的地方是作为集群节点内部数据结构。

结构

跳跃表包含两个部分 节点和保存节点信息的数据结构

 

左边是ziplist结构  ,右边有三个node  level记录层数最大哪个节点层数,length,记录目前表中包含节点数

跳跃表节点

typedef struct zskipListNode{

//后退指针

struct zskipListNode *backward;

//分值

double score;

//成员对象

robj *obj

//层

struct zskipLIstLevel {

//前进指针

struct zskipListNode * forward;



//跨度

unsigned int span;

}level[];

}zskiplistNode;

 

 

 

通过zskipList结构来持有这些节点,可以更方便获取节点信息和访问节点


typedef struct zskiplist{

//表头节点和表尾节点

structz skipListNode *header ,*tail;

//表中节点个数

unsigned long length;

//层次最大节点的层次

int level;

}

特点

1每个跳跃表节点层高都是1到32之间的随机数;

2同一个跳跃表中,多个节点可以包含相同的分值,但每个成员对象必须是唯一的;

3节点按分值大小排序,当分值相同时,节点按成员对象大小排序

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

     

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部