Redis之基本数据类型及其数据结构

男娘i 2023-02-18 14:27 15阅读 0赞

一直都有使用Redis，但是都停留在使用层面上，对其Redis的数据机构和原理并没有做过深入的研究，所以打算系统的学习一些Redis的核心知识点并记录下来。

##### redisObject数据结构 #####

redisObject 是 Redis 类型系统的核心， 数据库中的每个键、值，以及 Redis 本身处理的参数， 都表示为这种数据类型。

/*
     * Redis 对象
     */
    typedef struct redisObject {
    
        // 类型
        unsigned type:4;
    
        // 编码方式
        unsigned encoding:4;
    
        // LRU 时间
        unsigned lru:22;
    
        // 引用计数
        int refcount;
    
        // 指向对象的值
        void *ptr;
    
    } robj;

简单介绍一下这几个字段：

*  type：数据类型，就是我们熟悉的string、hash、list等。
 *  encoding：内部编码，其实就是本文要介绍的数据结构。指的是当前这个value底层是用的什么数据结构。因为同一个数据类型底层也有多种数据结构的实现，所以这里需要指定数据结构。
 *  lru：当前对象可以保留的时长，和过期时间有关。
 *  refcount：对象引用计数，用于GC。
 *  ptr：指针，指向以encoding的方式实现这个对象的实际地址。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70]  
众所周知，Redis有五种基本数据类型，分别是String、List、Hash、Set、zSet。了解了`redisObject`之后，我们逐一分析一下redis中五种基本数据类型。

##### String #####

string表示的是一个可变的字节数组，我们初始化字符串的内容、可以拿到字符串的长度，可以获取string的子串，可以覆盖string的子串内容，可以追加子串。

在Redis内部，string类型有两种底层储存结构。Redis会根据存储的数据及用户的操作指令自动选择合适的结构：

*  int：存放整数类型
 *  SDS（简单动态字符串 simple dynamic string）：存放浮点、字符串、字节类型

SDS源码如下：

typedef struct sdshdr {
        // buf中已经占用的字符长度
        unsigned int len;
        // buf中剩余可用的字符长度
        unsigned int free;
        // 数据空间
        char buf[];
    }

可见，其底层是一个char数组。buf最大容量为512M，里面可以放字符串、浮点数和字节。所以你甚至可以放一张序列化后的图片。它为什么没有直接使用数组，而是包装成了这样的数据结构呢？

因为buf会有动态扩容和缩容的需求。如果直接使用数组，那每次对字符串的修改都会导致重新分配内存，效率很低。那么string是如何扩容的呢？当字符串长度小于1M时，扩容都是加倍现有的空间，如果超过1M，扩容时一次只会多扩1M的空间。

##### list #####

Redis将列表数据结构命名为list而不是array，是因为列表的存储结构用的是链表而不是数组，而且链表还是双向链表。因为它是链表，所以随机定位性能较弱，首尾插入删除性能较优。如果list的列表长度很长，使用时我们一定要关注链表相关操作的时间复杂度。

list底层有两种数据结构：链表`linkedlist`和压缩列表`ziplist`。当list元素个数少且元素内容长度不大时，使用`ziplist`实现，否则使用`linkedlist`。

首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是`ziplist`，也即是压缩列表。它将所有的元素紧挨着一起存储，分配的是一块连续的内存。当数据量比较多的时候才会改成`linkedlist`。因为普通的链表需要的附加指针空间太大，会比较浪费空间。比如这个列表里存的只是int类型的数据，结构上还需要两个额外的指针prev和next。所以Redis将链表和`ziplist`结合起来组成了`linkedlist`。也就是将多个`ziplist`使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。

`ziplist`也是hash的底层实现之一。

typedef struct list{
        //表头节点
        listNode *head;
        //表尾节点
        listNode *tail;
        //链表所包含的节点数量
        unsigned long len;
        //节点值复制函数
        void *(*dup)(void *ptr);
        //节点值释放函数
        void *(*free)(void *ptr);
        //节点值对比函数
        int (*match)(void *ptr,void *key);
    }list;

##### hash #####

hash底层有两种实现：压缩列表（ziplist）和字典（dict）。压缩列表刚刚上面已经介绍过了，下面主要介绍一下字典的数据结构。

字典其实就类似于Java语言中的Map。与Java中的HashMap类似，Redis底层也是使用的散列表作为字典的实现，解决hash冲突使用的是链表法。Redis同样使用了一个数据结构来持有这个散列表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70 1]  
在键增加或减少时，会扩容或缩容，并且进行`rehash`，根据hash值重新计算索引值。那如果这个字典太大了怎么办呢？

为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成。当负载因子触达阈值之后，只申请新空间，但并不将老的数据搬移到新散列表中。当有新数据要插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，都重复上面的过程，经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次一次性数据搬移，插入操作就都变得很快了，这个过程也被称为`渐进式rehash`。

##### set #####

Java程序员都知道HashSet的内部实现使用的是HashMap，只不过所有的value都指向同一个对象。Redis的set结构也是一样，它的内部也使用hash结构，所有的value都指向同一个内部值。

set里面没有重复的集合。set的实现比较简单。如果是整数类型，就直接使用整数集合intset。使用二分查找来辅助，速度还是挺快的。不过在插入的时候，由于要移动元素，时间复杂度是`O(N)`。

如果不是整数类型，就使用上面在hash那一节介绍的字典。key为set的值，value为空。

##### zSet #####

zSet是可排序的set。与hash的实现方式类似，如果元素个数不多且不大，就使用压缩列表ziplist来存储。不过由于zSet包含了score的排序信息（给每一个元素value赋予一个权重score），所以在ziplist内部，是按照score排序递增来存储的。

zSet底层实现使用了两个数据结构，第一个是hash，第二个是跳跃列表，hash的作用就是关联元素value和权重score，保障元素value的唯一性，可以通过元素value找到相应的score值。跳跃列表的目的在于给元素value排序，根据score的范围获取元素列表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70 2]  
如上图所示，比如我们要查找8，先在最上层L2查找，发现在1和9之间；然后去L1层查找，发现在5和9之间；然后去L0查找，发现在7和9之间，然后找到8。

当元素比较多时，使用跳表可以显著减少查找的次数。

参考链接：[https://juejin.im/post/5b53ee7e5188251aaa2d2e16][https_juejin.im_post_5b53ee7e5188251aaa2d2e16]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200618152656694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200618224611325.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200618230303563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx,size_16,color_FFFFFF,t_70
[https_juejin.im_post_5b53ee7e5188251aaa2d2e16]: https://juejin.im/post/5b53ee7e5188251aaa2d2e16