| 类型 | 底层 | 应用场景 | 编码类型 |
|---|---|---|---|
| String | sds | 帖子、评论、热点数据、输入缓冲 | RAW << EMBSTR << INT |
| List | ziplist quickList | 评论列表、商品列表、发布与订阅、慢查询、监视器 | LINKEDLIST << ZIPLIST |
| Set | intset hashtable | 适合交集、并集、查集操作，例如朋友关系 | HT << INSET |
| Zset | ziplist skiplist | 去重后排序，适合排名场景 | SKIPLIST << ZIPLIST |
| Hash | ziplist hashtable | 结构化数据，比如存储对象 | HT << ZIPLIST |
sds
场景：string结构使用
特点：预分配内存--减少内存的频繁分配
结构：capacity+lenth+array，类似ArrayList
struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位，不理睬它
byte[] content; // 数组内容
}
embstr vs raw
Redis 的字符串有两种存储方式，在长度特别短时，使用 emb 形式存储 (embeded)，当长度超过 44 时，使用 raw 形式存储。
redis对象头(16)+SDS(3)
//4+4+8=16
struct RedisObject {
int4 type; // 4bits
int4 encoding; // 4bits
int24 lru; // 24bits
int32 refcount; // 4bytes
void *ptr; // 8bytes，64-bit system
} robj;
//1+1+1=3
struct SDS {
int8 capacity; // 1byte
int8 len; // 1byte
int8 flags; // 1byte
byte[] content; // 内联数组，长度为 capacity
}
这两种类型有什么区别呢？为什么分界线是 44 呢？
embstr 存储形式是这样一种存储形式，它将 RedisObject 对象头和 SDS 对象连续存在一起，使用 malloc 方法一次分配。而 raw 存储形式不一样，它需要两次 malloc，两个对象头在内存地址上一般是不连续的。
而内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。
当内存分配器分配了 64 空间时，那这个字符串的长度最大可以是多少呢？这个长度就是 44。
64-16-3-1(以字节\0结尾) = 44
dict
场景：hash结构使用
结构：包含两个hashtable，复制算法，只有一个hashtable使用，扩容时使用另一个
hashtable结构几乎同hashmap，数组+链表，同样有对应的扩容缩容、渐进式rehash、hash优化等
struct dictEntry {
void* key;
void* val;
dictEntry* next; // 链接下一个 entry
}
struct dictht {
dictEntry** table; // 二维
long size; // 第一维数组的长度
long used; // hash 表中的元素个数
...
}
ziplist
场景：zset 和 hash 元素个数少使用，set 集合容纳元素都是整数并且元素个数较小时
特点：不合适存储大对象，多元素对象。紧凑存储没有冗余空间(对比string)，插入新元素需要重新分配内存并拷贝。
结构：ziplist共用一块连续内存空间，通过ztail_offset快速定位最后一个元素，然后倒序遍历
hash-ziplist=ziplist<Entry> 通过ziplist.ztail_offset+entry.prevlen倒序实现双链
struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
int16 zllength; // 元素个数
T[] entries; // 元素内容列表，挨个挨个紧凑存储
int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}struct entry {
int<var> prevlen; // 前一个 entry 的字节长度
int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
quicklist
场景：list结构元素多时使用
特点：考虑到链表linkedlist的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。
结构：ziplist+quicklistnode
单个 ziplist 长度为 8k 字节
struct quicklistNode {
quicklistNode* prev;
quicklistNode* next;
ziplist* zl; // 指向压缩列表
int32 size; // ziplist 的字节总数
int16 count; // ziplist 中的元素数量
int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储
...
}
struct quicklist {
quicklistNode* head;
quicklistNode* tail;
long count; // 元素总数
int nodes; // ziplist 节点的个数
int compressDepth; // LZF 算法压缩深度
...
}
skiplist
使用场景：zset，zset通过skiplist+hash复合结构
基于链表，增加一个指向后边其他节点的指针（不同层数--通过随机层数算法），先延着高层数据找，找不到再沿着低层数据找，由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。
redis为什么选择了跳跃表而不是红黑树
1.跳表操作时间复杂度和红黑树相同
2.跳表代码实现更简单易读（平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速）
3.跳表区间查找效率更高（在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。）
跳跃表多少层
1-32，Level[0] 有 264 个元素时
网友评论