Redis数据结构与对象

你的名字 2023-07-12 14:28 38阅读 0赞

# **一、redis的数据结构** #

## 1、简单动态字符串 ##

“Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组，以下简称C字符串），而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。”

比如：set msg "hello",那么Redis将在数据库中创建一个新的键值对，其中：  
·键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串“msg”的SDS。  
·键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串“hello”的SDS

比如：rpush fruits "apple" "banana"那么Redis将在数据库中创建一个新的键值对，其中：  
·键值对的键是一个字符串对象，对象的底层实现是一个保存了字符串“fruits”的SDS。  
·键值对的值是一个列表对象，列表对象包含了两个字符串对象，这两个字符串对象分别由两个SDS实现：第一个SDS保存着字符串“apple”，第二个SDS保存着字符串“banana”

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70][]

一个sds示例

free表示sds未使用的空间。len表示sds的长度  buf是一个数组，保存了相应的字符。最后一个字节保存了空字符串 "\\0"，这是因为这么做，SDS可以直接重用一部分C字符串函数库里面的函数

**好处：**

**1、可以直接获取字符串的长度，因为len记载了它的长度，而不需要去遍历字符来获取长度。**

**2、杜绝缓冲区溢出，由于sds记录这字符串未使用的空间，所以进行相应操作（字符串拼接）。空间不足就会动态扩展。而C字符串则会发生缓冲区异常（两个字符串拼接，由于空间不足，导致一个字符串的部分内容被另一个字符串覆盖）。**

**3、减少内存重分配次数，C的每次拼接字符串，缩短字符串都需要动态扩展空间或者释放空间。  而sds提供了空间预分配与惰性空间释放两种策略应对以上情况。**

**（1）****如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。**

**（2）如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。举个例子，如果进行修改之后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度将为30MB+1MB+1byte。”**

**（3）缩短字符串时，sds不会直接释放空间，而是将空余出来的空间记录起来（free），以便后面拼接时使用。**

**4、二进制安全**

**5、兼容部分c字符串函数**

**                                                                                C字符串与sds之间的区别**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 1][]

## 2、链表 ##

链表与java中的链表基本一样。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 2][]

一个链表的基本结构

dup函数用于复制链表节点所保存的值；  
free函数用于释放链表节点所保存的值；  
match函数则用于对比链表节点所保存的值和另一个输入值是否相等

## 3、字典 ##

是一种保存键值对的数据结构（相当于java里面的map）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 3][]

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数

privdata属性则保存了需要传给那些类型特定函数的可选参数

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表 一般情况下只使用ht0，ht1是在rehash时才会使用。

rehsahindex表示rehash的进度

rehash解释：对hash表进行扩容。相当于java里面的map扩容。每次扩容（收缩）时，根据相应的算法为h1设置相应大小，并将h0上的数据hash到h1上，释放h0，将h1设置为h0。

渐进式rehash：由于可能字典中存在很多的键值对，不可能一次性将其全部转移。所以在逐渐转移数据的过程中，关于redis的操作都会去查两个表，也就是h0，h1(新增的直接到h1)每转移一个值，rehashindex就➕1，全部转移完之后，rehashindex重置为-1.

## 4、跳跃表 ##

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 4][]

level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。  
length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量

每次创建一个新的跳跃表节点时，程序会根据幂次定律（越大的数出现概率越小）随机生成level数组的大小。

由于level中有指向其他节点的指针，所以层数越高的访问其他节点越快！

跳跃表中，节点都是根据score大小排序，当score值相同的时候，大对象排在后面。所以上图中o1<=o2<=o3。

## 5、整数集合 ##

集合中只包含整数元素

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 5][]

整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。  
升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。  
整数集合只支持升级操作，不支持降级操作

升级解释：

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面

升级分为三步：

1）根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。  
2）将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程         中，需要继续维持底层数组的有序性质不变。  
3）将新元素添加到底层数组里面。

## 6、压缩列表（了解） ##

由于压缩列表数据结构经常忘。所以这里不给具体的结构。了解即可

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现

·压缩列表是一种为节约内存而开发的顺序型数据结构。  
·压缩列表被用作列表键和哈希键的底层实现之一。  
·压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。  
·添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

# 二、redis的对象 #

1、字符串对象

2、列表对象

3、哈希对象

4、集合对象

5、有序集合对象

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 6][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309101458637.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200309103438769.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200309103907913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200309104533187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200309111016734.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200309111906289.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020030911314154.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDAxOTQ1,size_16,color_FFFFFF,t_70