redis底层存储的数据结构

原创

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

Redis底层存储的数据结构

Redis是一种高性能的键值对存储系统，它提供了多种类型的数据结构来适应不同的需求。了解Redis的底层存储数据结构有助于我们更好地使用它，并优化性能。

1. 易懂动态字符串（SDS）

Redis的字符串数据类型使用易懂动态字符串（Simple Dynamic String，简称SDS）作为底层存储结构。SDS是一种抽象数据类型，它包含以下部分：


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

2. 链表

Redis的列表和发布/订阅等功能使用链表作为底层存储结构。链表是一种常用的数据结构，它由多个节点组成，每个节点包含数据部分和指向下一个节点的指针。


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

3. 字典

Redis的哈希表使用字典作为底层存储结构。字典是一种键值对的集合，它通过哈希表实现迅捷查找。


    typedef struct dict {
        // 类型特定函数
        dictType *type;
        
        // 私有数据
        void *privdata;
        
        // 哈希表
        dictht ht[2];
        
        // rehash索引，当不在进行rehash时，值为-1
        int rehashidx;
    } dict;

4. 跳跃表

Redis的有序集合使用跳跃表作为底层存储结构。跳跃表是一种有序的数据结构，它通过多级索引实现迅捷查找。


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