对比 Redis 链表与其他数据结构的内存占用

Redis 链表基础

Redis 链表是一种双向链表结构，在 Redis 中主要用于实现列表对象（当列表对象包含的元素数量较多或者元素都是比较长的字符串时）以及发布订阅、慢查询、监视器等功能。

从结构上来说，Redis 链表由 listNode 节点组成，每个 listNode 包含三个部分：前驱节点指针 prev、后继节点指针 next 以及节点的值 value。

// 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;

在这个结构中，list 结构体用于管理整个链表，包含链表头 head、链表尾 tail、链表长度 len 以及三个函数指针，分别用于节点值的复制 dup、节点值的释放 free 和节点值的比较 match。

Redis 链表的操作与特点

Redis 链表支持在链表头、链表尾进行节点的插入和删除操作。例如，在链表头插入节点的操作：

list *listAddNodeHead(list *list, void *value) {
    listNode *node = zmalloc(sizeof(*node));
    if (!node) return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->next = list->head;
        node->prev = NULL;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}

Redis 链表的特点在于其双向性，这使得可以在 O(1) 的时间复杂度内完成在链表头和链表尾的插入和删除操作，并且可以双向遍历链表。但是，由于每个节点都需要额外存储前驱和后继节点的指针，这在一定程度上增加了内存的开销。

与数组的数据结构内存占用对比

数组的数据结构基础

数组是一种线性数据结构，它在内存中是连续存储的。在 C 语言中，定义一个简单的整数数组如下：

int arr[5] = {1, 2, 3, 4, 5};

数组的优点在于可以通过下标直接访问元素，时间复杂度为 O(1)。例如，访问数组中的第三个元素 arr[2] 可以直接定位到内存中的相应位置。

内存占用对比分析

数组的内存占用：数组的内存占用主要取决于数组元素的类型和数组的长度。以一个存储 int 类型元素的数组为例，在 32 位系统下，int 类型通常占用 4 个字节。如果数组长度为 n，那么数组的内存占用大小为 4 * n 字节（不考虑数组名等额外的元数据开销）。例如，一个长度为 10 的 int 数组，其内存占用为 4 * 10 = 40 字节。
Redis 链表的内存占用：Redis 链表每个节点除了存储节点值外，还需要存储前驱和后继节点的指针。在 32 位系统下，指针通常占用 4 个字节。假设链表节点的值也是 int 类型，每个节点的内存占用为 4（值） + 4（前驱指针） + 4（后继指针） = 12 字节。如果链表长度为 n，再加上 list 结构体本身占用的内存（假设为 24 字节，包含头指针、尾指针、长度等信息），那么链表的总内存占用约为 12 * n + 24 字节。

例如，当存储 10 个 int 类型的数据时，数组的内存占用为 40 字节，而 Redis 链表的内存占用约为 12 * 10 + 24 = 144 字节。可以看出，在存储相同数量的简单数据类型时，Redis 链表由于节点结构的额外开销，内存占用明显大于数组。

与哈希表的数据结构内存占用对比

哈希表的数据结构基础

哈希表是一种以键值对形式存储数据的数据结构，它通过哈希函数将键映射到一个哈希值，然后根据哈希值找到对应的存储位置。在 Redis 中，哈希表主要用于实现哈希对象。

Redis 的哈希表由 dict 结构体和 dictht 哈希表结构组成。dict 结构体包含两个 dictht 哈希表（一个用于正常使用，另一个用于 rehash 操作）以及一些其他的元数据。dictht 哈希表包含一个数组 table，数组的每个元素是一个 dictEntry 节点，dictEntry 节点存储了键值对以及指向下一个节点的指针（用于解决哈希冲突）。

// 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; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

内存占用对比分析

哈希表的内存占用：哈希表的内存占用包括 dict 结构体、dictht 哈希表结构以及 dictEntry 节点的内存占用。dict 结构体本身占用一定的内存（假设为 32 字节），dictht 哈希表的 table 数组占用的内存取决于哈希表的大小 size，每个 dictEntry 节点占用的内存取决于键值对的大小以及指针的大小。假设键和值都是 int 类型，在 32 位系统下，每个 dictEntry 节点占用 4（键） + 4（值） + 4（下一个节点指针） = 12 字节。如果哈希表大小为 n（假设没有哈希冲突，且 size 刚好等于 n），那么哈希表的总内存占用约为 32 + n * 12 字节（不考虑 sizemask 和 used 等元数据占用的少量内存）。
Redis 链表的内存占用：如前文所述，当链表长度为 n，假设节点值为 int 类型时，链表的内存占用约为 12 * n + 24 字节。

