数据结构

字符串

1. 3.0 之前

struct sdshdr {
    unsgined int len;
    unsgined int free;
    char buf[];
}

2. 3.0 之后
   1. 引入 flags ，目的是为了区分结构体类型，为了节省空间，可能会采用 8 位 16位 64位的长度来存储 len 和 alloc

struct sdshdr {
    unsgined int len;
    unsgined int alloc; // 已使用的空间
    unsgined chat flags;  
    char buf[];
}

3. 总结
   1. Redis字符串本质上是c语言的字符数组，加上了一点别的标识属性的结构体而已。优点:
   2. 字符串长度获取时间复杂度从O(n)->o(1)
   3. 减少字符串扩容引起的数据搬运次数。
   4. 可以存储更加复杂的二进制数据

链表

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); // 截止释放函数
    void (*match) (void *ptr, void *key); // 节点值对比函数
}

2. 常见API
   1. lpush
   2. rpush
   3. lpop
   4. rpop
   5. llen
   6. lrange

哈希表

• 哈希表是一种存储数据的结构。在哈希表中，键和值是一一对应的关系，一个键key对应一个值value。哈希表这个数据结构可以通过键key，在o(1)时间复杂度的情况下获得对应的值。
• 由于C语言自己没有内置哈希表这一数据结构，因此Redis自己实现了Hash表。
• Redis 的哈希表基于拉链法实现

1. 数据结构
   1. 哈希表掩码：防止索引溢出，通过与运算？？？

// hash表
typedef struct dictht {
    dictEntry **table;      // 哈希表数组
    unsigned long size;     // Hash 表大小 2的幂次方
    unsigned long sizemask; // 哈希表掩码
    unsigned long used;     // Hash 表使用的大小 包括拉链表上的
} dictht;
// 节点结构
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t u64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

// 
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];  // 当表需要扩容时，0是老表 1是新表
    int rehashidx; // -1 没有进行过这是-1，
} dict;

2. rehash：used / size = 负载因子，负载因子越小效率越高，如果负载因子大了查询效率会变低，则需要扩容，所以需要控制在一个合理范围内
   1. 分配空间给ht[1]。分配空间由ht[0]的具体参数决定。
   2. 将ht[0]存储的键值对，重新计算hash值和索引值，并赋值到ht[1]的对应位置中。
   3. 当赋值完成后，释放ht[0]所占用空间，并把ht[0]指向ht[1]目前的地址。
   4. ht[1]指向空表。
3. 什么时候 rehash
   1. 按住鼠标左键拖动选择截图区域在执行后台备份，当负载因子大于等于1就执行。反正CPU闲着也是闲着)
   2. 如果redis在执行后台备份，当负载因子大于等于5就执行。(CPU在干备份了，咱对于实在挤的表改一改，等CPu闲下来，再把稍微偏挤的rehash)

集合

普通集合

采用 hash 表作为实现，唯一性

整数集合

1. 数据结构

typedef struct intset {
    uint32_t encoding;  // 编码 int16_t int32_t int64_t
    uint32_t length;    // 集合长度
    int8_t contents[];  // 元素数组
}

2. 操作
   1. 对于修改，intset保持其一段空间有序。由于intset占用段连续内存，所以每次修改数据需要重新申请空间，比如增加就是扩容，删除就是缩容
   2. 对于查找，由于inset一段空间有序，因此可以执行二分查找算法。

有序集合

跳表

1. 命令
   1. zadd
   2. zcard
   3. zrank
   4. zcount
   5. zrangebyscore
   6. zrem
   7. zscore