Redis五种基本数据结构：String、List、Set、Hash、Zset
一、Redis对象基本结构
Redis是键值对方式的存储，每一个Redis存储对象都包括两个对象，一个是Key,一个是Value。
Redisc创建的对象RedisObject数据结构如下：
unsigned type: 4 // 类型，其中type的值对应5中redis数据类型的类型常量
unsigned encoding: 4 // 编码，encoding则记录了底层实现所用的数据结构
void *ptr // 指向底层数据结构指针
二、内部数据结构
2.1 简单动态字符串
redis实现了一个SDS结构(简单动态字符串)类型来替代C语言中的原生字符串, 结构如下
struct sdshdr {
int len; //记录buf中字符串的实际长度
int free; //记录buf数组空闲长度
char buf[];//字节数组,用于保存字符串
};
和C语言原生字符串相比, 其有一下优点:
1、因为存储了字符串长度，可以在长量时间内获取字符串长度。
2、同样由于存储了字符串实际长度和buff空闲长度,字符串变化时不需要每次都重新分配内存；同时也避免了字符串长度变化可能导致的缓冲区溢出和内存泄漏。
3、SDS的设计由于根据字符串长度来判断字符串的末尾,因此中间可以存储任何数据包括空字符
2.2 双向链表
redis中的链表类型就是最常用的双向链表,涉及数据结构如下
//链表类型
typedef struct list {
listNode * head;//表头节点
listNode * tail;//表未节点,方便逆向遍历
unsigned long len;//节点数目, 优化链表求长度
}list;
2.3、Hash表
redis中的字典类型也就是基本的hash表
redis中的rehash就是通过创建一个临时的字典,将正在使用的字典中的所有键值对复制到临时字典中(这个过程需要重新计算hash值和索引值,因此称为rehash),最后释放老的字典,并将其指针指向临时字典。
当数据量比较小的时候,这个过程可以一次性完成，但是数据量大的时候,庞大的计算量可能导致整个服务停止,因此redis采用了渐进式rehash:
1、同时维护两个hash表hd[0]和hd[1]
2、设置rehash_idx设置为0，在0< rehash_idx < 槽位数组长度时, 对hash表的任何操作除了执行正常的操作过程以外，还会将hd[0]槽位数组rehash_idx索引上的所有键值对rehash到hd[1]
3、同时所有的添加键值对操作只会在hd[1]上进行,保证了hd[0]只减不增。
4、rehash完成后,hash表指针指向hd[1],释放hd[0]内存。
2.4 跳跃表
跳跃表是一种有序的数据结构，支持平均O(logN)复杂度的节点查找,其效率可以和平衡树媲美，同时实现简单,而且由于不需要reblance操作,在高并发情况下表现更加出色。redis中的跳跃表也就是基本的跳跃表实现, 涉及数据结构如下。
typedef struct zskiplistNode{
struct zskiplistLevel{ // 层数组，相当于索引，其中包括了当前节点砸每一层的前进指针以及到下一节点的跨度
struct zskiplistNode *forward; // 本层节点中的下一节点
unsinged int span; // 跨度，用于计算节点的排位。
} level[]
struct zskiplistNode *backWard; //指向前一个节点
duble score; // 所有节点按分值排序
robj *obj // 成员对象
}
typedef struct zskiplist {
struct zskiplistNode *header ,*tail;
unsigned long length; // 表中节点数
in level; 最大层数
}
实际上对有序链表稍加改造，我们就可以对链表进行二分查找。这就是我们要说的跳表。下面我们来看一下，跳表是怎么跳的。
上图是一个简单的有序的单链表，如果要查找某个数据，只能从头至尾遍历链表，查找到值与给定元素时返回该结点，这样的查询效率很低，时间复杂度是为O(n)。
假如对链表进行改造，先对链表中每两个节点建立第一级索引，再对第一级索引每两个节点建立第二级索引。如下图所示：
对于上图中的带二级索引的链表中，我们查询元素 16，先从第二级索引查询 1 -> 7->13，发现16大于13 ，然后通过 13 的 down 指针找到第一级索引的 17，发现 16 小于17 ，再通过13 的 down 指针找到链表中的 16，只需要遍历 6 个节点就完成 16 的查找。如果在单链表中直接查找 16 的话，只能顺序遍历，需要遍历 10 个节点，是不是效率上有所提升呢，由于数据量较小，遍历 10 个节点到遍历 6 个节点你可能觉得没有提升多少性能。
所以，当链表的长度 n 比较大时，比如 1000、10000 的时候，在构建索引之后，查找效率的提升就会非常明显。
跳表有多占内存？
假如有 n 个元素的链表，第一级索引为 n/2 个，第二级为 n/4 个，第三级为 n/8 个，......，最后一级为 2 个。这几级索引的结点总和就是n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。那我们有没有办法降低索引占用的内存空间呢？
其实 redis 中有序集合支持的核心操作也就是这几个。这里说下为什么 redis 使用跳表而不使用红黑树。
1、红黑树在查找区间元素的效率没有跳表高，其他操作时间复杂度一致。
2、相比红黑树，跳表的实现还是简单的，简单就意味着不容易出错，bug 少，稳定，易读，易维护。
3、跳表更加灵活，通过改变索引构建策略，有效平衡效率和内存消耗
2.5 压缩表
压缩列表是Redis为了节约内存而开发的, 是由一系列特殊编码的连续内存块组成的顺序型数据结构,每个压缩列表节点可以保存一个字节数组或一个整数值。其由三部分构成,如下所示:
zlbytes 表示的是整个压缩列表使用的内存字节数
zltail 指定了压缩列表的尾节点的偏移量
zllen 是压缩列表 entry 的数量
entry 就是 ziplist 的节点
zlend 标记压缩列表的末端
再看看一个 entry 的结构
typedef struct zlentry {
// prevrawlen 前置节点的长度 ；prevrawlensize 编码 prevrawlen 所需的字节大小
unsigned int prevrawlensize, prevrawlen;
// len 当前节点值的长度 ，lensize 编码 len 所需的字节大小
unsigned int lensize, len;
// 当前节点 header 的大小 等于 prevrawlensize + lensize
unsigned int headersize;
// 当前节点值所使用的编码类型
unsigned char encoding;
// 指向当前节点的指针
unsigned char *p;
} zlentry;
prevrawlen 前置节点的长度，这里多了一个 size，其实是记录了 prevrawlen 的尺寸。Redis 为了节约内存并不是直接使用默认的 int 的长度，而是逐渐升级的。
同理 len 记录的是当前节点的长度，lensize 记录的是 len 的长度。
三、数据类型
String类型
String类型在Redis底层可以是int,raw和embstr。
如果一个String对象保存的是整数值，并且可以使用long来表示,那么将会以整数形式保存。
如果一个String对象保存的是字符串值，并且其长度大于32字节，那么就直接使用SDS结构来保存，其encoding标记为raw。
如果一个String对象保存的字符串长度小于32字节，那么会使用embstr编码，embstr是一种短字符串的优化，其存储还是使用SDS结构，但raw编码会调用两次内存分配函数来分别创建redisObject结构和SDS结构，而embstr编码则通过调用一次内存分配函数来分配 一块连续的空间，空间中依次包含redisObject和SDS结构。
List类型
List类型在Redis底层可以是ziplist(压缩列表)或linkedlist(双向列表)。
Hash类型
Hash类型在Redis底层可以是ziplist(压缩列表)或hashtable(Hash表)，ziplist编码的哈希对象每当 有新的键值对要插入时,会将保存了键和值的节点依次推入到压缩列表表尾,因此同一键值对顺序存放在一起。
Set类型
Set类型在Redis底层可以是intset(整数集合)或hashtable(Hash表)，只有当Set中的所有元素均为整数类型时才会使用intset。
Zset类型
Zset类型在Redis底层可以是ziplist(压缩列表)或skiplist(跳跃
