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

我们知道Redis支持五种数据类型，

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

<code>/*</code>

<code> </code><code>* Redis 对象</code>

<code> </code><code>*/</code>

<code>typedef</code> <code>struct</code> <code>redisObject {</code>

<code>    </code><code>// 类型</code>

<code>    </code><code>unsigned type:4;</code>

<code>    </code><code>// 对齐位</code>

<code>    </code><code>unsigned notused:2;</code>

<code>    </code><code>// 编码方式</code>

<code>    </code><code>unsigned encoding:4;</code>

<code>    </code><code>// LRU 时间（相对于 server.lruclock）</code>

<code>    </code><code>unsigned lru:22;</code>

<code>    </code><code>// 引用计数</code>

<code>    </code><code>int</code> <code>refcount;</code>

<code>    </code><code>// 指向对象的值</code>

<code>    </code><code>void</code> <code>*ptr;</code>

<code>} robj;</code>

其中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的底层数据结构有以下几种：

简单动态字符串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值：

<code>redis:6379&gt;</code><code>set</code> <code>strtest 1</code>

<code>OK</code>

<code>redis:6379&gt; OBJECT ENCODING strtest</code>

<code>"int"</code>

<code>redis:6379&gt;</code><code>set</code> <code>strtest blog</code>

<code>"raw"</code>

　　

列表的底层实现有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_SKIPLIST

跳跃表在 Redis中的使用，就是实现有序集合数据类型。