Redis 底层数据结构介绍

Redis 底层数据结构

版本：2.9

支持的数据类型：

1. 字符串
2. 散列
3. 列表
4. 集合
5. 有序集合

字符串

Redis 利用原生的 c 字符串进行了一次封装。封装的字符串叫做简单动态字符串：SDS(simple dynamic string)

Redis 使用的简单动态字符串比 c 语言原生的字符串有以下优点：

1. 获取字符串长度的复杂度为O(1)
2. 不存在缓存区溢出
3. 修改字符串长度时，不需要频繁分配内存
4. 空间预分配策略
5. 惰性空间策略
6. 二进制安全
7. 二进制安全的意思是，可以将二进制数据使用 SDS 存储，而不会存在 c 语言中，遇到 \0 是字符串结尾的情况。
8. 兼容部分 c 字符串函数
9. 因为 SDS 遵循 c 语言以 \0 结尾的惯例，所以 SDS 可以使用 <string.h> 函数库，避免了重复代码

链表

链表作为最常用的数据结构之一，在 redis 中的使用场景是很多的，其中包括：

1. 发布、订阅
2. 列表键
3. 慢查询
4. 监视器
5. 多个客户端状态
6. 客户端缓冲区

Redis 中链表的几个特性：

1. 双向链表
2. 无环
3. 有表头和表尾指针
4. 有链表长度计数器
5. 多态（可以用来保存不同类型的值）

字典

字典又叫符号表，在 PHP 中叫关联数组，在 JAVA 中叫映射（map），在 Python 中叫字典（dict）。别管这么多叫法，字典就是一种保存键值对的一种数据结构。

使用场景

1. 散列（hash）
2. Redis 数据库

字典实现

Redis 使用 c 语言构建了自己的字典实现。hash 算法使用的是 murmurhash3 算法。遇到键的 hash 值冲突使用的解决方法是链地址法。当需要扩展时，Redis 利用两个哈希表进行渐进式的 rehash。

字典（内部的哈希表）扩展与收缩条件

哈希表内部会通过公式计算一个负载因子。公式为：

load_factor=ht[0].used/ht[0].Size

扩展条件：

1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于1。
2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于5。

收缩条件：负载因子小于 0.1

跳跃表

跳跃表的结构：

跳跃表是一种对标平衡树的一种数据结构。但是比平衡树更简单、更快速、使用更少空间。所以一般都会使用跳跃表。

跳跃表在 Redis 中的使用场景暂时仅限于实现有序集合。

跳跃表的实现参见： http://blog.jobbole.com/111731/

整数集合

整数集合的使用场景为元素不多且只包含整数元素的集合。

使用 c 数组实现。

压缩列表（ziplist）

压缩列表是 Redis 为了节省内存实现的。当列表键和哈希键的项比较少，并且存储的值比较小时，会使用压缩列表节省内存。