redis基本数据结构底层实现

redis有5种基本数据类型，分别是string、list、hash(哈希表)、set、zset(有序集合)

redis底层有6种数据结构: 分别是简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表

• redis基本数据类型string
  其底层是一个redis定义的简单动态字符串SDS，其基本结构如下

/* 字符串对象的结构 */  
struct sdshdr { // buf 中已占用空间的长度 
    int len; // buf 中剩余可用空间的长度 
    int free; // 数据空间 
    char buf[];  
}; 

• redis 基本数据结构list
  其底层是一个双向链表, 链表节点为

链表节点

typedef struct listNode{
      struct listNode *prev;
      struct listNode * next;
      void * value;  
}

• 链表的特性

双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）
无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
长度计数器：链表中存有记录链表长度的属性 len
多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

• redis中hash表结构的底层是字典
  • 字典
    字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。

SET msg "hello world"

创建这样的键值对（“msg”，“hello world”）在数据库中就是以字典的形式存储。但是C语言本身没有字典数据结构，redis是自己构建的字典数据结构。

• 字典的定义：

typedef struct dictht {
 //哈希表数组
 dictEntry **table;
 //哈希表大小
 unsigned long size;

 //哈希表大小掩码，用于计算索引值
 unsigned long sizemask;
 //该哈希表已有节点的数量
 unsigned long used;
}

一个空的字典结构如下

image.png

哈希表节点dictEntry定义：

typeof struct dictEntry{
   //键
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}

• 渐进式rehash

• redis中基本数据结构zset使用的是跳跃表(skiplist)
  

  跳跃表
  • zskiplistNode（节点） 数据结构：

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

• zskiplist 数据结构

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

• 整数集合(Intset)
  整数集合是集合建的底层实现之一，当一个集合中只包含整数，且这个集合中的元素数量不多时，redis就会使用整数集合intset作为集合的底层实现。
  • Intset实现

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

• 整数集合的升级

1 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2 将底层数组现有的所有元素都转换成新的编码格式，重新分配空间（其实就是如果以前是16位编码格式，现在会转为32位编码格式，或者更高。）
3 将新元素加入到底层数组中

• 压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只把少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，那么Redis 就会使用压缩列表来做列表键的底层实现。

参考：
1 说一下redis中5种数据类型的底层数据结构
2 深入浅出Redis-redis底层数据结构（上）
3 深入浅出Redis-redis底层数据结构（下）