简单动态字符串

Redis没有直接使用C语言传统的字符串标示，而是自己构建了一种名为简单动态字符串（simple dynamic string, SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。

1.SDS的定义

每个sds.h/sdshdr结构表示一个SDS值

struct sdshdr {

 //记录buf数组中已使用的字节数量

 //等于SDS所保存字符串的长度

 int len; 

 //记录buf数组中未使用的字节数量

 int free;

 //字节数组，用于保存字符串

 char buf[];

};

上图展示了一个SDS示例：

• free属性的值为0，表示这个SDS没有分配任何未使用空间。
• len属性的值为5，表示这个SDS保存了一个5字节长的字符串。
• bug属性是一个char类型的数组，数组的前五个字节分别保存了‘R’、'e'、'd'、'i'、's'五个字符，而最后一个字节则保存了空字符'\0'。

2.SDS优点：

• 获取字符串长度的复杂度为O(1)
• API是安全的，不会造成缓冲区溢出
• 修改字符串长度N次最多需要执行N次内存重分配
• 可以保存文本或者二进制数据
• 兼容部分C字符串函数

3.SDS API

下图列出了SDS的主要操作API

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活的调整链表的长度。链表在Redis中的应用非常广发，比如列表键的底层实现之一就是链表。

1.链表和链表节点的实现

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

typedef struct listNode {
 //前置节点
 struct listNode *prev;

 //后置节点
 struct listNode *next;

 //节点的值
 void *value;
} listNode;

多个liestNode可以通过prev和next指针组成双端链表，如下图所示：

虽然仅仅使用多个listNode结构就可以组成链表，但使用adlist.h/list来持有链表的话，操作起来会更方便，结构如下：

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;

2.Redis的链表实现的特性：

• 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1).
• 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。
• 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1).
• 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1).

3.链表和链表节点的API

字典

字典，又称符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。在字典中，一个键可以和一个值进行关联，这些关联的键和值就成为键值对。

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而没个哈希表节点就保存了字典中的一个键值对。

1.哈希表

Redis字典所使用的的哈希表由dict.h/dictht结构定义

typedef struct dictht {
 //哈希表数组
 dictEntry **table;

 //哈希表大小
 unsigned long size;

 //哈希表大小掩码，用于计算索引值
 //总是等于size-1
 unsigned long sizemask;

 //该哈希表已有节点的数量
 unsigned long used;
 } dictht;

table属性是一个数组，数组中的每个元素都是指向一个dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。

2.哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对

typedef struct dictEntry {
 //键
 void *key;

 //值
 union{
 void *val;
 uint64_t u64;
 int64_t s64;
 } v;

 //指向下个哈希表节点，形成链表
 struct dictEntry *next;
} dictEntry;

3.字典

Redis中字典由dict.h/dict结构表示

typedef struct dict {
 //类型特定函数
 dictType *type;
 //私有数据
 void *privdata;

 //哈希表
 dictht ht[2];

 //rehash索引
 //当rehash不在进行时，值为-1
 int trehashidx;
} dict;

4.字典API

5.重点回顾

字典被广泛用于Redis的各种功能，其中包括数据库和哈希键

Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算的哈希值

哈希表使用链地址法来解决冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表

在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性完成的，而是渐进式的完成。

跳跃表

跳跃表（skiplist）是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

1.跳跃表的实现

Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中zskiplistNode结构用于表示跳跃表节点，而zskiplist结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。

2.跳跃表节点

跳跃表节点的实现由redis.h/zskiplistNode结构定义：

typedef struct zskiplistNode {
 //后退指针
 struct zskiplistNode *backward;

 //分值
 double score;

 //成员对象
 robj *obj;

 //层
 struct zskiplistLevel {
 //前进指针
 struct zskiplistNode *forward;

 //跨度
 unsigned int span;
 } level [] ;
} zskiplistNod;

3.跳跃表

跳跃表 zskiplist结构的定义如下：

typedef struct zskiplist {
 //表头节点和表尾节点
 structz skiplistNode *header, *tail;

 //表中节点的数量(表头节点层数不计算在内)
 unsigned long length;

 //表中层数最大的节点的层数(表头节点层数不计算在内)
 int level;
} zskiplist;

4.跳跃表API

5.重点回顾：

跳跃表的层高都是1到32之间的随机数

同一跳跃表中，多个节点可以包含相同分值，但每个节点的成员对象必须是唯一的

跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序