关于redis:Redis数据结构底层原理

简略动静字符串（SDS）

redis 是 C 语言的程序，然而字符串并没有采纳 C 语言提供能的，本人写了一个字符串的构造。

redis 中的字符串构造：

struct sdshdr {
 // 记录 buf 数组中已应用字节的数量
 // 等于 SDS 所保留字符串的长度
 int len;
 // 记录 buf 数组中未应用字节的数量
 int free;
 // 字节数组，用于保留字符串
 char buf[];};

并且 redis 中字符串同样采纳了 C 语言中的格局，就是最初一个应用空字符 ”/0” 完结，这个过程对程序员是通明的，sds 主动追加的。

为什么有现成的构造，还要自定义构造呢？起因有以下几点：

SDS 构造的长处

取得字符串长度时，复杂度升高为 O(1)

C 语言中的字符串获取长度的时候，须要遍历所有字符，晓得碰到 ’/0’，过程中的个数是长度。复杂度为 O(n)，redis 为了谋求疾速。优化了这一点，构造体中保留数据的长度，属性诶 len。使得复杂度升高为 O(1).

防止缓冲区溢出的危险

c 语言中的字符串赋值前，须要先分配内存空间。如果扭转字符串的长度，还须要思考内存空间是否够用，如果没有提前调配空间，就会呈现缓冲区溢出。为了防止这种状况，sds 会先查看内存是否够用，不够用的状况下，会先分配内存空间，之后扭转字符串。这样就不会呈现缓冲区溢出。

缩小了内存重调配的次数

c 语言中的字符串扭转，追加字符换时，须要减少空间，截取字符串时，又要开释空间。内存中的重调配是一个耗时的操作。为了有话这一点。sds 会在追加的时候，事后调配额定的空间，而在截取的时候，不会立刻开释内存。

空间预调配

• 如果对 SDS 进行批改之后，SDS 的长度（也即是 len 属性的值）将小于 1MB，那么程序调配和 len 属性，同样大小的未应用空间，这时 SDS len 属性的值将和 free 属性的值雷同。举个例子，如果进行批改之后，SDS 的 len 将变成 13 字节，那么程序也会调配 13 字节的未应用空间，SDS 的 buf 数组的理论长度将变成
  13+13+1=27 字节（额定的一字节用于保留空字符）。
• 如果对 SDS 进行批改之后，SDS 的长度将大于等于 1MB，那么程序会调配 1MB 的未应用空间。举个例子，如果进行批改之后，SDS 的 len 将变成 30MB，那么程序会调配 1MB 的未应用空间，SDS 的 buf 数组的理论长度将为 30MB+1MB+1byte

用过这种策略，不必每次追加时都要调配空间。

惰性空间开释

截取字符串时，不会立刻开释空间，而是扭转属性 free 的值。

二进制数据安全

c 语言中的字符串是以‘/0’完结的。所以只有看到‘/0’，就认为该字符串曾经完结了，这样就无奈保留二进制数据。sds 优化了这一点。

总结

比起 C 字符串，SDS 具备以下长处：
1）常数复杂度获取字符串长度。
2）杜绝缓冲区溢出。
3）缩小批改字符串长度时所需的内存重调配次数。
4）二进制平安。
5）兼容局部 C 字符串函数（因为 sds 会主动追加一个‘/0’）。

链表

链表的作用通常是装一组数据。C 语言没有提供这种数据结构，redis 自定义了该构造。

链表的构造

应用 ListNode 节点承装数据

typedef struct listNode {
 // 前置节点
 struct listNode * prev;
 // 后置节点
 struct listNode * next;
 // 节点的值
 void * value;
}listNode;

list 作为工具类应用相似于 JDK 中的 LinkedList 类。redis 中的链表是一个双向链表。

typedef struct list {
 // 表头节点
 listNode * head;
 // 表尾节点
 listNode * tail;
 // 链表所蕴含的节点数量
 unsigned long len;
 // 节点值复制函数
 void *(*dup)(void *ptr);
 // 节点值开释函数
 void (*free)(void *ptr);
 // 节点值比照函数
 int (*match)(void *ptr,void *key);
} list;

Redis 的链表实现的个性

能够总结如下：

• 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O（1）。
• 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的拜访以 NULL 为起点。
• 带表头指针和表尾指针：通过 list 构造的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O（1）。
• 带链表长度计数器：程序应用 list 构造的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O（1）。
• 多态：链表节点应用 void* 指针来保留节点值，并且能够通过 list 构造的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表能够用于保留各种不同类型的值。

