[Redis]Redis的设计与实现-链表/字典/跳跃表

redis的设计与实现: 1.假如有一个用户关系模块,要实现一个共同关注功能,计算出两个用户关注了哪些相同的用户,本质上是计算两个用户关注集合的交集,如果使用关系数据库,需要 对两个数据表执行join操作,对合并的结果执行去重distinct操作,非常复杂 2.Redis直接内置了集合数据类型,支持对集合执行交集/并集/差集等集合计算操作,交集操作可以直接用于共同关注功能,使用之后速度更快代码量更少,可读性大大提高 3.越来越多的疑问:五种数据类型是由什么数据结构实现的?字符串数据类型既可以存储字符串,又可以存储整数浮点数,二进制位,在内部是怎么存储这些值的? 有些命令只能对特定数据类型执行,是如何进行类型检查的?怎样存储各种不同类型的键值对?过期键是怎样实现自动删除的?发布与订阅/脚本/事务等特性是如何实现的?使用什么模型处理客户端的命令请求?一条命令从发送到返回需要经历的步骤? 4.第一版发布的时候还不是很完善,作者一边注释源码一边写,只介绍了内部机制和单机特性,新版添加了关于二进制位操作/排序/复制/Sentinel和集群等主题的新章节 5.数据结构与对象,单机数据库的实现,多机数据库的实现,独立功能的实现 6.数据库里面的每个键值对都是由对象组成的:数据库键总是字符串对象;键的值可以是字符串对象/列表对象(list object)/哈希对象(hash object)/集合对象(set object)/有序集合对象(sorted set object),这五种中的其中一种 7.第一部分和第二部分单机功能比较重要:第一部分,简单动态字符串,链表,字典,跳跃表,整数集合,压缩列表,对象 8.Redis自己构建了一个SDS的类型用来保存所有的字符串对象,包括键值对的键,值中存储字符串对象的底层也是SDS

redis的设计与实现-链表 1.链表提供了高效的节点重排能力,顺序性的节点访问方式,通过增删节点调整链表的长度,C语言不内置,Redis构建了自己的链表实现 2.列表键的底层实现之一就是链表,当元素比较多,元素都是比较长的字符串,就会使用链表作为底层实现 3.发布与订阅,慢查询,监视器等功能也用到了链表,redis本身使用链表保存多个客户端的状态信息 4.每个链表节点使用adlist.h/listNode结构表示,通过prev和next指针组成双端链表;使用adlist.h/list结构操作更方便,提供了表头指针head,表尾指针tail,长度计数len,特定类型的函数等 5.链表表头前置和表尾后置都是指向null,所以是无环链表,设置不同类型特定函数,可以用于保存不同类型的值 字典 1.字典,又称为符号表/关联数组/映射,保存键值对的抽象数据结构;一个键和一个值进行关联,或者叫键映射为值 2.redis的数据库就是使用字典作为底层,对数据库的增删查改操作也是构建在对字典的操作之上;字典还是哈希键的底层实现 3.redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,每个哈希表节点保存了字典中的一个键值对 4.redis字典所使用的哈希表由dict.h/dictht结构,table属性是一个数组,每个元素都是指向dict.h/dictEntry结构的指针.每个dictEntry结构保存一个键值对 5.哈希表节点使用dictEntry结构表示,key属性保存着键值对中的键,v属性保存着键值对中的值,键值对的值可以是指针或整数,next属性是指向另一个哈希表节点的指针,以此解决键冲突,通过next指针将两个索引值相同的键k1和k0连接在一起 6.Redis字典由dict.h/dict结构表示,type属性和privdata属性是针对不同类型的键值对,为创建多态字典设置;ht属性是一个包含两个项的数组,每一项都是dictht哈希表,一般只使用ht[0],ht[1]只会在哈希表进行rehash的时候使用,rehashidx记录rehash的进度 7.哈希算法-将一个新的键值对添加到字典里面时,先根据键计算出哈希值和索引值,根据索引值将一个新键值对的哈希表节点放到哈希表数组的指定索引上 hash=dict->type->hashFunction(key);index=hash&dict->ht[x].sizemask Redis使用了MurmurHash2算法来计算键的哈希值 8.解决键冲突,使用了链地址法,被分配到同一个索引的多个节点可以用单向链表连接起来 9.哈希表保存的键值对逐渐增多或者减少,为了让哈希表的负载因子维持在一个合理的范围内,程序对大小进行扩展或者收缩

