【redis】redis的5种数据结构及其底层实现原理

男娘i 2023-10-12 16:52 62阅读 0赞

#### 文章目录 ####

*  redis中的数据结构
 *  redis数据结构底层实现
 *   *  string
     *  list
     *  hash
     *  set
     *   *  intset
         *  字典
     *  zset
     *   *  跳表插入删除过程

## redis中的数据结构 ##

Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（无序集合）及zset(有序集合)。

![在这里插入图片描述][a99c6ab6766641cbb17cffbb7f5c96a5.png]

在秒杀项目里，我用过redis的Set和Hash结构：

*  String：一个 key 对应一个字符串，string是Redis 最基本的数据类型。（字节的abase框架只实现了redis的string数据结构，导致我们如果想要存储复杂的数据结构的时候，只能转成json格式的字符串来存储）
 *  list：一个 key 对应一个字符串列表，底层使用双向链表实现，很多双向链表支持的操作它都支持。
 *  Hash：
 *  Set：比如一个Set的实例：A = \{‘a’, ‘b’, ‘c’\}，A是集合的key，‘a’, 'b’和‘c’是集合的member。无序、无重复元素。
 *  SortedSet：在set的基础上加上一个分数score，set里面的数据是有序的。

## redis数据结构底层实现 ##

### string ###

使用一种叫`简单动态字符串（SDS）的数据类型`来实现。

/*  
     * 保存字符串对象的结构  
     */  
    struct sdshdr {
          
        int len;  // buf 中已占用空间的长度  
        int free;  // buf 中剩余可用空间的长度
        char buf[];  // 数据空间  
    };

SDS 相比C 字符串的优势：

*  SDS保存了字符串的长度，而C字符串不保存长度，需要遍历整个数组（找到’\\0’为止）才能取到字符串长度。
 *  修改SDS时，检查给定SDS空间是否足够，如果不够会先拓展SDS 的空间，防止缓冲区溢出。C字符串不会检查字符串空间是否足够，调用一些函数时很容易造成缓冲区溢出（比如strcat字符串连接函数）。
 *  SDS预分配空间的机制，可以减少为字符串重新分配空间的次数。

### list ###

`使用双向链表来实现`。

![在这里插入图片描述][9f279bd4c29543d79801fb02e9e335f7.png]

### hash ###

hash结构里其实是一个字典，有许多的键值对（类似于python的dict类型）。

redis的哈希表是一个dictht结构体：

typedef struct dictht {
        
       dictEntry **table;//哈希表数组   
       unsigned long size;//哈希表大小  
       unsigned long sizemask;//哈希表大小掩码，用于计算索引值
       unsigned long used;//该哈希表已有节点的数量
    }

![在这里插入图片描述][ef89e8687eaf4969b90c266c58208339.png]

哈希表节点的结构体如下：

typeof struct dictEntry{
          
       void *key;//键
       union{
          //不同键对应的值的类型可能不同，使用union来处理这个问题
          void *val;
          uint64_tu64;
          int64_ts64;
       }
       struct dictEntry *next;
    }

其中解决哈希冲突的方法是拉链法。

为了让哈希表的装载因子维持在一个合理的范围之内，需要对哈希表的大小进行扩展或者收缩，这叫做rehash。字典中总共有两个哈希表dictht结构体，ht\[0\]用来存储键值对，ht\[1\]用于rehash时暂存数据，平时它指向的哈希表为空，需要扩展或者收缩ht\[0\]的哈希表时才为它分配空间。

比如扩展哈希表，就是为ht\[1\]分配一块大小为ht\[0\]两倍的空间，然后把ht\[0\]的数据通过rehash的方式全部迁移到ht\[1\]，最后释放ht\[0\]，使ht\[1\]成为ht\[0\]，再为ht\[1\]分配一个空哈希表。收缩哈希表类似。

渐进式rehash：redis并不是专门找时间一次性地进行rehash，而是渐进地进行，rehash期间不影响外部对ht\[0\]的访问，要求修改字典时要把对应数据同步到ht\[1\]中，全部数据转移完成时，rehash结束。

### set ###

set可以用intset或者字典实现。

#### intset ####

只有当数据全是整数值，而且数量少于512个时，才使用intset，intset是一个由整数组成的有序集合，可以进行二分查找。

