Redis是一个开源的、使用C语言编写的、支持网络交互的、可基于内存也可持久化的Key-Value数据库。
说起Redis数据结构，肯定先想到Redis的5 种基本数据结构：
String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。
但是Redis用C语言封装了一些底层数据结构：
SDS、Linked List、Dict、Skip List、整数集合、压缩列表。
要把基本数据结构和底层数据结构区分开来，基本数据结构是由底层数据结构实现。
SDS：Simple Dynamic String(简单动态字符串)
SDS定义源码(源码位置：src/sds.h/sdshdr)
Redis3.0版本源码
struct sdshdr{
int len;//buf数组已使用的字节数量
int free;//buf数组未使用的字节数量
char buf[];//char数组，保存字符串
}
Redis6.0版本源码
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; // 已使用长度
uint8_t alloc; // 总长度，用1字节存储
unsigned char flags; // 低三位存储，高五位预留
char buf[]; //char数组，保存字符串
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; // 已使用长度
uint16_t alloc; // 总长度，用2字节存储
unsigned char flags; // 低三位存储，高五位预留
char buf[];//char数组，保存字符串
};
.... //省略 32和64
因为Redis源码是C语言写的，所以源码看一下简单了解就可以。主要看看SDS的数据结构，这里以Redis3.0为例
举例：
存储一个Redis的String基本数据类型，其中一个String包含一个Key和一个Value，如下
但是Redis用C语言封装了一些底层数据结构：SDS
为什么不直接用C字符串，而要封装一个SDS：
Linked List即我们比较熟悉的数据结构——链表，Linked List是Redis基本数据结构列表的底层实现之一，当列表对象的所有字符串元素长度都小于64字节，并且保存的元素数量小于512个时，列表采用另外一个底层数据结构“压缩列表”实现，后续会介绍。
Linked List节点源码(位置：src/adlist.h/listNode)
//Redis3.0~Redis6.0的Linked List源码实现一致
//listNode为链表节点
typedef struct listNode {
//前置节点
struct listNode * prev;
//后置节点
struct listNode * next;
//节点的值
void * value;
}listNode;
从源码的定义有前置节点和后置节点可以看出，Redis链表为双向链表，如下图所示
Redis Linked List源码(位置：src/adlist.h/list)
typedef struct list {
//表头节点
listNode * head;
//表尾节点
listNode * tail;
//链表所包含的节点数量
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void (*free)(void *ptr);
//节点值对比函数
int (*match)(void *ptr,void *key);
} list;
字典即我们熟知的Map，用来保存键值对的抽象数据结构。
字典是基本数据结构 Hash的底层实现之一。
字典源码比较多，涉及三个部分：哈希表、哈希表节点、字典
哈希表和哈希表节点源码如下（位置dict.h/dictht）
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值。总是等于size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;
//每个dictEntry结构都保存着一个键值对
typedef struct dictEntry {
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
} v;
//指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
字典源码（位置 src/dict.h/dict）
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
//rehash 索引。当rehash 不在进行时，值为-1
in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
//为保证字典具有多态及泛型，dictType中提供了如哈希函数以及K-V的各种操作函数，使得字典适用于多重情景
typedef struct dictType {
//计算哈希值的函数
unsigned int (*hashFunction)(const void *key);
//复制键的函数
void *(*keyDup)(void *privdata, const void *key);
//复制值的函数
void *(*valDup)(void *privdata, const void *obj);
//对比键的函数
int (*keyCompare)
(void *privdata, const void *key1, const void *key2);
//销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
//销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
字典采用哈希实现，哈希就是通过哈希算法计算一个哈希值，哈希值作为存储在哈希表数组dictEntry **table的下标，所以会不可避免的出现两个数据计算出来同一个哈希值，即出现“哈希冲突”。
字典采用“链地址法”来解决哈希冲突，链地址法即在出现冲突的下标位置建一个链表，然后把后来的数据存储在当前下标的链表下，如下图所示：
（亲身经历：这里如果在面试中自己提到了哈希冲突，面试官会顺着往下挖，问你有哪些解决哈希冲突的方法或者问“你了解哪些计算哈希值的哈希算法”，这里不做更多补充，可以参考《大话数据结构》一书8.10、8.11章节）
跳跃表 SkipList 是一种有序数据结构，通过在每个节点中维持多个指向其它节点的指针，达到快速访问节点的目的
平均时间复杂度 O（logN），在大部分情况下，跳跃表的效率与平衡树相近，由于跳跃表实现的简易性，所以 Redis 使用跳表代替平衡树。
Redis中的基本数据结构有序集合ZSet采用跳表和哈希表实现
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
Redis 跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义
typedef struct zskiplist {
// 头节点，尾节点
struct zskiplistNode *header, *tail;
// 节点数量（不算表头）
unsigned long length;
// 目前表内节点的最大层数
int level;
} zskiplist;
typedef struct zskiplistNode {
// member 对象
robj *obj;
// 分值
double score;
// 后退指针，指向当前节点的前一个节点，用于表尾向表头遍历时使用
struct zskiplistNode *backward;
// 层，节点使用 L1、L2、L3 标记节点中的各个层，每个层里面又带有两个属性
struct zskiplistLevel {
// 前进指针，指向表尾方向的其它节点，当程序从表头向表尾遍历时，会沿着层的前进指针进行
struct zskiplistNode *forward;
// 这个层跨越的节点数量
unsigned int span;
} level[];
} zskiplistNode;
跳表查找过程
整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这 个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
整数集合的实现
整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为 int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。
源码：src/intset.h/intset结构表示一个整数集合∶
typedef struct intset (
//编码方式
uint32_t encoding;
// 集合包含的元素数量 ,即contents数组的长度
uint32_t length:
//保存元素的数组
int8_t contents[]:
)intset;
contents 数组是整数集合的底层实现∶整数集合的每个元素都是contents 数组的 一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含 任何重复项。
contents属性声明为int8 t类型的数组，但contents数组的真正类型取决于encoding属性的值：
升级
每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有 元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数 集合里面。
升级的好处
Ziplist 是由一系列特殊编码的内存块构成的列表，是为了节约内存而开发的顺序型数据结构， 一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组（不以 \0 结尾的 char 数组）或者整数
压缩列表的组成
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 整个 ziplist 占用的内存字节数，对 ziplist 进行内存重分配，或者计算末端时使用。 |
| zltail | uint32_t | 4字节 | 到达 ziplist 表尾节点的偏移量。 通过这个偏移量，可以在不遍历整个 ziplist 的前提下，弹出表尾节点。 |
| zllen | uint16_t | 2字节 | ziplist 中节点的数量。 当这个值小于 UINT16_MAX （65535）时，这个值就是 ziplist 中节点的数量； 当这个值等于 UINT16_MAX 时，节点的数量需要遍历整个 ziplist 才能计算得出。 |
| entryX | 列表节点 | \ | ziplist 所保存的节点，各个节点的长度根据内容而定。 |
| zlend | uint8_t | 1字节 | 255 的二进制值 1111 1111 （UINT8_MAX） ，用于标记 ziplist 的末端。 |
ziplist 可以包含多个节点，每个节点可以划分为以下几个部分：
| 属性 | 用途 |
|---|---|
| pre_entry_length | 记录压缩列表中前一个节点的长度 |
| encoding 、length | 记录content属性保存的数据的类型和长度 |
| content | 保存节点的值，节点值可以是字节数组或者整数 |
参考：
《Redis设计与实现》