总结

1. 哪里用到了链表这种构造呢？列表键，公布与订阅，慢查问，监视器等
2. redis 中的链表是双端的，无环的。

字典

字典是一种保留 键 - 值 的数据结构。有的中央也称作映射表。c 语言中没有提供这种数据结构的实现，所以 redis 本人实现了，java 语言中的 jdk 曾经提供了实现 HashMap。

构造

哈希表的构造

typedef struct dictht {
 // 哈希表数组
 dictEntry **table;
 // 哈希表大小
 unsigned long size;
 // 哈希表大小掩码，用于计算索引值
 // 总是等于 size-1
 unsigned long sizemask;
 // 该哈希表已有节点的数量
 unsigned long used;
} dictht;

table组是用来保留数据的;size记录的是数组的大小，并非是数据的个数；sizemash是用来取模的，用于计算索引。used是记录字典中数据个数的。

哈希表节点的构造

看完了哈希的构造，上面看看哈希表节点的构造。哈希表的数据是哈希表节点，也能够看成，哈希表是保留哈希表节点的，哈希表节点才是保留真正的数据的。

typedef struct dictEntry {
 // 键
 void *key;
 // 值
 union{
 void *val;
 uint64_tu64;
 int64_ts64;
 } v;
 // 指向下个哈希表节点，造成链表
 struct dictEntry *next;
} dictEntry;

须要质疑的是值的类型，能够说是一个指针，我对 c 语言不理解，我的猜想是保留了指针，那么哈希表就能够存任意类型的数据，只有赋值指针即可。除了指针，还能够保留整数，这个应该是一个优化操作吧。另外还有一个指向下一个节点的指针，用来将哈希值雷同的节点组成链表。

字典构造

和 Java 中的字典构造不同，在 java 中，哈希表其实就曾经是构造了，然而在 redis 的实现了有包了一层：

