文档章节

Redis 2.8.9源码 - 跳表的实现

logbird
 logbird
发布于 2014/06/16 14:36
字数 1309
阅读 1714
收藏 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

粉丝 48
博文 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
centos6.x下让redis以服务方式运行

1.从官网下载redis-2.8.9.tar.gz之后,将redis解压在/usr/local下,目录是redis-2.8.9,然后按照官网给出的办法安装redis即可。 2.安装完在redis-2.8.9目录下执行src/redis-server 然后在另一...

gaolu
2014/06/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

[雪峰磁针石博客]python3快速入门教程1 turtle绘图-2函数

菲波那契序列: >>> # Fibonacci series:... # the sum of two elements defines the next... a, b = 0, 1>>> while b < 10:... print(b)... a, b = b, a+b...112......

python测试开发人工智能安全
今天
0
0
java环境变量配置最正确的方式

原贴:https://blog.csdn.net/qq_40007997/article/details/79784711,十分详细,亲测有效

kitty1116
今天
0
0
49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
1
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部