Redis数据结构：字符串
目录
类型概要
redis的字符串是在c语言字符串的基础上，通过简单包装构建了一个简单动态字符串（Simple dynamic string，SDS）的抽象类型。数据结构定义如下:
xxxxxxxxxx//SDS结构定义struct sdshdr{ int len; //字符长度或者已使用字节数 int free; //未使用字节数 char buf[]; //字节数组}SDS除了用来保存字符值之外，在redis也被用来作为缓冲区的实现，AOF模块中的AOF缓冲区和客户端状态中的输入缓冲区，都是由SDS实现。
SDS与c字符串的区别
c字符串的形式并不能满足Redis对字符串安全性、性能以及功能方面的要求。sds的设计不仅考虑了api使用的安全性，更多的是提高了性能。提高性能的核心点在于最大限度减少了内存的申请和拷贝操作，是对空间换时间策略的一种践行，同样的思想在Python的对象数据结构上也有体现。
SDS的具体优势有如下：
常数复杂度获取字符串长度
避免缓冲区溢出
在进行字符串拼接操作等操作时，通过长度检查是否又足够的空间存储改变后的字符串，若无则先扩展空间。以此避免了C语言中字符串拼接等操作的缓冲区溢出问题。
减少修改字符串带来的内存重分配的次数
SDS申请的内存空间是有冗余的，新增字符不会导致每次都要临时申请，即所谓的空间预分配优化策略。删除元素也不会立即把内存释放掉，而是修改free数值来维护一个未使用空间，即所谓的惰性空间优化策略。
二进制安全
原始C字符串不能包含空字符串(会被认为时字符串结尾)，因此不能保存类似图片等复杂的二进制数据。
SDS API
| 函数接口 | 作用 | 时间复杂度 |
|---|---|---|
| sdsnew | 创建一个包含指定c字符串的SDS | O(N)，N为字符串长度 |
| sdsempty | 创建空SDS | O(1) |
| sdsfree | 释放SDS | O(N) |
| sdslen | 已使用空间字节数 | O(1) |
| sdsavail | 未使用空间字节数 | O(1) |
| sdsdup | 创建一个sds副本 | O(N) |
| sdsclear | 清空sds内容 | 因为惰性空间释放，O(1) |
| sdscat | 将c字符串拼接到sds | O(N) |
| sdscatads | 将sds拼接sds | O(N) |
| sdscpy | 将C字符复制到SDS，覆盖SDS原有字符 | O(N)，N为被复制C字符串的长度 |
| sdsgrowzero | 用空字符将SDS扩展至给定长度 | O(N),N为扩展新增的字节数 |
| sdsrange | 保留sds给定区间的数据，不在区间内的会被清除或覆盖 | O(N) |
| sdstrim | 接受一个SDS和一个c字符串作为参数，从sds中移除所有在c字符串出现过得字符 | O(N^2) |
| sdscmp | 比较两个sds是否相同 | O(N) |
参考
- 书籍《Redis设计与实现》