基础数据类型

基础数据类介绍

Redis的基础数据类型包括String（字符串）、List（链表）、Hash（哈希）、Set（集合）、Sorted Set（有序集合）五种。

底层数据结构

这里要分清楚Redis数据类型和Redis数据结构这两个概念。前者是对外的，也就是Redis的使用者，我们使用Redis时无需了解Redis的底层数据结构，只需要知道它有哪些数据类型，分表有什么功能，就可以使用Redis了。而Redis中的每种数据类型，在底层会有一种或多种不同的数据结构去实现。

Redis底层的数据结构主要有：SDS（简单动态字符串）、list（双向链表）、ziplist（压缩列表）、quicklist（快速表）、dict（字典）、intset（整数数组）、zskiplist（跳表）。

数据类型和数据结构的对应关系如下：

这里要注意的是，List的底层数据结构并不是同时使用“list”、“ziplist”、“quicklist”这三种结构的，在Redis3.0的版本，List的底层数据结构还是“list”和“ziplist”，而后面的版本中List的底层数据结构就替换为“quicklist”。

SDS（简单动态字符串）

SDS结构是Redis定义的字符串结构体，包含len（现有长度）、alloc（已分配长度）、flags（sds类型）、buf[]（字符数组）四个字段。

SDS结构体是Redis在字符数组上做的一个包装，之所以不直接使用C语言原生的字符数组（char*）来实现，是因为直接使用C语言的字符数组来实现字符串的话，如果要获取字符串长度，就要遍历一遍字符数组，直到遇到“\0”结尾，才能得到字符串的长度，这个操作的时间复杂度是O(n)，性能是比较低的。除此之外，直接使用C语言原生的字符数组实现字符串，在做字符串拼接的时候，也是个复杂操作，他需要创建一个新的字符数组，然后把原字符串和新字符串中的所有字符串逐一拷贝到新的字符数组中。

因此，Redis定义了一个SDS结构体。Redis创建一个SDS字符串时，会进行空间预分配，给字符数组buf[]分配足够多的空间，然后alloc字段记录已分配的长度（也就是当前可用的最大长度），而len字段记录buf数组中已经被使用的字节数。当Redis要获取字符串长度时，直接读取SDS结构体中的len字段即可，不需要遍历字符数组；当Redis要进行字符串拼接时，如果buf[]中的剩余空间足够的话，就无需创建新的字符数组，直接往后追加，并且更新len字段。

SDS结构体中有一个flags字段，这个字段是标记当前这个SDS的类型的，Redis不止定义了一种类型的SDS，Redis定义的SDS结构体类型包括sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，不同的SDS中len和alloc字段使用的整形类型都不一样。比如sdshdr8中的len和alloc字段的类型是uint8_t（8位无符号整形）。

list（双向链表）

Redis的List类型底层使用的数据结构中，其中一种就是list结构体，它是一个双向链表结构，是Redis在3.0版本及以前在数据量多的时候使用的一种数据结构（数据量少时使用压缩列表）。

list结构中定义了头结点指针listNode *head和尾节点指针listNode *tail，分别指向头节点和尾节点。

listNode结构体就是节点类型，包含了前驱节点指针listNode *prev，后继节点指针listNode *next，节点值指针void *value。可以看出是一个经典的双向链表结构。

ziplist（压缩列表）

Redis在3.0版本以及之前的版本，在List类型数据量少的时候，不会使用list结构体，因为list结构体是双向链表，需要创建大量的节点以及维护各种各样的指针，空间消耗比较大。因此在List类型数据量少时，会使用ziplist压缩列表来实现。

ziplist压缩列表是一个格式非常紧凑的数据结构，最大化程度的节省内存空间。ziplist包含zlbytes、zltial、zllen三个元数据属性，然后是一连串的entry，最后是固定的255结尾。

