redis skip list 结构解析
2021/7/21 19:16:35
本文主要是介绍redis skip list 结构解析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
先从基本的,去除掉span以后的开始
// zset的数据结构定义 /* 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; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict *dict; zskiplist *zsl; } zset; // 去除span后的zslInsert的插入逻辑 zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { //注意,这个是所有的level zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; int i, level; //每层结点找到插入位置前一结点 x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { // 针对某个level来说,forward若小于当前score,则继续往前走,由于通过forward去找,最后找到的是它的不小于它的前一个节点,放置在update中,算法链表可以考虑使用类似的方法 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; } //随机插入结点的层级 level = zslRandomLevel(); //将新层级header补充到update[],update[i]保存了i层级插入位置前一结点 if (level > zsl->level) { for (i = zsl->level; i < level; i++) { update[i] = zsl->header; } zsl->level = level; } //创建结点并插入相应的位置,其实就是链表插入结点的操作 x = zslCreateNode(level,score,ele); for (i = 0; i < level; i++) { x->level[i].forward = update[i]->level[i].forward; update[i]->level[i].forward = x; } //第一层是双向链表 x->backward = (update[0] == zsl->header) ? NULL : update[0]; if (x->level[0].forward) x->level[0].forward->backward = x; else zsl->tail = x; zsl->length++; return x; } ———————————————— 版权声明:本文为CSDN博主「_Lance」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/qq_19648191/article/details/85381769
带入span的 插入分析
// span的含义 /* Insert a new node in the skiplist. Assumes the element does not already * exist (up to the caller to enforce that). The skiplist takes ownership * of the passed SDS string 'ele'. */ zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { // update[i]保存了i层级插入位置前一结点 zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; // 每一层的排序,从1开始 unsigned int rank[ZSKIPLIST_MAXLEVEL]; int i, level; serverAssert(!isnan(score)); x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { /* store rank that is crossed to reach the insert position // span的话其实就是跨度,这一层中距离下一个节点有多少跨度,先取到上一层的rank值。 //如果为初始值,那么设置rank为0,rank用来计算span的值*/ rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; 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,rank实际上是前置的span(即到下一个节点的跨度)的和, //最后得到的是到前置节点为止的总跨度(因为foward节点小于它的时候,才去加上当前节点的span, //即若forward小于它,就去计算到forward节点的span),只是按照level的循环计算到当前level //的x的,新插入的节点一定在x后面了。 rank[i] += x->level[i].span; x = x->level[i].forward; } update[i] = x; } /* we assume the element is not already inside, since we allow duplicated * scores, reinserting the same element should never happen since the * caller of zslInsert() should test in the hash table if the element is * already inside or not. */ level = zslRandomLevel(); if (level > zsl->level) { for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } zsl->level = level; } x = zslCreateNode(level,score,ele); for (i = 0; i < level; i++) { x->level[i].forward = update[i]->level[i].forward; update[i]->level[i].forward = x; /* update span covered by update[i] as x is inserted here rank[0]实际上是 //最下面一层的值,也就是最下面的rank,i层其实是i层前置节点的数值*/ x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); // +1 是说插入了一个节点,导致前置节点+1 update[i]->level[i].span = (rank[0] - rank[i]) + 1; } /* increment span for untouched levels */ for (i = level; i < zsl->level; i++) { update[i]->level[i].span++; } x->backward = (update[0] == zsl->header) ? NULL : update[0]; if (x->level[0].forward) x->level[0].forward->backward = x; else zsl->tail = x; zsl->length++; return x; }
插入后
# 插入前 header(7) tail header 9(3) 15 tail header 1 9(3) 15 tail header 1 3 9(3) 15 tail header 1 3 7 9(1) 10(2) 15 tail header 1 3 7 9(1) 10(1) 14 15 tail # 插入时 header(7) tail header 9(3) 15 tail header 1 9(3) 15 tail header 1 3 9(2) 15 tail header 1 3 7 9(1) 10(1) 15 tail header 1 3 7 9(1) 10(1) 14 15 tail # 插入时 header(7) tail header 9(3) 15 tail header 1 9(3) 15 tail header 1 3 9(2) 13(2) 15 tail header 1 3 7 9(1) 10(1) 13(2) 15 tail header 1 3 7 9(1) 10(1) 13(1) 14 15 tail # 插入后 header(8) tail header 9(4) 15 tail header 1 9(4) 15 tail header 1 3 9(2) 13(2) 15 tail header 1 3 7 9(1) 10(1) 13(2) 15 tail header 1 3 7 9(1) 10(1) 13(1) 14 15 tail 看 ———————————————— 版权声明:本文为CSDN博主「_Lance」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/qq_19648191/article/details/85381769
这篇关于redis skip list 结构解析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-07Redis高并发入门详解
- 2024-12-07Redis缓存入门:新手必读指南
- 2024-12-07Redis缓存入门:新手必读教程
- 2024-12-07Redis入门:新手必备的简单教程
- 2024-12-07Redis入门:新手必读的简单教程
- 2024-12-06Redis入门教程:从安装到基本操作
- 2024-12-06Redis缓存入门教程:轻松掌握缓存技巧
- 2024-12-04Redis入门:简单教程详解
- 2024-11-29Redis开发入门教程:从零开始学习Redis
- 2024-11-27Redis入门指南:快速掌握Redis基础操作