1.Redis数据结构与对象

1.1 简单动态字符串

Redis 没有直接使用 C 语言传统的字符串表示(以空字符结尾的字符数组，以下简称 C 字符串)， 而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将 SDS 用作 Redis 的默认字符串表示.

• Redis 只会使用 C 字符串作为字面量,在大多数情况下,Redis 使用 SDS (Simple Dynamic String,简单动态字符串)作为字符串表示.
• 比起 C 字符串， SDS 具有以下优点：
  1. 常数复杂度获取字符串长度.
  2. 杜绝缓冲区溢出.
  3. 减少修改字符串长度时所需的内存重分配次数.
  4. 二进制安全.
  5. 兼容部分 C 字符串函数.

1.2 链表

• 链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器， 等等。
• 每个链表节点由一个 listNode 结构来表示， 每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis 的链表实现是双端链表。
• 每个链表使用一个 list 结构来表示， 这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
• 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
• 通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。
• 一个列表最多可以包含 2^32 - 1 个元素 (4294967295, 每个列表超过40亿个元素)

1.3 字典

• 字典被广泛用于实现 Redis 的各种功能， 其中包括数据库和哈希键。
• Redis 中的字典使用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时使用， 另一个仅在进行 rehash 时使用。
• 当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
• 哈希表使用链地址法来解决键冲突， 被分配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。
• Redis中每个hash可以存储 2^32 - 1 键值对(40多亿)

1.4 跳跃表

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

1.5 整数集合

• 整数集合是集合键的底层实现之一。
• 整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素， 在有需要时， 程序会根据新添加元素的类型， 改变这个数组的类型。
• 升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存。
• 整数集合只支持升级操作， 不支持降级操作。

1.6 压缩列表

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

1.7 对象

• Redis 数据库中的每个键值对的键和值都是一个对象。
• Redis 共有字符串、列表、哈希、集合、有序集合五种类型的对象， 每种类型的对象至少都有两种或以上的编码方式， 不同的编码可以在不同的使用场景上优化对象的使用效率。
• 服务器在执行某些命令之前， 会先检查给定键的类型能否执行指定的命令， 而检查一个键的类型就是检查键的值对象的类型。
• Redis 的对象系统带有引用计数实现的内存回收机制， 当一个对象不再被使用时， 该对象所占用的内存就会被自动释放。
• Redis 会共享值为 0 到 9999 的字符串对象。
• 对象会记录自己的最后一次被访问的时间， 这个时间可以用于计算对象的空转时间。