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 实现。