Redis的六种底层数据结构是什么

目录

1. 引言
2. 简单动态字符串（SDS）
   • 2.1 SDS的结构
   • 2.2 SDS的优势
   • 2.3 SDS的应用场景
3. 链表（Linked List）
   • 3.1 链表的结构
   • 3.2 链表的优势
   • 3.3 链表的应用场景
4. 字典（Dictionary）
   • 4.1 字典的结构
   • 4.2 字典的优势
   • 4.3 字典的应用场景
5. 跳跃表（Skip List）
   • 5.1 跳跃表的结构
   • 5.2 跳跃表的优势
   • 5.3 跳跃表的应用场景
6. 整数集合（IntSet）
   • 6.1 整数集合的结构
   • 6.2 整数集合的优势
   • 6.3 整数集合的应用场景
7. 压缩列表（ZipList）
   • 7.1 压缩列表的结构
   • 7.2 压缩列表的优势
   • 7.3 压缩列表的应用场景
8. 总结

引言

Redis（Remote Dictionary Server）是一个开源的高性能键值存储系统，广泛应用于缓存、消息队列、排行榜等场景。Redis之所以能够提供如此高效的性能，很大程度上得益于其底层数据结构的精心设计。本文将详细介绍Redis的六种底层数据结构：简单动态字符串（SDS）、链表（Linked List）、字典（Dictionary）、跳跃表（Skip List）、整数集合（IntSet）和压缩列表（ZipList）。通过对这些数据结构的深入理解，我们可以更好地掌握Redis的工作原理，并优化其在实际应用中的使用。

简单动态字符串（SDS）

2.1 SDS的结构

简单动态字符串（Simple Dynamic String，SDS）是Redis中用于存储字符串数据的基本数据结构。与C语言中的原生字符串不同，SDS在C字符串的基础上进行了扩展，提供了更多的功能和更高的性能。

SDS的结构定义如下：

struct sdshdr {
    int len;        // 字符串的长度
    int free;       // 未使用的空间
    char buf[];     // 字符串的实际内容
};

• len：表示字符串的实际长度。
• free：表示字符串中未使用的空间。
• buf：存储字符串的实际内容。

2.2 SDS的优势

SDS相较于C语言的原生字符串具有以下优势：

1. O(1)时间复杂度获取字符串长度：C语言中的字符串需要通过遍历整个字符串来计算长度，时间复杂度为O(n)。而SDS通过len字段直接记录字符串的长度，时间复杂度为O(1)。

2. 避免缓冲区溢出：C语言中的字符串操作容易导致缓冲区溢出，而SDS在进行字符串操作时会自动检查空间是否足够，并在必要时进行扩展。

3. 减少内存重分配次数：SDS通过free字段记录未使用的空间，可以在字符串增长时减少内存重分配的次数，从而提高性能。

4. 二进制安全：SDS可以存储任意二进制数据，而C语言中的字符串以\0结尾，无法存储包含\0的数据。

2.3 SDS的应用场景

SDS广泛应用于Redis中的字符串类型数据存储，如键值对的键和值、列表的元素等。由于其高效的性能和灵活的特性，SDS成为了Redis中最基础的数据结构之一。

链表（Linked List）

3.1 链表的结构

链表（Linked List）是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;

• listNode：链表的节点，包含指向前后节点的指针和节点的值。
• list：链表的结构，包含头节点、尾节点、长度以及一些操作函数。

3.2 链表的优势

链表相较于数组具有以下优势：

1. 动态扩展：链表可以动态地增加或删除节点，不需要预先分配固定大小的内存空间。

2. 插入和删除操作高效：在链表中插入或删除节点的时间复杂度为O(1)，而数组中的插入和删除操作需要移动元素，时间复杂度为O(n)。

3. 灵活的内存管理：链表中的节点可以分散在内存中的不同位置，不需要连续的内存空间。

3.3 链表的应用场景

链表广泛应用于Redis中的列表类型数据存储，如列表键、发布/订阅系统中的消息队列等。由于其高效的插入和删除操作，链表在处理动态数据时表现出色。

字典（Dictionary）

4.1 字典的结构

字典（Dictionary）是Redis中用于存储键值对数据的基本数据结构。Redis中的字典是一个哈希表，通过哈希函数将键映射到哈希表中的索引位置。

字典的结构定义如下：

typedef struct dictEntry {
    void *key;              // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;                    // 值
    struct dictEntry *next; // 指向下一个节点的指针
} dictEntry;

typedef struct dictht {
    dictEntry **table;      // 哈希表数组
    unsigned long size;     // 哈希表的大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used;     // 哈希表中已使用的节点数
} dictht;

typedef struct dict {
    dictType *type;         // 字典类型
    void *privdata;         // 私有数据
    dictht ht[2];           // 哈希表数组
    long rehashidx;         // 重哈希索引
    unsigned long iterators; // 当前正在运行的迭代器数量
} dict;

• dictEntry：字典的节点，包含键、值和指向下一个节点的指针。
• dictht：哈希表，包含哈希表数组、大小、掩码和已使用的节点数。
• dict：字典的结构，包含字典类型、私有数据、哈希表数组、重哈希索引和迭代器数量。

