跳跃表
定义:有序数据结构,在每一个节点中维护多个指向其他节点指针,从而能够达到快速访问节点得目的。
使用: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节点按分值大小排序,当分值相同时,节点按成员对象大小排序