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: 分数共享内存、跳跃表
|