我要评论跳表的基本思想
skip list(跳跃列表)这种随机的数据结构，可以看做是一个二叉树的变种，它在性能上与红黑树、avl树很相近；但是skip list(跳跃列表)的实现相比前两者要简单很多，目前redis的zset实现采用了skip list(跳跃列表)。
特点
1、分层，每层由有序链表构成
2、头节点在每层出现
3、某个节点如果在上层出现，那在下层也出现
4、节点的层数是随机的
节点与结构
跳跃表节点zskiplistnode
/* zsets use a specialized version of skiplists */
typedef struct zskiplistnode {
sds ele;
double score;
struct zskiplistnode *backward;
struct zskiplistlevel {
struct zskiplistnode *forward;
unsigned long span;
} level[];
} zskiplistnode;
属性
- ele：存储字符串数据
- score：存储排序分值
- *backward：指针，指向当前节点最底层的前一个节点
- level[]：柔性数组，随机生成1-64的值
- forward：指向本层下一个节点
- span：本层下个节点到本节点的元素个数
跳跃表链表
typedef struct zskiplist {
struct zskiplistnode *header, *tail;
unsigned long length;
int level;
} zskiplist;
属性
- header，tail：头节点和尾节点
- length：跳跃表长度（不包括头节点）
- tail：跳跃表高度
跳表的设计思想和优势
1、能够同时拥有链表和数优势的数据结构，既有链表插入快的特点又有数组查询快的特点
2、随机跨越层数
3、最底层的链表是双向链表，包含所有元素
4、对于有序链表查询优化，相比较于平衡数来说，更好实现
5、内存占用上来看，相比较于平衡数会更少
api解析
tip：以下的zsl为zskiplist
zslcreate（创建跳跃表）
/* create a new skiplist. */
zskiplist *zslcreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslcreatenode(zskiplist_maxlevel,0,null);
for (j = 0; j < zskiplist_maxlevel; j++) {
zsl->header->level[j].forward = null;
zsl->header->level[j].span = 0;
}
zsl->header->backward = null;
zsl->tail = null;
return zsl;
}
大致流程：
1、定义一个zsl，申请内存，赋初始值
2、调用zslcreatenode创建出头节点
3、每层头节点赋初始值
4、尾节点赋null值
zslcreatenode（创建节点）
/* create a skiplist node with the specified number of levels.
* the sds string 'ele' is referenced by the node after the call. */
zskiplistnode *zslcreatenode(int level, double score, sds ele) {
zskiplistnode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistlevel));
zn->score = score;
zn->ele = ele;
return zn;
}
大致流程：
1、申请内存（节点内存和柔性数组的内存）
2、属性赋值
zslgetrank（查找排位）
排位就是累积跨越的节点数量
unsigned long zslgetrank(zskiplist *zsl, double score, sds ele) {
zskiplistnode *x;
unsigned long rank = 0;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0))) {
rank += x->level[i].span;
x = x->level[i].forward;
}
/* x might be equal to zsl->header, so test if obj is non-null */
if (x->ele && x->score == score && sdscmp(x->ele,ele) == 0) {
return rank;
}
}
return 0;
}
大致流程：
1、从最上层开始遍历节点并对比元素，对比score
2、如果当前分值大雨下一个分值，则累加span（比对分值，如果分值一样就比对ele）
3、指向本层的下一个节点
4、如果找到了，也就是ele相同，则返回
zsldelete（删除节点）
int zsldelete(zskiplist *zsl, double score, sds ele, zskiplistnode **node) {
zskiplistnode *update[zskiplist_maxlevel], *x;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
/* we may have multiple elements with the same score, what we need
* is to find the element with both the right score and object. */
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
zsldeletenode(zsl, x, update);
if (!node)
zslfreenode(x);
else
*node = x;
return 1;
}
return 0; /* not found */
}
大致流程：
1、遍历跳表
2、比对分值，比对ele
3、如分值小于或等于当前值，并且ele不相等，继续下一个并记录节点
4、如分值和ele都相同，调用zsldeletenode删除该节点
跳表是在很多排名以及分数相关的场景中使用频率极高的数据结构，也是设计的极其巧妙的一种结构，希望本篇文章能帮助各位更加深入的理解这种结构。
到此这篇关于redis中跳表zset的具体使用的文章就介绍到这了,更多相关redis 跳表zset内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论