Redis常用数据类型及其对应的底层数据结构

Redis数据库

Redis是一种键值(Key-Value)数据库。相较于MySQL之类的关系型数据库，Redis是一种非关系型数据库。Redis存储的数据只包含键和值两部分，只能通过键来查询值。这样简单的存储结构，能让Redis的读写效率非常高(HashMap读写效率都是O(1))。

除此之外，Redis主要作为内存型数据库来使用。也即是说，Redis的数据存储在内存中。尽管如此，它也支持通过持久化机制将内存中的数据保存在硬盘中。

作为一种键值数据库，Redis键的数据类型一般是字符串，值的类型则有很多中，包括字符串(String)、列表(List)、字典(Hash)、集合(Set)、有序集合(Ordered Set)。

字符串(String)

字符串即普通的字符串，单个char组成的集合。

列表(List)

Redis有两种实现方法，一种是压缩列表(ziplist)，另一种是双向循环链表。

当列表需要存储的数据量比较小的时候，就可以采用压缩列表的方式实现，具体需要满足如下两个条件：

• 列表中保存的单个数据(字符串或其他)小于64字节
• 列表中数据个数小于512个。

压缩列表

压缩列表可以看做是特殊的数组，它也是通过一片连续的存储空间来存储数据的。但与数据要求每个元素占据的空间大小一致不同，压缩列表允许存储的单个元素大小不同。

存储格式：[data_num][data1_len][data1][data2_len][data_2][...]

data_num表示了压缩列表存储的数据数目，datai_len代表第i个数据项的长度，datai则表示具体存储的数据。因为允许每个数据大小不同，所以不可避免的需要知晓每个元素的大小，这是为什么要存储每个数据的长度。

而如果我们严格按照数组的要求，每个数据的大小相同，那么我们不需要存储每个数据的长度，但这样会造成空间的浪费，如下图：

压缩列表这样存储结构，一方面节省内存，一方面允许不同类型的数据的存储，比数组灵活。因为数据仍然存储在一片连续的内存空间中，仍然按照键来获取数据，因此仍然和数据一样具有随机存取的特性。

当数据存储量比较大的时候，即上述两个条件未得到满足，那么Redis使用双向循环链表来实现List。

// Redis 采用C语言实现
typedef struct ListNode {
	struct ListNode *prev;
	struct ListNode *next;
	void *value;
}

typedef struct List {
	ListNode *head;
	ListNode *tail;
	unsigned long len;
	//...
} List

字典(hash)

字典类型用来存储一组数据对，每组数据对包含键值两部分。字典类型也对应两种实现方式，一种是压缩列表，另一种是散列表。

类似于List，当字典需要存储的数量量比较小的情况下，Redis采用压缩列表来实现。具体而言，和List的条件大致相当：

• 字典中保存的键和值的大小都小于64字节。
• 字典中的键值对数目小于512。

不能满足上述条件，即存储的数据量较大时，采用散列表来实现字典类型。

Redis实现字典的散列表采用MurmuerHash2哈希算法实现，该哈希算法有运行速度快、随机性好的特点。Redis采用链表法来解决哈希冲突。除此之外，Redis支持动态扩容、缩容。装载因子小于0.1时，会出发缩容，缩小为字典中数据个数的大约两倍；而当装载因子大于1时，会触发扩容，扩大为原来的两倍左右。扩容缩容的比例都是两倍，具体见源码

扩容缩容要做大量的数据搬移和哈希值重新计算工作，因此较耗时。Redis采用渐进式扩容缩容策略，即将扩容操作穿插在插入操作的过程中，分批完成，缩容类似。这样将其均摊时间复杂度维持在O(1)，同时避免大量数据一次性搬移导致的服务停顿。

集合(Set)

集合用来存储一组不重复的数据。Redis中集合也对应两种实现方法，一种是基于有序数组，另一种是基于散列表。

集合需要存储数据量比较小的时候，Redis采用有序数组来实现，具体条件如下：

• 存储的数据都是整数。
• 存储的数据元素不超过512。

不能满足上述条件，即存储的数据量较大时，Redis就采用散列表来存储集合中的数据。

有序集合(Ordered Set)

有序集合大多基于跳表实现(如MySQL的有序集合)。它用存储一组数据，并且每个数据附带一个得分(可以是直接的大小)，通过得分的大小，将数据组织成跳表这样的数据结构。

当存储的数据量较小时，Redis采用压缩列表来实现有序集合，条件如下：

• 所有的数据大小都小于64字节。
• 元素个数小于128。

不满足上述条件，即存储的数据量较大时，Redis就采用跳表来实现有序集合。

数据持久化

Redis虽然被当做内存数据库来使用，但遇到服务器崩溃、机器断电等极端情况时，为了快速从故障中恢复，也提供了持久化机制，具体参见Redis专题。

这里我们谈一谈实现层面。

持久化机制有两种实现思路：

1. 清除原有存储结构，只将数据存储到磁盘中。
2. 保留原来的存储格式，按原格式存储到磁盘中。

第一种方式有明显的弊端，即从硬盘还原到内存中，还需要恢复原有的数据结构(以哈希表为例，需要重新计算哈希值)，数据量非常大时，这种操作的耗时不可小觑。但Redis作为内存型数据中，一般而言存储的数据规模不会很大。

第二种方式也并非完美，按原有存储格式需要占用更多的存储空间。Redis在持久化机制的实现上，可能是每秒落盘一次或者每次操作都落盘一次，空间问题也需要考虑。

Redis选择的是第一种实现方案。

总结

Redis常用数据结构:

• String
• List
• Hash
• Set
• Ordered Set

Redis实现这些数据结构使用的底层数据结构:

• 压缩列表
• 有序数组
• 链表
• 散列表
• 跳表

在数据量比较小的情况下，采用不同的数据结构来实现，主要是出于时间和空间的考虑。数组能实现随机存取，压缩列表作为特殊的数组保留了这一特性。

但当数据量比较大时，由于数组要占用连续的存储空间，可能就不太好实现了，因为转换到了链表，同时为了保证速度采用了散列表。

参考

数据结构与算法之美