redis...，用了好多年了，这也是面试八股文必问内容，但是你真的搞懂redis底层数据结构了吗？5种数据结构；对，但是然后呢，直击灵魂的一问~哈哈，下面咱们就重新回顾回顾。

一，服务器端整体数据结构

1.1 redisServer

redis服务器将所有的数据库保存在redisServer结构的db数组中，db数组中的每一个redisDB结构代表一个数据库。代码如下

typedef struct redisServer{
	redisDb *db;   // db是一个数组，服务器中的所有数据库
	int dbNum;     // 服务器的数量，一般是16个
    ...
}

同时在服务器内部，还有一个客户端状态的结构，redisClient,这个结构会记录客户端当前使用的数据库

typedef struct redisClient{
    redisDb *db; // 记录客户端正在中正在使用的数据库，db中保存的就是reidsServer 中的元素，即正在使用服务器中的哪个数据库
    ...
}

比如说，某个客户端连接数据库后，执行了select 2, 则其结构为：

1.2 redisDB

tydef struct redisDb{
	dict *dict;   // 数据库的键空间，保存着数据库中的所有的键值对。  dict 的建对象是一个字符串对象，值对象是5种基本数据类型中的. 都是redisObject  
    dict * expire;  // 键值对的过期时间
    ...
} 

每个redisDB代表一个数据库，其中的dict保存了数据库中的所有键值对，这个字典也称为键空间。

1.3 一个例子

在redis中执行这些代码

redis＞ SET message "hello world"
OK
redis＞ RPUSH alphabet "a" "b" "c"
(integer)3
redis＞ HSET book name "Redis in Action"
(integer) 1
redis＞ HSET book author "Josiah L. Carlson"
(integer) 1
redis＞ HSET book publisher "Manning"
(integer) 1
redis> expire alphabet xxxxx
redis> expire book yyyy

结果为：

根据图可知，执行ttl key 或者 pttl key 的时间复杂度为O(1)

1.4 redisObject

刚才看到redisDB中的dict中key和value都是一个redisObject结构，其结构如下

typedef struct redisObject {
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    // ...
} robj;

详细介绍下每个字段的意思：

1. type记录了对象的类型，常说的redis中的5大数据类型

type key 命令输出的也是这个字段对应的值，如下图

2. encoding 记录了对象所使用的编码，也就是说此redis对象底层使用的数据结构，每种类型的对象可以使用的编码如下。

二，redis 数据结构

接下来我们就详细讲一讲每种数据结构的编码，这才是真正的底层数据结构。

2.1 字符串对象

（1）encoding=REDIS_ENCODING_INT 底层使用数字类型编码

当set 的value值是数字类型时，redis会用数字类型存储，举例如下，

(2)encoding =REDIS_ENCODING_EMPTR

如果设设置的value值得大小小于32字节，则会使用此种编码格式，结构如下

示例如下：

（3）encoding =REDIS_ENCODING_RAW

如果设置的value值得大小大于32字节，则会使用此种编码格式，结构如下

说明：

（2），（3） 的区别在于分配内存的方式，对于value值小于32字节的情况，redisObject和SDS用同一块连续的内存。释放的时候只需要释放一次。对于大于32字节的情况。分配了两块内存。一块是redisObject ，另一块是SDS.redisObject中的ptr指向SDS。释放的时候释放两次。

不得不感叹一句，redis的开发者真的太细了~~~

redis中用到的字符串对是自己封装的，叫SDS，介绍下

SDS redis底层存储字符串的数据结构，如下图所示

struct sdshdr {
    //记录buf数组中已使用字节的数量
    //等于SDS所保存字符串的长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组，用于保存字符串
    char buf[];
};

示例：

2.2 列表对象编码

列表对象有两种编码方式， ziplist 和linkedlist，首先来介绍下这两种数据结构

linkedlist 列表：

typedef struct listNode {
    // 前置节点
    struct listNode * prev;
    // 后置节点
    struct listNode * next;
    //节点的值
    void * value;
}listNode;

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;

