Redis设计与实现——数据结构与对象

前言

Redis是一个KV数据库，常用于实现缓存，因为基于内存实现，所以速度极快。最近阅读《Redis设计与实现》一书，整理几篇文章，本文介绍Redis数据结构相关内容。

I. 数据结构

我们通常说的Redis支持的数据类型有五种，包括字符串、哈希、列表、集合、有序集合，其实这只是存储的数据类型，底层用于存储数据的数据结构并不是这些，而是动态字符串(SDS)、链表、字典(哈希表)、跳跃表、整数集合、压缩列表。

Redis的每一种数据类型其底层所用的数据结构并不只有一种，往往会在合适的情况下采用合适的数据结构，也是基于性能考虑。对照下面导图，我们可以简单的了解每种数据类型有哪些数据结构实现方式。

下面具体介绍Redis中定义的几种数据结构。

动态字符串 SDS

Redis中自定义了一个动态字符串取代了C语言中的字符串作为默认字符串数据结构，凡是可能会变化的字符串Redis都会用SDS作为实现。

用途：

• KV中键和值都会用
• 缓冲区：AOF缓冲区，客户端状态中的输入缓冲区

定义——ArrayList的感觉：

struct sdshdr {
   
    int len;    // 实际buf使用长度
    int free;   // 剩余长度
    char buf[]; // 存储字节数据数组
}

优势：

• 记录了长度信息，获取长度$O(1)$复杂度

• 自动扩容机制——缓冲区不会溢出（莫名其妙更改了别的内存空间数据）

• 空间预分配和惰性空间释放——减少增减字符串时带来的内存重分配次数

• 以 len 来判断数据结束——不仅仅可以存储字符，其实可以是二进制数据

双端链表 LinkedList

Redis定义的双端链表其实也很正常，就是一个能够双向遍历，含有头尾指针的链表数据结构，当然也就具有链表的优势与劣势——增删快，查询慢。

用途：

• 列表底层实现之一（数量比较多或者元素都是比较长的字符串）
• 发布订阅、慢查询、监视器等功能
• Redis保存多个客户端的状态信息
• 客户端输出缓冲区

节点定义——双向链表节点：

typedef struct listNode{
   
    struct listNode *prev;
    struct listNode *next;
    void *value；
}

链表定义——双端双向链表：

typedef struct list{
   
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup) (void *ptr);  // 节点值复制函数
    void (*free) (void *ptr);  // 节点释放函数
    int (*match) (void *ptr, void *key);  // 节点值对比函数
}

优势：

• 双端双向——前后节点查询复杂度 O ( 1