二、Redis的五种常用数据类型二、Redis的五种常用数据类型

在开篇之前，我先来介绍一下写这篇文章的意图，这是我学习过程中的一些思考，也是引领我一直探索下去的兴趣所在。
首先，对于Redis五种常用的数据类型，大部分人都耳熟能详；这几种数据类型的操作指令，随口都可以说出一大堆，但是这些数据类型的存储组织方式，如果被人问到能说出个所以然来吗？
有点编程基础的人可能能猜到一二，string不就是普通字符串，list要么是数组（并不是），要么是链表，set、zset、hash底层都是通过hashtable实现的嘛。但是事实真的那么简单吗？没有仔细学习过的人可能对自己说的话心里都犯嘀咕。
就算学习过常用数据类型的底层存储结构，不同数据结构之间的转换条件，这些数据结构都用来存储哪些类型的数据，又能说得清楚吗？不经过整理是说不清楚的。
本着以上几点学习疑问，我对Redis常用数据类型底层的数据结构进行了整理，通过这一节大家可以系统地学习Redis常用数据类型的存储方式。
1. 前言不捋一下脉络，可能大家在读到这篇文章时会有些疑惑，因为我会先说字符串，再讲string、list等数据类型，大家看到既出现字符串又出现string可能会一脸懵，两者有什么不同吗？
我们知道，Redis只能保存字符串，不支持保存二进制数据，所以字符串是所有key和value的存在形式。而string、list等数据类型是以对象的形式存在的，除了key和value是以字符串形式存在外，还包含很多其他属性。
2. 字符串 Redis的字符串并没有直接采用C字符串，而是自己实现了个SDS结构（simple dynamic string，简单动态字符串）进行存储。

SDS存储结构.png
len表示保存的字符串的长度，不包含空字符'\0'。
free表示buf数组中未使用的字节数，len+free+1即为字节数组的长度。
buf字节数组存储字符串内容，最后以空字符'\0'结尾
SDS与C字符串都以'\0'结尾，这种实现使得SDS可以共用某些C字符串的函数，而无需另外实现。但是SDS相比C字符串有很多优化的地方：

C字符串通过遍历的方式获取字符串长度，时间复杂度为O(n)；而SDS本身使用len属性保存了字符串长度，获取字符串长度的时间复杂度为O(1)。
拼接字符串时，C字符串是直接拼接到紧邻的内存中，可能会覆盖掉内存中原有的内容；而SDS在字符串拼接前会先判断剩余空间free是否满足需求，不满足则重新分配内存进行扩容。
由于C字符串不记录长度，所以每次字符串修改时都需要重新分配内存；而SDS采用空间预分配和惰性释放策略，减少内存重分配次数。

SDS结构在修改字符串前会先判断剩余空间是否足够存储修改后的字符串，如果空间不足，且修改后的字符串长度小于1M，则将空间扩容至修改后字符串长度的2倍（其实还要再多一个字节，用来存储空字符'\0'）；如果修改后的字符串长度大于等于1M，则每次扩容1M。
SDS在缩短字符串长度时，并不会马上释放空间，而是留作以后SDS增长时使用。SDS也提供了相应的API来释放空闲空间，必要时可以调用API释放内存空间。
3. Redis对象 Redis使用对象来表示数据库中的键和值，其中键对象一般为字符串对象，值对象则可以指向不同类型的数据。

Redis对象.png type记录了对象类型，可以取值为REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET，分别表示string、list、hash、set、zset对象。
encoding表示对象底层的编码和存储方式，取值和对象的对应关系如下表所示：

编码常量	底层数据结构
REDIS_ENCODING_INT	long类型的整数
REDIS_ENCODING_EMBSTR	embstr编码的动态字符串（SDS）
REDIS_ENCODING_RAW	简单动态字符串（SDS）
REDIS_ENCODING_HT	字典
REDIS_ENCODING_QUICKLIST	快表
REDIS_ENCODING_ZIPLIST	压缩列表
REDIS_ENCODING_INTSET	整数集合
REDIS_ENCODING_SKIPLIST	跳跃表+字典

ptr是指向具体内存数据结构的指针，由于Redis有多种数据类型，每种数据类型都有多种数据结构可以实现，因此ptr用void来修饰。
4. string对象 string是Redis中最简单的数据类型，它以键值对的方式存储，我们可以通过set [key] [value]命令添加一个string对象，也可以通过del [key]命令来删除一个string对象（当然，del命令对所有类型的key都适用）。
当string保存的是一个整数值，并可以用long型存储时，那么string对象会将整数值保存在ptr里面，将void*转换成long型，编码为int；当整数值太大无法用long型存储时，会将整数值转换成字符串，用SDS来存储，编码为embstr或者raw。

