redis_5种数据结构及其底层实现原理详解

浅浅的花香味﹌ 2024-03-23 15:05 109阅读 0赞

## 1、 redis中的数据结构 ##

> Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（无序集合）及zset(有序集合)  
> ![在这里插入图片描述][d7507f2072ae4ebb9a8ed09604060b72.png]  
> 在秒杀项目里，我用过redis的Set和Hash结构：

> String：一个 key 对应一个字符串，string是Redis 最基本的数据类型。（字节的abase框架只实现了redis的string数据结构，导致我们如果想要存储复杂的数据结构的时候，只能转成json格式的字符串来存储）  
> list：一个 key 对应一个字符串列表，底层使用双向链表实现，很多双向链表支持的操作它都支持。  
> Hash：  
> ![在这里插入图片描述][a31bd1a9fb4c464599005197436ad436.png]

> Set：比如一个Set的实例：A = \{‘a’, ‘b’, ‘c’\}，A是集合的key，‘a’, 'b’和‘c’是集合的member。无序、无重复元素。  
> SortedSet：在set的基础上加上一个分数score，set里面的数据是有序的。

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

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

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

> SDS 相比C 字符串的优势：

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

## 4、 list ##

> 使用双向链表来实现。  
> ![在这里插入图片描述][9368cab3759a43d7a8b6f9452abb0446.png]

## 5、hash ##

> hash结构里其实是一个字典，有许多的键值对（类似于python的dict类型）。  
> redis的哈希表是一个dictht结构体：  
> typedef struct dictht \{  
> dictEntry \*\*table;//哈希表数组  
> unsigned long size;//哈希表大小  
> unsigned long sizemask;//哈希表大小掩码，用于计算索引值  
> unsigned long used;//该哈希表已有节点的数量  
> \}

![在这里插入图片描述][e5dd0fba995d4d7687a835fd137f6e4b.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结束。  
> ————————————————

## 6、set ##

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

> intset  
> 只有当数据全是整数值，而且数量少于512个时，才使用intset，intset是一个由整数组成的有序集合，可以进行二分查找。  
> ![在这里插入图片描述][185b921aa86145af808c8fa8a7441580.png]  
> 字典  
> 不满足intset使用条件的情况下都使用字典（拉链法），使用字典时把value设置为null。  
> ![在这里插入图片描述][aefa1d948abf4190ba7dcc848ede6fe0.png]

## 7、 zset ##

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

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

> zset底层实现原理：  
> ![在这里插入图片描述][1728156ceb3e4903b72cdbf97325dc76.png]

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

[d7507f2072ae4ebb9a8ed09604060b72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/b0990b9f9ba4483b8741415ffe8010b8.png
[a31bd1a9fb4c464599005197436ad436.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/7cafe8c75c684c15a77de8a3fba773e8.png
[9368cab3759a43d7a8b6f9452abb0446.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/126f4791b9fb4674a78cf2b33041b874.png
[e5dd0fba995d4d7687a835fd137f6e4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d0cf166999834867b45e6e448a8d2c9f.png
[185b921aa86145af808c8fa8a7441580.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/be97bf68549d48168b5f7167288706e5.png
[aefa1d948abf4190ba7dcc848ede6fe0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/489781d1e9414b80b1eb04b73087c9d2.png
[1728156ceb3e4903b72cdbf97325dc76.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/1fb203d2bd6c460e83b800194d87338d.png