redis5-基本数据结构
2022-09-20 14:19:20 0 举报redis5-基本数据结构
作者其他创作
大纲/内容
head
tail
len
dup
free
match
length:2
level:4
null
由于ziplist存在连锁更新的其问题，诞生出了listpack结构他不存在连锁更新的问题；结构上和ziplist差不多，但是牺牲了内存，提升了性能
encoding
length
contents
插入元素a
level[32]
...
level[3]
level[2]
level[1]
level[0]
backward
score=0.1
ele
prev
next
value
有效长度>=新增长度
ht_table[0]
ht_table[1]
ht_used[0]
ht_used[1]
rehashidx
示意图
简单动态字符串
end
采用的是惰性空间释放：不会立即使用内存重分配来回收缩短字节。只是移动和标记。并且修改数据长度
每次加预分配长度
k3
v3
metadata
可以看到：之前存储元素的大小是16位，升级之后是32位
更新当前的编码
5
这样做的好处是：1、常量获取字符串长度；2、避免缓冲区溢出；3、减少字符串修改带来的内存频繁重分配次数；
否
按照新编码从后向前移动元素
prevlen
redis基本数据存在 sds.h sds.c sdsalloc.h 中
查找最佳位置
director=0
rehash
物理上的结构
content
entry
a
b
'\\0'
d
空间扩容
entry3
是
跳表查找：1、从最高层level开始查找数所在的区间；2、确定区间之后；到level-1层开始查找；3、直到找到那个数，就不在往下了，返回；4、平均查询时间复杂度为O(logn)---->属于递归查找
扩大一倍
ziplist head
在server.h中定义了跳表
-1
2
3
4
zlbytes
编码>当前编码
线段跳表(有序表)
这一部分其实就是hashmap的结构
这个结构是迭代器listIter
entry2
数组的数据从小到大排序
k4
v4
list
k1
v1
跳表插入操作
SDS_TYPE_5一般不使用，因为该类型不会存放数据
压缩列表
zskiplist
k6
v6
升级示例
链表
k2
v2
score=0.3
zskiplistNode
zlend
直接返回
score=0.2
结构示意图
zltail
否更新
查找示意图
结构
remalloc新内存更新intset长度
说明：1、通过自动升级底层数组来适应新元素，所以可以插入任意类型的整数；2、不同类型采用不同的存储空间，避免空间浪费；3、不支持降级；4、添加和删除：均需要进行remalloc操作，慎用；5、数组是排好序的；
director=1
listnode
重新分配内存更新intset长度
0
1
len: 5
alloc:5
flag:1
buf
zlbytes:记录整个压缩列表占用的字节数，在压缩列表进行内存重分配或者计算zlend时使用；zltail:记录压缩列表表尾节点距离列表的起始地址有多少个字节，通过该偏移量可以确定表尾节点，反向遍历时使用；zllen：记录压缩列表的节点数量，小于65535时，记录节点数；否则恒等于65535，这是要获取数量只能遍历；zlend：特殊值0xFF(十进制255)，用来标记压缩列表的末端；
v5
整数集合（元素有序）
空间缩容
6
新增后长度小于预分配长度(1024*1024)
Container
字典
entryN
一共有5种类型
zllen
压缩列表节点说明：1、prevlen：记录前一个节点的长度，以字节为单位；当前一个节点长度小于254时，只需一个字节； 否则prevlen需要5个字节来存储，其中第一个字节固定为254，后4字节储存前一个节点长度；作用是：根据该属性可以快速定位到前一个节点的起始位置，支持ziplist反向遍历；2、encoding记录节点的content属性所保存数据的类型和长度，支持整数和字符串类型；
如何rehash
例如trim操作时
0 条评论
下一页
为你推荐
查看更多
