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

Redis基本数据类型与底层数据结构的关系

简单动态字符串（SDS）

SDS的结构体

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

已使用长度（len）：一个整数，表示SDS当前保存的字符串的长度，不包括结尾的空字符。这个长度属性使得获取字符串长度的时间复杂度为O(1)，即常数时间。
未使用长度（free）：另一个整数，表示SDS在buf数组中尚未使用的空间长度。这个属性用于空间预分配和惰性空间释放，以减少频繁的内存重分配。
字符数组（buf）：一个灵活的字符数组，用于实际存储字符串的内容。这个数组的大小是已使用长度和未使用长度之和，加上一个额外的字节来存储结尾的空字符。

SDS的优点

常数时间复杂度获取长度：由于SDS结构体中直接保存了字符串的长度，因此获取长度的时间复杂度为O(1)，而C语言字符串需要遍历整个字符串直到遇到空字符才能确定长度。
预防缓冲区溢出：SDS在修改字符串时会检查剩余空间，如果空间不足则会自动进行内存重分配，从而避免了缓冲区溢出的风险。
减少内存重分配次数：SDS通过空间预分配和惰性空间释放策略来优化内存分配。当SDS修改字符串时，它会检查未使用长度是否足够，如果足够则直接使用现有空间，避免不必要的内存分配和释放。
二进制安全：SDS能够保存任意二进制数据，包括空字符和不可打印字符，这使得它非常适合用于存储图像、音频、视频等二进制文件。
兼容C字符串函数：虽然SDS有自己的操作函数，但它仍然兼容一部分C语言的标准字符串处理函数，因为这些函数通常期望字符串以空字符结尾。

SDS在Redis中的作用

统一字符串表示：Redis使用SDS作为统一的字符串表示形式，无论是键值对中的值、列表元素、集合成员还是哈希表的键值对，都使用SDS来存储。这简化了字符串的处理逻辑，并确保了字符串操作的一致性和安全性。
优化性能：通过常数时间复杂度获取长度、预防缓冲区溢出以及减少内存重分配次数等优化措施，SDS显著提高了Redis在处理字符串时的性能。
支持二进制数据：SDS的二进制安全特性使得Redis能够存储和处理各种类型的数据，包括非文本数据，从而扩大了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;

双向链表由一系列的节点组成，每个节点都包含数据和指向前后节点的指针。在Redis中，双向链表的结构体设计通常包含以下几个关键部分：

数据域：用于存储节点的实际数据。这可以是一个简单的值，也可以是一个更复杂的数据结构，取决于双向链表的具体用途。
前驱指针（prev）：指向链表中的前一个节点。这使得从当前节点可以方便地访问前一个节点，实现链表的逆序遍历。
后继指针（next）：指向链表中的下一个节点。这使得从当前节点可以方便地访问下一个节点，实现链表的顺序遍历。

此外，Redis的双向链表可能还包含一些额外的字段，如指向链表头尾节点的指针、链表长度计数器等，以支持更高效的操作和管理。

双向链表的特点

高效的节点插入和删除：由于每个节点都保存了前驱和后继节点的指针，因此在双向链表中插入或删除节点时，只需要更新相邻节点的指针，而不需要移动大量数据。这使得双向链表在节点操作上具有较高的效率。
顺序和逆序访问能力：双向链表支持从头节点到尾节点的顺序访问，也支持从尾节点到头节点的逆序访问。这种双向访问能力使得在处理需要遍历链表的操作时非常灵活。
动态内存管理：双向链表采用动态内存分配的方式，根据实际需要创建和销毁节点。这使得双向链表能够根据实际数据的增长或减少来调整内存使用，避免了固定大小数组可能出现的内存浪费或不足的问题。

双向链表在Redis中的作用

实现列表类型：Redis的列表类型底层使用双向链表作为数据结构。这使得Redis能够高效地处理与列表相关的命令，如lpush、rpush（在列表头部或尾部插入元素）、lpop、rpop（从列表头部或尾部移除元素）等。双向链表的双向访问能力使得这些操作能够在常数时间内完成。
支持范围查询：由于双向链表支持顺序和逆序访问，Redis可以很容易地实现范围查询操作，如获取列表的某个子区间内的元素。
灵活性和扩展性：双向链表作为一种通用的数据结构，具有很高的灵活性和扩展性。Redis可以利用双向链表来实现更复杂的数据结构或算法，以满足不同应用场景的需求。

压缩列表

压缩列表的结构体

