List
可从头部(左侧)加入元素,也可以从尾部(右侧)加入元素。有序列表。
像微博粉丝,即可以list存储做缓存。
key = 某大v value = [zhangsan, lisi, wangwu]
所以可存储一些list型的数据结构,如:
- 粉丝列表
- 文章的评论列表
可通过lrange命令,即从某元素开始读取多少元素,可基于list实现分页查询,这就是基于redis实现简单的高性能分页,可以做类似微博那种下拉不断分页的东西,性能高,就一页一页走。
搞个简单的消息队列,从list头推进去,从list尾拉出来。
List类型中存储一系列String值,这些String按照插入顺序排序。
5.1 内存数据结构
List 类型的 value对象,由 linkedlist 或 ziplist 实现。
当 List 元素个数少并且元素内容长度不大
采用ziplist 实现,否则使用linkedlist
5.1.1 linkedlist实现
链表的代码结构
typedef struct list { // 头结点 listNode *head; // 尾节点 listNode *tail; // 节点值复制函数 void *(*dup)(void * ptr); // 节点值释放函数 void *(*free)(void *ptr); // 节点值对比函数 int (*match)(void *ptr, void *key); // 链表长度 unsigned long len; } list; // Node节点结构 typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode;
linkedlist 结构图
5.1.2 ziplist实现
存储在连续内存
- zlbytes
ziplist 的总长度 - zltail
指向最末元素。 - zllen
元素的个数。 - entry
元素内容。 - zlend
恒为0xFF,作为ziplist的定界符
linkedlist和ziplist的rpush、rpop、llen的时间复杂度都是O(1):
- ziplist的lpush、lpop都会牵扯到所有数据的移动,时间复杂度为O(N)
由于List的元素少,体积小,这种情况还是可控的。
ziplist的Entry结构:
记录前一个相邻的Entry的长度,便于双向遍历,类似linkedlist的prev指针。
ziplist是连续存储,指针由偏移量来承载。
Redis中实现了2种方式实现:
- 当前邻 Entry的长度小于254 时,使用1字节实现
- 否则使用5个字节
当前一个Entry长度变化时,可能导致后续的所有空间移动,虽然这种情况发生可能性较小。
Entry内容本身是自描述的,意味着第二部分(Entry内容)包含了几个信息:Entry内容类型、长度和内容本身。而内容本身包含:类型长度部分和内容本身部分。类型和长度同样采用变长编码:
- 00xxxxxx :string类型;长度小于64,0~63可由6位bit 表示,即xxxxxx表示长度
- 01xxxxxx|yyyyyyyy : string类型;长度范围是[64, 16383],可由14位 bit 表示,即xxxxxxyyyyyyyy这14位表示长度。
- 10xxxxxx|yy…y(32个y) : string类型,长度大于16383.
- 1111xxxx :integer类型,integer本身内容存储在xxxx 中,只能是1~13之间取值。也就是说内容类型已经包含了内容本身。
- 11xxxxxx :其余的情况,Redis用1个字节的类型长度表示了integer的其他几种情况,如:int_32、int_24等。
由此可见,ziplist 的元素结构采用的是可变长的压缩方法,针对于较小的整数/字符串的压缩效果较好 - LPUSH命令
在头部加入一个新元素
- RPUSH命令
在尾部加入一个新元素
当在一个空的K执行这些操作时,会创建一个新列表。当一个操作清空了一个list时,该list对应的key会被删除。若使用一个不存在的K,就会使用一个空list。
LPUSH mylist a # 现在list是 "a" LPUSH mylist b # 现在list是"b","a" RPUSH mylist c # 现在list是 "b","a","c" (注意这次使用的是 RPUSH)
list的最大长度是2^32 – 1个元素(4294967295,一个list中可以有多达40多亿个元素)。
从时间复杂度的角度来看,Redis list类型的最大特性是:即使是在list的头端或者尾端做百万次的插入和删除操作,也能保持稳定的很少的时间消耗。在list的两端访问元素是非常快的,但是如果要访问一个很大的list中的中间部分的元素就会比较慢了,时间复杂度是O(N)
适用场景
- 社交中使用List进行时间表建模,使用 LPUSH 在用户时间线中加入新元素,然后使用 LRANGE 获得最近加入元素
- 可以把[LPUSH] 和[LTRIM] 命令结合使用来实现定长的列表,列表中只保存最近的N个元素
- 做MQ,依赖BLPOP这种阻塞命令
Set
类似List,但无序且其元素不重复。
向集合中添加多次相同的元素,集合中只存在一个该元素。在实际应用中,这意味着在添加一个元素前不需要先检查元素是否存在。
支持多个服务器端命令来从现有集合开始计算集合,所以执行集合的交集,并集,差集都很快。
set的最大长度是2^32 – 1个元素(一个set中可多达40多亿个元素)。
内存数据结构
Set在Redis中以intset 或 hashtable存储:
- 对于Set,HashTable的value永远为NULL
- 当Set中只包含整型数据时,采用intset作为实现
intset
核心元素是一个字节数组,从小到大有序的存放元素
结构图
因为元素有序排列,所以SET的获取操作采用二分查找,复杂度为O(log(N))。
进行插入操作时:
- 首先通过二分查找到要插入位置
- 再对元素进行扩容
- 然后将插入位置之后的所有元素向后移动一个位置
- 最后插入元素
时间复杂度为O(N)。为使二分查找的速度足够快,存储在content 中的元素是定长的。
当插入2018 时,所有的元素向后移动,并且不会发生覆盖。
当Set 中存放的整型元素集中在小整数范围[-128, 127]内时,可大大的节省内存空间。
IntSet支持升级,但是不支持降级。
- Set 基本操作
适用场景
无序集合,自动去重,数据太多时不太推荐使用。
直接基于set将系统里需要去重的数据扔进去,自动就给去重了,如果你需要对一些数据进行快速的全局去重,你当然也可以基于JVM内存里的HashSet进行去重,但若你的某个系统部署在多台机器呢?就需要基于redis进行全局的set去重。
可基于set玩交集、并集、差集操作,比如交集:
- 把两个人的粉丝列表整一个交集,看看俩人的共同好友
- 把两个大v的粉丝都放在两个set中,对两个set做交集
全局这种计算开销也大。
- 记录唯一的事物
比如想知道访问某个博客的IP地址,不要重复的IP,这种情况只需要在每次处理一个请求时简单的使用SADD命令就可以了,可确保不会插入重复IP
- 表示关系
你可以使用Redis创建一个标签系统,每个标签使用一个Set表示。然后你可以使用SADD命令把具有特定标签的所有对象的所有ID放在表示这个标签的Set中
如果你想要知道同时拥有三个不同标签的对象,那么使用SINTER
- 可使用SPOP 或 SRANDMEMBER 命令从集合中随机的提取元素。
Hash/Map
一般可将结构化的数据,比如一个对象(前提是这个对象未嵌套其他的对象)给缓存在redis里,然后每次读写缓存的时候,即可直接操作hash里的某个字段。
key=150 value={ “id”: 150, “name”: “zhangsan”, “age”: 20 }
hash类的数据结构,主要存放一些对象,把一些简单的对象给缓存起来,后续操作的时候,可直接仅修改该对象中的某字段的值。
value={ “id”: 150, “name”: “zhangsan”, “age”: 21 }
因为Redis本身是一个K.V存储结构,Hash结构可理解为subkey - subvalue
这里面的subkey - subvalue只能是
- 整型
- 浮点型
- 字符串
因为Map的 value 可表示整型和浮点型,因此Map也可以使用hincrby
对某个field的value值做自增操作。
内存数据结构
hash有HashTable 和 ziplist 两种实现。对于数据量较小的hash,使用ziplist 实现。