Redis基础数据类型

1 SDS

1.1 结构体

以下结构体表示一个SDS值：

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

1.2 结构图

1.3与c字符串的区别

可以常数复杂度获取字符串长度

c中获取字符串长度的方式是通过线性遍历，而SDS由于存储已使用的字节数量，可以通过常数复杂度获取
杜绝缓冲区溢出

例如，c的字符串在使用strcat为原字符串添加字符串时，如果未分配有效空间，很可能造成缓冲区溢出。而SDS的API会检查空间是否满足修改所需的要求。
减少修改字符串时带来的内存重分配次数

c中字符串在执行拼接操作时，如果空间不足，需要通过内存重分配来扩张空间大小，如果忘了则会发生缓冲区溢出

如果执行截断操作，程序就要释放不再使用的空间，如果忘了则会发生内存泄漏

以上两种操作，如果频繁地发生，是会对性能造成影响的。

由此，SDS通过空间预分配和惰性空间释放两种策略来进行优化
- 空间预分配
  
  当SDS在分配空间时，如果SDS长度小于1M，则会分配原来长度len同样大小的未使用空间（还得+1，空字符）；如果SDS大于1M，则会分配1M未使用空间+1。这样使得内存分配次数从N次降低到最多N次
- 惰性空间释放
  
  当SDS在释放空间时，不会进行空间回收，而是使用free属性将字节数量记录下来，方便将来使用
二进制安全

由于c中不能包含空字符（会被当成结尾），限制了不能保存像图片，音频，视频这样的二进制数据。但SDS由于通过len来判断字符串是否结束，从而不会发生这种问题。
兼容部分C字符串函数

2 链表

2.1 结构体

/*
	节点
*/
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;

2.2 结构图

3 字典

字典底层使用哈希表，一个哈希表可以有多个哈希表节点，每个哈希表节点就保存了字典中的一个键值对

3.1 结构体

/*
	哈希表节点
*/
typedef struct dictEntry {
    void *key; // 键
    union { // 值，可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数
        void *val; 
        uint64_tu64;
        int64_ts64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

/*
	哈希表
*/
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于size-1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

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

3.2 结构图

4 跳跃表

一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

支持平均O（logN），最坏O（N）复杂度的节点查找

4.1 结构体

typedef struct zskiplistNode {
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
} zskiplistNode;

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

4.2 结构图

5 整数集合

用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

5.1 结构体

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

5.2 结构图

6 压缩列表

6.1 构成

列表

节点
1. previous_entry_length
  
  记录了压缩列表中前一个节点的长度。
2. encoding
  
  记录了节点的content属性所保存数据的类型以及长度
3. content
  
  保存节点的值，节点值可以是一个字节数组或者整数

7 对象

Redis并没有直接使用上述数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。

7.1 结构体

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