typedef struct dict {
 // 类型特定函数
 dictType *type;
 // 公有数据
 void *privdata;
 // 哈希表
 dictht ht[2];
 // rehash 索引
 // 当 rehash 不在进行时，值为 -1
 in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

看到了，有一个 dictht ht[2]，相当于连个哈希表构造，为什么这么做呢？间接向 Java 中似的，用哈希表不行么？上面详细分析下。type 和privdata属性针对的是不同类型的数据，用不同的函数即参数，例如 Java 中，根本类型的比拟和对象的比拟能够用一个吗？不行吧，所以要离开，下面两个就是辨别用的；哈希表数组，为啥用两个呢？保留数据的时候是占用一个的，另一个是迁徙数据时用的，trehashidx就是保留迁徙进度的，如果没有 rehash，那么值是 -1；

哈希算法

如果增加一个键值对，底层是如何运作的呢？ 首先通过 Hash 算法计算出一个哈希值，再用这个值和数组大小取模，得出数组中的索引地位。将数据出入到该地位。
如果该地位曾经有数据了，不是抵触了吗？ redis 采纳的链表解决抵触，如果索引中有多个数据，这里的数据是哈希表节点，这些节点会以链表的构造存储。因为是单向链表，为了晋升增加效率，采纳的头插法。就是增加在头部。避免插入到尾部，遍历整个链表。

rehash

rehash 次要针对的是对数组的的扩容和缩容操作，将数据从新映射到新的数组中。

数据迁徙

当数组须要扩容或缩容时，会给 ht[1] 调配空间，将 ht[0] 的数据迁徙到 ht[1] 中，迁徙实现后，将 ht[1] 赋值给 ht[0], 开释ht[1] 的空间。也就是说 ht[0] 是放数据的，ht[1]是用来扩容的工具数组。

新数组的大小调配

• 如果执行的是扩大操作，那么 ht[1]的大小为第一个大于等于ht[0].used* 2 的（2 的 n 次方幂）；
• 如果执行的是膨胀操作，那么 ht[1]的大小为第一个大于等于 ht[0].used 的 2 的 n 次方幂。

举例：数据个数是 5，那么扩容之后的大小是：5*2=10,10 之后的第一个 2 的 n 次方幂是 16，所以扩容之后的大小是 16。

触发条件

• 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1。
• 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5。
• 当哈希表的负载因子小于 0.1 时，程序主动开始对哈希表执行膨胀操作

为什么条件不同呢? 在执行这两个命令的时候，大部分操作系统会采纳写时复制技术（copy-on-write）技术晋升效率，实质就是，不在原数据批改，复制一份正本。批改正本之后替换原数据。在这个过程中，为了防止频繁的扩大操作。须要进步负载因子。

渐进式 rehash

下面的迁徙过程并不是一次性实现的，这样会阻塞 redis 的服务线程。而是渐进的，分屡次的。
以下是哈希表渐进式 rehash 的具体步骤：

1. 为 ht[1] 调配空间，让字典同时持有 ht[0] 和ht[1]两个哈希表。
2. 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为 0，示意 rehash 工作正式开始。
3. 在 rehash 进行期间，每次对字典执行增加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表该索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作实现之后，程序将 rehashidx 属性的值增一。
4. 随着字典操作的一直执行，最终在某个工夫点上，ht[0]的所有键值对都会被 rehash 至ht[1]，这时程序将 rehashidx 属性的值设为 -1，示意 rehash 操作已实现。

渐进式 rehash 的益处在于它采取分而治之的形式，将 rehash 键值对所需的计算工作均摊到对字典的每个增加、删除、查找和更新操作上，从而防止了集中式 rehash 而带来的宏大计算量。
因为在进行渐进式 rehash 的过程中，字典会同时应用 ht[0]和 ht[1]两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典外面查找一个键的话，程序会先在 ht[0]外面进行查找，如果没找到的话，就会持续到 ht[1]外面进行查找，诸如此类。
另外，在渐进式 rehash 执行期间，新增加到字典的键值对一律会被保留到 ht[1]外面，而 ht[0]则不再进行任何增加操作，这一措施保障了 ht[0]蕴含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。
这里有个问题了，能操作到的能够迁徙，如果某个索引的地位的数据始终用不到，岂不是永远也迁徙不了了吗？

总结

字典被宽泛用于实现 Redis 的各种性能，其中包含数据库和哈希
键。

• Redis 中的字典应用哈希表作为底层实现，每个字典带有两个哈希表，一个平时应用，另一个仅在进行 rehash 时应用。
• 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 应用 MurmurHash2 算法来计算键的哈希值。
• 哈希表应用链地址法来解决键抵触，被调配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对哈希表进行扩大或者膨胀操作时，程序须要将现有哈希表蕴含的所有键值对 rehash 到新哈希表外面，并且这个 rehash 过程并不是一次性地实现的，而是渐进式地实现的

跳跃表

跳跃示意一种有序的数据结构。通过在每个节点中维持多个指向其余节点的指针，实现快速访问。

最右边是 zskiplist 构造：

• header：指向跳跃表的表头节点。
• tail：指向跳跃表的表尾节点。
• level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
• length：记录跳跃表的长度，也即是，跳跃表目前蕴含节点的数量（表头节点不计算在内）。

前面的是 zskiplistNode 构造：

• 层（level）：节点中用 L1、L2、L3 等字样标记节点的各个层，L1 代表第一层，L2 代表第二层，以此类推。每个层都带有两个属性：后退指针和跨度。后退指针用于拜访位于表尾方向的其余节点，而跨度则记录了后退指针所指向节点和以后节点的间隔。在下面的图片中，连线上带有数字的箭头就代表后退指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，拜访会沿着层的后退指针进行。
• 后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于以后节点的前一个节点。后退指针在程序从表尾向表头遍历时应用。
• 分值（score）：各个节点中的 1.0、2.0 和 3.0 是节点所保留的分值。在跳跃表中，节点按各自所保留的分值从小到大排列。
• 成员对象（obj）：各个节点中的 o1、o2 和 o3 是节点所保留的成员对象。

跳跃表节点构造

typedef struct zskiplistNode {
 // 层
 struct zskiplistLevel {
 // 后退指针
 struct zskiplistNode *forward;
 // 跨度
 unsigned int span;
 } level[];
 // 后退指针
 struct zskiplistNode *backward;
 // 分值
 double score;
 // 成员对象
 robj *obj;
} zskiplistNode;

层：层是一个数组，在创立节点的时候会随机调配一个 1~32 之间的值作为该节点的层数组大小。
层中的后退指针：用来连贯下一个节点的同一层，如果下一个节点没有该层，就跳过。
层中的跨度：这个属性次要是用来计算排位，就是从头结点到指标节点通过了几步。

后退指针：用于从后向前遍历的
分值：跳跃表的节点是依照分值的大小从小到大排序的。
成员对象：和分值成对呈现的数据

跳跃表构造

typedef struct zskiplist {
 // 表头节点和表尾节点
 structz skiplistNode *header, *tail;
 // 表中节点的数量
 unsigned long length;
 // 表中层数最大的节点的层数
 int level;
} zskiplist;

跳跃表的构造很简略，记录了节点个数，最大层数，表头，表位指针。

总结

• 跳跃表是有序汇合的底层实现之一。
• Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个构造组成，其中 zskiplist 用于保留跳跃表信息（比方表头节点、表尾节点、长度），而 zskiplistNode 则用于示意跳跃表节点。
• 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
• 在同一个跳跃表中，多个节点能够蕴含雷同的分值，但每个节点的成员对象必须是惟一的。
• 跳跃表中的节点依照分值大小进行排序，当分值雷同时，节点依照成员对象的大小进行排序。

整数汇合

整数汇合，顾名思义：一个汇合中只有整数。是 redis 汇合数据结构的一种优化，条件是，保留的数据是整数，同时，数据的个数不多。

构造

typedef struct intset {
 // 编码方式
 uint32_t encoding;
 // 汇合蕴含的元素数量
 uint32_t length;
 // 保留元素的数组
 int8_t contents[];} intset;

encoding: 数据类型；length: 元素个数；contents：数组外面的对象是依照从小打到的顺序存储的，并且没有反复元素。
元素数组标记为 int8_t，理论它并不存储 int8_t 的值，真正类型取决于 encoding 属性。

• 如果 encoding 属性的值为 INTSET_ENC_INT16，那么 contents 就是一个
  int16_t 类型的数组，数组里的每个项都是一个 int16_t 类型的整数值（最小值
  为 -32768，最大值为 32767）。
• 如果 encoding 属性的值为 INTSET_ENC_INT32，那么 contents 就是一个
  int32_t 类型的数组，数组里的每个项都是一个 int32_t 类型的整数值（最小值
  为 -2147483648，最大值为 2147483647）。
• 如果 encoding 属性的值为 INTSET_ENC_INT64，那么 contents 就是一个
  int64_t 类型的数组，数组里的每个项都是一个 int64_t 类型的整数值（最小值
  为 -9223372036854775808，最大值为 9223372036854775807）。

降级

每当咱们要将一个新元素增加到整数汇合外面，并且新元素的类型比整数汇合现有所有元素的类型都要长时，整数汇合须要先进行降级（upgrade），而后能力将新元素增加到整数汇合外面。
降级整数汇合并增加新元素共分为三步进行：
1）依据新元素的类型，扩大整数汇合底层数组的空间大小，并为新元素调配空间。
2）将底层数组现有的所有元素都转换成与新元素雷同的类型，并将类型转换后的元素搁置到正确的位上，而且在搁置元素的过程中，须要持续维持底层数组的有序性质不变。
3）将新元素增加到底层数组外面。

降级的益处：

1. 灵便，不必解放于类型；增加类型不同的，也会自定适应新元素。
2. 节约内存。多大的数据开拓多大的内存，不会一开始就开拓到最大。

留神：不反对降级

总结

• 整数汇合是汇合键的底层实现之一。
• 整数汇合的底层实现为数组，这个数组以有序、无反复的形式保留汇合元素，在有须要时，程序会依据新增加元素的类型，扭转这个数组的类型。
• 降级操作为整数汇合带来了操作上的灵活性，并且尽可能地节约了内存。
• 整数汇合只反对降级操作，不反对降级操作。

压缩列表

留神，压缩列表并不是一种数据结构，它是一中存储构造。实质是间断的内存块 。
它是列表和哈希键的底层实现构造之一。条件是数量小，数据要么是整数，要么是短的字符串。

构造

• 列表 zlbytes 属性，示意压缩列表的总长为 80 字节。
• 列表 zltail 属性，示意头结点到尾结点的偏移量。如果咱们有一个指向压缩列表起始地址的指针 p，那么只有用指针 p 加上偏移量 60，就能够计算出表尾节点的地址。
• 列表 zllen 属性，示意压缩列表中节点的个数。
• 列表 entryX 属性，示意压缩列表的节点对象。
• 列表 zlend 属性，示意压缩列表的末端标记。

压缩列表节点的构造

（1）previous_entry_length：保留的是前一个节点的占用的字节数。
如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节：前一节点的长度就保留在这一个字节外面。
如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性的长度为 5 字节：其中属性的第一字节会被设置为 0xFE（十进制值 254），而之后的四个字节则用于保留前一节点的长度。
该属性还有一个作用，能够计算出前一个节点的地位。因为曾经中转了长度，即即内存的偏移量。

（2）encoding：编码，示意数据的类型；保留的数据能够是字节数组还能够是整数。编码是不一样的。

（3）content：保留的数据，字节数组或者整数

数据保留的是字节数组：

数据是整数：

连锁更新

压缩列表节点中有个属性是previous_entry_length, 并不是一个定长度。如果插入一个节点，该节点的长度大于 254 了，那么前面的节点将更新从新分配内存，占 5 个字节的长度。如果这个节点大超过了 254, 前面的节点也会反复该操作。这连串的扩大内存，称为连锁更新。

会造成性能的影响吗？影响不大，起因是：触发的条件，其实很刻薄，在 254 左右的长度，另外，只有数据量小的时候才会应用压缩列表。所以数据量小，扩大内存耗费不大。

总结

• 压缩列表是一种为节约内存而开发的程序型数据结构。
• 压缩列表被用作列表键和哈希键的底层实现之一。
• 压缩列表能够蕴含多个节点，每个节点能够保留一个字节数组或者整数值。
• 增加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作呈现的几率并不高。

对象

之前介绍了 redis 中的几种底层数据结构，redis 并没有间接应用这些实现数据库，而是又封装了一层为 redis 对象，就如同哈希表的构造一样，并没有间接只用哈希表dictht，而是再一次封装为了dict 。

redis 对象

构造

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

type: 示意对象的类型，encoding: 示意编码，即底层的数据结构类型；*ptr: 数据

type 类型

redis 对象的类型：

应用 Type 命令能够查看该对象的类型

# 
键为字符串对象，值为字符串对象
redis> SET msg "hello world"
OK
redis> TYPE msg
string
# 
键为字符串对象，值为列表对象
redis> RPUSH numbers 1 3 5
(integer) 6
redis> TYPE numbers
list
# 
键为字符串对象，值为哈希对象
redis> HMSET profile name Tom age 25 career Programmer
OK
redis> TYPE profile
hash
# 
键为字符串对象，值为汇合对象
redis> SADD fruits apple banana cherry
(integer) 3
redis> TYPE fruits
set
# 
键为字符串对象，值为有序汇合对象
redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3
redis> TYPE price
zset

不同的对象对应不同的类型

留神：type key 这种命令不是查看的键的类型，而是查看的是值的类型。

encoding 编码

编码的作用是标注底层实现：

之前介绍的都是底层实现，而具体到对象用的是那种数据结构，就是 encoding 决定的了。

和类型的对应关系：

同样能够应用命令，查看对象的编码

redis> SET msg "hello wrold"
OK
redis> OBJECT ENCODING msg
"embstr"
redis> SET story "long long long long long long ago ..."
OK
redis> OBJECT ENCODING story
"raw"
redis> SADD numbers 1 3 5
(integer) 3
redis> OBJECT ENCODING numbers
"intset"
redis> SADD numbers "seven"
(integer) 1
redis> OBJECT ENCODING numbers
"hashtable"

为什么一种类型有多中底层实现呢？这是 redis 做的优化。在特定状况下应用特定的构造效率更高，就如同现实生活中，去左近超市买货色，走着就行了，要是到市里办事，就要开车了，要是跨省，就要飞机或者火车了。依据须要抉择开销小的，没必要去超市间接抉择开车。

字符串对象

字符串的底层实现有三种，上面具体看下具体的实现。

int

如果保留的值是数值，并且是 long 范畴内的，那么将会应用 int 编码存储。

raw

如果保留的是字符串，长度是是大于 32 字节的，那么采纳 raw 编码。

embstr

这种状况是存小长度的字符串，或者是 long 范畴之外的数值型。

raw 和 embstr 的区别

raw 有两次分配内存的操作，调配 redis 对象，调配 sds 对象；embstr 只有一次内存调配，redis 对象和 sds 对象是间断的内存空间。这样的益处就是快，效率高，调配和开释都只有一次，另外，因为是间断的空间，内存利用率更高了。

留神：只有整数，还需是 long 范畴内的能力用 int 编码，如果是浮点型的，会应用 embstr 编码。也就是说浮点型会以字符串的模式保留，之后转换为浮点型进行操作，之后又转换为字符串存储。

类型间的转换

int 编码的值追加字符串悔恨转换为 raw 编码
embstr 编码的字符串是没有操作方法的，须要转换为 raw 才能够。能够认为 embstr 编码是只读的。

总结

列表对象

列表对象的底层是压缩表或者是链表。

压缩表

应用压缩表的时候，每一个 entryNode 里保留一个数据。这里我想到了 three 这个字符串并不是 sds 构造，只是字节数组，因为压缩表节点中的 content 只能保留数值或者字节数组。

链表

留神：这里的 string 对象曾经介绍过了，是 redis 对象 +sds 对象。

转换条件

• 列表对象保留的 所有 字符串元素的长度 都小于 64 字节；
• 列表对象保留的元素数量 小于 512 个；
• 不能满足这两个条件的列表对象须要应用 linkedlist 编码。

哈希对象

哈希对象的底层是亚索表或者是字典

压缩表

当底层是压缩表时，键值对的间断存储的。

字典

留神字典的键和值都是字符串对象。并非字节数组。这一点肯定要分清。

转换条件

和列表的转换条件统一。

• 列表对象保留的 所有 字符串元素的长度 都小于 64 字节；
• 列表对象保留的元素数量 小于 512 个；

汇合对象

汇合对象底层是哈希表或者数组汇合

数组汇合

哈希表

应用哈希表，键保留的是数据，键值则是 null.

转换条件

当汇合对象能够同时满足以下两个条件时，对象应用 intset 编码：

• 汇合对象保留的所有元素都是整数值；
• 汇合对象保留的元素数量不超过 512 个。

不能满足这两个条件的汇合对象须要应用 hashtable 编码。

有序汇合对象

有序汇合对象应用的压缩表或者跳跃表和字典的组合。

压缩表

压缩表作为底层构造的时候是如何维持分数的从小到大的程序呢？新退出一个数据，怎么调配的？这个不懂了

跳跃表和字典的组合

redis 在跳跃表和字典的根底上有封装了一层。zset 对象。

typedef struct zset {
 zskiplist *zsl;
 dict *dict;
} zset;

跳跃表保障了数据的有序性，字典保障了取分数时的复杂度是 O(1)。

转换条件

当有序汇合对象能够同时满足以下两个条件时，对象应用 ziplist 编码：

• 有序汇合保留的元素数量小于 128 个；这个条件和下面的不一样，其余的是 512 个。
• 有序汇合保留的所有元素成员的长度都小于 64 字节；

不能满足以上两个条件的有序汇合对象将应用 skiplist 编码。

其余方面

对于 redis 命令的思考

客户端执行一个命令，redis 服务端进行对应的操作，底层其实就是调用对象的办法。对于一个对象而言，底层的构造实现是不同的，不同的实现有雷同的性能，比方列表的获取长度命令：LLen，列表的底层可能是亚索表或者是链表，每个构造都实现了返回长度的办法。

内存回收

redis 实现了本人的内存回收器。还记得对象的构造吗？还有一个属性用来援用计数。

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

当对象创立的时候，初始化为 1，之后每被援用一次，该值就会加一，不再被援用就会被减一，等到值为 0，就能够开释该对象。

共享对象

留神只有保留了整数的字符串对象是奉献的，保留了字符串的字符串对象不是共享的。

为什么是这样的呢？因为共享对象，就示意该数据是一样的，验证数据可能是 O(n)。尽管内存共享能够节俭内存，然而受限于 CPU 的工夫。

总结

• Redis 数据库中的每个键值对的键和值都是一个对象。
• Redis 共有字符串、列表、哈希、汇合、有序汇合五种类型的对象，每种类型的对象至多都有两种或以上的编码方式，不同的编码可，以在不同的应用场景上优化对象的应用效率。
• 服务器在执行某些命令之前，会先查看给定键的类型是否执行指定的命令，而查看一个键的类型就是查看键的值对象的类型。
• Redis 的对象零碎带有援用计数实现的内存回收机制，当一个对象不再被应用时，该对象所占用的内存就会被主动开释。
• Redis 会共享值为 0 到 9999 的字符串对象。
• 对象会记录本人的最初一次被拜访的工夫，这个工夫能够用于计算对象的空转工夫。