数据结构
一.动态字符串
动态字符串（Simple dynamic string,SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。SDS的结构如下：
struct sdshr{
//记录buf数组中已使用的字节数量
//等于SDS所有保存字符串的长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
};
1.1.SDS与C字符串的区别
- 常数复杂度获取字符串的长度：得益于len变量
- 杜绝缓冲区溢出
减少修改字符串时带来的内存重分配次数：在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。
- 空间预分配
- 惰性空间释放
SDS可以保存二进制
二 链表
listNode结构如下：
typedef struct listNode{
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void * value;
}
list结构如下：
typedef struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表所包含的节点数量
unsinged long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void （*free）(void *ptr);
//节点值对比函数
int (*match)(void ptr,void *key);
}
三 字典
又称为map，是一种用于保存键值对（key-value）的抽象数据结构。Redis的字典使用哈希表作为底层实现，一个哈希表可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
实现如下
1、哈希表结构
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}dictht;
2、哈希表节点结构
typedef struct dictEntry{
//键
void *key;
//值
union {
void *val;
uint64_t u64;
int64_t s64;
};
//指向哈希表节点，形成链表
sturct dictEntry *next;
}dictEntry;
3、字典结构
typedef struct dict{
//类型特定函数
dictType *type;
//私有数据
void privdata;
//哈希表
dictht ht[2];
//rehash索引
int trehashidx;
}dict;
字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用；trehashidx,记录目前rehash的进度。
4、解决键冲突
redis的哈希表使用链地址法来解决冲突。
5、rehash
扩展和收缩哈希表的工作都可以通过rehash操作完成。
四 跳跃表
跳跃表示一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表的效率可以和平衡树媲美，并且因为跳跃表的实现的实现比平衡树要来得更为简单，所有有不少程序都使用跳跃表来代替平衡树。
redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，redis就会使用跳跃表来作为有序集合键的底层实现。
五 整数集合
整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，redis就会使用整数集合作为集合键的底层实现。
六 压缩列表
压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。