一、Redis的常用数据类型
字符串（string），队列（list），哈希（hash），集合（sets），有序集合（sorted sets）。
二、底层实现
1、字符串
Redis中的字符串都是由动态字符串(simple dynamic string SDS)实现的
- 所有非数字的key。例如
set msg "hello world"中的key msg. - 字符串数据类型的值。例如`` set msg "hello world"中的msg的值"hello wolrd"
- 非字符串数据类型中的“字符串值”。例如
RPUSH fruits "apple" "banana" "cherry"中的"apple" "banana" "cherry"。
SDS数据结构定义：
struct sdshdr {
int len;// buf 中已占用字节数
int free;// buf 中剩余可用字节数
char buf[];// 数据空间
};
Redis 3.2之前的SDS这样设计的有点：
1）有单独的统计变量len和free（称为头部）。可以很方便地得到字符串长度。
2）内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。
3）由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。
2、队列（list）
list的底层数据结构时链表。Redis 3.2之前的版本（包含3.2）使用的时ziplist或者linkedlist，Redis 3.2之后版本使用的quicklist。
ziplist
压缩列表是为了节约内存而开发的，是存储在连续内存块上的顺序数据结构。一个压缩列表可以包含任意多的 entry 节点，每个节点包含一个字节数组或整数。redis 中并没有显式定义 ziplist 的数据结构，仅仅提供了一个描述结构 zlentry 用于操作数据。
typedef struct zlentry {
unsigned int prevrawlensize;// 用于记录前一个 entry 长度的字节数
unsigned int prevrawlen; // 前一个 entry 的长度
unsigned int lensize // 用于记录当前 entry 类型/长度的字节数
unsigned int len; // 实际用于存储数据的字节数
unsigned int headersize; // prevrawlensize + lensize
unsigned char encoding; // 用于指示 entry 数据的实际编码类型
unsigned char *p; // 指向 entry 的开头
} zlentry;
各字段含义如下：
- 1、zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最长(2^32)-1字节；
- 2、zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节；
- 3、zllen：压缩列表的元素数目，占两个字节；那么当压缩列表的元素数目超过(2^16)-1怎么处理呢？此时通过zllen字段无法获得压缩列表的元素数目，必须遍历整个压缩列表才能获取到元素数目；
- 4、entryX：压缩列表存储的若干个元素，可以为字节数组或者整数；entry的编码结构后面详述；
- 5、zlend：压缩列表的结尾，占一个字节，恒为0xFF。
该数据结构具有以下特征：
- 结构紧凑：一整块连续内存，没有多余的内存碎片，更新会导致内存 realloc 与内存复制，平均时间复杂度为 O(N)
- 逆向遍历：从表尾开始向表头进行遍历
- 连锁更新：对前一条数据的更新，可能导致后一条数据的 prev_entry_length 与 encoding 所需长度变化，产生连锁反应，更新操作最坏时间为 O(N2)
quicklist
在较早版本的 redis 中，list 有两种底层实现：
- 当列表对象中元素的长度比较小或者数量比较少的时候，采用压缩列表 ziplist 来存储
- 当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表 linkedlist 来存储
两者各有优缺点：
- ziplist 的优点是内存紧凑，访问效率高，缺点是更新效率低，并且数据量较大时，可能导致大量的内存复制
- linkedlist 的优点是节点修改的效率高，但是需要额外的内存开销，并且节点较多时，会产生大量的内存碎片.
为了结合两者的优点，在 redis 3.2 之后，list 的底层实现变为快速列表 quicklist。
快速列表是 linkedlist 与 ziplist 的结合: quicklist 包含多个内存不连续的节点，但每个节点本身就是一个 ziplist。
typedef struct quicklistNode {
struct quicklistNode *prev; // 上一个 ziplist
struct quicklistNode *next; // 下一个 ziplist
unsigned char *zl; // 数据指针，指向 ziplist 结构，或者 quicklistLZF 结构
unsigned int sz; // ziplist 占用内存长度（未压缩）
unsigned int count : 16; // ziplist 记录数量
unsigned int encoding : 2; // 编码方式，1 表示 ziplist ，2 表示 quicklistLZF
unsigned int container : 2; //
unsigned int recompress : 1; // 临时解压，1 表示该节点临时解压用于访问
unsigned int attempted_compress : 1; // 测试字段
unsigned int extra : 10; // 预留空间
} quicklistNode;
typedef struct quicklistLZF {
unsigned int sz; // 压缩数据长度
char compressed[]; // 压缩数据
} quicklistLZF;
typedef struct quicklist {
quicklistNode *head; // 列表头部
quicklistNode *tail; // 列表尾部
unsigned long count; // 记录总数
unsigned long len; // ziplist 数量
int fill : 16; // ziplist 长度限制，每个 ziplist 节点的长度（记录数量/内存占用）不能超过这个值
unsigned int compress : 16; // 压缩深度，表示 quicklist 两端不压缩的 ziplist 节点的个数，为 0 表示所有 ziplist 节点都不压缩
} quicklist;
该数据结构有以下特征：
- 无缝切换：结合了 linkedlist 与 ziplist 的优点，无需在两种结构之间进行切换
- 中间压缩：作为队列使用的场景下，list 中间的数据被访问的频率比较低，可以选择进行压缩以减少内存占用。
3、哈希（hash）
hash 类型是 Redis 常用数据类型之一，其底层存储结构有两种实现方式。
当存储的数据量较少的时，hash 采用 ziplist 作为底层存储结构，此时要求符合以下两个条件：
- 哈希对象保存的所有键值对（键和值）的字符串长度总和小于 64 个字节。
- 哈希对象保存的键值对数量要小于 512 个。
当无法满足上述条件时，hash 就会采用 dict（字典结构）来存储数据，数据结构如下：
typedef struct dictEntry {
void* key; // 键
union { // 值，可以为指针、有符号长整，无符号长整，双精度浮点
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictht {
dictEntry **table; // 哈希表数组，数组中的每个元素是一个单向链表
unsigned long size; // 哈希表数组大小
unsigned long sizemask; // 哈希掩码，用于计算索引
unsigned long used; // 已有节点数量
} dictht;
typedef struct dictType {
unsigned int (*hashFunction) (const void *key); // 哈希函数，用于计算哈希值
int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 键比较函数
void *(*keyDup)(void *privdata, const void *key); // 键复制函数
void *(*valDup)(void *privdata, const void *obj); // 值复制函数
void *(*keyDestructor)(void *privdata, const void *key); // 键销毁函数
void *(*valDestructor)(void *privdata, const void *obj); // 值销毁函数
} dictType;
typedef struct dict {
dictType *type; // 类型函数，用于实现多态
void *privdata; // 私有数据，用于实现多态
dictht ht[2]; // 哈希表，字典使用 ht[0] 作为哈希表，ht[1] 用于进行 rehash
int rehashidx; // rehash索引，当没有执行 rehash 时，其值为 -1
} dict;
数据结构有以下特征：
- 哈希算法：使用 murmurhash2 作为哈希函数，时间复杂度为O(1)
- 冲突解决：使用链地址法解决冲突，新增元素会被放到表头，时间复杂度为O(1)
4、集合（sets）
Redis set 采用了两种方式相结合的底层存储结构，分别是 intset（整型数组）与 hash table（哈希表），当 set 存储的数据满足以下要求时，使用 intset 结构：
- 集合内保存的所有成员都是整数值；
- 集合内保存的成员数量不超过 512 个。
当不满足上述要求时，则使用 hash table 结构。
intset 的结构体定义如下:
typedf struct inset{
uint32_t encoding;//指定编码方式，默认为INSET_ENC_INT16
uint32_t length;//集合内成员的总个数
int8_t contents[];//实际存储成员的数组，并且数组中的数值从小到大依次排列
}inset;
- encoding：用来指定编码格式，共有三种，分别是 INTSET_ENC_INT16、INSET_ENC_INT32 和 INSET_ENC_INT64，它们对应不同的数值范围。Redis 为了尽可能地节省内存，它会根据插入数据的大小来选择不同的编码格式。
- length：集合内成员的数量，记录 contents 数组*有多少个成员。
- contents：存储成员的数组，数组中的成员从小到大依次排列，且不允许重复。
有序整型集合，具有紧凑的存储空间，添加操作的时间复杂度为O(N)
5、有序集合（sorted sets)
有序集合（zset）同样使用了两种不同的存储结构，分别是 zipList（压缩列表）和 skipList（跳跃列表），当 zset 满足以下条件时使用压缩列表：
- 成员的数量小于128 个；
- 每个 member （成员）的字符串长度都小于 64 个字节。
当有序结合不满足使用压缩列表的条件时，就会使用 skipList 结构来存储数据。
跳跃列表（skipList）又称“跳表”是一种基于链表实现的随机化数据结构，其插入、删除、查找的时间复杂度均为 O(logN)。从名字可以看出“跳跃列表”，并不同于一般的普通链表，它的结构较为复杂，本节只对它做浅显的介绍，如有兴趣可自行研究。
在 Redis 中一个 skipList 节点最高可以达到 64 层，一个“跳表”中最多可以存储 2^64 个元素，每个节点都是一个 skiplistNode（跳表节点）。skipList 的结构体定义如下：
typedf struct zskiplist{
//头节点
struct zskiplistNode *header;
//尾节点
struct zskiplistNode *tail;
// 跳表中的元素个数
unsigned long length;
//表内节点的最大层数
int level;
}zskiplist;
- header：指向 skiplist 的头节点指针，通过它可以直接找到跳表的头节点，时间复杂度为 O(1)；
- tail：指向 skiplist 的尾节点指针，通过它可以直接找到跳表的尾节点，时间复杂度为 O(1)；
- length：记录 skiplist 的长度，也就跳表中有多少个元素，但不包括头节点；
- level：记录当前跳表内所有节点中的最大层数（level）；
跳跃列表的每一层都是一个有序的链表，链表中每个节点都包含两个指针，一个指向同一层的下了一个节点，另一个指向下一层的同一个节点。最低层的链表将包含 zset 中的所有元素。如果说一个元素出现在了某一层，那么低于该层的所有层都将包含这个元素，也就说高层是底层的子集。
该数据结构有以下特征：
- 查找：平均查找时间为O(logN)，最坏查找时间为O(N)，并且支持范围查找
- 概率：每次创建节点的时候，程序根据幂次定律随机生成一个 1 至 32 之间的随机数，用于决定层高
- 排位：在查找节点的过程中，沿途访问过所有的跨度 span 累计起来，得到目标节点在表中的排位