数据结构

Redis 底层有6种数据结构

使用SDS存储字符串对象

简单动态字符串（simpledynamicstring，SDS），用作Redis的默认字符串表示。

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

SDS遵循C字符串以空字符结尾的惯例，以便可以直接重用一部分C字符串函数库里面的函数，如：

printf("%s",s->buf);

SDS的优势

双向链表

链表可以高效的重排节点，灵活的增删节点调整长度。Redis中，主要应用于链表键、发布与订阅、慢查询、监视器等功能。

双向链表的数据结构

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;

typedef struct listNode {
    //前置节点
    struct listNode *prev;

    //后置节点
    struct listNode *next;

    //节点的值
    void *value;
} listNode;

字典

Redis中，字典用于保存数据库中的键值对，对数据库的增删改查就是构建在对字典的操作之上。

字典的数据结构

typedef struct dict {
    // 类型特定函数
    dictType *type;

    //私有数据
    void *privdata;

    //哈希表
    dictht ht[2];

    //rehash索引
    //当rehash不在进行时，值为1
    int rehashidx;

    /*rehashing not in progress if rehashidx==1 */
} dict;

dictType结构，用于对特定类型键值对进行操作：

typedef struct dictType {
    //计算哈希值的函数
    unsigned int(*hashFunction)(const void *key);

    //复制键的函数
    void*(*keyDup)(void* privdata, const void *key);

    //复制值的函数
    void*(*valDup)(void *privdata, const void *obj);

    //对比键的函数
    int(*keyCompare)(void *privdata, const void *key1, const void *key2);

    //销毁键的函数
    void(*keyDestructor)(void *privdata, void *key);

    //销毁值的函数
    void(*valDestructor)(void *privdata, void *obj);

} dictType

哈希表数据结构：

typedef struct dictht {
    //哈希表数组，每个元素都是一个指向`dictEntity`结构的指针
    dictEntry **table;

    //哈希表大小
    unsigned long size;

    //哈希表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;

    //该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dictEntity {

    // 保存键名
    void *key;
    
    // 保存键值，可以是指针或整数。
    union {
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    
    // 指向下个哈希表节点，用于将多个哈希值相同的键值对连接起来
    struct dictEntity *next;
} dictEntity

压缩列表

类似于一个数组，数组中的每一个元素都对应保存一个数据。
压缩列表在表头有三个字段 zlbytes（列表长度）、zltail（列表尾的偏移量） 和 zllen（列表中的 entry 个数）；压缩列表在表尾还有一个 zlend，表示列表结束。

跳跃表

跳跃表（Skip List）是一个有序的数据结构，用于实现有序集合键，以及用于集群节点中的内部数据结构。

跳跃表的数据结构

typedef struct zskiplist{
    //表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    //表中节点的数量（不含表头节点）
    unsigned long length;

    //表中层数最大的节点的层数
    int level;
}zskiplist;

typedef struct zskiplistNode {
     //层
     struct zskiplistLevel{
           //前进指针，用于访问位于表尾方向的其他节点
           struct zskiplistNode *forward;

           //跨度，表示前进指针指向的节点与当前节点的距离
           unsigned int span;
     }level[];
 
     //后退指针，从表尾向表头遍历时使用，指向当前节点的前一个节点
     struct zskiplistNode *backward;

     //分值，即排序值，排序方式为顺序
     double score;

     //成员对象
     robj *obj;
 
} zskiplistNode

整数数组

双向链表

Redis使用了一个哈希表来保存所有键值对

键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，所以高效的数据结构是 Redis 快速处理数据的基础。

哈希表中的哈希桶存放值的指针

哈希桶中的 entry 元素（底层使用字典实现）中保存了*key和*value指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过*value指针被查找到。

哈希表最大的好处是访问速度快

哈希表存在冲突以及rehash问题

往 Redis 中写入大量的数据后，就可能发现操作有时候会突然变慢了。这其实是因为你忽略了一个潜在的风险点，那就是哈希表的冲突问题和 rehash 可能带来的操作阻塞。

哈希冲突

哈希桶的个数通常要少于 key 的数量，这也就是说，难免会有一些 key 的哈希值对应到了同一个哈希桶中。

链式哈希解决冲突

链式哈希指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

通过 rehash 增加哈希桶的数量

Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

配置
中介模式