细谈Redis五大数据类型

jiezi

5 年前

文章原创于公众号：程序猿周先森。本平台不定时更新，喜欢我的文章，欢迎关注我的微信公众号。

上一篇文章有提到，Redis 中使用最频繁的有 5 种数据类型：String、List、Hash、Set、SortSet。上一篇文章只是单纯介绍了下这 5 种数据类型使用到的指令以及常用场景，本篇文章会谈谈 5 种数据类型的底层数据结构以及各自常用的操作命令来分别进行解析。Redis 作为目前最流行的 Key-Value 型内存数据库，不仅数据库操作在内存中进行，并且可定期的将数据持久化到磁盘中，所以性能相对普通数据库高很多，而在 Redis 中，每个 Value 实际上都是以一个 redisObject 结构来表示：
typedef struct redisObject{

    unsigned type:4;
    unsigned encoding:4;
    void *ptr;
    int refCount;
    unsigned lru:

}
我们可以看看这几个参数分别的含义：

type：对象的数据类型，一般情况就是 5 大数据类型。
encode：redisObject 对象底层编码实现，主要编码类型有简单动态字符串，链表，字典，跳跃表，整数集合及压缩列表。
*ptr：指向底层实现数据结构的指针。
refCount：计数器，当引用计数值为 0 将会释放对象。
lru：最后一次访问本对象的时间。

String 数据类型

String 数据结构是简单的 Key-Value 类型，是 Redis 中最常用的一种数据类型，Value 可以是 string 或者数字。String 数据类型实际上可以存储字符串、整数、浮点数三种不同类型的值，Redis 是如何做到自动识别字符串、整数、浮点数三种不同类型的值。Redis 是使用 C 实现的，但是并未使用 C 中的字符串，实际上 Redis 自己实现了一个结构体 SDS 来替代 String 类型：
struct sdshdr{

    // 记录 buf 数组中已使用字节的长度
    int len;
    // 记录 buf 数组中剩余空间的长度
    int free;
    // 字节数组，用于存储字符串
    char buf[];

};

我们可以看到 free 参数是用来判断剩余可使用空间的长度，len 表示字符串的长度，buf 存储字符串的每一个字符以及结尾的 ’0’。为什么 Redis 要自己实现 SDS 结构体呢？因为 SDS 结构体有几个优点：

由于 len 保存了当前字符串的实际长度，所以获取长度时间复杂度为 O(1)。
SDS 在拼接之前会对当前字符串的空间进行自动调整和扩展，防止当前字符串数据溢出。
减少内存分配次数，SDS 拼接字符串发生时，如果此时的字符串长度 len 小于 1M，则 SDS 会分配和 len 大小相同的未使用空间给 free，如果此时的字符串长度 len 大于 1M，则 SDS 会分配和 1M 的未使用空间给 free，当字符串缩短时，缩短的空间会叠加到 free 中，用于后续的拼接使用。

String 数据类型常用命令：

常用命令：set、get、decr、incr、mget 等。

String 数据类型适用场景：

分布式锁
分布式 session：将分布式应用 session 存储到 Redis 中
商品秒杀
常规计数：博客数，阅读数

List 数据类型

  List 数据结构是用来存储多个有序的字符串，List 中的每个字符串成为元素，List 提供了节点重排和节点顺序访问的能力，在 Redis 中，List 可以在两端 push 和 pop 元素，还可以获取指定范围的元素列表，获取指定索引下标的元素等，List 数据结构主要有 zipList(压缩链表)和 LinkedList(双向链表)两种实现方式。首先我们可以先看看 LinkedList 的结构：

type struct list{

        // 表头节点
        listNode *head;
        // 表尾节点
        listNode *tail;
        // 包含的节点总数
        unsigned long len;

};

可以看到每个 LinkedList 中都会包含一个表头节点head 和一个表尾结点tail，在 LinkedList 中每个节点都会有一个prev 指向前一个元素，同时还有一个next 指向后一个元素，每个节点的 value 就是节点的值。从而实现双向链表，理解起来实际上和 C 中的双向链表有很大程度的相似性。而另一种实现方式 zipList 是基于连续内存实现，有点类似于数组方式，但是和数组有点不一致的是 zipList 的每一个 entry 的大小可能不一致，需要特殊方法去控制解决，但是在执行 push，pop 操作时会有数据的迁移，时间复杂度为 O(n), 所以一般只有在元素较少时才会使用 zipList，我们可以看看 zipList 的结构：

