redis五种数据类型的底层数据结构

Redis五种数据类型的底层数据结构

Redis 是一款开源的高性能键值数据库。它提供了五种数据结构，分别是字符串（String）、列表（List）、集合（Set）、有序集合（ZSet）和哈希（Hash）。下面我们来分析这五种数据类型的底层数据结构。

1. 字符串（String）

字符串是Redis中最基本的数据类型，它可以是任何形式的文本数据。在Redis中，字符串数据类型的底层数据结构是明了动态字符串（Simple Dynamic Strings，简称SDS）。

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

2. 列表（List）

列表是Redis提供的另一种数据类型，它可以存储一系列有序的字符串。列表数据类型的底层数据结构是双向链表（LinkedList）或压缩列表（ziplist）。

    // 双向链表节点结构
    typedef struct listNode {
        // 前置节点
        struct listNode *prev;
        // 后置节点
        struct listNode *next;
        // 节点值
        void *value;
    } listNode;
    
    // 压缩列表结构
    struct zlentry {
        // 前一个节点的长度
        unsigned int prevlen;
        // 当前节点的长度
        unsigned int len;
        // 节点数据
        unsigned char data[];
    };
    

3. 集合（Set）

集合是一种无序的数据类型，其中的每个元素都是唯一的。集合数据类型的底层数据结构是哈希表（HashTable）或整数集合（intset）。

    // 哈希表结构
    typedef struct dict {
        // 类型特定函数
        dictType *type;
        // 私有数据
        void *privdata;
        // 哈希表数组
        dictht ht[2];
        // rehash索引，当rehash不进行时，值为-1
        long rehashidx;
    } dict;
    
    // 整数集合结构
    typedef struct intset {
        // 编码方案
        uint32_t encoding;
        // 集合包含的元素数量
        uint32_t length;
        // 保存元素的数组
        int8_t contents[];
    } intset;
    

4. 有序集合（ZSet）

有序集合是Redis中一种特殊的数据类型，它类似于集合，但每个元素都会相关性一个分数。有序集合的底层数据结构是跳跃表（SkipList）和哈希表。

    // 跳跃表结构
    typedef struct zskiplist {
        // 头节点和尾节点
        struct zskiplistNode *header, *tail;
        // 节点数量
        unsigned long length;
    } zskiplist;
    
    // 跳跃表节点结构
    typedef struct zskiplistNode {
        // 成员对象
        robj *obj;
        // 分数值
        double score;
        // 后退指针
        struct zskiplistNode *backward;
        // 层
        struct zskiplistLevel {
            // 前进指针
            struct zskiplistNode *forward;
            // 跨度
            unsigned int span;
        } level[];
    } zskiplistNode;
    

5. 哈希（Hash）

哈希是Redis中用于存储键值对的数据类型。哈希数据类型的底层数据结构可以是压缩列表（ziplist）或哈希表（HashTable）。

    // 哈希表结构（同集合）
    typedef struct dict {
        // 类型特定函数
        dictType *type;
        // 私有数据
        void *privdata;
        // 哈希
本文由IT视界版权所有,禁止未经同意的情况下转发