当存储相同数量 n 的键值对（假设键值对都是 int 类型）时，哈希表的内存占用主要受哈希表大小和节点结构影响，链表的内存占用受节点数量和节点结构影响。在没有哈希冲突的理想情况下，两者的内存占用公式较为接近，但实际应用中哈希表可能会因为负载因子等因素进行扩容，导致额外的内存开销。而链表则相对稳定，不会因为元素数量变化而进行大规模的内存重新分配，除非手动调整链表结构。

与跳跃表的数据结构内存占用对比

跳跃表的数据结构基础

跳跃表是一种随机化的数据结构，它在链表的基础上增加了多层索引，以提高查找效率。Redis 中的有序集合（sorted set）就是通过跳跃表和哈希表共同实现的。

Redis 的跳跃表由 zskiplist 和 zskiplistNode 组成。zskiplist 结构体包含跳跃表的头节点、尾节点、节点数量以及最大层数等信息。zskiplistNode 节点除了存储元素值和分数外，还包含一个 level 数组，用于存储不同层的后继节点指针。

// Redis 跳跃表节点
typedef struct zskiplistNode {
    sds ele;
    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;

内存占用对比分析

跳跃表的内存占用：跳跃表的内存占用较为复杂，zskiplist 结构体本身占用一定内存（假设为 24 字节）。每个 zskiplistNode 节点除了存储元素值 ele（假设为字符串类型，占用的内存大小取决于字符串长度）和分数 score（8 字节，double 类型）外，还需要存储前驱节点指针 backward（4 字节）以及 level 数组。level 数组的大小取决于节点的层数，节点层数是随机生成的，平均层数约为 logN（N 为跳跃表节点数量）。假设平均每个节点的层数为 3 层，每层的后继节点指针占用 4 字节，再加上 span 占用 4 字节，那么每个节点除了元素值外占用的内存约为 8（score） + 4（backward） + 3 * （4（forward） + 4（span）） = 32 字节。如果存储 n 个节点，跳跃表的总内存占用除了 zskiplist 结构体的 24 字节外，还需要加上所有节点的内存占用，假设每个元素值平均占用 10 字节，那么总内存占用约为 24 + n * （32 + 10） 字节。
Redis 链表的内存占用：对于长度为 n 的 Redis 链表，假设节点值为字符串类型，平均长度也为 10 字节，每个节点占用 10（值） + 4（前驱指针） + 4（后继指针） = 18 字节，再加上 list 结构体的 24 字节，总内存占用约为 24 + n * 18 字节。

对比可以发现，跳跃表由于多层索引结构，每个节点的内存开销相对较大，尤其是在节点数量较多时，其内存占用会明显高于 Redis 链表。但跳跃表的优势在于查找效率，它可以在 O(logN) 的时间复杂度内完成查找操作，而链表的查找时间复杂度为 O(N)。

实际应用场景中的内存占用考量

在实际应用中，选择使用 Redis 链表还是其他数据结构，内存占用是一个重要的考量因素，但并非唯一因素。

例如，在需要频繁插入和删除元素，并且对遍历方向有要求（如需要双向遍历）的场景下，Redis 链表虽然内存占用较大，但它的操作特性使得它成为一个合适的选择。比如在实现一个简单的消息队列时，链表的双向插入和删除操作可以方便地实现队列的入队和出队操作。

而对于需要快速查找元素的场景，如存储用户信息并根据用户 ID 快速获取用户数据，哈希表则更为合适，尽管它在某些情况下可能因为哈希冲突和扩容等因素导致内存占用较高。

在有序集合场景中，跳跃表与哈希表结合的方式虽然内存占用较大，但能够高效地实现元素的插入、删除和范围查找，满足了有序集合对数据有序性和操作效率的要求。

在内存资源有限的环境中，开发人员需要仔细评估不同数据结构的内存占用和性能特点，根据具体的业务需求进行选择，以达到最优的资源利用和系统性能。同时，也可以通过一些优化手段，如合理设置哈希表的负载因子、对链表进行适当的合并或拆分等，来进一步减少内存的浪费，提高系统的整体效率。