示例如下：

zipList 压缩列表：

压缩列表的构成：

举个例子：

1. 列表zlbytes属性的值为0x50（十进制80），表示压缩列表的总长为80字节

2. 列表zltail属性的值为0x3c（十进制60），这表示如果我们有一个指向压缩列表起始地址的指针p，那么只要用指针p加上偏移量60，就可以计算出表尾节点entry3的地址

3. 列表zllen属性的值为0x3（十进制3），表示压缩列表包含三个节点

entry结构:

1. 节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度

2. 节点的encoding属性记录了节点的content属性所保存数据的类型以及长度

3. content就是编码对应的数据

（1）列表对象使用ziplist 编码，使用ziplist 编码的列表对象有两个条件

1.列表对象保存的所有字符串元素的长度都小于64字节；

2.列表对象保存的元素数量小于512个；不能满足这两个条件的列表对象需要使用linkedlist编码

示例如下：

（2） 列表对象使用 linkelist ,不满足ziplist得即使用linkedlist,如下所示

2.3 哈希对象

哈希对象有两种编码方式 ziplist或者hashtable。

（1）使用ziplist 编码

1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节 2.哈希对象保存的所有键值对的键和值的字符串长度都小于64字节

例如：

redis＞ HSET profile name "Tom"
(integer) 1
redis＞ HSET profile age 25
(integer) 1
redis＞ HSET profile career "Programmer"
(integer) 1

（2）使用hashtable字典实现

首先讲下字典的实现方式

1.字典的结构

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    // rehash索引
    //当rehash不在进行时，值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

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;

(2)如果不满足（1）的条件，则其使用字典，结构如下

2.4 集合对象

集合对象的实现有两种实现方式，集合对象的编码可以是intset或者hashtable。

首先说下intset整数集合

inset整数集合的实现

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

（1）集合使用inset编码

条件：

1. 集合对象保存的所有元素都是整数值；

2. 集合对象保存的元素数量不超过512个

当使用整数集合时，结构如下

举例如下：

（2）集合使用hastable结构如下

2.5 有序集合

有序集合的编码可以是ziplist或者skiplist

条件：1.有序集合保存的元素数量小于128个

2. 集合对象保存的元素数量不超过512个

（1）当使用ziplistb 编码时，其结构如下

 redis＞ ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

跳跃表的实现

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点

跳跃表示例：

由此看，在redis的实现中，跳跃表的实现分成了两部分。

左半部分参数说明：

1.header：指向跳跃表的表头节点

2. tail：指向跳跃表的表尾节点

3. 记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）

4.length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）

右半部分参数说明：

1. Ln 代表第n层数,如L2代表第二层。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离，跨度可以计算目标节点在跳跃表中的排位

2. 后退（backward）指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用

3. 分值（score）：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。

4. 成员对象（obj）：各个节点中的o1、o2和o3是节点所保存的成员对象。

（2）有序集合使用skiplist编码时

有序集合使用skiplist时，使用的数据结构是skiplist和dict组合而成。如下

typedef struct zset {
    zskiplist *zsl;
    dict *dict;
} zset;

即ptr指针指向的是zset 的地址，举例如下；

说明：为什么在使用skiplist和dict做有序集合的底层编码？

其实，skiplist和dict 两种数据结构都可以单独作为有序集合的底层编码的。如果单独使用dict作为底层编码，可以有O(1)的时间复杂度某个成员的分值，但是每次在执行范围型操作——比如ZRANK、ZRANGE等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少O（NlogN）时间复杂度，以及额外的O（N）内存空间。另一方面如果使用skiplist,范围操作的优势将会保存，但是所以根据成员查找分值这一操作的复杂度将从O（1）上升为O（logN）。因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。还有要注意的点，这样做也不会浪费内存，因为在redis中，数据是共享的，他们的指针都指向通一份数据。

不得不再感叹一句，redis真的太细了，太强了~~