字符串

Redis中所有的key都是字符串，但是Redis没有采用c字符串，而是自己封装了个动态字符串，称为SDS。
SDS结构定义如下：

struct sdshdr {
  //已使用字节数
  int len;
  //空闲字节数
  int free;
  //字节数组，用于存储二进制数据
  char[] buf;
}

特性：

使用len来记录长度，获取长度的时间复杂度为O(1),而C字符串是O(n)。
buf数组不是刚好放得下字符串内容，而是会进行预分配，同时可以通过懒释放内存，减少长度变化导致的内存重分配的次数来提高性能。
封装了空间分配的操作，避免缓冲区溢出。比如C的字符串拼接。
二进制安全。记录了len，而不是通过空字符来做字符串结束标识。这样字符串内容也可以出现空字符。
buf数组在存储了字符串内容之外，总会在后面添加一个空字符。通过这个方法兼容C的部分函数。

链表

没有太多特殊的地方：

无环的双向链表，保留了头结点和尾节点的引用。
保存了节点数量，使得获取长度的时间复杂度为O(1)。
使用多态，节点可以承载任何类型数据。

哈希表

typedef struct dictht {
  //一个数组，每个元素都是dictEntry*，指向一个链表（解决哈希冲突问题）
  dictEntry** table;
  //哈希表大小
  unsigned long size;
  //哈希表大小掩码，用于计算索引值，等于size - 1
  unsigned long sizemask;
  //哈希表已有节点数量
  unsigned long used;
} dictht;

typedef struct dictEntry {
  void* key;
  union {
    void* val;
    uint64_t u64;
    int64_t s64;
  } v;
  struct dictEntry* next;
} dictEntry;