一 Redis数据结构-Redis的数据存储及String类型的实现( 三 ) _生活百科

3.2 String类型的实现——SDS结构Redis并没有直接使用C字符串实现String类型，在Redis3.2版本之前通过SDS实现
Typedef struct sdshdr {int len;int free;char buf[];};

len：分配内存空间
free：剩余可用分配空间
char[]：value值实际数据

3.3 SDS与C字符串之间的区别3.3.1 查询时间复杂度
C获取字符串长度的复杂度为O(N) 。而SDS通过len记录长度，从C的O(n)变为O(1) 。
3.3.2 缓冲区溢出
C字符串不记录自身长度容易造成缓冲区溢出（buffer overflow）。SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性,当需要对SDS进行修改时，会先检查SDS的空间是否满足修改所需的要求，如果不满足的话SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现缓冲区溢出问题。
在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略：

空间预分配：当对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。扩展SDS 空间之前，会先检查未使用空间是否足够，如果足够的话，就会直接使用未使用空间，而无须执行内存重分配。如果不够根据(len + addlen(新增字节)) * 2的方式进行扩容，大于1M时，每次只会增加1M大小。通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。
惰性空间释放：惰性空间释放用于优化SDS的字符串缩短操作：当需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。

3.3.3 二进制安全
C字符串中的字符必须符合某种编码（比如 ASCII，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾。
SDS的API都是二进制安全的（binary-safe）：都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的，它被读取时就是什么样。redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。
3.4 SDS结构优化String类型所存储的数据可能会几byte存在大量这种类型数据，但len、free属性的int类型会占用4byte共8byte存储，3.2之后会根据字符串大小使用sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64数据结构存储，具体结构如下：

struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; /* 3 lsb of type, and 5 msb of string length */char buf[];};struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* used */uint8_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];};struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* used */uint16_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];};struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* used */uint32_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];};struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* used */uint64_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];};