redis数据结构和底层实现

  • 时间:
  • 浏览:1
  • 来源:跟我学网络

redis数据类型:

  String (字符串类型):

    String是redis最基本的类型,你可以理解成与Memcached一模一样的类型,一个key对应一个value。

    String类型是二进制安全的。意思是redis的string可以包含任何数据。比如jpg图片或者序列化的对象 。

    String类型是Redis最基本的数据类型,一个键最大能存储512MB。

    Redis自己构建了一种名叫Simple dynamic string(SDS)的数据结构,他分别对这几个问题作了处理。我们先来看看它的结构源码:

struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组,用于保存字符串
     char buf[];
}

    再来说说它的优点:

    1. 开发者不用担心字符串变更造成的内存溢出问题。

    2. 常数时间复杂度获取字符串长度len字段

    3. 空间预分配free字段,会默认留够一定的空间防止多次重分配内存。

  Hash(哈希):

    Redis hash 是一个键值对集合。

     Redis hash是一个string类型的field和value的映射表,hash特别适合用于存储对象。

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

Hash表节点: typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点,形成链表 struct dictEntry *next; // 单链表结构 } dictEntry;

字典: typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时,值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict;

   List(列表):

    Redis 列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素导列表的头部(左边)或者尾部(右边)。

    列表最多可存储 232 - 1元素 (4294967295, 每个列表可存储40多亿)。

  Set(集合):

    Redis的Set是string类型的无序集合。

    集合是通过哈希表实现的,所以添加,删除,查找的复杂度都是O(1)。

    sadd 命令:添加一个string元素到,key对应的set集合中,成功返回1,如果元素以及在集合中返回0,key对应的set不存在返回错误。

  Zset(有序集合):

    Redis zset 和 set 一样也是string类型元素的集合,且不允许重复的成员。不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。

    zset的成员是唯一的,但分数(score)却可以重复。

    zadd 命令:添加元素到集合,元素在集合中存在则更新对应score