Redis不同数据类型的的数据结构实现

181次阅读

共计 3051 个字符，预计需要花费 8 分钟才能阅读完成。

我们知道 Redis 支持五种数据类型，分别是字符串、哈希表（map）、列表（list）、集合（set）和有序集合，和 Java 的集合框架类似，不同数据类型的数据结构实也是不一样的。

1.Redis 中的 redisObject 对象

Redis 是使用 C 编写的，内部实现了一个 struct 结构体 redisObject 对象，

通过结构体来模仿面向对象编程的“多态”，作为一个底层的数据支持，redisObject 代码：

/*
* Redis 对象
*/
typedef struct redisObject {
// 类型
unsigned type:4;
// 对齐位
unsigned notused:2;
// 编码方式
unsigned encoding:4;
// LRU 时间（相对于 server.lruclock）
unsigned lru:22;
// 引用计数
int refcount;
// 指向对象的值
void *ptr;
} robj;

其中 type、encoding、ptr3 个属性分别表示：
type：redisObject 的类型，字符串、列表、集合、有序集、哈希表
encoding：底层实现结构，字符串、整数、跳跃表、压缩列表等
ptr：实际指向保存值的数据结构

如果一个 redisObject 的 type 属性为 REDIS_LIST，encoding 属性为 REDIS_ENCODING_LINKEDLIST，
那么这个对象就是一个 Redis 列表，它的值保存在一个双端链表内，而 ptr 指针就指向这个双端链表；
如果一个 redisObject 的 type 属性为 REDIS_HASH，encoding 属性为 REDIS_ENCODING_ZIPMAP，
那么这个对象就是一个 Redis 哈希表，它的值保存在一个 zipmap 里，而 ptr 指针就指向这个 zipmap。

下面这张图片中的 REDIS_STRING/REDIS_LIST/REDIS_ZSET/REDIS_HASH/REDIS_SET 针对的是 redisObject 中的 type，
后面指向的 REDIS_ENCODING_LINKEDLIST 等针对的是 encoding 字段。

Redis 不同数据类型的的数据结构实现

Redis 的底层数据结构有以下几种：

Redis 的底层数据结构有以下几种：
简单动态字符串 sds(Simple Dynamic String)
双端链表 (LinkedList)
字典 (Map)
跳跃表(SkipList)

下面针对五种数据类型，学习相关的底层数据结构。

如果一个 String 类型的 value 能够保存为整数，则将对应 redisObject 对象的 encoding 修改为 REDIS_ENCODING_INT，将对应 robj 对象的 ptr 值改为对应的数值。
如果不能转为整数，保持原有 encoding 为 REDIS_ENCODING_RAW。
因此 String 类型的数据可能使用原始的字符串存储（实际为 sds – Simple Dynamic Strings，对应 encoding 为 REDIS_ENCODING_RAW）或者整数存储。

Redis 可以直接查看对象的 ENCODING 值：

redis:6379> set strtest 1
OK
redis:6379> OBJECT ENCODING strtest
“int”
redis:6379> set strtest blog
OK
redis:6379> OBJECT ENCODING strtest
“raw”

列表的底层实现有 2 种：
REDIS_ENCODING_ZIPLIST
REDIS_ENCODING_LINKEDLIST
ZIPLIST 相比 LINKEDLIST 可以节省内存，
当创建新的列表时，默认是使用压缩列表作为底层数据结构的。
Redis 内部会对相关操作做判断，
当 list 的 elem 数小于配置值: hash-max-ziplist-entries 或者 elem_value 字符串的长度小于 hash-max-ziplist-value, 可以编码成 REDIS_ENCODING_ZIPLIST 类型存储，以节约内存；
但由于在 zip list 添加和删除元素会涉及到数据移动，
因此当 list 内容较多时，使用双向链表。

创建新的 Hash 类型时，默认也使用 ziplist 存储 value，保存数据过多时，使用 hast table。

集合的底层实现也有两种：
REDIS_ENCODING_INTSET
REDIS_ENCODING_HT(字典)
创建 Set 类型的 key-value 时，如果 value 能够表示为整数，则使用 intset 类型保存 value。
数据量大时，切换为使用 hash table 保存各个 value。

有序集合的底层实现也是 2 种：
REDIS_ENCODING_ZIPLIST
REDIS_ENCODING_SKIPLIST

关于 Redis 中的跳跃表，查看这篇文章：跳跃表或 http://www.linuxidc.com/Linux/2017-12/149436.htm
跳跃表在 Redis 中的使用，就是实现有序集合数据类型。

下面关于 Redis 的文章您也可能喜欢，不妨参考下：

Ubuntu 14.04 下 Redis 安装及简单测试 http://www.linuxidc.com/Linux/2014-05/101544.htm

Redis 主从复制基本配置 http://www.linuxidc.com/Linux/2015-03/115610.htm

Redis 集群搭建与简单使用 http://www.linuxidc.com/Linux/2017-03/142210.htm

CentOS 7 下 Redis 的安装与配置 http://www.linuxidc.com/Linux/2017-02/140363.htm

Ubuntu 14.04 安装 Redis 与简单配置 http://www.linuxidc.com/Linux/2017-01/139075.htm

Ubuntu 16.04 环境中安装 PHP7.0 Redis 扩展 http://www.linuxidc.com/Linux/2016-09/135631.htm

Redis 单机 & 集群离线安装部署 http://www.linuxidc.com/Linux/2017-03/141403.htm

CentOS 7.0 安装 Redis 3.2.1 详细过程和使用常见问题 http://www.linuxidc.com/Linux/2016-09/135071.htm

Ubuntu 16.04 环境中安装 PHP7.0 Redis 扩展 http://www.linuxidc.com/Linux/2016-09/135631.htm