4.2 字典的优势

字典相较于其他数据结构具有以下优势：

1. 高效的查找操作：通过哈希函数将键映射到哈希表中的索引位置，查找操作的时间复杂度为O(1)。

2. 动态扩展：字典可以根据需要动态扩展哈希表的大小，避免哈希冲突导致的性能下降。

3. 灵活的键值对存储：字典可以存储任意类型的键和值，适用于各种场景。

4.3 字典的应用场景

字典广泛应用于Redis中的键值对数据存储，如哈希表键、集合键等。由于其高效的查找操作和灵活的键值对存储，字典成为了Redis中最常用的数据结构之一。

跳跃表（Skip List）

5.1 跳跃表的结构

跳跃表（Skip List）是Redis中用于存储有序集合数据的基本数据结构。跳跃表是一种概率平衡的数据结构，通过多层链表实现高效的查找、插入和删除操作。

跳跃表的结构定义如下：

typedef struct zskiplistNode {
    sds ele;                        // 元素值
    double score;                   // 分数
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span;           // 跨度
    } level[];                      // 层级数组
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头节点和尾节点
    unsigned long length;               // 跳跃表的长度
    int level;                          // 跳跃表的层级
} zskiplist;

• zskiplistNode：跳跃表的节点，包含元素值、分数、后退指针和层级数组。
• zskiplist：跳跃表的结构，包含头节点、尾节点、长度和层级。

5.2 跳跃表的优势

跳跃表相较于其他有序数据结构具有以下优势：

1. 高效的查找操作：通过多层链表实现快速查找，时间复杂度为O(log n)。

2. 动态扩展：跳跃表可以根据需要动态调整层级，保持高效的查找性能。

3. 简单的实现：跳跃表的实现相对简单，易于理解和维护。

5.3 跳跃表的应用场景

跳跃表广泛应用于Redis中的有序集合数据存储，如有序集合键、排行榜等。由于其高效的查找操作和动态扩展能力，跳跃表在处理有序数据时表现出色。

整数集合（IntSet）

6.1 整数集合的结构

整数集合（IntSet）是Redis中用于存储整数类型数据的基本数据结构。整数集合是一个有序的整数数组，支持高效的查找、插入和删除操作。

整数集合的结构定义如下：

typedef struct intset {
    uint32_t encoding;  // 编码方式
    uint32_t length;    // 集合的长度
    int8_t contents[];  // 集合的内容
} intset;

• encoding：表示整数集合的编码方式，可以是INTSET_ENC_INT16、INTSET_ENC_INT32或INTSET_ENC_INT64。
• length：表示整数集合的长度。
• contents：存储整数集合的实际内容。

6.2 整数集合的优势

整数集合相较于其他数据结构具有以下优势：

1. 高效的查找操作：通过二分查找实现快速查找，时间复杂度为O(log n)。

2. 内存紧凑：整数集合使用紧凑的内存布局，节省内存空间。

3. 动态扩展：整数集合可以根据需要动态调整编码方式，支持不同范围的整数。

6.3 整数集合的应用场景

整数集合广泛应用于Redis中的整数类型数据存储，如集合键中的整数元素等。由于其高效的查找操作和紧凑的内存布局，整数集合在处理整数数据时表现出色。

压缩列表（ZipList）

7.1 压缩列表的结构

压缩列表（ZipList）是Redis中用于存储小型列表和哈希表数据的基本数据结构。压缩列表是一种紧凑的内存布局，通过连续的内存块存储多个元素。

压缩列表的结构定义如下：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

• zlbytes：表示压缩列表的总字节数。
• zltail：表示压缩列表的尾节点偏移量。
• zllen：表示压缩列表的元素个数。
• entry：表示压缩列表的元素，包含前一个元素的长度、当前元素的编码和内容。
• zlend：表示压缩列表的结束标志。

7.2 压缩列表的优势

压缩列表相较于其他数据结构具有以下优势：

1. 内存紧凑：压缩列表使用连续的内存块存储多个元素，节省内存空间。

2. 高效的插入和删除操作：压缩列表支持在任意位置插入和删除元素，时间复杂度为O(n)。

3. 灵活的存储：压缩列表可以存储不同类型的数据，如整数、字符串等。

7.3 压缩列表的应用场景

压缩列表广泛应用于Redis中的小型列表和哈希表数据存储，如列表键、哈希表键等。由于其紧凑的内存布局和高效的插入删除操作，压缩列表在处理小型数据时表现出色。

总结

Redis的六种底层数据结构——简单动态字符串（SDS）、链表（Linked List）、字典（Dictionary）、跳跃表（Skip List）、整数集合（IntSet）和压缩列表（ZipList）——各自具有独特的优势和适用场景。通过对这些数据结构的深入理解，我们可以更好地掌握Redis的工作原理，并优化其在实际应用中的使用。无论是高效的查找操作、动态扩展能力，还是紧凑的内存布局，这些数据结构都为Redis的高性能提供了坚实的基础。在实际开发中，根据具体需求选择合适的数据结构，可以显著提升系统的性能和稳定性。