redis五种基本数据类型底层实现

原创

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

Redis五种基本数据类型底层实现

Redis是一个开源的，高性能的键值对存储数据库。它提供了五种基本的数据结构类型，分别是字符串（String），列表（List），集合（Set），哈希（Hash）和有序集合（Sorted Set）。以下是这五种数据类型的底层实现原理。

1. 字符串（String）

字符串是Redis最基础的数据类型，通常用于缓存一些简洁的数据。其底层实现采用了SDS（Simple Dynamic String）结构，是Redis自定义的一种数据类型，提供了二进制可靠的字符串存储。


struct sdshdr {
    // 记录buf数组中已使用的字节数量
    int len;
    // 记录buf数组中剩余未使用的字节数量
    int free;
    // 字节数组，用于存储实际的字符串内容
    char buf[];
};

2. 列表（List）

列表是一种按照插入顺序排序的字符串元素集合。它的底层实现采用了双向链表和压缩列表（ziplist）两种数据结构。当列表元素数量较少且元素大小较小时，使用压缩列表存储；当列表元素数量较多或元素大小超过阈值时，使用双向链表存储。


// 双向链表节点
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;
// 压缩列表结构体
typedef struct ziplist {
    // 压缩列表的尾节点
    zlentry tail;
    // 压缩列表的长度
    unsigned int length;
    // 压缩列表的字节大小
    unsigned int size;
    // 压缩列表中的元素数组
    unsigned char[] entries;
} ziplist;

3. 集合（Set）

集合是一种无序的元素集合，其底层实现采用了哈希表和整数集合（intset）两种数据结构。当集合元素都是整数且数量较少时，使用整数集合存储；当集合元素不是整数或数量超过阈值时，使用哈希表存储。


// 哈希表节点
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;
// 整数集合结构体
typedef struct intset {
    // 编码行为
    uint32_t encoding;
    // 集合中元素的个数
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

4. 哈希（Hash）

哈希是一个键值对的集合，其底层实现采用了压缩列表和哈希表两种数据结构。当哈希元素数量较少且大小较小时，使用压缩列表存储；当哈希元素数量较多或大小超过阈值时，使用哈希表存储。


// 哈希表结构体（与集合中的哈希表结构相同）
typedef struct dict {
    // 哈希表的类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表节点数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    unsigned long sizemask;
    // 已使用的节点数量
    unsigned long used;
} dict;
// 压缩列表结构体（与列表中的压缩列表结构相同）
typedef struct ziplist {
    // 压缩列表的尾节点
    zlentry tail;
    // 压缩列表的长度
    unsigned int length;
    // 压缩列表的字节大小
    unsigned int size;
    // 压缩列表中的元素数组
    unsigned char[] entries;
} ziplist;