Redis中五大数据结构的底层实现 _Redis

一、概述

redis是一个开源的使用ANSI C语言编写、遵守BSD协议、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，与Memcached类似，却优于Memcached的一个高性能的key-value数据库。下面让我们来详细介绍一下redis中五大数据结构的底层实现。

二、简单动态字符串

1、概述

Redis是一个开源的使用ANSI C语言编写的key-value 数据库，我们可能会较为主观的认为 Redis 中的字符串就是采用了C语言中的传统字符串表示，但其实不然，Redis没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串（simple dynamic string SDS）的抽象类型，并将SDS用作Redis的默认字符串表示：redis>SET msg "hello world"

SDS 定义：

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

文章插图

图片来源：《Redis设计与实现》

我们看上面对于 SDS 数据类型的定义：

len 保存了SDS保存字符串的长度
buf[] 数组用来保存字符串的每个元素
free j记录了 buf 数组中未使用的字节数量

2、与C语言相比较

文章插图

一般来说，SDS 除了保存数据库中的字符串值以外，SDS 还可以作为缓冲区（buffer）：包括 AOF 模块中的AOF缓冲区以及客户端状态中的输入缓冲区。后面在介绍Redis的持久化时会进行介绍。

三、链表

1、概述

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

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

每个链表节点使用一个listNode结构表示（adlist.h/listNode）：

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

链表的数据结构：

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

组成结构图

文章插图

2、Redis链表特性

双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1) 。
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。
带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1) 。
多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

四、字典

1、概述

字典又称为符号表或者关联数组、或映射（map），是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。C 语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己构建的。

哈希表结构定义：

typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
//总是等于 size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;

}dictht

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

typedef struct dictEntry{
//键
void *key;