专栏首页用户7890857的专栏5、Redis数据结构——跳跃表-skiplist
原创

5、Redis数据结构——跳跃表-skiplist

跳跃表简介:

跳跃表是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳跃表支持评价O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。

在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树来得更简单,所以有不少程序都是用跳跃表来代替平衡树。

Redis使用跳跃表作为有序结合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员时比较长的字符串时,redis就会使用跳跃表来作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表。一个是实现有序集合键,另一个是在集群节点中用作内部数据结构。

为什么使用跳跃表

首先,要支持随机的插入和删除,所以 不宜使用数组来实现,关于排序问题,也很容易想到 红黑树/平衡树 这样的树形结构,为什么 Redis 不使用这样的树结构呢?

  1. 性能考虑:高并发的情况下,树形结构需要执行类似于 rebalance 这样可能涉及整棵树的操作,相对来讲跳跃表的变化只涉及局部;
  2. 实现考虑:在复杂度与红黑树相同的情况下,跳跃表实现起来更简单,看起来也更加直观;

1、跳跃表的实现

Redis的跳跃表由zskiplistNode和zskiplist两个结构定义,zskiplistNode结构用于表示跳跃表节点,而zskiplist结构则用于保存跳跃表节点的相关信息,比如节点数量,以及表头节点和表尾节点的指针等。

上图最左边的就是zskiplist结构,该结构包含以下属性:

  • header:指向跳跃表的表头表头节点;可以在 O(1) 的时间复杂度内定位到跳跃表的头部
  • tail:指向跳跃表的表尾节点;可以在 O(1) 的时间复杂度内定位到跳跃表的尾部
  • level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)。
  • length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)。位于zskiplist结构右方的四个zskiplistNode结构,该结构包含一下属性:

1)层:如图L1、L2、L3等标记节点的各个层。每层都有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点。跨度记录了前进指针所指向节点和当前节点的距离。图里的箭头表示前进指针,数字表示跨度。

  • 两个节点之间的跨度越大,它们相距得就越远。
  • 指向 NULL 的所有前进指针的跨度都为0,因为它们没有连向任何节点。

2)后退指针:BW标记的后退指针,指向位于当前节点的前一个节点。后退指针用于表尾向表头遍历使用。

3)分值:在跳跃表中,节点按照各自所保存的分值从小到大排列。

4)成员对象:各个节点的o1、o2等是节点所保存的成员对象。

1.1、跳跃表节点定义:

/* ZSETs use a specialized version of Skiplists */ 
typedef struct zskiplistNode { 
//成员对象 
robj *obj; 
//分值 
double score; 
//后退指针 
struct zskiplistNode *backward;     
//层     
struct zskiplistLevel {      
  struct zskiplistNode *forward;//前进指针       
    unsigned int span;//跨度   
 } level[]; 
 } zskiplistNode; 

1.2、跳跃表定义:

仅靠多个跳跃表节点就可以组成一个跳跃表

但通过使用一个zskiplist结构来持有这些节点,程序可以更加方便地对整个跳跃表进行处理,比如快速访问跳跃表的表头节点和表尾节点,或者快速获取跳跃表节点的数量(也即是跳跃表的长度)等信息。

typedef struct zskiplist { 
//表头节点和表尾节点 
struct zskiplistNode *header, *tail; 
//表中节点的的数量 
unsigned long length; 
//表中层数最大的节点层数 
int level; 
} zskiplist; 

header和tail指针分别指向跳跃表的表头和表尾节点,通过这两个指针,程序定位表头和表尾节点的复杂度为O(1)。

通过使用length属性来记录节点的数量,程序可以在O(1)复杂度内返回跳跃表的长度。

level属性则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数量,注意表头节点的层高并不计算在内。

