IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> redis5种数据结构内部编码 -> 正文阅读

[数据结构与算法]redis5种数据结构内部编码

Redis 是用C语言写的,所以对于数据结构而言,越清楚原理,越能够明白redis的厉害之处。

几个名词先记住: RedisDB RedisObject dict sds dictEntry

存储值 要知道 存的结构为什么 支持 string hash list这么多数据结构

而且知道结构之后,还要针对不同的结构不同的编码,来提升效率。

依赖

1.RedisDB 也就是 数据库 它从0到15 一共16个 这是第一步入口数据在哪个库
2. RedisDB 里面有 dict 也就是字典载体也就是存数据的载体
3. dict 里面有 dictEntry 也就是存的核心节点区域了哈希形式的表现形式
4. dictEntry里面key 是 sds value是 RedisObject 也就是涉及编码相关存对象 也就是5种基础结构的体现

结构流程梳理:源码文件 server.h - dict.h -sds.h - server.h
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

SDS

在这里插入图片描述

字符串string基于SDS实现

用于计数:粉丝数
还可用于保存用户的session,前提是保证redis的高可用
2种编码 raw embstr

raw 开辟两次空间 大于44字节的时候
embstr 小于44字节的时候 开辟一次空间,预留一次空间 会造成空间冗余

为什么是44,原来是39,因为 sds 后续优化 有了5兄弟 sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64
本身就是针对短字符串的embstr自然会使用最小的sdshdr8,而sdshdr8与之前的sdshdr相比正好减少了5个字节(sdsdr8 = uint8_t * 2 + char = 1*2+1 = 3, sdshdr = unsigned int * 2 = 4 * 2 = 8),所以其能容纳的字符串长度增加了5个字节变成了44.

sds内部buf的扩容机制:新buf长度 = (原buf长度 + 添加buf长度)*2。如果buf长度大于1M后,每次扩容也只会增大1M
在这里插入图片描述
在这里插入图片描述

所以 一般推荐用hash

哈希hash 基于字典实现

适用于存储对象,前提是这个对象没有嵌套其它对象
2种编码 hashtable ziplist

ziplist: 小key的个数不超过512而且长度都不大于64个字节
hashtable:超过512 大于64个字节 时间复杂度 o(1) 哈希算法

ziplist 相当于压缩型的集合,但是查找时间复杂度 o(n),所以又限制512
而且开辟空间是以最大元素字节开辟的,所以如果是1,2,3,100就会开辟4个100,所以又限制不大于64

所以要hashtable 时间复杂度o(1)通过哈希算法 每个元素确定一个相应寻址,找的时候就直接根据下标就找到了。

在这里插入图片描述

列表list 基于双向链表实现

修改list中间的数据时,时间复杂度较高
适用于粉丝列表 消息列表
2种编码 linkedlist ziplist
3.0之后list键已经不直接用ziplist和linkedlist作为底层实现了,取而代之的是quicklist

单向链表,好差入查询,但不好删除 反着来
双向链表 可以当队列也可以当栈 使用
在这里插入图片描述

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

集合set 基于字典实现

功能与list类似,但可以自动去重 ,但无序
可以用set来求交集,如共同关注、共同粉丝、共同喜好
使用srandommember来获取随机数

2种编码 hashtable intset

intset :都是数字 而且对应大小 编码int16 32 64 而且寻找 二分查找 有顺序的
hashtable : 存在不是数字的值/数字超过2的64次方/长度超过512

有序集合zset 基于跳表实现

2种编码 skiplist ziplist

ziplist: 集合数量小于128个 而且 元素的大小都小于 64字节

skiplist: 分数共享内存、跳跃表
在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-03-11 22:26:29  更:2022-03-11 22:28:14 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 14:33:25-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码