提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
目录
前言
????????redis是一种远程内存数据库，其内部提供了五种不同类型的数据结构。简而言之，redis就是一个速度非常快的非关系型数据库（Nosql），可以存储键（key）与五种不同类型的值（value）之间的映射，就像散列表一样。接下来就来对其五种数据结构进行介绍。
一、字符串（String）
????????redis没有直接使用C语言中的字符串表示，而是自己构建了一个字符串，名为 “简单动态字符串” （simple dynamic string ， SDS）。其中，C语言中的字符串只是作为字符串面量（通常在无须对字符串值进行修改的地方使用）。
比如，在客户端（redis-cli） 使用指令：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
redis-cli> set world "peace"????????那么redis就会在数据库中创建一个新的键值对。其中，键是一个字符串对象，对象的底层是一个保存着 “world” 的SDS；值也是一个字符串对象，对象的底层是一个保存着字符串 “peace” 的SDS。
1.SDS的定义
SDS的数据结构如下：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
struct sdshdr{
//记录buf数组中已经使用的字节的数量
int len;
//记录buf数组中还未使用的字节的数量
int free;
//字节数组，用于存储字符串
char buf[];
}；????????虽然SDS是redis自定义的字符串结构，但是依旧遵守C语言字符串以空字符结尾的惯例，原因在于可以直接使用C语言字符串函数库中的函数（提高代码的复用性）。
2.SDS与C语言中字符串的区别（优点）
2.1?获取字符串长度
????????因为C语言字符串本身不记录自身的长度，若要获取其长度，则需要遍历字符串才能得到，时间复杂度为O(N)；而SDS在其自身的数据结构中记录了以使用字符串空间（也就是len），所以获取一个字符串长度的时间复杂度为O(1)。
2.2?防止缓冲区的溢出
? ? ? ? 依旧是C语言字符串不记录自身长度的所造成的差异，C语言中字符串在修改时有可能会造成缓冲区的溢出（buffer overflow）；SDS由于其自身记录了长度，在每次修改SDS时：（1）API会检查SDS的空间是否足够；（2）若不足，则API会自动将SDS的空间扩展至所需的大小，再进行接下来的操作。由此，SDS可以避免缓冲区的溢出。
2.3 减少修改字符串时内存重分配的次数
????????（1）在一般的程序中，每次修改字符串都执行一次内存重分配，这是可以接受的；? ? ? ? ? ? ????????（2）但是redis作为数据库，经常用于速度要求严苛、数据要求频繁修改的场合，每次修改字符串所需要内存重分配，可能会对性能造成影响。
? ? ? ? 通过使用未使用的空间（free），SDS实现了空间预分配与惰性空间释放两种优化策略
????????
二、链表（List）
1.链表的定义
? 链表节点的数据结构如下：
typedef struct listNode{
//前置节点
struct listNode * prev;
//后置节点
struct listNode * next;
//节点的值
void * value;
};redis中的链表的数据结构为双向链表，其结构如图2-1：
?图 2-1
链表的数据结构如下：
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;例如，一个list结构由两个listNode结构组成的链表，如图2-2：
?图 2-2
三、哈希表（Hash）
? ? ? ? ?redis中哈希键的底层实现之一就是字典，实际与C++语言中的哈希表一样，都是一个键与一个值进行关联，并称为键值对。由于redis使用的C语言没有这种数据结构，所以redis自己构建了字典实现。在我看来，在redis中的字典与哈希表的关系就是，字典就是对哈希表的结构的一个封装而已，只是为了方便使用。下面会讲到二者的关系。
1.哈希表的定义
哈希表的数据结构如下：
typedef struct dictht{
//哈希表函数
dictEntry ** table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
unsigned long sizemask;
//记录哈希表已有节点的数量
unsigned long used;
} dictht;其中，哈希表节点的数据结构如下：
typedef struct dictEntry{
//键
void * key;
//值
union{
void * val;
unint64_t u64;
int64_t s64;
} v;
//指向下个哈希表节点，形成链表
struct dictEntry * next;
} dictEntry;哈希表的的具体结构如图3-1：
图 3-1
?2.字典的定义
redis中的字典结构还包含了上面的哈希表，如下：
typedef struct dict{
//类型特定的函数
dictType * type;
//私有数据
void * private;
//哈希表
dictht ht[2];
//rehash的索引
int rehashidx;
} dict;????????其中，type与private是针对不同类型的键值对，为创建多态字典而设置。至于具体的dictType结构这里就不详细介绍了，只是一些用于操作特定类型键值对的函数。?
? ? ? ? 值得注意的是，ht属性包含两个元素。正常情况下，字典只会使用ht[0]，ht[1]只会在对ht[0]扩容时使用。还有，rehashidx也与哈希扩容有关，记录了rehash的进度。
3.解决哈希冲突
????????redis解决哈希冲突时使用链地址法，其结构上已经有所介绍。链地址法这里就不过多介绍了，此处添加新的节点时，为了提高速度，选择将新的节点添加到链表的表头位置，时间复杂度为O(1)。
4.哈希表扩容（rehash）
? ? ? ? redis中哈希表的扩容有四步：
（1）为字典的 ht[1] 哈希表分配空间（ht[1] 大小为 ht[0] 的 2^n）；
（2）将 ht[0] 中的键值对reahash到 ht[1] 中；
（3）当 ht[0] 中的所有数据拷贝到 ht[1] 后，释放 ht[0];
??(4)? ?将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次rehash做准备。
5.渐进式rehash（面试时问到过）
原因：当数据量过大时，可能会导致服务器崩溃；
? ? ? ? ? ?若一次性rehash，则程序可能会访问到正在rehash的数据；
rehash的步骤：
（1）为ht[1]分配空间，让字典同时持有 ht[0]?与?ht[1] ;
（2）在字典中维持一个索引计数器变量rehashidx，并将其设置为0，表示rehash开始；
（3）rehash期间，每次的修改，程序除了指定的操作外，还会将 ht[0]?在rehashidx上的所有键值rehash到 ht[1]，rehash完成后，rehashidx加一；
（4）当 ht[0]?中所有的数据都rehash到 ht[1]?时，rehashidx设置为-1，rehash完成；
注：?当查找一个元素时，优先在 ht[0]?上查找。
四、有序集合（Zset）
? ? ? ? redis中使用跳跃表作为有序集合键（zset）的底层实现，也算是 redis?的一种特有的数据结构。跳跃表是一种有序集合，通过在每个节点维持多个指向其他节点的指针，达到快速访问其他节点的目的。跳跃表的效率相近与平衡树（AVL），但是实现比平衡树简单。
????????redis 的跳跃表由 zskiplist 与 zskiplistNode?两个结构构成，前者保存跳跃表信息（表头节点，表尾节点，长度），而后着则用于表示跳跃表节点。
1.跳跃表的定义?
跳跃表节点结构如下：
typedef struct zskiplistNode{
//后退指针
struct zskiplistNode * backward;
//分值
double score;
//成员对象
robj * obj;
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode * forward;
//跨度
unsigned int span;
} level[];
} askiplistNode;?图 4-1
????????如图4-1所示，是一个跳跃表实例，位于最左边的黑丝跳跃表 zskiplist 结构。其中，header?指向跳跃表头结点，tail?指向表的尾节点，level?记录跳跃表中层数最大的那个节点的层数（表头节点不包括在内），length?记录跳跃表的长度（节点的数量）。
2.跳跃表的特性
? ? ? ? 之前说到跳跃表类似与平衡树，其内部所有的节点都按照分值从小到大排序。其中节点的对象是唯一的，但是分值是可以相同的，若分值相等，则对象较大的会排在后面。
五、集合（Set）
? ? ? ? redis 中的集合结构类似于其他变成语言（例如：C++）中的集合结构，其底层是用整数集合（inset）实现的。当一个集合包含的元素不多且都为整数时，redis?就会使用整数集合作为集合键的底层实现。
1.整数集合的定义
? ? ? ? 整数集合的数据结构如下：
typdef struct inset{
//编码方式
uint32_t encoding;
//集合中的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;? ? ? ? contents 数组是整数集合的底层实现，数组中的元素是有序（由小到大）且不重复的。contents 中元素的数据类型由 encoding?决定。
2.整数集合的特性
? ? ? ? 当添加的新元素的类型比现有的集合的类型要长时，整数结合需要先进行升级。将所有元素都转换为与新元素相同的类型。且升级之后无法降级。
? ? ? ? 优点：使用者可以随意将不同大小的类型数据添加到整数集合中。
总结
提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。