众所周知，redis是有名的哈希存储，从而实现从键对值的快速访问。它使用了一个哈希表来保存所有键值对。
redis值的基本数据类型包含五大类：String、List、Set、Sorted Set、Hash。除String外，其它4种类型因为value值都是一组集合，所以后4中类型也叫做集合类型。它们所对应的底层数据结构如下:
因为redis有多种数据类型，不同的数据类型有一些元数据需要记录(如LRU,被引用次数等），所以redis会用一个redisObject对象来保存这些元数据，并用指针指向实际数据。redisObject的定义如下：(https://github.com/redis/redis/blob/unstable/src/server.h):
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
type表示对象的类型，占4个bit。string,list,hash等
encoding:对象的编码类型，占4个bit。如string类型有int、raw、embstr三种编码。
refcount:*记录该对象被引用的次数，占用4字节。
ptr:指向具体数据的指针，占用8字节。
所以一个redisObjects的大小为16个字节。
综合起来，redis的存储结构大概如下：
关于key存储的是SDS还是redisObject,一定要注意。redis在开始时把key和value都转成了redisObject。但在最后进行db存储操作的时候，又只取出了redisObject对象中ptr所指向的SDS结构体。看源码时看到db中的setKey之后没细看，纠结了我好久。
好了，接下来就开始逐一了解一下这五种数据类型以及他们的数据结构。首先是String。
-----------------------------------------String---------------------------------------
String就是我们经常用到的典型的键-单值,例如：
127.0.0.1:6379> SET 'name' 'huan'
OK
String类型的数据，redis会用简单动态字符串(Simple Daynamic String,SDS)结构体来保存数据。
buffer： 字节数组，保存实际数据。为表示数据结束，会在最后加一个'\0'
Len： buffer的已用长度。会使用sdsReqType方法据长度的大小和系统选择合适的字节数（1/2/4/8）。
Alloc： 实际的分配长度，会取离len最近的2的幂次方。一般会大于len。和len一样根据长度的大小选择合适的字节数。
flags： 标记字段，目前只使用了3bits
sdshdr8结构体定义如下:
struct __attribute__ ((__packed__)) sdshdr8{
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
当我们设置一个简单的字符串键值对(<6bytes)，计算使用内存为80bytes.
before_mem = get_memory_info()
r.set("key1","key1")
after_mem = get_memory_info()
print("used:{}".format(after_mem-before_mem))
#输出
已使用的内存为1109120B
已使用的内存为1109200B
used:80
但如果key和value都是字符串形式的整型， 则只需要使用64bytes.
before_mem = get_memory_info()
r.set("1001","100202")
after_mem = get_memory_info()
print("used:{}".format(after_mem-before_mem))
#输出
已使用的内存为1109056B
已使用的内存为1109120B
used:64
get_memory_info方法：
def get_memory_info()->(float,float):
info_mem = r.info(section='memory')
used_memory = info_mem['used_memory']
print("已使用的内存为{}B".format(used_memory))
return used_memory
这是因为String有三种编码方式int,embstr, raw，所对应的底层存储方式不同。
当字符串为长整型时，直接将redisObject的指针ptr直接存储为整型数据。
当字符串小于等于44字节时，redisObject的指针ptr与它所指向的SDS结构连续存储。
当字符串大于44字节时，SDS不再和redisObject连续存储了，而是单独地分配空间，通过ptr指针指向。
这样做的目的是为了更好地利用内存，减少内存碎片。
-----------------------------------------Hash---------------------------------------
Hash类型包含key、filed、value三部分,如：
127.0.0.1:6379> hset website google google.cn
(integer) 0
127.0.0.1:6379> hget website google
"google.cn"
即一个key下面还有域的概念，一个key将对应多组field:value。这样对于一些具有相同前缀的key我们可以进行切割，把key的相同部分提取出来作为key,不同部分为field,既可以进行一个分类区分，又可以节省内存空间。
Hash的底层结构使用紧凑列表listpack(改进版的压缩列表ziplist)和哈希表两种方式进行存储。
int hashTypeSet(robj *o, sds field, sds value, int flags) {
if (o->encoding == OBJ_ENCODING_LISTPACK) {
...
} else if (o->encoding == OBJ_ENCODING_HT){
...
}
Hash类型默认使用压缩列表存储，但它设置了用压缩列表保存数据时的两个阈值，如果超过了这两个阈值，则使用哈希表保存数据。两个阈值分别是：
hash-max-ziplist-entries:表示用压缩列表保存时哈希集合中的最大元素个数
hash-max-ziplist-value:表示用压缩列表保存时哈希集合中单个元素的最大长度。
我们可以在redis.conf中设置这两个值，默认设置为：
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
我们看一下内存存储情况
before = get_memory_info()
r.hset('website','baidu','baidu.com')
after = get_memory_info()
print(after-before)
before = get_memory_info()
r.hset('website','google','google.cn')
after = get_memory_info()
print(after-before)
#输出
已使用的内存为1090160B
已使用的内存为1090288B
128 此时我的redis里面是没有数据的，如果非空，此值为96
已使用的内存为1090288B
已使用的内存为1090304B
16
如果key不存在，需要分配dictEntry等，实际数据所占的内存比比较小，而一旦key已存在，所使用的内存就小了。那就看看压缩列表是怎样存储以减少内存的吧
压缩列表
因为listpack是ziplist的改进版，我们就先从压缩列表看起吧。压缩列表的文档相对详细很多。我们可以看下他们两个的entry的定义，基本一样的：
/* Each entry in the ziplist is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
unsigned int slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} ziplistEntry;
/* Each entry in the listpack is either a string or an integer. */
typedef struct {
/* When string is used, it is provided with the length (slen). */
unsigned char *sval;
uint32_t slen;
/* When integer is used, 'sval' is NULL, and lval holds the value. */
long long lval;
} listpackEntry;
zlbytes:4字节，指整个压缩列表的长度
zltail:4字节，最后一个entry的偏移量。主要是用于pop的时候可以直接定位而不需要遍历。（listpack没有此字段）
zllen:2字节，entry的个数。当超过2^16-2 个时，设置为2^16-1，此时需要遍历才能知道有多少个。
zlend:ziplist的结束标志。0xFF。ziplist中其它字段都不会存在0xFF。
entry:
entry里面可以存字符串，可以存整型。主要包括以下几部分:
prev_len:前一个数据的长度。当长度小于254的时候，只需1个字节；当长度大于等于254的时候，占5个字节，第一个字节设置为FE，后面4个字节表示长度。
encoding:2个bit。表示数据是字符串还是整型等，以及是多少长度的。如：
00|pppppp:表示长度小于或等于63(6bits)的字符串。后面6bits表示字符串长度
len数据的长度
结合源码中给出的注释例子：
* The following is a ziplist containing the two elements representing
* the strings "2" and "5". It is composed of 15 bytes, that we visually
* split into sections:
*
* [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
* | | | | | |
* zlbytes zltail entries "2" "5" end
看完上面，为什么说ziplist节省空间呢？因为ziplist是按顺序存储数据的，相当于数组。但是又不同于数据，数据只需要多大的空间，它存分配多少给存取，因为它有记录长度的字段。而不像数组，它每一个数据都需要按数组的最大长度的数据分配空间。而它不能存储过大的数据，也是因为它是顺序存取，所以读取的时候是要遍历的，如果数据过多，就会影响其性能。当其超过其阈值时，就要转换成其它的数据结构存储了。
-----------------------------------------List---------------------------------------
示例
r.lpush('op','on')
r.lpush('op','off')
r.linsert('op','AFTER','on','color')
r.lrange('op',0,r.llen("op"))
许多地方都说列表的底层存储结构为压缩列表或双向链表。实际上，redis后面也做了优化，用的是快速列表quicklist。根据它的描述可得知是一个listpack的链表。即综合了压缩列表和双向链表。
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
整数数组的结构定义如下：
typedef struct intset {
uint32_t encoding; #有16B/32B/64B
uint32_t length; #整型数组中数据的个数
int8_t contents[]; #一个柔性数组，用于存取具体的集合数据
} intset;
-----------------------------------------Set---------------------------------------
示例
SADD bbs "discuz.net"
Set集合的底层存储结构为整数数组和哈希表。在redis的配置中有一个参数可配置整型数组中元素的最大个数，默认为512。最大不能超过1G，即使配置超过1G了，代码也会进行修正。当超过最大个数时，就转成哈希表存储。
set-max-intset-entries 512
/* Convert to regular set when the intset contains
* too many entries. */
size_t max_entries = server.set_max_intset_entries;
/* limit to 1G entries due to intset internals. */
if (max_entries >= 1<<30) max_entries = 1<<30;
if (intsetLen(subject->ptr) > max_entries)
setTypeConvert(subject,OBJ_ENCODING_HT);
-----------------------------------------Sorted Set---------------------------------
sorted set 底层使用紧凑列表listpack和跳表skiplist两种结构保存数据。同时为了插入和删除的时间复杂度为O(log(n))，它还使用哈希表保存数据。
ZSETs are ordered sets using two data structures to hold the same elements in order to get O(log(N)) INSERT and REMOVE operations into a sorted data structure.
The elements are added to a hash table mapping Redis objects to scores. At the same time the elements are added to a skip list mapping scores to Redis objects (so objects are sorted by scores in this "view").
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
它同样有两个配置选项控制是使用压缩列表还是跳表
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
zset-max-ziplist-entries: 压缩列表中元素的最大个数
zset-max-ziplist-value：压缩列表中单个元素的最大长度