String存储整数值.png
当string对象保存的是一个字符串，并且字符串长度小于等于39字节时，就会用embstr编码来保存字符串值。此时SDS与字符串redisObject紧邻在一起，只需申请一次内存。
embstr.png
当字符串内容长度大于39字节时，会用raw编码来保存字符串，申请内存时需申请两次，一次用来存储redisObject，另一次用于存储SDS结构。释放内存也需要两次释放。
raw.png
另外需要注意的是，string保存浮点数时用embstr或者raw编码保存，当执行数值运算的时候，会转换回浮点型进行运算，运算完之后再转为字符串形式保存。
5. list对象在Redis中，列表对象可用lpush或者rpush命令来创建，并往里面添加元素。也可通过lpop或者rpop命令来弹出列表对象里面的元素。
【二、Redis的五种常用数据类型】考虑到链表的附加空间相对太高，对于64位操作系统来说，prev 和 next 指针就要占去 16 个字节；并且链表的每个节点都单独分配，内存碎片化程度较高，list对象在底层使用quicklist（快速列表）来存储。quicklist是由一个个ziplist组成的链表，每个ziplist连续地存放多个list元素，ziplist中的每个entry块存放一个list元素。相对链表实现来说，quicklist可以大大节省prev 和 next 指针的占用空间。

List对象.png
quicklist内部每个ziplist大小默认为8k，超过这个大小就会另起一个ziplist，封装成quicklistNode添加到quicklist尾部。单个ziplist的大小可通过参数配置。

# Lists are also encoded in a special way to save a lot of space. # The number of entries allowed per internal list node can be specified # as a fixed maximum size or a maximum number of elements. # For a fixed maximum size, use -5 through -1, meaning: # -5: max size: 64 Kb<-- not recommended for normal workloads # -4: max size: 32 Kb<-- not recommended # -3: max size: 16 Kb<-- probably not recommended # -2: max size: 8 Kb<-- good # -1: max size: 4 Kb<-- good # Positive numbers mean store up to _exactly_ that number of elements # per list node. # The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size), # but if your use case is unique, adjust the settings as necessary. list-max-ziplist-size -2

quicklistNode中的ziplist可用压缩的方式存储，压缩深度通过参数list-compress-depth来配置，默认为0（不压缩）。如果设置为1，则首尾两个ziplist不压缩，其他都压缩。不压缩时元素存取速度较快，省去了压缩和解压的开销，但是占用的空间会比较多。
6. hash对象我们可以采用Redis的hash数据类型来存储value包含多个键值对的数据，如保存包含多个属性的用户信息。我们可以通过hset [key] [field] [value]命令来创建hash对象并往里面添加元素。
当元素个数较少，并且每个元素较短时，hash对象底层通过ziplist来存储，field和value存储在两个相邻的entry中。

Hash对象ziplist.png
当元素个数较多，或者存在较长的元素时，hash对象会转为dict（字典）存储。临界点的元素个数和元素长度可由参数hash-max-ziplist-entries和hash-max-ziplist-value进行配置，默认值分别为512和64.
Hash对象dict.png
7. set对象 Redis中的set数据结构可以去重地保存元素，我们可以使用sadd指令往set里添加元素，也可以通过scard指令统计集合元素数量。
默认情况下，当集合元素全为能用long声明的整数值，并且元素个素不大于512个（可通过参数set-max-intset-entries配置）时，集合数据通过intset来存储，intset中的元素按从小到大的顺序排列。其他情况下，集合数据一律使用dict（字典）来存储，字典的键为集合元素的value，字典的值为null。

Set.png
8. zset对象与set对象一样，zset对象也可以去重地保存元素，zset中的元素还可以按照score的顺序排列，score相同的情况下按照value的大小排序。
默认情况下，当zset中的元素个数不大于128（通过参数zset-max-ziplist-entries控制），并且所有元素的长度都不大于64字节（通过参数zset-max-ziplist-value控制）时，zset底层采用ziplist来存储，相邻的两个entry分别表示value和score。如果两个条件有一个不满足，都采用hashtable+skiplist的形式存储，其中hashtable存储value和score的映射关系，skiplist按顺序存储value。

ZSet对象.png
之所以采用hashtable+skiplist的形式存储zset，是因为这两种结构都各有好处。首先，zset是按照score排序的，skiplist的排序特性刚好满足这种需求；然后，hashtable保存了value和score的映射关系，可以直接通过value来获取score，时间复杂度为O(1)。假如没有使用hashtable，获取score就得在skiplist中逐层下沉地搜索，时间复杂度为O(lg n)。虽然同时使用hashtable和skiplist来保存zset，但是他们共用同一个value和score，因此不会造成空间浪费。
至于为啥zset使用skiplist实现排序功能，而不用红黑树呢？我总结出来主要有两点：