![在这里插入图片描述][ae4a7e79962947ce87a86719bc9cd27e.png]

#### 字典 ####

不满足intset使用条件的情况下都使用字典（拉链法），使用字典时把value设置为null。

![在这里插入图片描述][e6c36708ccf04fc4accb0274da6cbe1e.png]

### zset ###

zset中的每个元素包含数据本身和一个对应的分数(score)。

经典例子：一个zset的key是"math"，代表数学课的成绩，然后可以往这个key里插入很多数据。输入数据的时候，每次需要输入一个姓名和一个对应的成绩。那么这个姓名就是数据本身，成绩就是它的score。

zset的数据本身不允许重复，但是score允许重复。

zset底层实现原理：

1.  数据少时，使用ziplist：ziplist占用连续内存，每项元素都是（数据+score）的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大的数据（long long），就多用一些字节来存储，而对于小的数据（short），就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。
2.  数据多时，使用字典+跳表：  
    ![在这里插入图片描述][44f4f310df2a4392a4ebdd4e37d0ead1.png]

字典用来根据数据查score，跳表用来根据score查找数据（查找效率高）。

理论上来讲，查找、插入、删除以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样的。

redis使用跳表而不是红黑树的原因：

1.  按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn)时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了。
2.  相比于红黑树，跳表还具有代码更容易实现、可读性好、不容易出错、更加灵活等优点。
3.  插入、删除时跳表只需要调整少数几个节点，红黑树需要颜色重涂和旋转，开销较大。

#### 跳表插入删除过程 ####

跳表是基于一条有序单链表构造的，通过构建索引提高查找效率，空间换时间，查找方式是从最上面的链表层层往下查找，最后在最底层的链表找到对应的节点：

![在这里插入图片描述][0cf310aae0464b09b7715fb0311eff53.png]

*  插入：逐层查找位置，然后插入到最底层链表。注意需要维护索引与原始链表的大小平衡，如果底层结点大量增多了，索引也相应增加，避免出现两个索引之间结点过多的情况，查找效率降低。同理，底层结点大量减少时，索引也相应减少。
 *  删除：如果这个结点在索引中也有出现，那么除了要删除原始链表中的结点，还要删除索引中的这个结点。
    
    跳表查找的时间复杂度为O(log(n))。索引占用的空间复杂度为 O(n)。
 *  时间复杂度：时间复杂度 = 索引的层数 \* 每层索引遍历元素的个数。
    
    首先看索引层数，假设每两个节点抽一个出来作为上一级索引的结点，而且最高一级索引有3个节点，则索引层数为log2(n)。
    
    然后看每层遍历多少个元素，首先最高层最多遍历3个节点，就能往下走了，同理，次高层也最多遍历三个节点，就能往下走。取平均之后，可以认为每层遍历2个节点。
    
    因此时间复杂度=2log2(n)，同理，如果是每k个节点取一个索引的话，就是klogk(n)
 *  空间复杂度：也是以每两个节点取一个索引为例，第一层n个节点，第二层n/2，第三次n/4，等比序列求和，或者取极限，可以认为索引节点数量无限接近于n，所以空间复杂度为O(n)。

[a99c6ab6766641cbb17cffbb7f5c96a5.png]: https://img-blog.csdnimg.cn/a99c6ab6766641cbb17cffbb7f5c96a5.png
[9f279bd4c29543d79801fb02e9e335f7.png]: https://img-blog.csdnimg.cn/9f279bd4c29543d79801fb02e9e335f7.png
[ef89e8687eaf4969b90c266c58208339.png]: https://img-blog.csdnimg.cn/ef89e8687eaf4969b90c266c58208339.png
[ae4a7e79962947ce87a86719bc9cd27e.png]: https://img-blog.csdnimg.cn/ae4a7e79962947ce87a86719bc9cd27e.png
[e6c36708ccf04fc4accb0274da6cbe1e.png]: https://img-blog.csdnimg.cn/e6c36708ccf04fc4accb0274da6cbe1e.png
[44f4f310df2a4392a4ebdd4e37d0ead1.png]: https://img-blog.csdnimg.cn/44f4f310df2a4392a4ebdd4e37d0ead1.png
[0cf310aae0464b09b7715fb0311eff53.png]: https://img-blog.csdnimg.cn/0cf310aae0464b09b7715fb0311eff53.png