Redis 学习笔记 02：SDS 简单动态字符串

一、定义

Redis 使用的链表是双向无环链表，链表节点可用于保存各种不同类型的值。

二、数据结构

1、链表数据结构

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

2、链表节点数据结构

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

三、结构图

三个 listNode 结构组成的链表，实例如下：

四、Redis 链表的特性

• 双端:链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度是 O(1);

• 无环:表头节点的 prev 指针和表尾节点 next 指针都指向 NULL，对链表的访问以 NULL 为终点;

• 带表头指针和表尾指针:通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1);

• 带链表⻓度计数器:程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表节点数量的复杂度为 O(1);

• 多态:链表节点使用 void*指针来保持节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点设置类型特定函数，所以链表可以用于

五、适用场景

1. 作为列表键的底层实现之一：当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。

2. 除此之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis 服务器本身还使用链表来保存多个客户端的状态信息， 以及使用链表来构建客户端输出缓冲区。

• 列表

redis 列表是简单的字符串列表，列表是有序的，列表中的元素可以重复。可以添加一个元素到列表的头部或者尾部。（频繁增删，数据量过大且元素过长，继续使用压缩列表需要大量连续存储空间）

• 发布与订阅

涉及管理客户端订阅，订阅与退订客户端使用链表来管理的（客户端数量不确定，且频繁增删）

• 慢查询

使用链表记录所有慢查询日志（慢查询数量不定）

• 监视器

monitors 链表，会将客服端加入 monitors 链表（客户端数量不确定，且频繁增删）

• redis 服务器用链表保存多个客户端状态信息 （不清楚会链接多少个客户端）

• 客户端输出缓冲区(不清楚数据类型和规模)