redis的数据结构

Redis支持多个数据库,并且每个数据库的数据是隔离的不能共享,并且基于单机才有,如果是集群就没有数据库的概念。

用select命令可以手动切换redis数据库,默认从0开始

redis> select 0

typedef struct redisDb {  //一个redis库的结构
 int id;         // 数据库ID标识
 dict *dict;     // 键空间,存放着所有的键值对
 dict *expires;  // 过期哈希表,保存着键的过期时间
 dict *watched_keys; // 被watch命令监控的key和相应client
 long long avg_ttl;  // 数据库内所有键的平均TTL(生存时间)
} redisDb;

键空间

字典格式(这个字典的底层数据结构就是hash表),键是字符串对象, 值对应五种不同对象, string对象list对象hash对象集合对象有序集合对象中任意一种redis对象。

typedef struct redisObject{ 
     //类型
     unsigned type:4;
     //编码
     unsigned encoding:4;
     //指向底层数据结构的指针,一共有6种底层数据结构
     void *ptr;
     //引用计数
     int refcount;
     //记录最后一次被程序访问的时间
     unsigned lru:22;
}robj

1.String对象

Redis 是用 C 语言写的,但Redis的字符串是自己构建了一种名为 简单动态字符串(simple dynamic string,SDS)的抽象类型。

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

string对象的编码类型有 int,raw或者embstr。 int 编码是用来保存整数值,raw编码是用来保存长字符串,而embstr是用来保存短字符串。

2.List对象

底层数据结构是双向链表或者 压缩列表(ziplist), 当列表保存元素个数小于512个且每个元素长度小于64字节时为ziplist, 可以更改list-max-ziplist-value选项和 list-max-ziplist-entries 选项进行配置。 压缩列表其实就是把数据放在连续的内存中。

3.Hash对象

底层数据结构是哈希表

# 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_tu64;
          int64_ts64;
     }v; 
     //指向下一个具有相同索引值的哈希表节点,形成链表,链地址法解决哈希冲突问题
     struct dictEntry *next;
}dictEntry

4.Set对象,集合对象

底层数据结构是整数集合(intset)或者hash表, 当集合对象中所有元素都是整数且所有元素数量不超过512时为intset类型,可通过set-max-intset-entries 进行配置。

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

}intset;

5.zset对象,有序集合

底层数据结构为 跳跃表(skiplist),是一种有序数据结构,它通过在每个节点中维持多个指向其它节点的指针,从而达到快速访问节点的目的。

redis内存回收算法

Redis使用的内存回收算法是引用计数算法LRU算法
1.引用计数算法:对于创建的每一个对象都有一个与之关联的计数器,这个计数器记录着该对象被使用的次数,垃圾收集器在进行垃圾回收时,对扫描到的每一个对象判断一下计数器是否等于0,若等于0,就会释放该对象占用的内存空间,同时将该对象引用的其他对象的计数器进行减一操作。
2.LRU算法:LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录该页面自上次被访问以来所经历的时间 t,当必须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面给予淘汰。LRU算法最为经典的实现,就是HashMap+Double LinkedList,时间复杂度为O(1),但是如果按照HashMap和双向链表实现,需要额外的存储存放next和prev指针,牺牲比较大的存储空间,显然是不划算的。所以Redis中的LRU算法,就是随机取出若干个key,然后按照访问时间排序后,淘汰掉最不经常使用的那个。

本作品采用《CC 协议》,转载必须注明作者和本文链接
用过哪些工具?为啥用这个工具(速度快,支持高并发...)?底层如何实现的?
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!