详解redis数据结构之sds

首页 > 数据库 > Redis 更新日期: 2017-08-10
sds是Simple Dynamic String的缩写,译为简单动态字符串,redis使用该结构保存字符串,不同于c中的字符串,redis使用该结构来更方便的进行字符串的处理,需要的朋友可以参考下

详解redis数据结构之sds

  字符串在redis中使用非常广泛,在redis中,所有的数据都保存在字典(Map)中,而字典的键就是字符串类型,并且对于很大一部分字典值数据也是又字符串组成的。以下是sds的具体存储结构:

详解redis数据结构之sds

      从图中可以看出,sds的属性有三个:len、free和buf数组。这里len字段是用来保存sds字符串中所包含字符数目的,free字段则是用来保存buf数组中空余的部分的长度的,而buf数组则是实际用来保存字符串的。比如如下结构保存了“Hello World!”这个字符串:

详解redis数据结构之sds

      这里需要注意的是,sds和c字符串一样,需要在字符串结尾加上一个“\0”表示该字符串的结束。这里这个sds对象的len属性保存了“Hello World!”这个字符串的长度,而free属性保存了数组中空余的位数,buf数组则实际保存了这个字符串,空字符和空余位。

      redis使用sds结构而不用c字符串保存字符串的原因有如下几点:

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

      通过读取sds对象的len属性的值我们可以使用O(1)获取sds对象保存的字符串长度,而在c字符串中,我们必须对整个数组进行遍历从而获取字符串的长度,其时间复杂度为O(N)。

      ②杜绝缓冲区溢出

      在c字符串中,比如char *strcat(char *dest, const char *src)函数将src连接到dest的末尾,但是c字符串假定dest数组中有足够的空余空间来保存src数组,如果dest数组长度不够就会造成缓冲区溢出;在sds对象中也提供了类似的函数sds sdscat(sds s, const char *t)和sds sdscatsds(sds s, const sds t),这两个函数在调用之前会检查目标sds对象s中free属性是否能够保存要连接的字符串的长度,如果不够,就会对目标sds对象扩容,这就保证了sds对象不会造成缓冲区溢出。

      ③减少修改字符串时内存重分配的次数

      在对sds进行修改的时候,redis可以通过“空间预分配”和“惰性空间释放”来保证后续对sds对象的频繁修改而不会造成sds对象的buf数组经常分配空间;而对于c字符串,每次对其进行修改都需要进行一次空间分配和复制操作。

      ④二进制安全

      对于c字符串,由于其判断是否结束的标志是从字符串开始到结尾碰到的第一个“\0”字符,这就限制了c字符串不能保存像图片、音频、视频、压缩文件等二进制保存的内容;而对于sds对象,由于判断其是否结束的标志是其len属性,也就是说无论在len长度内,buf数组中是否包含“\0”都不影响redis判断其是否结束。

      上面讲到了sds的空间预分配和惰性空间释放,sds通过这两种操作极大的简化了其对字符串的修改和对空间的分配工作。

      空间预分配指的是当对一个sds对象进行结构性增加时,比如修改其内容使其增长或者连接另一个字符串到其末尾,sds会预先分配一定的空间以预防未来可能对其进行的修改。如下是redis进行空间预分配的主要代码:

