redis有5种基本数据类型，分别是string、list、hash(哈希表)、set、zset(有序集合)
redis底层有6种数据结构: 分别是简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表
- redis基本数据类型string
其底层是一个redis定义的简单动态字符串SDS，其基本结构如下
/* 字符串对象的结构 */
struct sdshdr { // buf 中已占用空间的长度
int len; // buf 中剩余可用空间的长度
int free; // 数据空间
char buf[];
};
- redis 基本数据结构list
其底层是一个双向链表, 链表节点为
typedef struct listNode{
struct listNode *prev;
struct listNode * next;
void * value;
}
- 链表的特性
双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）
无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
长度计数器：链表中存有记录链表长度的属性 len
多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。
- redis中hash表结构的底层是字典
- 字典
字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。
- 字典
SET msg "hello world"
创建这样的键值对（“msg”，“hello world”）在数据库中就是以字典的形式存储。但是C语言本身没有字典数据结构，redis是自己构建的字典数据结构。
- 字典的定义：
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}
一个空的字典结构如下
哈希表节点dictEntry定义：
typeof struct dictEntry{
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}
struct dictEntry *next;
}
- 渐进式rehash
-
redis中基本数据结构zset使用的是跳跃表(skiplist)
跳跃表- zskiplistNode（节点） 数据结构：
typedef struct zskiplistNode{
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
} level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
}
- zskiplist 数据结构
typedef struct zskiplist {
//表头节点和表尾节点
structz skiplistNode *header,*tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点的层数
int level;
} zskiplist;
- 整数集合(Intset)
整数集合是集合建的底层实现之一，当一个集合中只包含整数，且这个集合中的元素数量不多时，redis就会使用整数集合intset作为集合的底层实现。- Intset实现
typedef struct intset{
//编码方式
uint32_t enconding;
// 集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
}
- 整数集合的升级
1 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2 将底层数组现有的所有元素都转换成新的编码格式，重新分配空间（其实就是如果以前是16位编码格式，现在会转为32位编码格式，或者更高。）
3 将新元素加入到底层数组中
- 压缩列表
压缩列表是列表键和哈希键的底层实现之一。当一个列表键只把少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，那么Redis 就会使用压缩列表来做列表键的底层实现。
参考：
1 说一下redis中5种数据类型的底层数据结构
2 深入浅出Redis-redis底层数据结构（上）
3 深入浅出Redis-redis底层数据结构（下）
