redis六种基本数据结构

1.sds(simple dynamic string)简单动态字符串

struct sdshdr {
    int len;        //buf中已占用空间的长度
    int free;       //buf中剩余可用空间的长度
    char buf[];     //初始化sds分配的数据空间，而且是柔性数组（Flexible array member）
}

定义：

• sds.h定义了字符串的已使用的长度，剩余空间，已经初始化分配的空间大小
• sds.c定义了内存申请、回收策略
  • 预分配策略，字符串修改后。如果表头len小于1M，则扩容len相同的空间。free和len大小相同。否则扩容固定大小为1M的空间。
  • 回收策略，惰性空间释放，当要缩短字符串时并不是立即释放全部空间，而是修改头文件len的长度，待之后使用。

优点：

• 时间复杂度为O(1)
  • 因为表头存放字符串len，可以根据长度直接获取整个字符串
• 杜绝缓冲区溢出
  • C语言中使用strcat进行字符串拼接，如果没分配足够的空间就会导致缓冲区溢出。Redis会先判断len长度，自动扩容满足空间需要。
• 兼容C部分函数
  • 使用字符串/0结尾与C语言相同
• 二进制安全性
  • 支持存放图片，视频二进制文件。传统字符串当遇到/0就结束了，所以不能存放图片视频二进制文件

---

2.链表

typedef  struct listNode{
       //前置节点
       struct listNode *prev;
       //后置节点
       struct listNode *next;
       //节点的值
       void *value;  
}listNode

根据listNode定义了一个双端链表

typedef struct list{
     //表头节点
     listNode *head;
     //表尾节点
     listNode *tail;
     //链表所包含的节点数量
     unsigned long len;
     //节点值复制函数
     void (*free) (void *ptr);
     //节点值释放函数
     void (*free) (void *ptr);
     //节点值对比函数
     int (*match) (void *ptr,void *key);
}list;

特点：

• 双端
• 无环
• len记录了链表长度，获取长度O(1)
• ListNode中void类型可以存放不同类型的值

---

3.字典

typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry

头文件中定义了字典的大小和使用情况

typedef struct dictht{
     //哈希表数组
     dictEntry **table;
     //哈希表大小
     unsigned long size;
     //哈希表大小掩码，用于计算索引值
     //总是等于 size-1
     unsigned long sizemask;
     //该哈希表已有节点的数量
     unsigned long used;
 
}dictht

特点：

• 哈希算法

  #1、使用字典设置的哈希函数，计算键 key 的哈希值
  hash = dict->type->hashFunction(key);
  #2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值
  index = hash & dict->ht[x].sizemask;

• 使用链表法解决hash冲突

• 扩容和缩容

  • 扩容会增加一倍空间，缩容会根据已使用空间缩小一倍，两者都会创建新的哈希表。

• 触发扩容条件

  • 当没有执行BGSAVE或BGREWRITEAOF命令，且负载因子大于等于1
  • 当正在执行BGSAVE或BGREWRITEAOF命令，且负载因子大于等于5
  • 负载因子 = 哈希表已使用空间/哈希表大小

• 渐进式rehash

  • 哈希表扩容和缩容并不会一次性将数据导入新的哈希表，而是分多次迁移，保证哈希表的可用性。读取时先查老的哈希表再查新的哈希表，插入一定是插入新的哈希表。

4.跳跃表skiplist

typedef struct zskiplistNode {
     //层
     struct zskiplistLevel{
           //前进指针
           struct zskiplistNode *forward;
           //跨度
           unsigned int span;
     }level[];
 
     //后退指针
     struct zskiplistNode *backward;
     //分值
     double score;
     //成员对象
     robj *obj;
 
} zskiplistNode

多个节点构成跳跃表

typedef struct zskiplist{
     //表头节点和表尾节点
     structz skiplistNode *header, *tail;
     //表中节点的数量
     unsigned long length;
     //表中层数最大的节点的层数
     int level;
 
}zskiplist;

特点：

• 由多层结构组成
• 每层都是有序的
• 上层节点有下层节点的指针，只对应一个，这个是b+Tree有所不同
• 底层包含所有的数据

5.整数集合

用来保存整数集合，可以存放uint16,uint32,uint64类型,可以保证不会重复

typedef struct intset{
     //编码方式
     uint32_t encoding;
     //集合包含的元素数量
     uint32_t length;
     //保存元素的数组
     int8_t contents[];
 
}intset;

6.压缩列表(ziplist)

特点：

• 压缩列表并不是对数据做了压缩，而是在像数组一样在连续的内存空间存放数据。
• 数组必须要每个数据大小都相同,按最大长度的数据作为元素大小。压缩列表可以存放不同大小的数据并且不浪费空间，还有个好处是可以存放不同类型的数据。