相当于Redis 中的 sorted set
跳跃表节点结构:
typedef struct zskiplistNode {
struct zskiplistNode *backward; //后退指针
double score; //分值
robj *obj; //值
struct zskiplistLevel { //层
struct zskiplistNode *forward; //前进指针
unsigned int span; //跨度
} level[];
}
跳跃表结构:
typedef struct zskiplist {
structz zkiplistNode *heard; //表头节点指针
structz zkiplistNode *tail; //表尾节点指针
unsigned long length; //表中的节点数目
int level; //表中层数最大的节点的层数
} zskiplist;
结构图:
查找的步骤:
1、从header指针出发,找到第一个节点。
2、从节点一的最高层拿到值,进行比较,如果等于则返回结果。如果值大于查询值,则返回查找不到的消息(因为是排序的,头节点为最小值)。如果值小于查找值,则根据前进指针,找到下一个节点。
3、节点的比较方法,类比步骤2.
4、如果节点的前进节点为空(最尾值),还是找不到相应的值,则返回查找不到消息。
5、如果节点的当前节点值 > 查询的值,其下一个节点的值 > 查询的值。那么就在当前节点降层查找。
6、依次执行步骤5,直到找到对应的值。
类图: