本文主要介绍了 Redis 的 6 种数据结构：SDS、链表、字典、跳跃表、整数集合、压缩列表，和 5 种对象：字符串、列表、哈希、集合、有序集合。
一、数据结构
SDS
SDS 是对 C 字符串的封装，用于表示字符串
SDS 使用预分配的方式为字符串分配空间，free 字段表示当前未使用的空间，当字符串增长时，会优先使用未使用的空间，如果未使用的空间不足，Redis 会为 SDS 分配额外的空间。分配算法具体为：1）如果增长后的字符串长度小于 1MB，Redis 将额外分配等同于增长后的字符串长度的空间，此时 free 和 len 的大小相等；2）如果增长后的字符串长度大于 1MB，Redis 将额外分配 1MB 大小的空间。
分配后的空间不会被回收，如果字符串缩短，缩短的空间会被加入到 free 空间中。
链表
Redis 的链表是一个双向链表，它的特性如下：
- 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置和后置节点的复杂度都是 O(1)。
- 无环：表头节点的 prev 和表尾节点的 next 指针都指向 NULL。
- 带表头指针和表尾指针：通过 head 和 tail 指针获取表头和表尾节点的复杂度为 O(1)。
- 计数器：获取节点个数复杂度为 O(1)
- 多态：利用 dup（复制节点保存的值）、free(释放节点保存的值) 和 match（比较节点的值和输入的值是否相等），来实现保存不同的值。
字典
字典是一个散列表结构，使用 MurmurHash2 算法计算哈希值，使用拉链法保存哈希冲突。
Redis 的字典 dict 中包含两个哈希表 dictht，这是为了方便进行 rehash 操作。在扩容时，将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上面，完成之后释放空间并交换两个 dictht 的角色。
渐进式 rehash 通过记录 dict 的 rehashidx 完成，它从 0 开始，然后每执行一次 rehash 都会递增。例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。
在 rehash 期间，每次对字典执行添加、删除、查找或者更新操作时，都会执行一次渐进式 rehash。
采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上，因此对字典的查找操作也需要到对应的 dictht 去执行。
跳跃表
跳跃表是有序集合的底层实现之一。
跳跃表是基于多指针有序链表实现的，可以看成多个有序链表。每个跳跃表节点的层高都是 1-32 之间的随机数。
跳跃表中的节点按照分数大小排列，当分值相同时，节点按照成员对象的大小进行排序。
和通用的跳表不同的是，Redis 为每个索引节点增加了 span 字段，表示该节点和前驱节点的跨度，使得 zrank（返回元素排名） 操作效率提升（O(N)->O(logN)）。
与红黑树等平衡树相比，跳跃表具有以下优点：
- 插入速度非常快速，因为不需要进行旋转等操作来维护平衡性；
- 并发插入时只需锁住少数节点
- 支持范围查找
- 更容易实现
跳跃表的缺点：
- 重复存储分层节点，消耗内存
整数集合
整数集合是集合键的底层实现之一，它的底层是一个数组，这个数组以有序、无重复的方式保存集合元素。元素的类型可以为 int16_t,int32_t 或者 int64_t。程序会根据新添加元素的类型，改变数组中元素的类型。
encoding 表示元素的类型，数组中所有元素的类型是一样的。当有更大的数加入进来的时候，数组会进行升级操作，比如从 int16_t 升级到 int32_t。
整数集合只能升级，不能降级。
压缩列表
压缩列表被用作列表和哈希的底层实现之一，是一种为节约内存而开发的，由任意多个节点组成的顺序数据结构。每个节点可以保存一个字节数组或一个整数值。
entry1、entry2…是实际存储数据的节点，除此之外还有些字段记录列表的信息：zlbytes 记录整个压缩列表占用的内存字节数，zltail 指向压缩列表表尾节点，zllen 记录包含的节点数量，zlend 是个特殊值字段（0xFF）用于标记末端。
每个节点由 previous_entry_length、encoding、content 三部分组成。previous_entry_length 保存了前一个节点的长度，由此可以实现从表尾向表头的遍历。encoding 是个复用字段，记录了 content 的编码和长度。下图的 encoding 最高两位 00 表示节点保存的是一个字节数组，后六位 001011 记录了字节数组长度 11。content 保存着节点的值”hello world”。
二、对象
Redis 并没有使用以上的数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统。
| 对象类型 | 底层实现 | 可以存储的值 | 操作 |
|---|---|---|---|
| STRING | int，sds | 字符串、整数或者浮点数 | 对整个字符串或者字符串的其中一部分执行操作 对整数和浮点数执行自增或者自减操作 |
| LIST | 链表，压缩列表 | 列表 | 从两端压入或者弹出元素 对单个或者多个元素 进行修剪，只保留一个范围内的元素 |
| HASH | 字典，压缩列表 | 包含键值对的无序散列表 | 添加、获取、移除单个键值对 获取所有键值对 检查某个键是否存在 |
| SET | 整数集合，字典 | 无序集合 | 添加、获取、移除单个元素 检查一个元素是否存在于集合中 计算交集、并集、差集 从集合里面随机获取元素 |
| ZSET | （字典+跳跃表），压缩列表 | 有序集合 | 添加、获取、删除元素 根据分值范围或者成员来获取元素 计算一个键的排名 |
SET 对象使用整数集合保存只包含整数的集合，使用字典保存含有字符串的集合。使用字典保存集合时，字典的键是一个元素的成员，字典的值为 NULL。
ZSET 对象同时使用字典和跳跃表保存有序集合，使用字典保存有序集合时，字典的键保存了元素的成员，字典的值保存了元素的分值。ZSET 集合元素会同时共享在字典和跳跃表中（保存的是指针，不会造成数据的重复）
为什么有序集合需要同时使用字典和跳跃表来实现？
在理论上，有序集合可以单独使用字典或者跳跃表来实现。但两者都有不可替代的地方：字典可以在 O(1) 时间复杂度查找成员的分值，跳跃表可以执行范围型操作。因此为了同时获得这两个特性，Redis 使用了字典和跳跃表来实现有序集合。
关于 zrank 的时间复杂度
Redis 的 zset 提供了 zrank（返回元素排名）的功能，时间复杂度是 O(logN)。这得益于在跳表的每一个索引节点除了存储 score 外还会存储一个 span 变量用来表示该节点距离上个节点的跨度，计算某个节点的排名时只需要将查询路径上的跨度相加即可（由于记录的是跨度，所以插入时只需要修改前后两个节点的跨度，不会降低插入的时间复杂度）。
同理，如果我们要实现查找第 n 个元素，时间复杂度也是 O(logN)。