数据结构

String

其底层实现就可以分为 int、embstr 以及 raw 这三种类型

Redis 中所有的 key 都是字符串，这些字符串是通过一个名为简单动态字符串（SDS） 的抽象数据类型实现的

1
2
3
4
5
6
7
8
9
struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串
     char buf[];
}

1）如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 类型标识，那么字符串对象会讲整数值保存在 ptr 属性中，并将 encoding 设置为 int。比如 set number 10086 命令。

2）如果字符串对象保存的是一个字符串值，并且这个字符串的长度大于 44 字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为 raw。

3）如果字符串对象保存的是一个字符串值，并且这个字符串的长度小于等于 44 字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串。

存储形式是这样一种存储形式，它将 RedisObject 对象头和 SDS 对象连续存在一起，使用 malloc 方法一次分配。embstr的最小占用空间为19（16+3），而64-19-1（结尾的\0）=44，所以empstr只能容纳44字节

List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct list{
     //表头节点
     listNode *head;
     //表尾节点
     listNode *tail;
     //链表所包含的节点数量
     unsigned long len;
     //节点值复制函数
     void (*free) (void *ptr);
     //节点值释放函数
     void (*free) (void *ptr);
     //节点值对比函数
     int (*match) (void *ptr,void *key);
}list;

typedef  struct listNode{
       //前置节点
       struct listNode *prev;
       //后置节点
       struct listNode *next;
       //节点的值
       void *value;  
}listNode
  1. 双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为 O(1)。
  2. 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。
  3. 带长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。
  4. 多态：链表节点使用指针来保存节点值，可以保存各种不同类型的值。

SET

Set底层实现分为俩种，hashtable和inset

hashtable:

key为Set的值，value为null

inset

简单理解为数组

使用条件

  1. 元素个数不少于默认值512
  2. 元素可以用整型表示

ZSET

底层实现为 字典（dict） + 跳表（skiplist），当数据比较少的时候用ziplist编码结构存储

ziplist

ziplist作为zset的底层存储结构时候，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值

使用条件

  1. 有序集合保存的元素数量小于默认值128个
  2. 有序集合保存的所有元素的长度小于默认值64字节

skipList

1
2
3
4
5
6
typedef struct zset {
    zskiplist *zs1;
    dict *dict;
}

![img.png](img.png)