zlbytes属性记录ziplist的总字节数；zltial记录了最后一个entry的偏移量，通过zltial可以定位到最后一个entry，然后entry中又通过prevlen字段记录了前一个entry的长度，可以通过prevlen定位到前一个entry，这样就可以不断往前遍历；而zllen则记录了ziplist的元素数量，也就是entry的个数。

但是ziplist有一个问题，就是有可能发生连锁更新。因为每一个entry元素都会存储前一个entry的长度prevlen，如果ziplist在中间插入了一个占用空间很大的entry，那么后面的entry就要更新它的prevlen，而后面的prevlen更新也会引起该元素占用空间的增大，于是又会影响到再后面一个entry的prevlen，这样会引起后面许多entry的连环更新。

quicklist（快速表）

Redis3.2版本之后，List使用了新的数据结构去实现。

它是结合了list和ziplist两种数据结构的一种新的数据结构，由一个个的quicklistNode节点组成双向链表，每个quicklistNode节点都有一个指针指向一个ziplist，每个ziplist不超过8KB，并且有元素个数限制。

每次往quicklist中插入数据时，首先检查要插入到的quicklistNode节点对应的ziplist是否有足够的容量，以及是否满足元素个数限制，如果满足条件，则可以直接插入到该ziplist中，否则就要新建一个quicklistNode。

通过限制每个ziplist的大小，以及ziplist中的元素个数，就可以减少ziplist的连锁更新带来的性能损耗。

dict（字典）

Redis使用dict结构实现了Hash表这种数据类型。Redis为了实现hash表，一共定义了dict、dictht、dictEntry三个结构体。

dictht结构体有一个table属性，指向dictEntry指针数组。dictEntry指针数组中的每个元素，都是一个指向dictEntry的指针。而dictEntry结构体代表一个键值对，有key和val两个属性，以及一个next指针指向链表中的下一个dictEntry，当发生hash冲突时，会通过next指针指向落到数组同一位置的另一个dictEntry。

dict结构体的属性中有一个大小为2的dictht数组ht，平常一般使用ht[0]来做hash表元素的增删改查，而当进行rehash时，就会使用到ht[1]这个dictht，这跟Redis采取的是渐进式rehash这种rehash策略有关。

redis的hash表的rehash过程与我们Java的HashMap的rehash过程不一样，Java的HashMap的rehash是一次性的进行数组扩容和数据迁移，然后方法调用才返回。而redis的rehash过程是渐进式的rehash，渐进式rehash的底层实现细节我们没必要深究，我们可以理解为它就是每次操作hash表时都会检查一下是否正在进行rehash，如果是，那么就顺便迁移一批数据，这一批数据是从ht[0]迁移到ht[1]。直到所有数据迁移完，ht[1]赋值给ht[0]，然后ht[1]赋值为null，然后把dict的rehashidx属性置为-1，表示当前没有在进行rehash。

intset（整数数组）

intset是整形数组，是实现Set类型的其中一种数据结构，当数据量不大，并且都是整形时，redis会使用intset这种数据结构去实现Set集合。

zskiplist（跳表）

Redis的Sorted Set有序集合类型是使用zskiplist跳表结构实现的。

zskiplist结构有一个头指针header和尾指针tail分表指向头节点和尾节点，节点类型则是zskiplistNode。

zskiplistNode中的ele属性指向的是当前节点对应的内容；而score则是当前节点对应的分数，用于排序；backward是返回指针，指向前一个节点；还有一个level属性是zskiplistLevel类型的数组，这个level数组是组成跳表的关键。

level数组中的每个level，都有一个forward指针，这个forward指针会跨过若干个节点指向后面的某个节点，越上层的level的forward指针跳过的节点越多，所以叫做跳表；然后每个level中还有一个span属性，表示forward指针的跨度。节点与节点间通过level数组，就会串联出类似于下面这种形状的一个链表：

相同层的level，会通过forward指针，指向后面拥有相同层的level的节点，中间的节点则跳过。

