redis数据结构的底层实现原理及应用场景

字符串：

简单动态字符串（SDS）的数据类型来实现。
struct sdshdr {  
    int len;  // buf 中已占用空间的长度  
    int free;  // buf 中剩余可用空间的长度
    char buf[];  // 数据空间  
};
SDS保存了字符串的长度，而C字符串不保存长度，需要遍历整个数组（找到’\0’为止）才能取到字符串长度；修改SDS时，检查给定SDS空间是否足够，如果不够会先拓展SDS 的空间，防止缓冲区溢出，而且可以减少为字符串重新分配空间的次数。

场景:
String数据结构是简单的key-value类型，value其实不仅可以是String，也可以是数字。常规key-value缓存应用；

list：

使用双向链表来实现，可以直接获得头、尾节点，获取链表长度时间复杂度是O(1);
场景：
通过链表实现的，获取靠近两端的数据速度极快，而当元素增多后，访问中间数据的速度会较慢，所以它更加适合实现如“新鲜事”或“日志”这样很少访问中间元素的应用。

哈希(Hash)：

数组+链表的基础上，进行了一些rehash优化;如何优化：
rehash：字典中总共有两个哈希表(dictht结构体)，ht[0]用来存储键值对，ht[1]用于rehash时暂存数据，平时它指向的哈希表为空，需要扩展或者收缩ht[0]的哈希表时才为它分配空间；(比如扩展哈希表，就是为ht[1]分配一块大小为ht[0]两倍的空间，然后把ht[0]的数据通过rehash的方式全部迁移到ht[1]，最后释放ht[0]，使ht[1]成为ht[0]，再为ht[1]分配一个空哈希表)
渐进式rehash:redis并不是专门找时间一次性地进行rehash，而是渐进地进行，rehash期间不影响外部对ht[0]的访问，要求修改字典时要把对应数据同步到ht[1]中，全部数据转移完成时，rehash结束.
采用链地址法来处理冲突,
场景：
hash特别适合用于存储对象。存储部分变更的数据，如用户信息等

set：

set可以用intset或者字典实现。
intset：只有当数据全是整数值，而且数量少于512个时，才使用intset，intset是一个由整数组成的有序集合，可以进行二分查找。
字典：不满足intset使用条件的情况下都使用字典（拉链法），使用字典时把value设置为null。

zset：

数据少时，使用ziplist：ziplist省内存但是查找效率低。（ziplist占用连续内存，每项元素都是（数据+score）的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大的数据就多用一些字节来存储，而对于小的数据（short），就少用一些字节来存储。因此查找的时候需要按顺序遍历）。
数据多时，使用字典+跳表：字典用来根据数据查score，跳表用来根据score查找数据（查找效率高）。
跳表是基于一条有序单链表构造的，通过构建索引提高查找效率，空间换时间，查找方式是从最上面的链表层层往下查找，最后在最底层的链表找到对应的节点：
场景：
有序集合类型是使用散列表和跳跃表（Skip list）实现的，所以即使读取位于中间部分的数据速度也很快（时间复杂度是O(log(N))）；列表中不能简单地调整某个元素的位置，但是有序集合可以；有序集合要比列表类型更耗费内存。有序集合类型算得上是 Redis的5种数据类型中*的类型了。