redis数据结构实现--简单动态字符串

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: redis数据结构实现(一) 1. SDS简单动态字符串详解 sds是redis自己实现的一种数据结构,用来作为redis底层默认字符串,与c语言的字符串区别开来。在redis中c字符串一般用于不需要改变的字符串值,叫做字符串字面量,如:打印日志。

redis数据结构实现--简单动态字符串

1. SDS简单动态字符串详解

sds是redis自己实现的一种数据结构,用来作为redis底层默认字符串,与c语言的字符串区别开来。
在redis中c字符串一般用于不需要改变的字符串值,叫做字符串字面量,如:打印日志。
redis中每对键值的键都是一个sds对象。

传统c字符串与sds比较:

  • sds数据结构中也是用字符数组存储字符串,但是带有两个额外参数:len(记录字符串长度)和free(未使用空间)
  • 想要获得传统c字符串的长度不得不遍历整个字符串,然而sds则可直接读取len值。降低了时间复杂度
  • 两者的字符数组都是以空字符'/0'结尾,在sds中此空字符不计入len中但是也同样分配一个字节空间,空字符的相关操作都是由sds的API自动完成的,所以对于开发者来说此空字符是透明的。sds保持和c字符串一致以空字符作为结尾是为了能够复用c语言的字符串函数库里的函数。
  • 传统c字符串如果在对字符串操作没有注意空间剩余有可能会出现内场溢出的现象,而sds的API中执行拼接操作的函数sdscat,拼接时会先判断空间是否足够,如果不够则会先执行扩容操作,从而杜绝内场溢出.
  • 避免频繁内存重分配:传统c字符串的长度为n+1(空字符),每一次append时需要重新分配内存,否则内存溢出;如果trim字符串,后面不需要的空间也要释放,否则内存泄露。内存重分配设计复杂算法且可能需要系统调度,不符合redis的速度要求。而sds通过free-未使用空间来解除了底层数组长度与字符串长度间的关联,sds拥有空间预分配与惰性空间释放两钟优化策略。

    1. 空间预分配

      在对sds空间拓展时,先判断空间是否足够,如果足够,则直接使用未使用空间。如果空间不够则使用空间预分配策略
      如果计算得出的sds修改后的长度小于1MB,那么预分配的未使用空间将于已使用的空间一样长。如果sds修改后的长度大于1MB,
      那么将分配1MB的未使用空间。
      通过这种策略将连续增长N次的sds字符串所需的内存重分配次数从必定是N次改为最多N次。
    2. 惰性空间释放

      在对sds字符串进行缩短操作时,并不立即回收缩短的长度,而是利用free将缩短的字符串记录起来,以备以后拓展时使用。
      同样sdsAPI中也提供了真正回收空间的API,所以惰性空间释放并不会浪费空间。
    • 二进制安全:c字符串必须得符合某种编码,且字符串除了尾部中间不能存放空字符,否则被读取到空字符时忽略后面的字符段。所有c字符串只能存放文本信息不能存放二进制数据。而sds的API都是二进制安全(binary-safe)的,buf中存放的就是一系列二进制数据。
相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
8天前
|
存储 缓存 NoSQL
3)深度解密 Redis 的字符串
3)深度解密 Redis 的字符串
15 1
|
11天前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
2月前
|
存储 监控 NoSQL
redis数据结构-HyperLogLog
redis数据结构-HyperLogLog
36 1
|
2月前
|
存储 NoSQL Redis
redis数据结构-ziplist
redis数据结构-ziplist
18 2
|
2月前
|
C# 开发者 UED
WPF开发者必备秘籍:深度解析文件对话框使用技巧,打开与保存文件原来如此简单!
【8月更文挑战第31天】在WPF应用开发中,文件操作是常见需求。本文详细介绍了如何利用`Microsoft.Win32`命名空间下的`OpenFileDialog`和`SaveFileDialog`类来正确实现文件打开与保存功能。通过示例代码展示了如何设置文件过滤器、初始目录等属性,并使用对话框进行文件读写操作。正确使用文件对话框能显著提升用户体验,使应用更友好易用。
53 0
|
2月前
|
存储 NoSQL 数据处理
redis数据结构-Bitmaps
redis数据结构-Bitmaps
30 0
|
2月前
|
存储 缓存 NoSQL
redis数据结构-hash
redis数据结构-hash
11 0
|
8天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
8天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
下一篇
无影云桌面