前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Redis基本类型及其数据结构【面试题】

Redis基本类型及其数据结构【面试题】

作者头像
CBeann
发布2023-12-25 19:21:37
1440
发布2023-12-25 19:21:37
举报
文章被收录于专栏:CBeann的博客CBeann的博客

数据类型与底层数据结构的关系

在这里插入图片描述
在这里插入图片描述

String

参考:https://blog.csdn.net/ysl19910806/article/details/99326455 在Redis内部,string类型的底层储存结构是SDS。 SDS: 简单动态字符串 simple dynamic string SDS的数据结构如下所示

代码语言:javascript
复制
typedef struct sdshdr {
    // buf中已经占用的字符长度
    unsigned int len;
    // buf中剩余可用的字符长度
    unsigned int free;
    // 数据空间
    char buf[];
}

既然C语言有字符串,为什么还需要重新设计一个SDS呢?原因有如下几点:

  • 常数复杂度获取字符串长度

因为 C 字符串并不记录自身的长度信息, 所以为了获取一个 C 字符串的长度, 程序必须遍历整个字符串, 对遇到的每个字符进行计数, 直到遇到代表字符串结尾的空字符为止, 这个操作的复杂度为 O(N) 。

在这里插入图片描述
在这里插入图片描述

和 C 字符串不同, 因为 SDS 在 len 属性中记录了 SDS 本身的长度, 所以获取一个 SDS 长度的复杂度仅为 O(1)

  • 二进制安全

C 字符串中的字符必须符合某种编码(比如 ASCII), 并且除了字符串的末尾之外, 字符串里面不能包含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据, 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

举个例子, 如果有一种使用空字符来分割多个单词的特殊数据格式, 如下图 所示, 那么这种格式就不能使用 C 字符串来保存, 因为 C 字符串所用的函数只会识别出其中的 “Redis” , 而忽略之后的 “Cluster” 。

在这里插入图片描述
在这里插入图片描述

使用 SDS 来保存之前提到的特殊数据格式就没有任何问题, 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束

  • API是安全,杜绝缓冲区溢出(自动扩容)

因为 C 字符串不记录自身的长度, 所以 strcat(两个字符串相加) 假定用户在执行这个函数时, 已经为 dest 分配了足够多的内存, 可以容纳 src 字符串中的所有内容, 而一旦这个假定不成立时, 就会产生缓冲区溢出。

与 C 字符串不同, SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性: 当 SDS API 需要对 SDS 进行修改时, API 会先检查 SDS 的空间是否满足修改所需的要求, 如果不满足的话, API 会自动将 SDS 的空间扩展至执行修改所需的大小, 然后才执行实际的修改操作, 所以使用 SDS 既不需要手动修改 SDS 的空间大小, 也不会出现前面所说的缓冲区溢出问题。

  • 空间预分配

空间预分配用于优化 SDS 的字符串增长操作: 当 SDS 的 API 对一个 SDS 进行修改, 并且需要对 SDS 进行空间扩展的时候, 程序不仅会为 SDS 分配修改所必须要的空间, 还会为 SDS 分配额外的未使用空间。

其中, 额外分配的未使用空间数量由以下公式决定: 1)如果对 SDS 进行修改之后, SDS 的长度(也即是 len 属性的值)将小于 1 MB , 那么程序分配和 len 属性同样大小的未使用空间, 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子, 如果进行修改之后, SDS 的 len 将变成 13 字节, 那么程序也会分配 13字节的未使用空间, SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节(额外的一字节用于保存空字符)。 2)如果对 SDS 进行修改之后, SDS 的长度将大于等于 1 MB , 那么程序会分配 1 MB 的未使用空间。 举个例子, 如果进行修改之后, SDS 的 len 将变成 30 MB , 那么程序会分配 1 MB 的未使用空间, SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。 通过空间预分配策略, Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

  • 惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作: 当 SDS 的 API 需要缩短 SDS 保存的字符串时, 程序并不立即使用内存重分配来回收缩短后多出来的字节, 而是使用 free 属性将这些字节的数量记录起来, 并等待将来使用。

  • 兼容部分 C 字符串函数

虽然 SDS 的 API 都是二进制安全的, 但它们一样遵循 C 字符串以空字符结尾的惯例: 这些 API 总会将 SDS 保存的数据的末尾设置为空字符, 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符, 这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。

Hash

参考:https://www.cnblogs.com/hunternet/p/12651530.html

hash是日常开发过程中使用Redis的一个数据结构,其底层实现方式有两种,如下所示。一种是zipList,这种是当hash结构的V值较小的时候使用的编码方式,另一种是字典dict

  • 压缩列表zipList

同时满足以下条件使用压缩列表:

  1. 哈希对象保存的所有键值的字符串长度小于64字节;
  2. 哈希对象保存的键值对数量小于512个;
在这里插入图片描述
在这里插入图片描述
  • 哈希表dict

哈希表dict类似于Java中的HashMap,字典dict采用连链地址法解决冲突碰撞问题。 参考:https://www.cnblogs.com/reecelin/p/13362104.html

List

参考:https://www.cnblogs.com/hunternet/p/12624691.html List的底层使用压缩列表ziplist和双向链表list实现(3.0之后list键已经不直接用ziplist和linkedlist作为底层实现了,取而代之的是quicklist)

Set

参考:https://www.cnblogs.com/hunternet/p/12695738.html Set的底层数据结构有两种:intset 和 hashtable。

  • intset

当一个集合满足以下两个条件时,Redis 会选择使用 intset 编码:

  1. 集合对象保存的所有元素都是整数值;
  2. 集合对象保存的元素数量小于等于 512 个(这个阈值可以通过配置文件 set-max-intset-entries 来控制);
  • hashtable

哈希表

ZSet

参考:https://www.cnblogs.com/hunternet/p/12717643.html

有序集合对象的底层数据结构有两种:skiplist 和 ziplist

  • ziplist

当有序集合对象同时满足以下两个条件时,会使用 ziplist 编码进行存储:

  1. 有序集合对象中保存的元素个数小于 128 个(可以通过配置 zset-max-ziplist-entries 修改);
  2. 有序集合对象中保存的所有元素的总长度小于 64 字节(可以通过配置 zset-max-ziplist-value 修改);
  • skiplist

跳表:有索引的链表结构,查询效率可以媲美红黑树。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-03-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据类型与底层数据结构的关系
  • String
  • Hash
  • List
  • Set
  • ZSet
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档