如果没有记错的话,应该是在两个月前把 《Redis设计与实践》 这本书啃完了,确实是一本讲
的不可多得的好书,但是一直迟迟没有写自己的一些总结。一来是因为没有时间,二来是没有找到一个合适的思考点。
- Redis
本身支持很多种不同的类型,能让我们在不同的复杂的业务逻辑中游刃有余。
- Redis
也可以说是万物皆对象,他就是一个个的键值对所组成,但是我们都知道,作为一款
- Redis
,虽然通过
- NoSql
的方式能很快获取到数据,但是这也就暴露了他的一个弊端,对于范围查找,或者排序之类的无法很好的处理。 然而我们都知道,
- O(1)
有一个
- Redis
的有序集合对象,这能帮助我们实现范围查找,所以,为什么他能实现
- Sorted Set
此类关系型数据库才有的特性?而这也是我想写这篇文章的原因,也是作为自己对于《Redis设计与实践》这本书的一个总结。
- MySql
我们经常看到此类的文章:
Redis的五种数据结构
Redis的数据结构以及对应的使用场景
其实以数据结构这个词去说明
的
- Redis
、
- String
、
- Hash
、
- List
、
- Set
是不够严谨和准确的,准确的来讲,这是
- Sorted Set
的五个对象,所以这也是我在上文为什么把有序集合称之为对象的原因。
- Redis
也好,
- PHP
也罢,我们好像很少会去讲
- Python
有哪几种数据结构,其实我们都知道我们想要阐述的是什么,但是,我个人认为用
- PHP
或者
- 类型
会更为准确,因为数据类型往往是指
- 基础类型
,
- 链表
之类的字眼。
- 字典
本身也是有自己的数据结构的,比如我们上面提到的五种对象,其实他们也是基于某些数据结构来实现的,具体包括: 简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表。而这些数据结构,也就是我们所使用的五种对象的构建基础。当然,每种对象所使用的数据结构可能不止一种。
- Redis
首先要介绍的就是SDS,简单动态字符串是
中大多数对象所需要使用的一个结构,比如我们设置一个简单的
- Redis
:
- String
- set hello nine
此时其实
会创建两个
- String
,分别用于报告键和值。 再比如:
- SDS
- rpush nine 18 male
此时会创建一个列表对象,而列表对象中的两个值又会使用两个
。
- SDS
在
中有两个特点需要阐述一下:
- SDS
的长度;
- String
添加值或者拦截值的时候,他会重新判断是否长度,如果是
- SDS
值,分配的空间是:
- concat
如果是截取字段,那么空间还保留,以便下次使用。
- min(2 * len, 1M)
链表是
中
- Redis
的底层实现,其实和我们经常所看到的双向链表一致,不过
- List
的链表中有封装一个
- Redis
和
- head
用于指向表头和表尾,能帮助我们很快的找到头和尾。
- tail
字典相对而言结构会复杂一些,下图是该书的作者所画的字典的结构图:
中有两个较为重要的,一个是
- dict
数组,包含了两个
- ht
结构,为什么有两个,这样岂不是很占内存吗?的确,不过第二个
- dictht
其实是为了减少我们在
- dictht
中所耗费的时间而采用的一种解决方式。
- rehash
代表此字典是否在
- rehashidx
的过程中。
- rehash
中的
- dictht
用来管理数据,其中的0-n代表的是指向键值对的索引,而对应的
- table
和
- key
结构中还有一个
- value
,这个可以帮助我们找到这个索引下面的另外的键值对。
- next
代表这个
- size
的长度,
- table
代表哈希表的大小掩码,用于计算索引值,总是等于
- sizemask
。
- size - 1
其实前面也提到了一个问题,就是哈希表是比较占用空间的,所以我们应该有一个工具来定期给哈希表瘦身,这也就是我们前面提到的
,而前面我们所提到的
- rehash
中的另外一个
- ht
,就是用来做这个事情的: 当我们对数据进行
- dictht
的时候,我们在操作之后,会把这个键值对记录到第二个
- CRUD
中,然后删掉
- dictht
中所对应的键值对,一旦当我们的
- ht[0]
的长度为空,那么也就意味着我们的
- ht[0]
已经完成,此时交换二者即可(这里其实有点像
- rehash
引擎中的新生代的过程)。
- node v8
但是,这里就有一个问题了,我在删除的过程中,如果我删掉了,但是还没完成
,那么我怎么获取数据呢?其实
- rehash
也已经帮我们做完了这份工作,当我们在
- Redis
中获取不到我们的值时,我们会到
- ht[0]
中去查找。此外,
- ht[1]
的字典还有一个非常智能的方式,当我们开始
- Redis
之后,那么我们就不会再往
- rehash
中添加任何元素,都会直接添加到
- ht[0]
中,而这也就加快了我们
- ht[1]
的过程。
- rehash
跳跃表作为有序集合的实现方式之一,在
中也同样扮演者重要的角色。在网上没有找到很好的图示,所以自己根据书中的图花了一个对应的结构图:
- Redis
其中的
,
- o1
...代表所绑定的成员对象。而上面的1.0之类的就代表对应的分值了,我们可以看到,跳跃表引入了层级的概念,这会帮助我们系统在查找范围时更加快捷和方便(为什么会更快可以参考这篇文章)。
- o2
上面这张图大概就是描述redis里面的一个跳跃表结构,score就是分数也就是节点的value值,查找的时候就是利用每一层的跨度从高到低去比较value的大小最终确定结果,也可以理解成从高到低不断的缩小查找范围,跟二分查找有点类似,这也就是我们上面说的跳跃表就是一个可以二分的链表,但是可以看到除了score还有一个span字段,正常的跳跃表是没有这个span字段的,而作者为了可以实现范围查找(分页)扩展了一个这个字段用来记录从高到低每个节点距离下一个节点之间的跨度。
同时,我们可以看到,在
中还有一个
- zskiplist
元素,代表后退指针,这个可以帮助我们倒序,也就是
- BW
中用到的
- ZSET
。
- rev
整数集合是集合的底层实现之一,当集合只包含整数并且个数较少时,会使用到整数集合,是一个无重复且按照大小排列的数组。
提供了一个方法帮助我们去识别所使用的数据结构:
- redis
- sadd test 1 2 3 object encoding test
- //intset
整数集合非常简单,不过有一个升级和降级的过程有点意思,可以稍微留意一下。在整数集合的结构中,有一个
用于记录集合的类型,取决于最大的数所占的空间,每次添加值时,会对值进行判断,如果超过了目前的
- encoding
,那么就需要对整个数组进行升级,增加了灵活度,同时也节约了空间。降级同理。
- encoding
压缩列表也是
和
- List
的实现方式之一,他的主要特点是数据紧凑在一起,放在一块连续的空间中,当我们使用时,如果字段本身没有超过一定的范围,同时整体的长度没有超过限制,那么就会使用压缩列表。比如:
- Hash
- rpush nine 18 male object encoding nine
- // ziplist
压缩列表有以下几个较为重要的属性:
zlbytes:记录整个压缩列表所占的内存字节数
zltail:尾部距离首部的距离
zllen:字节数量
zlend:标记末端
entryX:列表中所对应的节点
而
结构中有一个重要属性:
- entryX
代表前面一个节点的长度,所以当我们知道了某一个节点所对应的位置时,那么用这个位置减去
- previous_entry_length
即可得到他的前一个节点的位置,这样就完成了遍历。
- previous_entry_length
前面已经讲完了我们所需要用到的
的几种数据结构,我们所使用的五种类型,正是基于这几种数据结构来实现的,但是前面我们也说过了,一种类型可以由不同的数据结构来实现,或者由几个数据结构来共同实现。下面我整理了一个表格,关于这五种类型的实现方式以及细节:
- Redis
这是我的个人博客地址。
来源: http://www.cnblogs.com/nineyang/p/7469120.html