redis五种数据类型底层结构

原创

ithorizon 1个月前 (10-03) 阅读数 103 #Redis

Redis五种数据类型底层结构

Redis是一个开源的、高性能的键值数据库。它提供了五种数据结构，分别是字符串(String)、列表(List)、集合(Set)、有序集合(Sorted Set)和哈希(Hash)。下面将详细介绍这五种数据类型的底层结构。

1. 字符串(String)

字符串是Redis最基础的数据类型，它可以是单纯的字符串、整数或者浮点数。在Redis中，字符串的底层结构是单纯动态字符串（Simple Dynamic String，简称SDS）。


struct SDS {
    int len;        // 字符串长度
    int free;       // 未使用的空间长度
    char buf[];     // 字符数组，保存字符串内容
};

2. 列表(List)

列表是一种按照插入顺序排序的字符串元素集合。列表的底层结构是双向链表（LinkedList）。


typedef struct listNode {
    struct listNode *prev; // 前一个节点
    struct listNode *next; // 后一个节点
    void *value;           // 节点值
} listNode;
typedef struct list {
    listNode *head;        // 头节点
    listNode *tail;        // 尾节点
    unsigned long len;     // 列表长度
} list;

3. 集合(Set)

集合是无序的、不重复的字符串元素集合。集合的底层结构是哈希表（HashTable）。


typedef struct dict {
    dictType *type;        // 操作函数表
    void *privdata;        // 私有数据
    dictht ht[2];          // 两个哈希表，用于渐进式rehash
    long rehashidx;        // rehash进度
    unsigned long iterators; // 当前正在进行迭代的迭代器数量
} dict;
typedef struct dictht {
    dictEntry **table;     // 哈希表数组
    unsigned long size;    // 哈希表大小
    unsigned long sizemask; // 哈希表掩码
    unsigned long used;    // 已使用桶的数量
} dictht;
typedef struct dictEntry {
    void *key;             // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;                   // 值
    struct dictEntry *next; // 下一个节点
} dictEntry;

4. 有序集合(Sorted Set)

有序集合是集合和列表的结合体，元素具有唯一性，但每个元素都会相关性一个分数（score）。有序集合的底层结构是跳跃表（SkipList）和哈希表。


typedef struct zskiplistNode {
    sds ele;               // 元素
    double score;          // 分数
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span; // 跨度
    } level[];             // 层级数组
} zskiplistNode;
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头节点和尾节点
    unsigned long length;                 // 长度
    int level;                            // 最大层级
} zskiplist;
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;