Redis教程
redis skip list 结构解析
本文主要是介绍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 结构解析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
docker-compose 启动redis 指定密码-icode9专业技术文章分享07-25
-
Redis中的缓存穿透、雪崩、击穿的原因以及解决方案07-17
-
Tiny RDM：你的下一代Redis桌面GUI神器-icode9专业技术文章分享05-31
-
redisinsight-v203-21
-
Typed property App\Api\Mapper\GamePropsConfigMapper::$apiRedis must not be accessed before initia-icode9专业技术文章分享02-26
-
redisson getlock02-21
-
redis config02-20
-
redis leaderboard02-20
-
缓存选型：Redis or MemCache01-23
-
面试官：Redis持久化能关吗？怎么关？01-22
-
Redis压测工具redis-benchmark-icode9专业技术文章分享01-21
-
这才是你应该了解的Redis数据结构！01-19
-
Redis系列：使用 Redis Module 扩展功能01-18
-
工作中使用Redis的10种场景01-18
-
CloudCanal x Redis 数据同步指令集丰富与细节优化01-11
栏目导航
