Redis 的数据结构和内部编码

Love The Way You Lie 2024-05-06 21:28 30阅读 0赞

## Redis的 5 种数据类型 ##

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

Redis 底层在实现上述数据结构的时候，会在源码层面，针对上述实现进行 特定的优化 ，来达到节省时间/节省空间效果  
特定的优化：内部的具体实现的数据结构，在特定场景下，不是其对应的标准数据结构，而是使用别的数据结构实现，不过仍然保证时间复杂度符合要求  
编码方式：redis 数据结构的底层实现  
同一个数据类型，背后可能的编码实现方式是不同的，会根据特定场景优化

## 数据类型对应的内部编码 ##

<table> 
 <thead> 
  <tr> 
   <th align="center">数据结构</th> 
   <th align="center">内部编码</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">string</td> 
   <td align="center">1.raw <br>2.embstr <br>3.int</td> 
  </tr> 
  <tr> 
   <td align="center">hash</td> 
   <td align="center">1.hashtable<br>2.ziplist</td> 
  </tr> 
  <tr> 
   <td align="center">list</td> 
   <td align="center">1.linkedlist <br> 2.ziplist</td> 
  </tr> 
  <tr> 
   <td align="center">set</td> 
   <td align="center">1.hashtable <br>2.intset</td> 
  </tr> 
  <tr> 
   <td align="center">zset</td> 
   <td align="center">1.skiplist <br>2.ziplist</td> 
  </tr> 
 </tbody> 
</table>

### String ###

#### 1. raw ####

最基本的字符串.的实现，底层是一个C++的 char数组，类似于或者Java中的 byte数组

#### 2. embstr ####

针对短字符串进行的特殊优化

#### 3. int ####

redis 用来实现一些"计数"这样的功能 ，value 为一个整数的时候，此时 redis 会直接使用 int 来保存字符串

### hash ###

#### 1. hashtable ####

最基本的哈希表

#### 2.ziplist ####

在哈希表里面元素比较少的时候，就会优化成 ziplist ，通过压缩列表，来够节省空间；  
由于元素过少，通过遍历，时间复杂度还是可以认为是 O(1)  
压缩原因：当对应的是 hash 的 key 特别多，但是每个 hash 又不大的情况下，就去压缩，压缩之后让整体占用更小的内存

### list ###

#### 1.linkedList ####

链表

#### 2.ziplist ####

压缩链表

> 从 redis 3.2 开始，引入了新的实现方式 `quicklist`，同时兼顾了linkedlist和ziplist的优点；  
> `quicklist` 就是一个链表，每个元素又是一个ziplist，把空间和效率都兼顾到；  
> `quicklist`类似于C+＋中的std:deque

### set ###

#### 1.hashtable ####

最基本的哈希表

### 2.intset ###

针对特殊常景的特殊优化，比如：当集合中存的都是整数时，就会优化为 intset

### zset ###

#### 1.skiplist ####

skiplist：跳表

跳表也是链表，不同于普通的链表，每个节点上有多个指针域；  
通过巧妙的搭配这些指针域的指向，就可以做到，从跳表上查询元素的时间复杂度是O(logN)  
**示例：** 链表笔试题中的一个经典题目[【138. 随机链表的复制】][138.]

#### 2.ziplist ####

压缩链表  
ziplist 是一种紧凑的、压缩的数据结构，它将多个元素按顺序存储在一起，节省内存空间

## object encoding 命令查询内部编码 ##

object encoding key：查看 key 对应的 value 的实际编码方式

**示例代码：**

127.0.0.1:6379> type key1
    string
    127.0.0.1:6379> OBJECT encoding key1
    "int"
    127.0.0.1:6379> type key2
    list
    127.0.0.1:6379> OBJECT encoding key2
    "quicklist"
    127.0.0.1:6379> type key3
    set
    127.0.0.1:6379> OBJECT encoding key3
    "intset"
    127.0.0.1:6379> type key4
    hash
    127.0.0.1:6379> OBJECT encoding key4
    "ziplist"

redis 会自动根据当前的实际情况选择内部的编码方式，是自动适应的，我们在使用 redis 的时候一般感知不到

[1d89cbd7cfae41b1b6bd20188dfc93e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/0b7f747d74ce45dd841eeb4062d13ba1.png
[138.]: https://leetcode.cn/problems/copy-list-with-random-pointer/