Redis 设计与实现 — Redis 设计与实现 (redisbook.com)
Redis中的五种对象分别是：string、list、hash、set、zset。它们的数据结构是怎样的呢？
每种对象都由一个被称为RedisObject的结构体来表示。我正在这里称它为：Redis对象头
struct RedisObject { int4 type; // 4bits int4 encoding; // 4bits int24 lru; // 24bits int32 refcount; // 4bytes void *ptr; // 8bytes，64-bit system } //由此可见一个Redis对象头所占空间为16字节。type可以是以下五种：
?encoding是什么呢？
事实上，上面每种类型都是由多个底层数据结构来表示的。
就比如string类型，它的编码会有三种：int，embstr，raw。
ptr?则是指向对象底层数据结构实现的指针，也就是对象本身。
1. 字符串string
SDS 简单动态字符串
Redis是用C语言编写的，但是Redis当中的字符串则是它自身重新设计的，被称为SDS。
SDS依然以 '\0' 作为字符串结尾，但是包含了free和len属性，以此来满足Redis对于内存安全和运行效率的要求。
1. 字符串空间预分配
当对字符串进行修改操作时，比如append,strcat等，假如当前空闲空间不能满足修改后的长度要求，则Redis不仅会为字符串分配当前所需空间，还会额外分配一倍的未使用空间。使得free与len的值相等，free的最大值为1M.
预分配策略通过减少内存分配次数，以此达到空间换时间的目的。
2. 字符串空间惰性释放
当字符串长度减小时，多余的空闲空间依然会被保留，并不会被立即释放掉。
Redis字符串底层有三种实现方式，int，embstr，raw。
- 当存储8字节以内的整数时，使用int
- 当存储长度小于44字节的字符串时，使用embstr
- 否则使用raw
前面介绍了Redis对象头的概念以及SDS的数据结构。RedisObject中的?ptr?指针将会指向一块SDS，以此来表示一个字符串。
embstr和raw两者的区别就是：
raw需要两次内存分配（RedisObject和SDS），而且内存地址可能不连续。
embstr使用一次内存分配，分配一块连续的内存空间来存储短字符串。
因为Redis对象头占16字节，SDS对象头占3个字节，字符串结束符占1个字节。而内存分配器 分配内存大小的单位都是 2、4、8、16、32、64 等， 因此embstr 相当于字符串创建的快捷方式，用了存储小于44长度的短字符串。
另外，embstr 对象可以看作是只读的，对它的任何操作都会使其encoding转化为raw。
假如对int?编码字符串的操作使其结果不再是int时，其encoding也会转化成raw。
?2. 列表List
?列表对象的底层数据结构有两种，ziplist或者linkedlist。Redis列表是双向的。
linkedlist是包含pre和next指针的双端链表
ziplist 则是为了节约空间而设计的内存连续链表， 它同样也可以双向操作。
当列表对象可以同时满足下列两个条件时，列表对象采用压缩链表编码：
（1）列表对象保存的所有字符串元素的长度都小于64字节；
（2）列表元素保存的元素数量小于512个；
否则采用双端链表编码
3.?哈希对象Hash
哈希对象的底层结构可以是ziplist或者hashtable
Redis当中的哈希表使用的是拉链法设计，大家可以参考我之前写的两篇博客来了解实现原理：
C# 中Dictionary源码详解_郭麻花的博客-CSDN博客
C# 中Hashtable 源码详解_郭麻花的博客-CSDN博客
使用?ziplist实现的hash对象
使用hashtable实现的hash对象?
当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码：
（1）哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
（2）哈希对象保存的键值对数量小于512个；
否则使用 hashtable编码。
4. 集合对象Set
集合对象的编码可以是intset或者hashtable
intset就是整数集合，它的数据结构是这样的：
?当集合对象可以同时满足以下两个条件时，对象使用intset编码：?
1.集合对象保存的所有元素都是整数值。
2. 集合对象保存的元素数量不超过512个。
否则集合对象需要使用hashtable编码。
5.有序集合zset
zset编码可以是ziplist或者skiplist，但当编码是skiplist时，却是由字典和skiplist共同实现的。
什么是跳跃链表skiplist呢？
跳跃链表是一种近似二分查找的数据结构，类似于kafka的稀疏索引，但它是多层的
原理很简单，但查询效率却很高：跳跃表原理 - thrillerz - 博客园 (cnblogs.com)
它的数据是冗余的，假如你存了10个整数，那么它最终可能会占用20个节点来存储。
因为它会随机选择一些数据做为“目录”。而且从概率上讲，上级目录的节点数通常是下级目录的1/2，且同样是有序的。
目录的层数也是随机决定的，大家可以看下上文链接。
字典的好处是提供更高的查询效率，但它并不是有序排列的；
skiplist是有序的，对于某些应用场景来说非常合适，但查询效率偏低；
因此，zset使用两者结合的方式来实现：
?当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码：
1. 有序集合保存的元素数量小于128个
?2. 有序集合保存的所有元素成员的长度都小于64字节
?否则将使用skiplist编码