文档章节

Redis 2.8.9源码 - 跳表的实现

logbird
 logbird
发布于 2014/06/16 14:36
字数 1309
阅读 1727
收藏 29

本文为作者原创,转载请注明出处:http://my.oschina.net/fuckphp/blog/280168

本文代码可以在 src/redis.h 和 src/t_zset.c 两个文件中找到,关于跳表相关的api请参考另外一篇文章   Redis 2.8.9源码 - 跳表操作 操作函数头整理,并注释作用和参数说明

Redis中用zset数据结构,用来存放一组有序的数据集,可以实现排行榜等功能,zset的内部实现使用的是一个叫做 跳表(skiplist)的数据结构,这个数据结构是由 William Pugh(《Skip lists: a probabilistic alternative to balanced trees》) 发明的一个性能上可以和平衡术媲美的数据结构,不熟悉此数据结构的可以见文章结尾的参考资料。

首先看一下实现跳表的数据结构

跳表节点(如下代码定义在 src/redis.h 中)

typedef struct zskiplistNode {
    //跳表节点中key的对象
    robj *obj;
    //跳表节点中存储的分值
    double score;
    //跳表节点中 存放的前驱节点
    struct zskiplistNode *backward;
    //保存每个节点中每一层指向的后继节点数组
    struct zskiplistLevel {
        //存放每一层的节点指针
        struct zskiplistNode *forward;
        //当前节点与后继节点跨过的节点数量
        unsigned int span;
    } level[];
} zskiplistNode;

跳表结构(如下代码定义在 src/redis.h 中)

typedef struct zskiplist {
    //指向跳表节点的头尾指针
    struct zskiplistNode *header, *tail;
    //跳表节点的个数
    unsigned long length;
    //跳表节点最大层数
    int level;
} zskiplist;

然后我们看一下跳表的创建

创建跳表节点(如下代码定义在 src/t_zset.c 中)

zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
    //根据当前节点 的层高来 分配 不同大小的内存
    //内存大小为 结构本身 + 层数 * 每一层的占用的空间
    zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    //设置分值
    zn->score = score;
    //设置key对象
    zn->obj = obj; 
    //返回创建好的 节点指针
    return zn;
}

创建跳表(如下代码定义在 src/t_zset.c 中)

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    //分配内存空间
    zsl = zmalloc(sizeof(*zsl));
    //设置默认层高为1 (每个节点都有一个层高为1 指向后继接节点的指针)
    zsl->level = 1; 
    //节点数量
    zsl->length = 0; 
    //设置头结点 头结点高度默认为 32
    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; 
}

跳表的插入(如下代码定义在 src/t_zset.c 中)

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
    //定义 节点数组 update用户保存插入节点每一层的前驱节点
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    //rank 数组 用于保存 插入节点插入位置在每一层中跨国的节点数
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    redisAssert(!isnan(score));
    //设置头节点
    x = zsl->header;
    //根据 跳表结构中定义的最高层数,来遍历每一层
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        //如果是最高层,则标示扩过0个 节点,否则 记录跨过的节点数 与上一层相同
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        //通过比较 如果插入分值小于右边节点就继续 向右遍历,并计算每一层的跨度,如果大于右边则降低一层
        //如果相等则 通过key对象进行大小比较
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                compareStringObjects(x->level[i].forward->obj,obj) < 0))) {
            //记录每一层扩过的节点数
            rank[i] += x->level[i].span;
            //向右遍历
            x = x->level[i].forward;
        }
        //将每一层 插入节点的前驱节点记录到update数组中
        update[i] = x;
    }
    /* we assume the key is not already inside, since we allow duplicated
     * scores, and the re-insertion of score and redis object should never
     * happen since the caller of zslInsert() should test in the hash table
     * if the element is already inside or not. */
    //随机层的高度
    level = zslRandomLevel();
    //如果层高 比 当前层高 要高,则将header的指针指向 超出当前层高的部分
    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,obj);
    //遍历 节点的每一层,并与前驱 和 后继节点进行关联
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;

        //计算您当前节点与后继节点的跨过的节点数
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    
    //插入位置的节点 与 新插入的节点 之间跨过的 节点数
    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;
}