redis的设计与实现-跳跃表 1.跳跃表(skiplist)是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,达到快速访问其他节点的目的,跳跃表支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作批量处理节点

1.跳跃表(skiplist)大部分情况下效率可以和平衡树媲美,并且比平衡树要简单 2.Redis使用跳跃表作为有序集合键的底层实现之一,在内部的集群节点中也有使用 3.比如zrange fruit 0 2 withscores 水果名是成员,水果价钱是分数值,每个水果存储在跳跃表节点中,价钱由低到高排序 4.redis跳跃表由redis.h/zskiplist和redis.h/zskiplistNode两个结构定义,zskiplist包含,header指向表头节点,tail指向表尾节点,length跳跃表的长度,level节点中最高层数 zskiplistNode结构包含,level表示层每层都有前进指针和跨度指向下一个节点,backward表示后退指针,score表示分值,obj表示成员对象;遍历时这些前进指针和后退指针就能启动快速访问的目的 5.迭代程序遍历跳跃表的时候只与前进指针有关,每个层的跨度与节点在跳跃表中的排位有关,每个节点的层高在1-32之间的随机数

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Linyb极客之路

当你收到面试通知后,如下的准备可以大大提升面试成功率

由于我做了比较长时间的技术面试官,根据我的面试体会,不少同学收到面试后,什么准备也不会做,到时候问题就来了。

14350
来自专栏A周立SpringCloud

一个高频面试题:怎么保证缓存与数据库的双写一致性?

来源:https://blog.csdn.net/chang384915878/article/details/86756463

10720
来自专栏天马行空布鲁斯

liquibase和flyway中分布式锁实现的区别?

大家可能都知道,锁的存在本质上是为了解决共享资源互斥访问的问题,为了解决这个问题,在单机系统中(一个进程),很多开发语言都提供了锁的特性,比如说java的syn...

18120
来自专栏Java后端技术栈cwnait

彻底搞懂MySQL的索引

MyISAM和InnoDB是MySQL最常用的两个存储引擎,本文将进行详尽的介绍和对比。对于MySQL其余几种存储引擎,请读者自行搜索学习。

8540
来自专栏方球

golang sql 数据库链接

13330
来自专栏Java工程师成长之路

分布式事务原理解析

了解过TCC分布式事务的都知道它有三个阶段:try,confirm,cancel,但很多文章就只有原理图,和对原理图的解释,看一遍也留不下印象,这里用实际场景举...

10640
来自专栏智能计算时代

「Postgresql架构」使用PostgreSQL中的JSONB数据类型加快操作

从版本9.4开始,PostgreSQL在使用JSON数据的二进制表示jsonb时提供了显着的加速,这可以为您提供增加性能所需的额外优势。

17720
来自专栏搜狗测试

Redis入门

最近在学Redis,相信大家对Redis这个技术都有所耳闻,前段时间通过搜狗手机助手与合作方流量合作需求的测试过程中需要用到Redis,当时对Red...

13910
来自专栏sktj

flask migrate 使用

安装Flask-Migrate插件 1 (venv) $ pip install flask-migrate 注意到虚拟环境中(因为Flask环境就安装在...

6610
来自专栏后端开发你必须学会的干货

explain的属性详解与提速百倍的优化示例

在MySQL中,可以通过EXPLAIN命令获取MySQL如何执行SELECT语句的信息,包括在SELECT语句执行过程中表如何连接和连接的顺序。

17530

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励