sds sdsMakeRoomFor(sds s, size_t addlen) {

  struct sdshdr *sh, *newsh;

  // 获取 s 目前的空余空间长度
  size_t free = sdsavail(s);

  size_t len, newlen;

  // s 目前的空余空间已经足够,无须再进行扩展,直接返回
  if (free >= addlen) return s;

  // 获取 s 目前已占用空间的长度
  len = sdslen(s);
  sh = (void*) (s-(sizeof(struct sdshdr)));

  // s 最少需要的长度
  newlen = (len+addlen);

  // 根据新长度,为 s 分配新空间所需的大小
  if (newlen < SDS_MAX_PREALLOC)
    // 如果新长度小于 SDS_MAX_PREALLOC 
    // 那么为它分配两倍于所需长度的空间
    newlen *= 2;
  else
    // 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
    newlen += SDS_MAX_PREALLOC;
  // T = O(N)
  newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

  // 内存不足,分配失败,返回
  if (newsh == NULL) return NULL;

  // 更新 sds 的空余长度
  newsh->free = newlen - len;

  // 返回 sds
  return newsh->buf;
}

      从图中可以看出,当要添加的内容比目标sds对象的free属性要短时直接返回并将要添加的内容添加到目标sds对象的buf数组中即可;当要添加的内容比目标sds对象的free属性要长时,就会计算要添加的内容和sds对象的当前长度的和newlen,如果newlen小于SDS_MAX_PREALLOC也即1M的时候,新创建的buf数组的长度为newlen的两倍,如果newlen大于SDS_MAX_PREALLOC的时候,新创建的buf数组的长度为newlen+SDS_MAX_PREALLOC,即只多分配1M的预留空间。空间预分配保证了sds对象的空余位长度至多为扩张之后字符串长度的1倍,这也就保证了后续对sds对象的修改将尽可能少的分配空间。

      惰性空间释放指的是当对一个sds对象进行缩短操作时,其不会直接将buf数组缩短为目标数组的长度,而是只改变sds对象的len属性的值,数组中多余的部分则保存在free属性中,这样就可以保证后续可能的对该sds对象的增长操作不需要重新分配空间。

      最后需要进行说明的是,sds对象也和c一样使用“\0”作为字符串的结尾的原因是redis也是使用c语言编写的,使用“\0”结尾就可以直接使用部分c函数库中对字符串操作的函数。

      通过上面对sds对象的说明可以发现,redis对sds对象的处理极大的减少了字符串处理中可能出现的复杂操作,并且大部分操作基本上都可以在极短的时间内完成,这就保证了redis对字符串处理的高速率。

       感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • JavaScript数据结构与算法之栈详解
    JavaScript数据结构与算法之栈详解
    这篇文章主要介绍了JavaScript数据结构与算法之栈详解,本文讲解了对栈的操作.对栈的实现实例等内容,需要的朋友可以参考下在上一篇博客介绍了下列表,列表是最简单的一种结构,但是如果要处理一些比较复杂的结构,列表显得太简陋了,所以我们需要某种和列表类似但是更复杂的数据结构---栈.栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样操作很快,而且 ...
  • 数据结构之堆详解
    这篇文章主要介绍了数据结构之堆详解,本文讲解了堆的基本常识堆的基本操作.堆的应用等内容,需要的朋友可以参考下1. 概述 堆(也叫优先队列),是一棵完全二叉树,它的特点是父节点的值大于(小于)两个子节点的值(分别称为大顶堆和小顶堆).它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等. 2. 堆的基本操作 堆是一棵完全二叉树,高度为O(lg n) ...
  • 数据结构之Treap详解
    数据结构之Treap详解
    这篇文章主要介绍了数据结构之Treap详解,本文讲解了Treap的基本知识.Treap的基本操作.Treap的高级操作技巧等,需要的朋友可以参考下1. 概述 同splay tree一样,treap也是一个平衡二叉树,不过Treap会记录一个额外的数据,即优先级.Treap在以关键码构成二叉搜索树的同时,还按优先级来满足堆的性质.因而,Treap=tree+h ...
  • 数据结构之位图bitmap详解
    数据结构之位图bitmap详解
    这篇文章主要介绍了数据结构之位图详解,本文讲解了位图的基本知识.位图的实现方法.位图的应用等内容,需要的朋友可以参考下1.  概述 位图(bitmap)是一种非常常用的结构,在索引,数据压缩等方面有广泛应用.本文介绍了位图的实现方法及其应用场景. 2. 位图实现 (1)自己实现在位图中,每个元素为"0"或"1",表示其 ...
  • RPC、RMI、SOAP的区别详解
    这篇文章主要介绍了RPC.RMI.SOAP的区别详解,本文还同时讲解了RPC.SOAP.WSDL的关系,需要的朋友可以参考下============================================================================RPC与RMI的区别================================ ...
  • JSON字符串和对象之间的转换详解
    这篇文章主要介绍了JSON字符串和对象之间的转换详解,需要的朋友可以参考下JSON(JavaScript Object Notation) 是JavaScript编程语言的一个子集.正因JSON是JavaScript的一个子集,所以它可清晰的运用于此语言中. eval函数 JSON文本转换为对象 为了将JSON文本转换为对象,可以使用eval函数.eval函 ...
猜你喜欢