Redis有5种数据结构：String、List、Hash、Set和Sorted Set。
这里仅仅谈String和Hash.
Redis没有使用C语言传统的字符串，而是使用了SDS（simple dynamic string）
struct sdshdr {
int len; //字符串长度，不含空字符
int free; // 未使用字节的数量，不含空字符
char buf[]; // 保存字符串，最后一个字符是空字符
}
C语言字符串用长度是N+1的字符数组表示长度是N的字符串，字符数组最后一个元素是空字符'\0'。这种字符串的长度是静态的，所以安全性较差，当字符串扩展时容易发生溢出（buffer flow），这样会覆盖其他内存。而sds会检查扩展时的空间是否足够，所以说sds是一种可以动态扩展的字符串，通过预分配内存来实现扩展：
如果扩展之后，sds的长度len小于1M，那么将分配和len相同的空闲内存，此时buf数组的长度是len + len + 1.
如果扩展之后，sds的长度大于等于1M，那么将分配1M的空闲内存，此时buf数组的长度是len + 1MB + 1.
当sds缩短时不会释放空闲内存，这样避免重复分配内存。只有在真正有需要时，才会真正释放未使用的内存。
C语言字符串只能保存文本数据，不能保存二进制文件的数据，因为二进制文件中可能包含空字符，而sds却可以自如存取。
sds用途不仅仅是实现字符串，还被用作缓冲区，比如实现AOF缓冲区和客户端输入缓冲区。
Hash是一种保存键值对（key-value pair）的数据结构，其实现与JDK HashMap类似。
动态数据结构都要考虑扩展的策略。比如Hash，当K-V较多时，会影响性能，这就需要把原来的数据结构扩展，也就是rehash。
负载因子 load_factor = node_size / hash_size （有几个桶）
当load_factor大于等于1时，会扩展hash，当小于0.1时，会收缩hash。
当扩展时，hash_size 是 第一个大于等于node_size * 2^n
当收缩时，hash_size是 第一个大于等于node_size * 2^n
redis内有两个hash，互相作为rehash的对象。redis采用的是渐进式rehash，不会一次性、集中式地完成，而是分多次、渐进式地完成。这是因为hash中的元素一般会比较多，这样做的成本太高，所以要分摊到每次操作中。
在rehash的过程中，hash的操作是在两个表中进行的，比如查找，如果在第一个表中找不到，会在第一个表中寻找。
2017-12-26再阅：
本文看似简单，但涉及到不少重要的计算机思想。
- 数据结构大小（所占内存）动态扩展或者动态收缩，这种扩展策略可能分不同层级
- C语言字符串的缺点：容易溢出，不能存储某些特殊字符。
- 批量操作和逐个操作各有利弊，前者胜在一次集中处理，后者胜在多次渐进分摊。
- 2015年，架构中使用AB结构，现在在数据结构这一层次上也看到了这种设计。
2019-07-24
静态的数据结构能应对的非常简单，就是因为单一，而动态的数据结构则能应对多种场景。具体的例子是C语言字符串和Redis的SDS
