详解Redis数据结构之跳跃表_Redis

来源:脚本之家  责任编辑:小易  

Redis的作者Salvatore Sanfilippo曾经2113对这两种基于内存的5261数据存储系统进行过比较:Redis支持服务器端的数据操4102作:Redis相比Memcached来说,拥有更多1653的数据结构和并支持更丰富的数据操作,通常在Memcached里,你需要将数据拿到客户端来进行类似的修改再set回去。这大大增加了网络IO的次数和数据体积。在Redis中,这些复杂的操作通常和一般的GET/SET一样高效。所以,如果需要缓存能够支持更复杂的结构和操作,那么Redis会是不错的选择。内存使用效率对比:使用简单的key-value存储的话,Memcached的内存利用率更高,而如果Redis采用hash结构来做key-value存储,由于其组合式的压缩,其内存利用率会高于Memcached。性能对比:由于Redis只使用单核,而Memcached可以使用多核,所以平均每一个核上Redis在存储小数据时比Memcached性能更高。而在100k以上的数据中,Memcached性能要高于Redis,虽然Redis最近也在存储大数据的性能上进行优化,但是比起Memcached,还是稍有逊色。具体为什么会出现上面的结论,以下为收集到的资料:1、数据类型支持不同与Memcached仅支持简单的key-value结构的数据记录不同,Redis支持的数据类型要丰富得多。最为常用的数据类型主要由五种:String、Hash、List、Set和Sorted Set。Redis内部使用一个redisObject对象来表示所有的key和value。redisObject最主要的信息如图所示:type代表一个value对象具体是何种数据类型,encoding是不同数据类型在redis内部的存储方式,比如:type=string代表value存储的是一个普通字符串,那么对应的encoding可以是raw或者是int,如果是int则代表实际redis内部是按数值型类存储和表示这个字符串的,当然前提是这个字符串本身可以用数值表示,比如:”123″ “456”这样的字符串。只有打开了Redis的虚拟内存功能,vm字段字段才会真正的分配内存,该功能默认是关闭状态的。1)String常用命令:set/get/decr/incr/mget等;应用场景:String是最常用的一种数据类型,普通的key/value存储都可以归为此类;实现方式:String在redis内部存储默认就是一个字符串,被redisObject所引用,当遇到incr、decr等操作时会转成数值型进行计算,此时redisObject的encoding字段为int。2)Hash常用命令:hget/hset/hgetall等应用场景:我们要存储一个用户信息对象数据,其中包括用户ID、用户姓名、年龄和生日,通过用户ID我们希望获取该用户的姓名或者年龄或者生日;实现方式:Redis的Hash实际是内部存储的Value为一个HashMap,并提供了直接存取这个Map成员的接口。如图所示,Key是用户ID, value是一个Map。这个Map的key是成员的属性名,value是属性值。这样对数据的修改和存取都可以直接通过其内部Map的Key(Redis里称内部Map的key为field), 也就是通过 key(用户ID) + field(属性标签) 就可以操作对应属性数据。当前HashMap的实现有两种方式:当HashMap的成员比较少时Redis为了节省内存会采用类似一维数组的方式来紧凑存储,而不会采用真正的HashMap结构,这时对应的value的redisObject的encoding为zipmap,当成员数量增大时会自动转成真正的HashMap,此时encoding为ht。3)List常用命令:lpush/rpush/lpop/rpop/lrange等;应用场景:Redis list的应用场景非常多,也是Redis最重要的数据结构之一,比如twitter的关注列表,粉丝列表等都可以用Redis的list结构来实现;实现方式:Redis list的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销,Redis内部的很多实现,包括发送缓冲队列等也都是用的这个数据结构。4)Set常用命令:sadd/spop/smembers/sunion等;应用场景:Redis set对外提供的功能与list类似是一个列表的功能,特殊之处在于set是可以自动排重的,当你需要存储一个列表数据,又不希望出现重复数据时,set是一个很好的选择,并且set提供了判断某个成员是否在一个set集合内的重要接口,这个也是list所不能提供的;实现方式:set 的内部实现是一个 value永远为null的HashMap,实际就是通过计算hash的方式来快速排重的,这也是set能提供判断一个成员是否在集合内的原因。5)Sorted Set常用命令:zadd/zrange/zrem/zcard等;应用场景:Redis sorted set的使用场景与set类似,区别是set不是自动有序的,而sorted set可以通过用户额外提供一个优先级(score)的参数来为成员排序,并且是插入有序的,即自动排序。当你需要一个有序的并且不重复的集合列表,那么可以选择sorted set数据结构,比如twitter 的public timeline可以以发表时间作为score来存储,这样获取时就是自动按时间排好序的。实现方式:Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序,HashMap里放的是成员到score的映射,而跳跃表里存放的是所有的成员,排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率,并且在实现上比较简单www.zgxue.com防采集请勿采集本网。

