Redis数据结构——五种数据类型

一、String

String是Redis中常见的数据存储类型：

• 其基本编码方式是**RAW,**基于简单动态字符串（SDS）实现，存储上限为512mb。
• 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一点连续空间。申请内存时只需要调用一次内存分配函数，效率更高。
  之所以规定SDS长度小于44字节，是因为RedisObject+SDS刚好是64字节，redis底层内存分配是2的n次方，也就是采用64字节为一个分片大小，这样的话就不会产生内存碎片。
• 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了
  

二、List

Redis的List类型可以从首、尾操作列表中的元素：

哪一个数据结构能满足上述特征？

• LinkedList:普通链表，可以从双端访问，内存占用较高，内存碎片较多
• ZipList:压缩列表，可以从双端访问，内存占用低，存储上限低
• QuickList:LinkedList+ZipList,可以从双端访问，内存占用较低，包含多个ZipList,存储上限高

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

• 在3.2版本之前，Redis采用ZipList和LinkedList来实现List,当元素数量小于512并且元素大小小于62字节时采用ZipList编码，超过则采用LinkedList编码。
• 在3.2版本之后，Redis统一采用QuickList来实现List:
  
  

三、Set

Set是Redis中的单例集合，满足下列特点：

• 不保证有序性
• 保证元素唯一（可以判断元素是否存在）
• 求交集、并集、差集
  
  可以看出，Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？
• HashTable,也就是Redis中的Dict,不过Dict是双列集合（可以存键，值对）
• 为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的Key用来存储元素，value统一为null
• 当存储的所有数据都是整数，并且元素数量不超过set-max-inset-entries时，Set会采用IntSet编码，以节省内存

可以看出当插入一个非整数值的时候，编码就会由IntSet转换为HT格式
底层源码：

四、ZSet

Zset也就是SortedSet,其中每一个元素都需要指定一个score值和member值：

• 可以根据score值排序
• member必须唯一
• 可以根据member查询分数
  
  因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。
• SkipList:可以排序，并且可以同时存储score和ele值
• HT(Dict):可以键值存储，并且可以根据key找value
  
  
  当元素不多时，HT和SkiptList的优势不明显，而且更耗内存，因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：
  ①元素数量小于zset_max_ziplist_entries，默认值128
  ②每个元素都小于zset_max_ziplist_value字节，默认是64
  ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：
• ZipList是连续内存，因此score和element是紧挨在一起的两个entry,element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列
  
  底层源码片段：
  
  

Hash

Hash结构与Redis中的Zset非常类似：

• 都是键值存储
• 都需要根据键获取值
• 键必须唯一

两者的区别在于是否需要排序，因此Hash底层采用的编码与zset基本一致，只需要把排序有关的Skiplist去掉即可：

• Hash结构默认采用ziplist编码。用以节省内存。ziplist中相邻两个entry分别保存field和value
• 当数据量较大时，Hash结构会转为HT编码，也就是Dict,触发条件有两个：
  ①ziplist中的元素数量超过了hash-max-ziplist-entries(默认512)
  ②ziplist中的任意entry大小超过了hash-max-ziplist-value(默认64字节)
  
  
  源码片段：
  
  
  判断每个元素的大小
  
  判断元素的个数