讲讲Redis各个数据类型的底层数据结构
哈喽，大家好，我是指北君。
前段时间有朋友面试京东的时候，遇到这样的面试题。
讲讲Redis的数据类型以及其对应的底层数据结构
那么今天指北君带大家了解一下Redis基本数据类型对应的底层数据结构。
1. 前言
Redis的键值对中的常见数据类型有String
(字符串)、List(列表)、Hash(哈希)、Set(集合)、Zset(有序集合)。那么其对应的底层数据结构有SDS(simple dynamic
string)、链表、字典、跳跃表、压缩列表、快速列表，整数集合等。
下面我们来了解一下其底层数据结构的精妙之处。
2. Redis底层数据结构
2.1 SDS
Redis自定义了一种简单动态字符串(simple dynamic string)，将其作为Redis的默认字符串表示。
其主要结构如下：
len表示这个SDS字符串长度，如果buff字节数组中保存了5个字符那么长度就是5。同时也方便获取SDS的长度。alloc表示分配的字符数组长度。其值一般是大于SDS字符串长度(len)，由于Redis的设计场景就是会频繁的访问，修改数据，所以无论是数据增大或者是缩小都需要尽量减少重新分配内存的操作。所以SDS会预留一些空间，在下一次修改数据的时候可以直接使用原先预分配的内存，同时在每次数据操作的时候也会动态的增加或者减少预留内存空间，。Redis3.0的版本的SDS结构中使用free， 表示未分配的空间，但也是同一个设计思想。flags 标志位，低3位表示类型，其余5位未使用。buf 实际存储数据的数组，可以保存字符，也可以保存二进制数据。
redis6.0中SDS定义如下 (越来越节约使用内存了，内存是省出来的!)
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
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[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
相对于C语言的字符串，SDS具有以下优点。
获取字符串的长度复杂度更低(常数复杂度)。更加节省内存(针对不同长度设置了不同的数据类型 sdshdr5、sdshdr8、sdshdr16等。)杜绝缓冲区溢出。大大减少了修改字符串长度时所需要的内存分配次数。二进制安全。2.2 链表
链表是大家比较熟悉的数据结构了，链表提供了高效的节点重排能力，顺序访问，通过增删节点调整长度等特点。Redis
List对象的底层实现之一就是链表。
每一个链表节点使用如下的结构来表示。
/* Node, List, and Iterator are the only data structures used currently. */
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
而多了listNode可以通过prev 和 next 指针组成一个双端队列如下图：
多个节点可以组成一个链表，Redis使用了List结构来持有这些节点，操作更方便。其结构如下：
typedef struct list {
listNode *head; //链表头节点指针
listNode *tail; //链表尾节点指针
void *(*dup)(void *ptr); // 用于复制链表节点所保存的值
void (*free)(void *ptr); // 用于释放链表节点所保存的值
int (*match)(void *ptr, void *key); //用于对比链表节点所保存的值和另一个输入值是否相等
unsigned long len; // 链表所包含的节点数量
} list;
简单结构如下图：
Redis链表具有如下特性：
由于是双端链表，有prev和next指针，获取节点的前置节点和后置节点的复杂度为O(1)。头节点的prev和尾节点的next均指向NULL，为无环链表，可以以NULL为链表访问终点。链表本身提供了指针，可以快速获取链表的表头节点和表尾节点。自带链表长度计数器，可以快速获取链表长度。链表可以保存各种不同类型的值。2.3 字典
字典是一种用于保存键值对的抽象数据结构。
在字典中，一个键(key)可以和一个值(value)进行关联，称之为键值对。字典中每个键都是独一无二的，并且程序都是通过key来操作更新value或者删除数据等。
Redis的字典使用哈希表作为底层实现的， 一个哈希表可以包含多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
下面再讲一下哈希表，哈希表节点，以及字典的实现。
哈希表及哈希表节点结构，字典结构 如下：
//字典结构
typedef struct dict {
dictType *type; // 类型特定的函数
void *privdata; //私有数据
dictht ht[2]; //长度为2的哈希表数组， 一般情况下字典仅使用 ht[0]哈希表， ht[1]在rehash的时候会使用到。
long rehashidx; /* 未进行rehash的时候 rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
//哈希表结构
typedef struct dictht {
dictEntry **table; //哈希数组
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表掩码，用于计算索引值， 总是等于size-1
unsigned long used; //表示已有节点数量
} dictht;
//哈希节点
typedef struct dictEntry {
void *key; //键
union { //value值，包含了多种类型的值，不同类型的值可以使用不同的数据结构存储，节省内存。
void *val; //其值可以是一个指针
uint64_t u64; //其值也可以是一个uint64_t 整数
int64_t s64; //其值可以是一个int64_t 整数
double d; //其值可以是一个double
} v;
struct dictEntry *next; //指向像一个哈希节点
} dictEntry;
普通状态下的字典结构示意图：
添加新建的机制是大家比较熟悉的思路啦。
使用字典设置的哈希函数计算key的哈希值，
哈希值与sizemask 进行
