C语言没有提供像map、set、list等复杂的数据结构，虽然提供了string类型char*， 但是但是效率比较差（主要表现在申请和释放空间上）。因此Redis封装了这些数据结构，当然在封装的时候使用了很巧妙的设计，能够最大化的优化时间和空间复杂度。Redis的性能能够如此优秀，可以说这些数据结构是基石。
(一) 字符串类型sds
在sds.h中定义了sds:
typedef char *sds;
可以看到sds其实就是char*类型，我们来看，sds做了怎样的设计，来提高使用时的性能。
sds的结构如下：
len：字符串的长度
alloc：总空间的大小
flag：字符串的类型
sds：存放字符串的空间
\0：末尾的’\0’可以防止越界访问
sds的设计思路是，预分配一定量的空间，再使用一个len表示已使用的空间大小，这样可以准确的访问内容，减少操作时的内存申请或释放。同时提供不同空间范围的字符串类型，使空间的使用更合理，减少空间浪费。
类型根据字符串长度（初次申请时）确定，类型及长度如下：
SDS_TYPE_5 [0, 1<<5)
SDS_TYPE_8 [1<<5, 1<<8)
SDS_TYPE_16 [1<<8, 1<<16)
SDS_TYPE_32 [1<<16, 1<<32)
SDS_TYPE_64 [1<<32, max(uint64_t))
定义这5种类型，使用3bits就可以表示，所以在实现时使用了1byte。
每种类型定义了一个struct，例如SDS_TYPE_8类型定义：
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
在申请一个SDS_TYPE_8类型的sds时，实际上申请的空间大小是 sizeof(struct(sdshdr8)) + len(str)+1，即包含了头和尾，而sds指向的地址是申请空间首地址+sizeof(struct(sdshdr8))，这样做的好处是访问sds的[0,len)时就是我们需要的字符串内容，要获取sds的头信息也很方便，我们经常在代码里看到的sds[-1]即sdshdr8中的flags，SDS_HDR(8,sds)->len就可以直接读取len字段，实际上是在内存中向后移动了一个sdshrd8的距离就可以完成直接读写。需要注意的是，alloc的值是不包括头和尾的，指的是能保存的字符串的空间。
考虑一个使用场景：有sds a和sds b两个遍历，需要把b拼接到a后面。如果a的剩余空间大于b的长度（a(alloc-len) > len(b)），这时只需要将b的内容拷贝到a后，再更新a的len字段即可，这也是预申请空间的好处。但是当空间不够时就需要申请更多空间。sds申请新空间的做法是：
-
确定空间大小
-
根据空间大小确定sds类型
-
如果类型不变，使用realloc直接申请所需空间
-
如果类型改变，使用malloc申请一段空间，计算新的sds[0]的位置，将原sds内容拷贝至新地址，释放原空间
说明：
-
新空间大小的计算 新空间=字符串长度+新增长度，如果新空间<1M，新空间再乘2，否则新空间+1M
-
类型改变时并没有使用realloc，而是申请了新的空间并用memcpy进行了内容拷贝。这样做是因为不同类型的sdshdr的大小并不一样，sds[0]相对空间的偏移量也不一样。如果使用realloc，就会使用类似strcpy的函数从尾到头进行逐个字符拷贝来达到移位的目的，但是实际上因为memcpy采用了page copy和word copy等优化策略，效率比stcpy要好很多，使用这种方式效率更高。由此也可以看出作者在设计时对细节的优化很到位。