1、简介

我们先不谈Redis,来看一下跳表。

1.1、业务场景

Redis的作者Salvatore Sanfilippo曾经对这两种基于内存的数据存储系统进行过比较: Redis支持服务器端的数据操作:Redis相比Memcached来说,拥有更多的数据结构和并支持更丰富的数据操作,通常在Memcached里,你需要将数据拿到客户端来进行类似

场景来自小灰的算法之旅,我们需要做一个拍卖行系统,用来查阅和出售游戏中的道具,类似于魔兽世界中的拍卖行那样,还有以下需求:

Redis与Memcached的区别 传统MySQL+ Memcached架构遇到的问题 实际MySQL是适合进行海量数据存储的,通过Memcached将热点数据加载到cache,加速访问,很多公司都曾经使用过这样的架构,但随着业务数据量的不断增加,和访问量的持续增长,我们遇到

拍卖行拍卖的商品需要支持四种排序方式,分别是:按价格、按等级、按剩余时间、按出售者ID排序,排序查询要尽可能地快。还要支持输入道具名称的精确查询和不输入名称的全量查询。

Redis 和 Memcache 都是基于内存的数据存储系统。Memcached是高性能分布式内存缓存服务;Redis是一个开源的key-value存储系统。与Memcached类似,Redis将大部分数据存储在内存中,支持的数据类型包括:字符串、哈希 表、链表、等数据类型的相关

这样的业务场景所需要的数据结构该如何设计呢?拍卖行商品列表是线性的,最容易表达线性结构的是数组和链表。假如用有序数组,虽然查找的时候可以使用二分法(时间复杂度O(logN)),但是插入的时间复杂度是O(N),总体时间复杂度是O(N);而如果要使用有序链表,虽然插入的时间复杂度是O(1),但是查找的时间复杂度是O(N),总体还是O(N)。

Redis常用数据类型 Redis最为常用的数据类型主要有以下五种: String Hash List Set Sorted set 在具体描述这几种数据类型之前,我们先通过一张图了解下Redis内部内存管理中是如何描述这些不同数据类型的: 首先Redis内部使用一个redisObject对

那有没有一种数据结构,查找时,有二分法的效率,插入时有链表的简单呢?有的,就是 跳表。

1.2、skiplist

因为是拿 Python 测试的,所以可能对其他语言并不完全适用。 使用的测试数据是特定的,可能对更小或更大的数据并不完全适用。 测试结果就不列出了,直接说结论吧。 最差的存储方式就是用一个 hash 来存储一个实体(即一条记录)。时间上比其他方

skiplist,即跳表,又称跳跃表,也是一种数据结构,用于解决算法问题中的查找问题。

一般问题中的查找分为两大类,一种是基于各种平衡术,时间复杂度为O(logN),一种是基于哈希表,时间复杂度O(1)。但是skiplist比较特殊,没有在这里面

2、跳表

2.1、跳表简介

跳表也是链表的一种,是在链表的基础上发展出来的,我们都知道,链表的插入和删除只需要改动指针就行了,时间复杂度是O(1),但是插入和删除必然伴随着查找,而查找需要从头/尾遍历,时间复杂度为O(N),如下图所示是一个有序链表(最左侧的灰色表示一个空的头节点)(图片来自网络,以下同):

链表中,每个节点都指向下一个节点,想要访问下下个节点,必然要经过下个节点,即无法跳过节点访问,假设,现在要查找22,我们要先后查找 3->7->11->19->22,需要五次查找。

但是如果我们能够实现跳过一些节点访问,就可以提高查找效率了,所以对链表进行一些修改,如下图:

我们每个一个节点,都会保存指向下下个节点的指针,这样我们就能跳过某个节点进行访问,这样,我们其实是构造了两个链表,新的链表之后原来链表的一半。

我们姑且称原链表为第一层,新链表为第二层,第二层是在第一层的基础上隔一个取一个。假设,现在还是要查找22,我们先从第二层查找,从7开始,7小于22,再往后,19小于22,再往后,26大于22,所以从节点19转到第一层,找到了22,先后查找 7->19->26->22,只需要四次查找。

以此类推,如果再提取一层链表,查找效率岂不是更高,如下图:

