本人博客同步发表,排版更佳
- 通过在每个节点中维持多个只想其他节点的指针,从而达到快速访问节点的目的。
- 作为redis有序集合键的底层实现之一(数量多,元素字符长)
- 跳跃表的原理可参考: http://www.cnblogs.com/acfox/p/3688607.html
- 不同的是:先从上层插入的,而不是底层,先随机判断插入的层数。
redis跳跃表的实现
/*
* 跳跃表节点
*/
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;