typedef struct ziplistEntry {  
    unsigned int prevrawlensize;  // 前一个节点长度所占的字节数  
    unsigned int prevrawlen;      // 前一个节点的长度  
    unsigned int lensize;         // 当前节点值长度所占的字节数  
    unsigned int len;             // 当前节点值的长度  
    unsigned char header[];       // 头部信息，包含编码等  
    unsigned char entry[];        // 节点值  
} ziplistEntry;  
  
typedef struct ziplist {  
    uint32_t zlen;                // 压缩列表的元素数量  
    uint32_t ztail_offset;      // 指向压缩列表最后一个元素的偏移量  
    uint16_t zhead;             // 指向压缩列表第一个元素的起始位置  
    unsigned char entries[];    // 压缩列表的节点数组  
} ziplist;

压缩列表的特点

节省内存：压缩列表通过一系列连续的entry保存数据，而不是为每个元素分配独立的内存块，从而减少了内存碎片，并提高了内存利用率。此外，压缩列表还使用特定的编码方式来存储数据，如小整数使用固定长度的字节表示，这进一步减少了空间占用。
顺序型数据结构：压缩列表保持了数据的顺序性，使得在遍历列表时能够按顺序访问每个元素。
高效的插入和删除：由于压缩列表是连续的内存空间，插入和删除操作相对高效，不需要进行大量的内存分配和释放。

压缩列表的作用

优化内存使用：对于存储大量小字符串或整数的场景，压缩列表能够显著减少内存使用，提高Redis的内存利用率。这在处理大量小数据时尤为重要，有助于降低存储成本和提高性能。
支持小列表的高效操作：对于长度较短的列表，使用压缩列表可以避免普通链表结构带来的额外内存开销。同时，由于压缩列表是顺序型数据结构，它支持高效的顺序访问和范围查询操作。
适应不同数据类型：Redis的列表（List）、哈希（Hash）和有序集合（Sorted Set）在元素个数较少且元素长度较短时，可能会使用压缩列表作为底层数据结构。这种灵活性使得Redis能够根据不同数据的特点选择最合适的存储方式。

哈希表

Redis底层数据结构中的哈希表是其实现键值对存储的核心组件。哈希表通过哈希函数将键映射到数组的某个位置，从而实现了快速的键值查找和存储。下面将详细讲解Redis哈希表的源码、结构体、特点以及作用。

哈希表的源码与结构体