跳表的遍历方式与 插入方式相同,都是从高层开始遍历,逐渐降低层数。




Redis2.8.9源码   src/redis.h   src/t_zset.c

Redis 设计与实现(第一版)

一个C语言实现的跳表结构

Skiplist 跳表







© 著作权归作者所有

共有 人打赏支持
logbird

logbird

粉丝 50
博文 43
码字总数 37949
作品 3
朝阳
高级程序员
加载中

评论(1)

黎明前夕
黎明前夕
赞一个
Redis 2.8.9源码 - Redis中的双端链表实现 adlist

本文为作者原创,转载请注明出处:http://my.oschina.net/fuckphp/blog/269801 adlist作为Redis中的双端链表,在Redis中被广泛的应用到了很多地方,比如 slowlog的存储,主从复制中报错客户端...

logbird
2014/05/27
0
0
Redis 2.8.9 源码阅读笔记,索引目录

字符串对象的实现 双端链表 字典的实现 跳表的实现 IO操作实现 RDB模块 AOF模块 ae事件模块

logbird
2015/09/16
69
0
构建高性能数据库缓存之Redis(一)

一、Redis概述 1、1 什么是redis Redis是一个开源的用ANSI C编写、支持网络、基于内存、亦可持久化的日志型、Key-Value数据库,根据DB-Engines.com站点月度排行的数据显示,Reidis是最流行的...

晨风微凉
2014/06/06
0
0
安装redis服务器 jedis分片存放数据到redis服务器

redis windows 下载地址:https://github.com/ServiceStack/redis-windows 一、下载的安装包解压到盘符的指定位置,如下结构:(纯手敲,如果有缺失,见谅) Redis.doc redis-benchmark.exe r...

薄暮凉年
2015/08/07
0
0
Redis 2.8.9源码 - ae模块

本文为作者原创,转载请注明出处:http://my.oschina.net/fuckphp/blog/505956 Redis 的 ae模块的代码主要分布在 ae.c ae.h 还有 ae*.c 中,分别实现了epoll、evport、kqueue、select几种网络...

logbird
2015/09/14
93
0

没有更多内容

加载失败,请刷新页面

加载更多

兄弟连区块链教程之以太坊源码分析交易数据分析

交易的数据结构 交易的数据结构定义在core.types.transaction.go中,结构如下: type Transaction struct {data txdata// cacheshash atomic.Valuesize atomic.Valuefrom atomic.V...

兄弟连区块链入门教程
17分钟前
1
0
Tomcat优化经验之谈

Tomcat优化经验之谈 程序员小新人学习 2018-07-23 12:09:36 由于刚做完一个tomcat,jboss,Oracle性能优化项目,想做个总结。写写项目过程中对他们优化过程的理解。 tomcat安装配置就不讲啦(...

两广总督bogang
23分钟前
2
0
Spark中foreachPartition和mapPartitions的区别

spark的运算操作有两种类型:分别是Transformation和Action,区别如下: Transformation:代表的是转化操作就是我们的计算流程,返回是RDD[T],可以是一个链式的转化,并且是延迟触发的。 Ac...

张泽立
26分钟前
2
0
git reset 和 git revert, git log 和 git reflog 比较

前言:仙儿苦设相思局,寻欢误入冷香处 故事背景: 那一晚 月黑风高之夜 李寻欢 在自诩为江湖正义的一群伪君子设计好的圈套(repository)中做了(commit)三件事:              ...

猿神出窍
36分钟前
1
0
kotlin使用spring mvc(一)

过滤器Filter,是Servlet的一种技术。可通过Filter,对请求进行拦截,比如判断用户是否登录、验证黑名单等并且可对请求进行预处理。 接下来介绍使用WebFilter配置过滤器并实现读取cookie判断...

weidedong
40分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部