目录

Rdis数据类型

动态字符串SDS

IntSet

Dict

Dict的扩容

ZipList

QuickList

SkipList

RedisObject

Redis的编码方式

五种数据类型

String

List

Set

ZSet

Hash

---

Rdis数据类型

动态字符串SDS

SDS具备动态扩容能力

• 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1

• 如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1，称为内存预分配

优点：

1、获取字符串长度的时间复杂度为0（1）

2、支持动态扩容

3、减少内存分配次数

4、二进制安全

IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组实现，具备长度可变、有序等特征

IntSet升级：

1、当有数值超过INT16_t的范围，intset会自动升级编码到合适大小

2、倒叙依次将数组中的元素拷贝到扩容后的正确位置

3、将新添加进来的元素放入数组末尾

IntSet特点：

🙌Redis会保证IntSet中的元素唯一、有序

😒具备类型升级机制，可以节省内存空间

😍底层采用二分查找法来查询

Dict

Redis是一个键值型的数据库，可以根据键实现CRUD，而键与值的映射关系是通过Dict实现

Dict由三部分组成：

• 哈希表（DictHashTable）

• 哈希节点（DictEntry）

• 字典（Dict）

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合元素较多时，导致哈希冲突、链表过长，查询效率下降

Dict每次新增键值对时都会检查负载因子（LoadFactor = used/size） used = 元素 size = 数组大小

满足两种情况会触发哈希表扩容：

• 哈希表的LoadFactor >= 1 ,并且服务器没有执行BGSAVE或BGREWRITEAOT等后台进程

• 哈希表的LoadFactor > 5

rehash过程：

1、触发时机 :

——扩容：负载因子（used/ size）≥ 1 且允许扩容，或负载因子 ≥ 5 （强制扩容）

——收缩：负载因子 < 0.0

2、计算新表大小

——扩容：新 size = ≥ (used + 1) 的 2^n

——收缩：新 size = ≥ used 的 2^n（最小为 4）

3、步骤

😒创建新哈希表ht[1], 大小为计算值

🤣设置rehashidx = 0（开始标记）

😊将ht[0] 所有键值对重新哈希到ht[1]

👌完成后，ht[1] 赋值给ht[0] ，ht[1]重置为空表

❤️释放旧ht[0] 内存

4、渐进式rehash

——为避免阻塞，分多次迁移

——每次CRUD迁移1个桶（rehash指向的索引）

——期间先查找ht[0], 再查ht[1]

---

ZipList

ZipList是一种特殊的“双端链表” ，由特殊编码的连续内存块组成。

可以在任意一端压入/弹出操作，并且该操作的时间复杂度为 O（1）

ZipList中的Entry不像普通链表记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存

所以Entry采用了下面结构：

• previous_entry_length

• encoding

• contents

注意：ZipList所有存储长度的数值均使用小端字节序，即低位字节在前，高位字节在后。例如：数值O1234，采用小端字节序实际存储值为： Ox3412

ZipList特性：

❤️压缩列表可以看成一种连续内存空间的“双向链表”

👍列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用低

💖如果列表数据过多，导致链表过长，可能会影响查询性能

💕增或删较大数据时有可能发生连续更新问题

---

QuickList

QuickList特点：

• 是一个节点为ZipList的双端链表

• 节点采用ZipList，解决了传统链表的内存占用问题

• 控制了ZipList大小，解决连续内存空间申请效率问题

• 中间节点可以压缩，进一步节省了内存

为什么要这样设计？

1. 普通双端链表的问题：

   • 每个元素单独占用一个节点，每个节点都有前驱/后继指针（每个指针 8 字节，共 16 字节额外开销）

   • 对于小元素（比如整数、短字符串）来说，指针开销比例太高，内存利用率低

SkipList

SkipList（跳表）是链表，但与传统链表相比有几点差异：

• 元素按照升序排列存储

• 节点可能包含多个指针，指针跨度不同

SkipList特点：

——跳跃表是一个双向链表，每个节点都包含score和ele值

——节点按照score值排序，score值一样则按照ele字典排序

——每个节点都可以包含多层指针，层数是1到32之间的随机数

——不同层指针到下一个节点跨度不同，层级越高，跨度越大

——CRUD效率与红黑树一致，实现却简单

---

RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫Redis对象

Redis的编码方式

Redis会根据存储的数据类型不同，选择不同的编码方式，共包含11种类型：

---

五种数据类型

String

String是Redis中最常见的数据存储类型：

• 基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb

• 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存只需要调用一次内存分配函数，效率高

• 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8个字节），不再需要SDS

EMBSTR编码：

RAW编码：

INT编码：

---

List

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

• 在3.2版本前，Redis采用ZipList和LinkedList实现List，当元素数量小于512并且元素大小小于64字节采用ZipList编码，超过则采用LinkedList编码

• 在3.2版本后，Redis统一采用QuickList来实现List

---

Set

Set是Redis中的单列集合

特点：

• 不保证有序性

• 保证元素唯一（可以判断元素是否存在）

• 交集、并集、差集

——为了保证查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null

——当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，节省内存

---

ZSet

ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值：

• 可以根据score值排序后

• member必须唯一

• 可以根据member查询分数

zset底层数据结构必须满足键值存储、键必须唯一、可排序，底层为编码SkipList、HT（Dict）

当元素数量不多，以上两种编码更耗内存，因此zset会采用ZipList节省内存，不过同时需要满足两个条件

——😉元素数量小于zset_max_ziplist_entries,默认值128

——💕每个元素都小于zset_max_ziplist_value节点，默认值64

ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：

• ZipList是连续内存，因此score和element是紧挨在一起的两个entry，element在前，score在后

• score越小越接近队首，score越大越接近队尾，按照score值升序排列

---

Hash

Hash结构与Redis中的Zset类似：

• 都是键值存储

• 都需要根据键获得值

• 键必须唯一

区别：

• zset的键为member，值是score；hash的键和值都是任意值

• zset要根据score排序；hash无需排序

1、Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value

2、当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：

• ZipList中的元素数量超过hash-max-ziplist-entries（默认512）

• ZipList中的任意entry大小超过了hash-max-ziplist-value(默认64字节)

制作不易，麻烦点个小爱心吧！