美文网首页
Redis数据结构学习-SDS(一)

Redis数据结构学习-SDS(一)

作者: 牛牛_735d | 来源:发表于2020-04-24 17:26 被阅读0次

SDS 简单动态字符串

SDS 定义

每个sds.h/sdshdr 结构表示一个SDS值

struct sdshdr {
  int len; // 记录buf数组中已使用字节的数量 (=SDS所保存字符串的长度)
  int free; // 记录buf数组中未使用的字节的数量
  char buf[]; // 字节数组, 保存字符串  
}
image-SDS.png
  • free属性值为0, 表示 SDS 未分配 未使用空间
  • len 属性为5, 表示 SDS 保存了一个5字节长的字符串
  • buf 属性是一个char类型的数组, 数组的前5个字节保存了 R, e,d,i, s, 五个字符, 最后一个字节保存了空字符串\0

为什么不使用C原生字符串呢 ?

  1. C字符串获取长度需要遍历, SDS则记录了自身长度(len), 将获取字符串长度的时间复杂度从O(N)降低到了O(1), 即使反复执行strlen, 也不会对系统造成任何影响
  2. C字符串不记录自身长度, 容易造成缓冲区溢出, eg. strcat可以将字符串拼接, 执行这一操作时, 系统假定用户已分配了足够长度的内存, 假设不成立时, 就会造成缓冲区溢出(覆盖后边的字符)
  3. C的实现是一个N+1字符长的数组, 每次增长或缩短一个C字符串, 都会重新分配内存
    • 若增长, eg. append、需要先扩容, 否则会产生内存溢出
    • 若缩容, eg. trim、需要先缩容, 否则会造成内存泄露
  4. 为避免C字符串的缺陷, SDS通过未使用空间分配, 实现了空间预分配惰性空间释放来优化.
    • 空间预分配: 当字符串扩展时, 不仅分配必须空间, 还会分配额外空间(len<1M时, free=len, len>=1M时, free=1M), 来减少连续执行字符串增长需要的内存分配次数, 将字符串连续增长N次需要的内存重分配次数从必定N次, 降低到最多N次
    • 惰性释放: 用free来标记被释放的空间, 而不真正操作内存, 也提供了API, 在需要时释放free空间, 不必担心惰性释放造成的空间浪费
  5. C字符串用\0标记字符串结尾, 字符串本身不能包含空字符, 使得C字符串只能保存文本数据, 而不能保存图片、音频、视频、压缩文件等二进制数据. 而redis SDS字符靠len属性来判断字符串结尾, 是二进制安全的.
  6. 兼容部分C字符. SDS总在结尾多分配一个字符\0 是为了保证C函数可以正常使用, 避免不必要的代码重复

总结

C字符串 SDS字符串
获取字符串长度时间复杂度 O(N) 获取字符串长度时间复杂度 O(1)
API非安全, 可能造成缓冲区溢出 API安全, 不会操作缓冲区溢出
修改字符串会造成NN次内存分配 修改字符串最多N次内存分配
只保存文本数据 可以保存文本及二进制数据
可以使用 <string.h> 库中的函数 可以使用部分 <string.h> 库中的函数

相关文章

  • Redis容量评估模型

    一、redis常用数据结构 做容量评估之前,有必要对redis常用数据结构有大概了解。 1、SDS redis没有...

  • Redis对象(一) - 类型和编码

    对象 前边学习了Redis底层实现的各种数据结构, 包括SDS, list, skiplist, dict, in...

  • Redis设计与实现-笔记(一)

    数据结构与对象 Redis的底层数据结构,了解Redis的底层数据结构有助于我们更好的运用Redis。 SDS R...

  • Simple Dynamic String (SDS)

    Simple Dynamic String (SDS) SDS是在redis中用于表示字符串的数据结构,相比C语言...

  • reids string

    redis中支持的数据结构都是经过设计优化的数据结构和算法。 1. redis string数据结构 见sds.h...

  • Redis源码

    一、Redis数据结构: SDS SDS(动态字符串)包含字符数组buf[],字符数组现有长度len,字符数组分配...

  • Redis底层数据结构

    Redis底层数据结构类型 简单动态字符串(simple dynamic string)SDS Redis 没有直...

  • Redis字符串与C字符串区别

    一、数据结构 redis的字符串底层数据结构是sds(simple dynamic string),即简单动态字符...

  • redis基本数据结构

    redis 基本数据结构. redis的基本数据结构主要有: SDS动态字符串,链表,字典,哈希表,跳跃表,整数集...

  • redis

    redis Redis 数据结构和底层实现string:简单动态字符串SDS,Redis 的字符串是动态字符串,是...

网友评论

      本文标题:Redis数据结构学习-SDS(一)

      本文链接:https://www.haomeiwen.com/subject/uctqwhtx.html