现在,又多了第三层链表,第三层是在第二层的基础上隔一个取一个,假设现在还是要查找22,我们先从第三层开始查找,从19开始,19小于22,再往后,发现是空的,则转到第二层,19后面的26大于22,转到第一层,19后面的就是22,先后查找 19->26>22,只需要三次查找。

由上例可见,在查找时,跳过多个节点,可以大大提高查找效率,skiplist 就是基于此原理。

上面的例子中,每一层的节点个数都是下一层的一半,这种查找的过程有点类似二分法,查找的时间复杂度是O(logN),但是例子中的多层链表有一个致命的缺陷,就是一旦有节点插入或者删除,就会破坏这种上下层链表节点个数是2:1的结构,如果想要继续维持,则需要在插入或者删除节点之后,对后面的所有节点进行一次重新调整,这样一来,插入/删除的时间复杂度就变成了O(N)。

2.2、跳表层级之间的关系

如上所述,跳表为了解决插入和删除节点时造成的后续节点重新调整的问题,引入了随机层数的做法。相邻层数之间的节点个数不再是严格的2:1的结构,而是为每个新插入的节点赋予一个随机的层数。下图展示了如何通过一步步的插入操作从而形成一个跳表:

每一个节点的层数都是随机算法得出的,插入一个新的节点不会影响其他节点的层数,因此,插入操作只需要修改插入节点前后的指针即可,避免了对后续节点的重新调整。这是跳表的一个很重要的特性,也是跳表性能明显由于平衡树的原因,因为平衡树在失去平衡之后也需要进行平衡调整。

上图最后的跳表中,我们需要查找节点22,则遍历到的节点依次是:7->37->19->22,可见,这种随机层数的跳表的查找时可能没有2:1结构的效率,但是却解决了插入/删除节点的问题。

2.3、跳表的复杂度

跳表搜索的时间复杂度平均 O(logN),最坏O(N),空间复杂度O(2N),即O(N)

3、Redis中的跳表

在理解 Redis 的跳跃表之前,我们先回忆一下 Redis 的有序集合(sorted set)操作 不重复但有序的字符串元素集合; 每个元素均关联一个double类型的score,Redis 根据score进行从小到大排序; score可以重复,重复的按照插入顺序进行排序;

示例如下:

redis 127.0.0.1:6379> ZADD runoobkey 1 redis(integer) 1redis 127.0.0.1:6379> ZADD runoobkey 2 mongodb(integer) 1redis 127.0.0.1:6379> ZADD runoobkey 3 mysql(integer) 1redis 127.0.0.1:6379> ZADD runoobkey 3 mysql(integer) 0redis 127.0.0.1:6379> ZADD runoobkey 4 mysql(integer) 0redis 127.0.0.1:6379> ZRANGE runoobkey 0 10 WITHSCORES"redis""1""mongodb""2""mysql""4"

这个是 Redis 中的有序列表的基本操作,我们答题可以看出,在有序列表中,有一个浮点数作为 score, 当对应一个值,可以根据 score 精确查找和范围查找,且效率很高

Redis 里面的这种操作的底层实现就是跳表。

上面理解了跳表,再去看 Redis 中的跳表就轻松多了,跳表的实现在 Redis 源码目录下 redis.h 文件中

3.1、zskiplistNode

zskiplistNode 表示跳表的一个节点,声明如下:

typedef struct zskiplistNode { robj *obj; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[];} zskiplistNode;

robj 类型是 Redis 中用C语言实现一种集合数据结构,它可以表示 string、hash、list、set 和 zset 五种数据类型,这里不做详细说明,在跳表节点中,这个类型的指针表示节点的成员对象

score 表示分值,用于排序和范围查找

level 是一个柔性数组,它表示节点的层级,每层都有一个前进指针 forward,用于指向相同层级指向表尾方向的下一个节点,而 span 则表示当前节点在当前层级中距离下一个节点的跨度,即两个节点之间的距离。

初看上去,很容易以为跨度和遍历节点有关,实际并不是,遍历操作只用前进指针就够了,跨度是用来计算排位(rank)的:在查找某个节点的过程中,沿途访问过的所有层的跨度累计起来,就是目标节点在跳表中的排位。

下图中,查找成员o3,只经历了一层,排位为3

在 Redis 中,每个节点的层级都是根据幂次定律(power law,越大的树出现的概率越小)随机生成的,它是1~32之间的一个数,作为level数组的大小,即高度

下图分别展示了三个高度为1、3、5层的节点

