五种数据类型

• string字符串
• hash 哈希
• list 列表
• set 无序集合
• zset 有序集合

string字符串类型实现

redis的字符串类型是由一种叫做简单动态字符串(SDS)的数据类型来实现

struct sdshdr {
  int len;          //buf中已占用空间的长度
  int free;        //buf中剩余空间的长度
  char buf[];    //数据空间
}

SDC和C语言字符串的区别：
1：SDS保存了字符串的长度，而C语言不保存，只能遍历找到第一个\0的结束符才能确定字符串的长度
2：修改SDS，会检查空间是否足够，不足会先扩展空间，防止缓冲区溢出，C字符串不会检查
3：SDS的预分配空间机制，可以减少为字符串重新分配空间的次数
备注：重新分配空间方式，小于1M的数据 翻倍+1，例如：13K+13K+1，如果大于1M，每次多分配1M，例如：10M+1M+1,如果字符串变短，并不会立即缩短，而是采用惰性空间释放，有专门的API可以释放多余空间

hash哈希

hash结构里其实是一个字典，有许多的键值对
redis的哈希表是一个dictht结构体：

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

哈希表节点的结构体如下：

typedef struct dictEntry{
  void *key;  //键
  union {      //不同键对饮的值得类型可能不同，使用union来处理这个问题
    void *val;
    uint64_tu64;
    int64_ts64;
  }
  struct dictEntry *next;
}

hash算法：
当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

hash冲突解决方式：链表法，后入的放到最前面
rehash：
键值数据量变动时，时为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。
如果是扩充，新数组的空间大小为 大于2*used的2的n次方，比如：used=5,则去大于10的第一个2的n次方，为16
如果是缩小，新数组的空间大小为第一个不大于used的2的n次方，比如：used=5,则新大小为4

list列表类型实现

redis的list列表是使用双向链表来实现的
···
typedef struct listNode {
struct listNode * pre; //前置节点
struct listNode * next; //后置节点
void * value; //节点的值
}

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

zset有序集合

1：有序集合的底层实现之一是跳表， 除此之外跳表它在 Redis 中没有其他应用。
2：整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。
3：数据少是，使用ziplist(压缩列表)，占用连续内存，每项元素都是(数据+score)的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大数据(long long),就多用一些字节存储，而对于小的数据(short)，就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。

set无序集合

无序集合可以用整数集合(intset)或者字典实现

Stream

Redis的5.0版本中，放出一个新的数据结构Stream。其实也是一个队列，没一个不同的key对应的是不同的队列，没个队列的元素，也就是消息，都有一个msgid，并且需要保证msgid是严格递增的。在Stream当中，消息是默认持久化的，即便是Redis重启，也能够读取到信息。
Stream的多播，与其它队列系统相似，对不同的消费者，也有消费者Group这样的概念，不同的消费组，可以消费通一个消息，对于不同的消费组，都维护一个Idx下标，表示这一个消费群组费到了哪里，每次进行消费，都会更新一下这个下标，往后面一位进行偏移。

其它

一、 跳跃表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而大道快速访问节点的目的，具有以下性质：
1：有很多层结构组成
2：每一层都是一个有序的链表，排列顺序为由高到低，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点
3：最底层的链表包含了所有的元素
4：如果一个元素出现在某一层的链表中，那么在该层之下的链表也全部都会出现
5：链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的通一个链表节点

image.png

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

多个跳跃表节点构成一个跳跃表

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

跳表操作

1：搜索，从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也及时和当前层的下一层的节点下一个节点
2：插入，首先确定插入的层数，有一种方法是抛一个硬币，如果是正面就累加，直到遇到反面为止，最后记录正面的次数作为插入的层数，当确定插入的层数K后，则需要将新元素插入从底层到K层
3：删除，在各个层中找到包含指定值得节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

二、整数集合

整数集合是Redis用于保存整数值集合的抽象数据类型，它可以保存int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。

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

整数集合的每个元素都是contents数组的一个数据项，他们按照从小到大的顺序排列，并且不包含任何重复项。
length属性记录了contents数组的大小。
需要注意的是虽然contents数组声明为int8_t类型，但是实际上contents数组并不保存任何int8_t类型的值，其真正类型由encoding来决定。

• 升级
  当我们新增元素类型比原集合元素类型的长度要大时，需要对整数集合进行升级，才能将新元素放入整数集合中，具体步骤：
  1：根据新元素类型，扩展整数集合底层数组的大小，并为新元素分配空间
  2：将底层数组现有的所有元素都转成与新元素相同类型的元素，并将转换后的元素放到正确的位置，放置过程中，维持整个元素顺序都是有序的。
  3：将新元素添加到整数集合中(保证有序)
• 降级
  整数集合不支持降级，一旦对数组进行了升级，编码就会一直保存升级后的状态

三、压缩列表

压缩列表(ziplist)是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或一个整数值。
压缩列表的原理：压缩列表并不是对数据利用某种算法进行压缩的，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

image.png

压缩列表的每个节点构成如下：

image.png