文档章节

Redis 2.8.9源码 - 跳表的实现

logbird
 logbird
发布于 2014/06/16 14:36
字数 1309
阅读 1705
收藏 29
点赞 1
评论 1

本文为作者原创,转载请注明出处: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
博文 40
码字总数 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

Redis 2.8.9 源码阅读笔记,索引目录

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

logbird ⋅ 2015/09/16 ⋅ 0

构建高性能数据库缓存之Redis(一)

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

晨风微凉 ⋅ 2014/06/06 ⋅ 0

安装redis服务器 jedis分片存放数据到redis服务器

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

薄暮凉年 ⋅ 2015/08/07 ⋅ 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 ⋅ 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

Java连接redis的使用示例

Java连接redis的使用示例 Redis是开源的key-value存储工具,redis通常用来存储结构化的数据,因为redis的key可以包含String、hash、listset和sorted list。 Redisserver目前最稳定的版本是2...

小贱是个程序员 ⋅ 2016/11/18 ⋅ 0

redis源码分析之有序集SortedSet

有序集SortedSet算是redis中一个很有特色的数据结构,通过这篇文章来总结一下这块知识点。 一、有序集SortedSet命令简介 redis中的有序集,允许用户使用指定值对放进去的元素进行排序,并且基...

凌风郎少 ⋅ 2017/11/19 ⋅ 0

Redis 2.8.9源码 - Redis Dict 中的Hash算法

本文为作者原创,转载请注明出处:http://my.oschina.net/fuckphp/blog/270258 djb2 算法: unsigned long hash(unsigned char *str){ //hash种子 unsigned long hash = 5381; int c; //遍历......

logbird ⋅ 2014/05/28 ⋅ 0

CentOS上安装redis

安装tcl支持 安装redis我们以最新的2.8.9为例 测试通过后安装,安装后会自动把redis-server,redis-cli,redis-benchmark,redis-check-aof,redis-check-dump复制到/usr/local/bin目录下。 编辑...

听_风 ⋅ 2016/02/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vim介绍、vim颜色显示和移动光标、vim一般模式下移动光标、一般模式下复制粘贴剪切

VIM Vim 是 UNIX 文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff),语法高亮,全面的帮助系统,本地脚本(Vimscript),和便于选择的...

蛋黄Yolks ⋅ 17分钟前 ⋅ 0

springboot+mockito测试controller层遇到的问题

使用MockitoJUnitRunner测试的一个例子,原来报错无法找到bean, 类似的异常如下:createBeanError..... 原因:是因为@Runwith使用了SpringRunner,应该修改为MockitoJUnitRunner 代码如下: ...

writeademo ⋅ 28分钟前 ⋅ 0

关于“幂等”操作

一个幂等(idempotent)操作的特点是其任意多次执行所产生的影响均与一次执行的影响相同. 开发中, 我们经常考虑幂等操作的场景有“接口调用”、“MQ消费”、“自动任务”等 接口调用, 可能出现...

零二一七 ⋅ 36分钟前 ⋅ 0

Dubbo服务服务暴露之ProxyFactory Invoker

Dubbo服务暴露过程中有涉及到调用ProxyFactory 中方法获取Invoker对象的过程,现在我们来深究下源码,来看下这个过程是在做些什么,返回的Invoker 对象是什么,我们来看一下代码的切入点: ...

哲别0 ⋅ 51分钟前 ⋅ 0

GP两种连接方式性能测试

GP两种连接方式性能测试 Pivotal import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.ResultSet; public class GPQueryStrin......

仔仔1993 ⋅ 55分钟前 ⋅ 0

jsonrpc-4j代码解析

解析文件 AutoJsonRpcServiceImplExporter JsonServiceExporter AutoJsonRpcServiceImplExporter 路径:com.googlecode.jsonrpc4j.spring.AutoJsonRpcServiceImplExporter AutoJsonRpcServi......

郭恩洲_OSC博客 ⋅ 今天 ⋅ 0

百度搜索

from selenium import webdriver import time brower=webdriver.Firefox() brower.get('http://www.baidu.com') input=brower.find_element_by_id('kw') input.send_keys('中南大学') time.s......

南桥北木 ⋅ 今天 ⋅ 0

tomcat 日志记录器

1、日志记录器是记录消息的组件 日志记录器需要与某个servlet 容器相关联 2、Logger 接口 共定义了5种日志级别:FATAL、ERROR、WARNING、INFORMATION、DEBUGGER setVerbosity 设置级别 setC...

职业搬砖20年 ⋅ 今天 ⋅ 0

Thrift RPC实战(三) Thrift序列化机制

1.Thrift基础架构 Thrift是一个客户端和服务端的架构体系,数据通过socket传输; 具有自己内部定义的传输协议规范(TProtocol)和传输数据标准(TTransports); 通过IDL脚本对传输数据的数据结构...

lemonLove ⋅ 今天 ⋅ 0

网站建设就要像2018世界杯的俄罗斯队大杀四方[图]

今天心情不错,因为昨天晚上观看了世界杯比赛,尤其是对俄罗斯队的大杀四方感到十分霸气侧漏啊,因此我联想到了自己的博客网站,我的博客是去年年底上线的,一直想建设一个关于读书和读后感作...

原创小博客 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部