backward 是一个后退指针,每个节点都有一个,指向当前节点的表头方向的下一个节点,用于从表尾进行遍历

3.2、zskiplist

zskiplist 表示一个跳表,声明如下:

typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level;} zskiplist;

header 和 tail 指针分别指向表头和表尾节点

length 记录了节点数量

level 记录了所有节点中层级最高的节点的层级,表头节点的层高不计算在内

下图是一个跳表的示例,最左侧是一个 zskiplist 结构,其右侧是四个 zskiplistNode 节点,从左向右分别有32层、4层、2层、5层。每个节点向右的指针即前进指针 forward, BW 则表示后退指针 backward,每个节点依据节点的分值 score 进行排列

到此这篇关于Redis数据结构中的跳跃表的文章就介绍到这了,更多相关Redis数据结构跳跃表内容请搜索真格学网以前的文章或继续浏览下面的相关文章希望大家以后多多支持真格学网! 您可能感兴趣的文章:redis中的数据结构和编码详解redis内部数据结构之SDS简单动态字符串详解详解redis数据结构之sds详解redis数据结构之压缩列表Redis中5种数据结构的使用场景介绍

(1)列表类型是通过链表2113实现的,获取靠近两端的数据5261速度极快,而当元4102素增多后,访问中间数据的速1653度会较慢,所以它更加适合实现如“新鲜事”或“日志”这样很少访问中间元素的应用。(2)有序集合类型是使用散列表和跳跃表(Skip list)实现的,所以即使读取位于中间部分的数据速度也很快(时间复杂度是O(log(N)))。(3)列表中不能简单地调整某个元素的位置,但是有序集合可以(通过更改这个元素的分数)。(4)有序集合要比列表类型更耗费内存。有序集合类型算得上是 Redis的5种数据类型中最高级的类型了,在学习时可以与列表类!内容来自www.zgxue.com请勿采集。


  • 本文相关:
  • redis教程(八):事务详解
  • windows下redis安装配置教程
  • 如何利用redis分布式锁实现控制并发操作
  • 利用supervisor管理redis进程的方法教程
  • redis命令使用技巧之keys的相关操作
  • redis自动化安装及集群实现搭建过程
  • windows下redis的安装使用图解
  • 安装redis就那么几步,很简单
  • 使用redis实现微信步数排行榜功能
  • 简介lua脚本与redis数据库的结合使用
  • Redis 跳跃表如何实现
  • redis 和map有什么区别
  • 为啥redis 使用跳表而不是使用 red-black
  • 如何高效深入的阅读Redis的源码
  • redis 和map存储有什么区别
  • Redis和Memcached的区别
  • Redis 和 Memcached 各有什么优缺点,主要的应用场...
  • redis这些内存消耗数据怎么看呢,主要看哪个说明内...
  • 总结redis在节省内存开销方面做过哪些设计
  • redis中有序集合类型和列表类型的不同点与相同点
  • 网站首页网页制作脚本下载服务器操作系统网站运营平面设计媒体动画电脑基础硬件教程网络安全mssqlmysqlmariadboracledb2mssql2008mssql2005sqlitepostgresqlmongodbredisaccess数据库文摘数据库其它首页redis中的数据结构和编码详解redis内部数据结构之sds简单动态字符串详解详解redis数据结构之sds详解redis数据结构之压缩列表redis中5种数据结构的使用场景介绍redis教程(八):事务详解windows下redis安装配置教程如何利用redis分布式锁实现控制并发操作利用supervisor管理redis进程的方法教程redis命令使用技巧之keys的相关操作redis自动化安装及集群实现搭建过程windows下redis的安装使用图解安装redis就那么几步,很简单使用redis实现微信步数排行榜功能简介lua脚本与redis数据库的结合使用超强、超详细redis数据库入门教程redis常用命令、常见错误、配置技redis操作命令总结redis中5种数据结构的使用场景介64位windows下安装redis教程redis中使用redis-dump导出、导入redis中统计各种数据大小的方法redis常用命令小结让redis在你的系统中发挥更大作用centos 6.6下redis安装配置记录redis源码分析教程之压缩链表ziplist详解redis实现分布式锁的方法示例在redis数据库中实现分布式速率限制的方法redis中scan命令的深入讲解redis中的数据结构和编码详解详解redis中lua脚本的应用和实践redis全量复制与部分复制示例详解redis哈希和集合_动力节点java学院整理谈谈redis分布式锁的正确实现方法查看redis内存信息的命令
    免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.zgxue.com All Rights Reserved