Redis教程

redis数据结构---动态字符串(SDS)

本文主要是介绍redis数据结构---动态字符串(SDS),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Redis只会用C字符串作为字面量,在大多数情况下Redis会使用SDS(Simple Dynamic String,简单动态字符串)作为字符串表示。

Redis为什么不用C字符串(c字符串与SDS的区别)

 

获取字符串长度复杂度

C语言使用N+1的字符串数组来表示长度为N的字符串,并且数组的最后一个元素总是空字符串'/0',C字符串并不记录自身的长度信息,每次获取长度需要重新遍历字符串直到遇到'/0'为止,这个复杂度为O(N)。

SDS在len属性中保存了字符串的长度,所以获取字符串长度的复杂度为O(1),设置和更新SDS长度的工作是由SDS的API在执行时自动完成的,不需要进行手动的修改。

杜绝缓冲区溢出

C字符串如果在修改字符串之前没有分配足够的内存空间会造成缓冲区溢出。

SDS在修改时会先检查SDS的空间是否足够,如果空间不足,会自动扩展空间至修改所需要的大小,再去执行修改操作。

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

C字符串的底层实现总是一个N+1个字符长度的数组,因为C字符串和底层数组之间的长度存在这种关联性,所以每次修改字符串时会重新分配数组的内存空间(如果增长字符串而不进行重新分配内存会产生缓冲区溢出,减少的话会产生内存泄露)。

为了避免C字符串的这种缺陷,SDS通过未使用空间解除了字符串长度和底层数组之间的关联,在SDS中buff长度不一定是字符数量+1,数组里面可以包含未使用的字节,而这些字节数量由SDS的free属性记录。

通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配:

当对一个SDS进行修改并需要扩展SDS的空间时,程序不仅会分配修改所需要的空间,还会为SDS额外分配未使用的空间。(SDS小于1M会额外分配等于SDS的空间,大于等于1M则额外分配1M)

通过空间预分配策略,Redis可以减少连续执行字符串增长操作所需的内存从新分配次数。(如果要增长的长度小于未使用的空间就不会重新分配内存)

惰性空间释放:

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

二进制安全

C字符串中的字符必须符合某种编码格式,并且除了字符串的末尾处,不允许有空字符串,否则会被认为是字符串结尾,这些限制使C字符串只能保存文本数据,不能保存二进制数据。

SDS会以处理二进制的方式来处理SDS存放在buf数组中的数据,程序不会对数据做任何限制,数据写入时是什么样,读取时就是什么样。(SDS的buf属性不是保存字符,而是保存的一系列二进制数据)

这篇关于redis数据结构---动态字符串(SDS)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!