type struct ziplist{

        // 整个压缩列表的字节数
        uint32_t zlbytes;
        // 记录压缩列表尾节点到头结点的字节数，直接可以求节点的地址
        uint32_t zltail_offset;
        // 记录了节点数，有多种类型，默认如下
        uint16_t zllength;
        // 节点
        List entryX;

}

zipList 中每个节点都会有以下几个参数信息：

previous_entry_length：记录前一个节点的字节长度
content：节点所存储的内容，可以是一个字节数组或者整数
encoding：记录 content 属性中所保存的数据类型以及长度

* List 数据类型适用场景

在渲染文章列表时可以使用 List 数据类型，一般情况下每个用户都会有自己发布的文章列表，如果需要展示文章列表，就可以使用 List 数据类型，不但可以有序而且可以按照索引范围去查询文章列表。

Set 数据类型

Set 数据类型和 List 数据类型有点类似，也可以用来保存多个元素，但最大的一点区别在于 Set 数据类型不允许出现重复的元素，并且 Set 中的元素是无序的，所以没办法和 List 一样通过索引下标获取元素，但是 Set 类型支持多个 Set 集合取交集、并集、差集，所以合理使用 Set 数据类型，可以在实际项目开发中解决很多问题。Set 数据类型有两种数据结构：IntSet 和 HashTable。首先我们来看看 IntSet 的结构：

typedef struct intset {

    // 编码方式
    uint32_t enconding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组 
    int8_t contents[];

} intset;

当 Set 集合中所有元素都为整型时，Redis 才会使用 IntSet 数据结构。有一点需要格外注意的是：IntSet 数据结构是有序的。因为为了减轻性能的消耗，Redis 在 Set 集合元素都为整型时，会使用一种基于动态数组的结构体，同时在 push 元素的时候控制元素的大小顺序，这样就可以使用二分查找算法来对元素进行 push 及 pop 操作，这样时间复杂度仅为 O(logN)。在 Set 集合中元素存在非整型数据时，Redis 这时会自动采用 HashTable 数据结构来存放数据，在 HashTable 中，存放的只有 key 值而没有 value 值，所以说在 HashTable 中，键值永远为 null。我们可以看下 HashTable 的结构：

typedef struct dict{

    // 类型特定函数
    dictType *type;
    // 哈希表 两个，一个用于实时存储，一个用于 rehash
    dictht ht[2];
    //rehash 索引 数据迁移时使用
    unsigned rehashidx;

}

Set 数据类型使用场景：

记录唯一值：比如登录 ip，身份证号
添加标签：可以通过标签的交并集计算用户喜好程度等数据。

Hash 数据类型
在 Redis 中哈希类型是指键本身又是一种键值对结构，也就是我们所说的对象，所以 Hash 数据类型用来存储对象是最合适的数据类型。Hash 数据类型的编码可以是 zipList 或 HashTable。当哈希对象保存的所有键值对长度小于 64 字节并且元素数量少于 512 时使用 zipList，否则使用 HashTable。zipList 与刚才 List 数据类型中讲到的 zipList 实际上基本一致，唯一区别在于 Hash 存储 entry 数量成对增加，所以长度一定为 2 的整数倍。当然，使用 zipList 刚才已经说过 push 和 pop 时间复杂度为 O(n)，所以只能在数据量少的情况下才允许使用。而 HashTable 其实有点类似于 Java 中的 HashTable，HashTTable 主要依赖于三个结构：dict、dictht、entry。三个结构的关系可以表示为如下这幅图：

Hash 数据类型适用场景：

存储对象数据。
结合 Json 描述对象集合。

SortSet 数据类型

有序集合是在 Set 集合的基础上，保留了 Set 集合中不能存在重复元素的特性，但是不同的是，SortSet 集合中元素是可以排序的，SortSet 排序和 List 排序都可以使用索引下标作为排序依据，所以说 SortSet 实现了数据有序且键值对唯一的集合，SortSet 的数据结构有两种：zipList 和 skipList + HashTable，zipList 都不用多少了，是用于数据量较少的情况，默认排序为元素从小到大。而采用 skipList + HashTable 的数据结构，skipList 会在保证集合有序的情况下优化范围查找的时间复杂性，而 HashTable 刚才已经提到过它可以优化 push 和 pop 元素时的时间复杂性。skipList 基于有序链表，可以创建多层索引，实现以空间复杂度来换取时间复杂度的做法，最终实现时间复杂度为 O(logN)的元素查询过程，当需要 push 或者 pop 元素时，则使用 HashTable 实现时间复杂度仅为 O(1).

SortSet 数据类型适用场景

积分排行榜：根据积分排序从小到大
获取某个范围的数据：考试 80-100 分的数据

欢迎关注公众号：程序员周先森