Redis的五种数据结构及其底层实现原理

五种数据类型

• 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
Redis中跳跃表的定义如下：

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
1、previous_entry_ength：记录压缩列表前一个字节的长度。previous_entry_ength的长度可能是1个字节或者是5个字节，如果上一个节点的长度小于254，则该节点只需要一个字节就可以表示前一个节点的长度了，如果前一个节点的长度大于等于254，则previous length的第一个字节为254，后面用四个字节表示当前节点前一个节点的长度。利用此原理即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置，压缩列表可以从尾部向头部遍历。这么做很有效地减少了内存的浪费。
2、encoding：节点的encoding保存的是节点的content的内容类型以及长度，encoding类型一共有两种，一种字节数组一种是整数，encoding区域长度为1字节、2字节或者5字节长。
3、content：content区域用于保存节点的内容，节点内容类型和长度由encoding决定。