如果我们要在跳表中寻找一个元素时，会首先通过最高层的level往后遍历，如果发现当前层的某个节点的排序比要找的目标元素大，就会使用当前遍历到的level的下一层level去遍历，直到找到目标元素，或者遍历到尾节点的最下层level也没找到。时间复杂度是O(logn)。

redisObject

redis不是直接使用上面的这些数据结构的，而是把他们都包装在redisObject结构体中，redisObject是redis的基本数据结构体。

redisObject分表有五个属性：type、encoding、lru、refcount、ptr。

type表示的时当前redisObject使用的是哪种数据类型，数据类型指的就是我们熟知的string、list、hash、set、sorted set等的这些数据类型。

encoding是编码类型，指的是当前redisObject是使用哪种数据结构，数据结构指的就是上面说的SDS、list、ziplist、quicklist、dict、intset、zskiplist这些，不同的数据类型底层有可能使用的是不同的数据结构，就是通过encoding字段区分。

lru指的是当前redisObject的LRU时间，当内存满了以后，如果redis使用LRU算法淘汰部分数据，就会依据这个字段来筛选部分数据进行淘汰，lru值越大，代表越久没有被访问过，越容易被redis淘汰出内存。

refcount指的是当前这个redisObject被多少个指针引用。

ptr则是当前redisObject用于指向值的指针，通过这个ptr指针，就可以找到真正的值。

应用场景

String

redis的string类型，可以用作分布式session，比如我们以集群方式部署我们的服务，当我们在一台服务器登录后，可以把session存储到redis中，然后把存储到redis的session对应的key，作为cookie返回给客户端。当客户端请求携带cookie打到另外一台服务器时，可以以相同的key从redis中取到对应的session数据，则表示当前用户已经登录。

redis的string类型有两个自增命令，一个是incr，还有一个是incrby命令。incr是自增1，比如incr num，表示对key为num的值加1；incrby是增加指定的步长，比如incrby num 10，表示对key为num的值增加10。redis可以用这两个命令来实现分布式id生成器。比如我们给redis定义一个名称为id的key，然后每台服务器都向redis发送incrby id 1000的命令，向redis申请范围为1000的id号段，然后每台服务器需要生成id时直接在这个号段范围内自增，这个号段用完后，再向redis发送请。

List

redis的list队列可以用作队列、阻塞队列、栈等结构

redis的lpush和rpop（或者rpush和lpop）可以实现队列结构。

如果要用redis实现阻塞队列，只需要把rpop命令缓存brpop命令即可，brpop命令当redis对应的key的list中没有数据时，会进行阻塞等待，直到超时。

用lpush命令加上lpop命令，则可以实现栈结构。

Hash

redis的hash类型用途很多，比如可以用来做电商购物车数据的存储。以用户id作为key，商品id作为hash里面的field，商品对应的数量作为value，就可以存储对应一个用户的购物车数据。

Set

set类型可以实现求交并差集的功能，可以实现交友软件中的“我可能认识的人”、“共同好友”等功能。

“sinter set1 set2 set3”表示求set1、set2、set3三个集合的交集。

“sunion set1 set2 set3”表示求set1、set2、set3三个集合的并集。

“sdiff set1 set2 set3”表示求set1中，在set2、set3这两个集合中不存在的元素。

Sorted Set

Sorted Set类型的“zrevrange key start end”命令，可以实现求出有序集合中指定区间的元素，比如我们有一个表示一天新闻的集合，以新闻的点击量作为score进行排序，那么：

zrevrange news_20240115 0 9

就可以求出2024年1月15日当天点击量最高的新闻的前10名。

还有一个“zunionstore destination numkeys key1 key2…”命令可以合并多个有序集合，比如：

zunionstore news_20240115~20240121 7 news_20240115 news_20240116 news_20240117 news_20240118 news_20240119 news_20240120 news_20240121

表示把2024年1月15日到2024年1月21日这七天的新闻合并到“news_20240115~20240121”这个新闻集合当中。

这两个命令配合使用，就可以求出一周中新闻点击量的前十名。