数据结构与对象

跳跃表

• 跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
• Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳跃表节点。
• 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
• 在同一个跳跃表中， 多个节点可以包含相同的分值， 但每个节点的成员对象必须是唯一的。
• 跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。

整数集合

整数集合是redis Set数据结构的实现之一，等Set中的数据只有整数的时候，就会使用它，整数集合可以保存，从16位到64位的整数，

• encoding 属性决定了，集合使用那种长度的int类型存储数据。
• length 记录总数
• cotents 数组按从小到大的顺序保存着整数数据，它的类型是由encoding属性觉得的。
  升级：如果一个新添加的元素的长度超过了 encoding类型的长度，那么整数集合就会自动执行升级操作，就是指，按照新元素的大小，重新分配一个数组空间，然后将原来contents中的内容转换成新的类型，在顺序存在新的数组中，最后将新元素存放在length-1处。

压缩列表

Redis会在当列表键的，元素是小整数，或是短字符串时，使用压缩列表作为底层实现，可见压缩列表是Redis为了节省内存而开发的。

对象

Redis并没有直接使用如SDS，字典，整数集合等等的数据结构来实现键值对数据库，而是基于这些数据结构构建的对象系统，分别是

• 字符串对象
• 列表对象
• 哈希对象
• 集合对象
• 有序集合对象

Redis 的对象系统还实现了引用计数的垃圾回收器，并且Redis 还通过引用计数技术实现了对象共享机制， 这一机制可以在适当的条件下， 通过让多个数据库键共享同一个对象来节约内存。Redis 的对象带有访问时间记录信息， 该信息可以用于计算数据库键的空转时长， 在服务器启用了 maxmemory 功能的情况下， 空转时长较大的那些键可能会优先被服务器删除。

内存回收

redis 使用 redisObject结构中的refcount属性记录引用计数，当对象初始化的时候计数为1，每有一个新的引用就自增1，相反就自减1，到最后计数为0就会被回收。

typedef struct redisObject {
    // ...
    // 引用计数
    int refcount;
    // ...
} robj;

对象共享

redis利用引用计数的功能实现了整数字符串对象的共享功能，（两个键指向同一个对象，引用计数加1）

Redis 会在初始化服务器时， 创建一万个字符串对象， 这些对象包含了从 0 到 9999 的所有整数值， 当服务器需要用到值为 0 到 9999 的字符串对象时， 服务器就会使用这些共享对象， 而不是新创建对象。

因为Redis共享对象需要先确认两个对象是否相同，字符串对象和哈希对象验证操作的复杂度为O(N)和O O(N^2)，而整数字符串是O(1)所以redis只共享整数字符串对象。

类型检查与命令多态

Redis中操作对象的命令分为两种分别是，多态命令和特定类型命令，Redis在执行特定类型命令是会先对操作值进行类型检查，如果配型不匹配的话就会直接返回错误。

对象的编码与类型

Redis中的一个键值对有两部分组成，键对象和值对象，对象在底层都由redisObject结构存储。

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // ...
} robj;

其中编码代表着ptr指针指向的结构的类型，就比如：同样是列表键对象，但是可以由压缩表，双端链表实现，encoding 就是决定到底使用那种数据结构去实现对象结构。

数据类型和编码方式：

数据类型	编码方式	转换条件	结构
字符串对象	int	整数字符串
	raw	大于39字符的字符串值
	embstr	小于等于39个字符
列表对象	ziplist	列表对象保存的所有字符串元素的长度都小于 64 字节，元素数量小于 512 个
	linkedlist	相反
哈希对象	ziplist	长度都小于 64 字节,元素数量小于 512 个
	hashtable	相反
集合对象	intset	所有元素都是整数值，元素数量不超过 512 个
	hashtable	相反
有序集合对象	ziplist	元素数量小于 128 个，所有元素成员的长度都小于 64 字节
	skiplist	底层同时使用跳跃表和字典两种结构