redis五种数据结构底层

Redis五种数据结构底层原理

Redis是一种开源的、高性能的、基于键值对的缓存和存储系统。它拥护多种类型的数据结构，包括字符串、列表、集合、散列表和有序集合。以下是这五种数据结构底层的原理分析。

1. 字符串（String）

字符串是Redis中最基本的数据结构。在底层，Redis使用SDS（明了动态字符串）来即字符串。SDS是一个长度可变的字节数组，其结构如下：

    struct SDS {
        int len; // 字符串长度
        int free; // 剩余空间
        char buf[]; // 实际数据
    };
    

2. 列表（List）

列表是按照插入顺序排序的字符串元素集合。Redis列表的底层实现有两种：压缩列表（ziplist）和双向链表（linkedlist）。

当列表元素数量较少且元素长度较小（默认配置是元素数量小于512且元素长度小于64字节）时，Redis使用压缩列表作为底层实现。压缩列表可以节省内存空间，尽大概缩减损耗存储快速。

当列表元素数量较多或元素长度较大时，Redis使用双向链表作为底层实现。双向链表结构如下：

    typedef struct listNode {
        struct listNode *prev; // 前一个节点
        struct listNode *next; // 后一个节点
        void *value; // 节点值
    } listNode;
    

3. 集合（Set）

集合是无序的、不重复的字符串元素集合。Redis集合的底层实现有三种：整数集合（intset）、压缩列表（ziplist）和哈希表（hashtable）。

当集合元素都是整数且元素数量较少（默认配置是元素数量小于512）时，Redis使用整数集协作为底层实现。整数集合可以节省内存空间。

当集合元素数量较少且元素长度较小（默认配置是元素数量小于512且元素长度小于64字节）时，Redis使用压缩列表作为底层实现。

当集合元素数量较多或元素长度较大时，Redis使用哈希表作为底层实现。哈希表结构如下：

    typedef struct dict {
        dictType *type; // 类型特定函数
        void *privdata; // 私有数据
        dictht ht[2]; // 两个哈希表
        long rehashidx; // rehash索引
    } dict;
    

4. 散列表（Hash）

散列表是字段和字段值的映射表，字段和字段值都是字符串。Redis散列表的底层实现有两种：压缩列表（ziplist）和哈希表（hashtable）。

当散列表的元素数量较少且元素长度较小（默认配置是元素数量小于512且元素长度小于64字节）时，Redis使用压缩列表作为底层实现。

当散列表的元素数量较多或元素长度较大时，Redis使用哈希表作为底层实现。哈希表结构如上所述。

5. 有序集合（ZSet）

有序集合是元素带分数的集合，元素按照分数从小到大排序。Redis有序集合的底层实现有两种：压缩列表（ziplist）和跳表（skiplist）。

当有序集合的元素数量较少且元素长度较小（默认配置是元素数量小于128且元素长度小于64字节）时，Redis使用压缩列表作为底层实现。

当有序集合的元素数量较多或元素长度较大时，Redis使用跳表作为底层实现。跳表结构如下：

    typedef struct zskiplistNode {
        robj *obj; // 成员对象
        double score; // 分数
        struct zskiplistNode *backward; // 后退指针
        struct zskiplistLevel {
            struct zskiplistNode *forward; // 前进指针
            unsigned int span; // 跨度
        } level
本文由IT视界版权所有,禁止未经同意的情况下转发