typedef struct dict {  
    dictType *type;             // 类型特定函数  
    void *privData;            // 私有数据  
    dictht ht[2];              // 哈希表数组，通常只使用ht[0]，ht[1]用于rehash  
    long rehashidx;            // rehash的进度，-1表示没有进行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;

哈希表的特点

动态扩展与收缩：当哈希表中元素数量过多或过少时，Redis会进行扩展或收缩操作，以维持一个合理的负载因子，保证查找效率。
渐进式rehash：为了避免一次性rehash导致的性能开销，Redis采用渐进式rehash策略。在rehash过程中，每次对哈希表的操作都会带动一部分键值对迁移到新的哈希表中，直至全部完成。
链地址法解决冲突：当两个或多个键的哈希值相同时，Redis采用链地址法（开放寻址法的变种）来解决冲突。具有相同哈希值的节点通过next指针链接成一个链表。
自定义哈希函数与类型特定函数：Redis允许用户为不同类型的键定义自己的哈希函数和类型特定函数，这使得Redis能够灵活地支持多种数据类型。

哈希表的作用

快速存储与查找：哈希表为Redis提供了O(1)平均时间复杂度的键值存储和查找功能，使得Redis在处理大量数据时能够保持高效的性能。
支持丰富的数据类型：由于哈希表可以存储任意类型的键值对，并且允许自定义哈希函数和类型特定函数，Redis能够支持字符串、哈希、列表、集合、有序集合等多种数据类型。
实现高级功能：哈希表作为Redis底层数据结构之一，为实现诸如事务、Lua脚本、发布订阅等高级功能提供了基础支持。

总的来说，Redis的哈希表源码设计精巧、高效且灵活，为Redis提供了强大的键值存储和查找功能，是Redis高性能表现的重要保证之一。

跳表

Redis底层数据结构中的跳表（Skip List）是一种用于实现有序集合和有序哈希的数据结构。跳表是一种动态数据结构，它通过构建多层索引来加速查找操作。下面将详细讲解Redis中跳表的源码、结构体、特点以及作用。

跳表的源码与结构体


typedef struct zskiplist {  
    struct zskiplistNode *header, *tail; // 跳表的头尾节点  
    unsigned long length;                 // 跳表中元素的数量  
    int level;                            // 跳表当前的最大层数  
} zskiplist;

typedef struct zskiplistNode {  
    struct zskiplistNode *forward[1]; // 前进指针数组，每个层级有一个指针  
    struct zskiplistNode *backward;   // 后退指针  
    double score;                     // 排序分数  
    robj *obj;                       // 节点保存的对象  
    int level;                       // 节点所在的层级  
} zskiplistNode;

forward数组用于存储指向下一层级的节点的指针。注意这里forward数组是一个变长数组，在结构体中通常只定义一个指针，实际使用时根据节点的层级动态分配空间。
backward指针用于从后向前遍历跳表。
score用于存储排序分数
obj是节点保存的实际对象。
level表示节点所在的层级。

跳表的特点

有序性：跳表中的所有元素都是按照score字段的大小进行有序存储的，这使得跳表可以支持范围查找操作。
动态性：跳表在插入、删除元素时，会动态地调整节点的层级，以保持跳表的平衡性。
空间效率：跳表通过多层索引来加速查找，但相比平衡树（如红黑树）来说，跳表在实现上更为简单，空间效率也更高。
支持快速查找：由于跳表的多层索引结构，使得在查找某个元素时，可以从最高层开始逐级向下查找，从而减少了查找次数。

跳表的作用

实现有序集合：Redis中的有序集合（Sorted Set）就是通过跳表实现的。跳表能够保持元素的顺序性，并支持快速的插入、删除和查找操作。
支持范围查找：由于跳表是有序的，因此可以很容易地实现范围查找功能，比如查找分数在某个区间内的所有元素。
与哈希表配合使用：在Redis的有序集合实现中，除了跳表外，还使用了哈希表。哈希表用于快速定位元素的位置，而跳表则用于维护元素的顺序性。这种组合使得有序集合在保持元素顺序的同时，也能保持高效的查找性能。

总的来说，Redis中的跳表是一种高效、有序且动态的数据结构，它为Redis的有序集合提供了强大的支持，使得Redis能够高效地处理有序数据的存储和查找操作。

整数数组

在 Redis 中，Set 数据类型并不是直接基于整数数组实现的。Redis 的 Set 数据类型实际上是通过哈希表（Hash Table）来实现的，这提供了高效的元素插入、删除和查找操作。哈希表在 Redis 中是一个核心的数据结构，用于实现多种数据类型。
然而，当 Set 中的元素全部为整数，并且元素数量较少时，Redis 会使用一种特殊的内部编码来优化存储和性能，这就是整数集合（Intset）。整数集合是 Redis 中用于存储整数值的紧凑数据结构，它确实在某些情况下使用了类似于数组的结构来存储整数。

整数集合的结构体

typedef struct intset {  
    uint32_t encoding;     // 编码方式：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64  
    uint32_t length;       // 集合包含的元素数量  
    int8_t contents[];     // 柔性数组，用于存储整数  
} intset;

encoding：表示整数集合中整数的编码方式，可以是16位、32位或64位整数。Redis 根据集合中整数的实际大小和数量来选择合适的编码方式，以节省空间。
length：整数集合中存储的整数数量。
contents：这是一个柔性数组（也称为可变长数组），用于存储实际的整数。柔性数组是 C99 标准中引入的特性，允许在结构体中定义一个没有大小的数组，数组的大小由结构体分配的总空间决定。

特点

空间优化：整数集合通过紧凑存储和选择合适的编码方式来节省空间。当所有整数都可以使用较小位数的编码来表示时，Redis 会选择更小的编码方式。
内存连续：整数集合中的整数在内存中连续存储，这有助于减少内存碎片并提高缓存效率。
高效操作：由于整数集合在内存中连续存储，因此插入、删除和查找操作的时间复杂度都是 O(1) 或 O(n)，其中 n 是集合中元素的数量。

作用

存储整数集合：当 Redis 的 Set 数据类型只包含整数元素，并且元素数量较少时，整数集合提供了一种高效的存储方式。
性能优化：通过选择适当的编码方式和紧凑的存储结构，整数集合能够减少内存占用并提高操作效率，这对于大量小整数集合的场景特别有用。
内部实现细节：整数集合是 Redis 内部实现的一部分，用于优化特定情况下的存储和性能。Redis 的其他数据类型和内部机制也可能使用整数集合来存储整数值。

当 Set 中的整数数量增多或整数的大小超出当前编码方式的范围时，Redis 会将整数集合转换为哈希表来存储，以支持更多的元素和更大的整数。这种转换是自动进行的，无需用户干预。