重点回顾:

  1. 跳跃表是有序集合的底层实现之一
  2. Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,zskiplistNode用于表示跳跃表节点,zskiplist用于表示跳跃表信息。
  3. 每个跳跃表节点的层高都是1到32之间的随机数
  4. 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点成员对象必须是唯一的。
  5. 跳跃表节点按照分值大小排序,当分值相同,节点按照成员对象的大小进行排序。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis数据结构-跳跃表

    跳表(skiplist)是一个特殊的链表,相比一般的链表,有更高的查找效率,其效率可比拟于二叉查找树。

    程序员酷森
  • 数据结构--跳表SkipList

    以上写的比较简单,删除多个节点后,索引重新合理重建没有写。应该还有很多需要改进的地方,先放一放,往后继续学,保持学习进度。 测试结果:

    Michael阿明
  • 《闲扯Redis十一》Redis 有序集合对象底层实现

    备注: 本节中涉及到的跳跃表实现,已经在上节《闲扯Redis十》Redis 跳跃表的结构实现一文中详情分析过,本文中将直接引用,不再赘述。

    大道七哥
  • 《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理

    《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理 (原创内容,转载请注明来源,谢谢) 一、集合 集合的编码方式有intset和has...

    用户1327360
  • redis高性能数据结构之有序集

    已经讲了两个数据结构了,今天我们来讲一下在redis中最具有特色的数据结构zset(有序列表)

    居士
  • redis数据结构及内部编码-hash数据结构

    在讲redis的hash数据结构之前我们先了解下skiplist Wikipedia给出的解释如下: 跳跃列表(skiplist)是一种数据结构。它允许快速查询...

    日薪月亿
  • Redis底层数据结构详解

    上一篇说了Redis有五种数据类型,今天就来聊一下Redis底层的数据结构是什么样的。是这一周看了《redis设计与实现》一书,现来总结一下。(看书总是非常烦躁...

    Liusy
  • Redis 的底层数据结构(跳跃表)

    字典相对于数组,链表来说,是一种较高层次的数据结构,像我们的汉语字典一样,可以通过拼音或偏旁唯一确定一个汉字,在程序里我们管每一个映射关系叫做一个键值对,很多个...

    Single
  • Redis之zset数据结构与range复杂度分析

    Redis 的几种主要数据结构,大家应该都有所了解。例如最常用的五种:字符串,list,hash,set,zset。各自的适用场景也算是比较常见容易考察的内容。...

    程序员架构进阶
  • Redis系列(七)底层数据结构之跳跃表

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • Redis(2)——跳跃表

    跳跃表(skiplist)是一种随机化的数据结构,由 William Pugh 在论文《Skip lists: a probabilistic alternat...

    乔戈里
  • 面试官:你看过Redis数据结构底层实现吗?

    面试中,redis也是很受面试官亲睐的一部分。我向在这里讲的是redis的底层数据结构,而不是你理解的五大数据结构。你有没有想过redis底层是怎样的数据结构呢...

    用户5224393
  • 一文读懂 Redis 常见对象类型的底层数据结构

    Redis 是一个基于内存中的数据结构存储系统,可以用作数据库、缓存和消息中间件。Redis 支持五种常见对象类型:字符串(String)、哈希(Hash)、列...

    肉眼品世界
  • [Redis]Redis的设计与实现-链表/字典/跳跃表

    redis的设计与实现: 1.假如有一个用户关系模块,要实现一个共同关注功能,计算出两个用户关注了哪些相同的用户,本质上是计算两个用户关注集合的交集,如果使用关...

    陶士涵
  • [Redis] redis的设计与实现-对象系统

    1.redis并没有直接使用前面的数据结构实现键值对数据库,而是基于数据结构创建了一个对象系统,字符串对象/列表对象/哈希对象/集合对象/有序集合对象都用到了至...

    陶士涵
  • 跟着大彬读源码 - Redis 9 - 对象编码之 三种list

    Redis 底层使用了 ziplist、skiplist 和 quicklist 三种 list 结构来实现相关对象。顾名思义,ziplist 更节省空间、sk...

    北国风光
  • 万字长文的Redis五种数据结构详解(理论+实战),建议收藏。

    但是作为一名优秀的程序员可能不能只停留在只会用这五种类型进行crud工作,还是得深入了解这五种数据结构的底层原理。

    码农小胖哥
  • 数据结构:跳跃链表

    开发时经常使用的平衡数据结构有B数、红黑数,AVL数。但是如果让你实现其中一种,很难,实现起来费时间。而跳跃链表一种基于链表数组实现的快速查找数据结构,目前开源...

    潜行前行
  • 数据结构:跳跃链表

    开发时经常使用的平衡数据结构有B数、红黑数,AVL数。但是如果让你实现其中一种,很难,实现起来费时间。而跳跃链表一种基于链表数组实现的快速查找数据结构,目前开源...

    呆呆

扫码关注云+社区

领取腾讯云代金券