redis数据结构实现（一）

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

sds是redis自己实现的一种数据结构，用来作为redis底层默认字符串，与c语言的字符串区别开来。

传统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中存放的就是一系列二进制数据。