跳跃表在 Redis 中的应用_其他数据库_数据库_码蚁之家_www.codes51.com
返回首页
专题
网络编程
ASP教程 .NET教程 PHP教程 JSP教程 C#教程 Java教程 Delphi教程 VB教程 C/C++教程 Android开发 IOS开发 Windows Phone开发 Python教程 Ruby教程 移动开发 其他编程教程
网页制作
HTML教程 CSS教程 Dreamweaver教程 FrontPages教程 Javascript教程 web前端
数据库
SqlServer MySql Oracle Access DB2 SQLite 其他数据库
图形设计
photoshop教程 Fireworks教程 CorelDraw教程 Illustrator教程 AutoCad教程 FLASH教程
操作系统
Windows xp教程 Windows 7教程 Windows 8教程 Windows 2003教程 Windows Server 2008教程 Linux教程 Windows 10
网站运营
建站经验 SEO优化 站长心得 网赚技巧 网站推广 站长故事
手机学院
手机速递 安卓教程 iphone教程 手机评测 手机技巧 手机知识 手机应用 手机游戏 手机导购
网店宝典
开店指导 开店经验 网店装修 网店推广 网店seo 网购技巧
软件教程
办公软件 系统工具 媒体工具 压缩工具 图文处理 文件管理
范文之家
自我介绍 自我鉴定 写作模板 合同范本 工作总结 贺词祝福语 演讲致辞 思想汇报 入党申请书 实习报告 心得体会 工作计划 简历模板 工作报告 导游词 评语寄语 口号大全 策划书范文
信息工程
软件工程 企业开发 系统运维 软件测试
移民之家
移民动态 移民政策 移民百科 移民生活 技术移民 投资移民
知识大全
母婴 数码 摄影 装修 美文 常识 时尚 婚嫁 美食 养生 旅游 兴趣 职场 教育 文学 健康
问答大全
电脑网络 手机数码 QQ专区 生活 游戏 体育运动 娱乐明星 休闲爱好 文化艺术 社会民生 教育科学 健康医疗 商业理财 情感家庭 地区问题 其他
编程问答
IOS Android .NET Java C/C++ Delphi VC/MFC 其他语言 PHP MSSQL MYSQL Oracle 其他数据库 Web开发 Windows Linux 硬件/嵌入开发 网络通信 移动开发 云计算 企业IT 游戏开发
笑话大全
幽默笑话 爱情笑话 成人笑话 校园笑话 爆笑笑话 综合笑话 古代笑话 现代笑话 国外笑话

跳跃表在 Redis 中的应用

来源:互联网  时间:2018/8/23 9:17:29
    前提申明,因篇幅有限,本文只介绍跳跃表在 Redis 中的应用,而关于跳跃表的原理性介绍,还请参考其他相关书籍,或参考博文跳跃表 SkipList【数据结构】原理及实现。
    跳跃表是一种有序数据结构,它实现了同二分查找一样的平均 O(logN)、最坏 O(N) 复杂度的节点查找。由于它的效率可以和平衡树相媲美,而实现又比平衡树简单,因此很多情况下可以用来代替平衡树。
    跳跃表在 Redis 中不如链表和字典等数据结构的应用广泛,只有两个地方用到。一是实现有序集合键,另一个是在集群节点中用作内部数据结构。
    Redis 中的跳跃表节点的实现如下:
typedef struct zskiplistNode{
    struct zskiplistLevel{                // 层数组
        struct zskiplistNode *forward;            // 前进指针
        unsigned int span;                        // 跨度
    }level[];
    struct zskiplistNode *backward;       // 后退指针
    double score;                         // 成员分数
    robj *obj;                            // 成员对象
}zskiplistNode;

    关于该结构中的成员需要作如下说明:
    * 层数组 level:其中的每个 zskiplistLevel 结构元素都表示一层,该结构中包含一个指向同层中下一个链表节点的指针 forward,称为前进指针,以及一个称为跨度的属性 span,表示前进指针指向的下一个节点与当前节点的距离。跨度主要是用来计算目标节点的排位(rank,即相当于在底层整个有序链表中的索引位置):在查找某个节点的过程中,将沿途访问过的所有层的跨度累计起来,得到的结果就是目标节点在跳跃表中的排位。层就如同于对一个普通有序链表建立起了多级索引,所以一般层的数量越多,访问相应节点的速度就越快。每次创建一个新跳跃表节点的时候,Redis 都会根据幂次定律(即越大的数出现的概率越小)随机生成一个介于 1 到 32 之间的数作为 level 数组的大小,也就是层的“高度”。
    * 后退指针 backward:主要用于从表尾向表头方向访问节点。它不能像前进指针一样可以一次跳过多个中间节点,因为每个节点只有一个后退指针,所以每次只能后退至前一个节点。
    * 成员分值 score 和成员对象 obj:这两个属性就是每个节点中保存的真正的数据值。跳跃表中的所有节点都按分值从小到大来排序。成员分值可以相同,但成员对象必须唯一:分值相同的成员将按照成员对象的字典序来进行排序。
    虽然通过多个跳跃表节点就可以组成一个跳跃表,不过 Redis 使用了如下的 zskiplist 结构来持有这些节点,这样就能更方便地对整个跳跃表进行处理,比如快速访问跳跃表的表头节点和表尾节点,或者快速地获取跳跃表的节点数量等。
typedef struct zskiplist{
    struct zskiplistNode *header, *tail;    // 表头节点和表尾节点指针
    unsigned long length;                   // 节点的数量
    int level;                      // 节点的最大层数(表头节点的层数不计算在内)
}zskiplist;

    下图是 Redis 中的一个跳跃表示例。

    图中的 L1、L2 等字样表示节点的各个层,连线上带有数字的箭头代表前进指针,而那个数字就是跨度,后退指针用 BW 字样表示。另外,由于表头节点的后退指针、成员分值和成员对象都不会被用到,所以图中只显示了表头节点的各个层。


上一篇MYSQL主从复制
下一篇IK中文分词器配置txt
明星图片
相关文章
《 跳跃表在 Redis 中的应用》由码蚁之家搜集整理于网络,
联系邮箱:mxgf168#qq.com(#改为@)