redis 数据结构

本贴最后更新于 702 天前,其中的信息可能已经事过境迁

1. 全局 hash 表

a58e355345b6ce58d359bdaf5a6a7eb4.png

image.png

1.1 hash 冲突

开放寻址法: 当产生冲突时,向后寻址,直到找到第一个空位置

链表法(拉链法): 在桶中使用链表

1.2 rehash

当 redis 字典李数据越来越多的时候,就会发生扩容,即 rehash

redis 字典(hash 表)底层有两个数组,还有一个 rehashidx 用来控制 rehash

b949b63555ff53a451921062f8ac03da.png

渐进式 rehash

渐进式 rehash 采用的是一种分而治之的方式,将 rehash 的操作分摊在每一个的访问中,避免集中式 rehash 而带来的庞大计算量。

需要注意的是在渐进式 rehash 的过程,如果有增删改查操作时,如果 index 大于 rehashindex ,访问 ht[0] ,否则访问 ht[1]。

  1. ht[1] 分配空间,让字典同时持有 ht[0] 和 ht[1] 两个哈希表
  2. 将 rehashindex 的值设置为 0 ,表示 rehash 工作正式开始
  3. 在 rehash 期间,每次对字典执行增删改查操作是,程序除了执行指定的操作以外,还会顺带将 ht[0] 哈希表在 rehashindex 索引上的所有键值对 rehash 到 ht[1] ,当 rehash 工作完成以后, rehashindex 的值 +1
  4. 随着字典操作的不断执行,最终会在某一时间段上 ht[0] 的所有键值对都会被 rehash 到 ht[1] ,这时将 rehashindex 的值设置为 -1 ,表示 rehash 操作结束

rehash 会造成内存占用突升,当内存不足时会出发大量 key 被淘汰,可能影响业务,解决方案

  1. 修改源码,内存不足不去 rehash
  2. 运维规避,监控内存

2.SDS

2.1 结构

struct sdshdr{
	int len;//字符串长度
	int free;//未使用字节数
	char buf[];//字节数组
}

2.2 为什么使用 sds 而不是普通 c 字符串

  1. 自带 length, 常数复杂度
  2. 杜绝缓冲区溢出,每次修改 sds 时都会校验空间是否足够,如果不够,会扩容
  3. 减少修改字符串时带来的内存重分配次数
    1. 空间预分配
    2. 惰性空间释放
  4. 二进制安全,c 字符串无法使用\0,sds 通过 len 和 free 配合不需要使用\0 为结束标志
  5. 部分兼容 string.h 的函数

3.链表

//链表
typedef struct list {
    listNode *head;   //头结点
    listNode *tail;   //尾结点
    void *(*dup)(void *ptr);  //节点复制函数
    void (*free)(void *ptr);  //节点释放函数
    int (*match)(void *ptr, void *key); //节点对比函数
    unsigned long len;  //链表所包含的节点数量
} list;

//节点
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

特点:

  1. 双向,每个节点带 prev 和 next 指针
  2. 无环,两头都指向 null,链表访问到 null 即为终点
  3. 双指针,头指针和尾指针
  4. 带长度计数器,即自带 length
  5. 多态

4. 字典(map)

Redis(一)字典 - Jomini - 博客园 (cnblogs.com)

5. 跳表(skiplist)

(40 条消息) redis 跳表_春天的早晨的博客-CSDN 博客_redis 跳表

6.整数集合(intset)

(40 条消息) redis 之 intset_happytree001 的博客-CSDN 博客_redis 的 intset

7. 压缩链表(ziplist)

Redis 源码笔记:压缩链表 - NotFoundException - 博客园 (cnblogs.com)

8.redisObject

Redis 学习笔记(篇五):对象(RedisObject) - 风中抚雪 - 博客园 (cnblogs.com)

  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 247 回帖 • 211 关注
3 操作
AshShawn 在 2022-04-26 23:47:06 更新了该帖
AshShawn 在 2022-04-26 12:25:37 更新了该帖
AshShawn 在 2022-04-21 10:04:04 更新了该帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...