五张图带你看透 Redis 数据结构
这篇文章主要聊聊 Redis 具体功能数据结构的实现,主要针对常用的五种数据结构,string
,hash
,list
,set
和zset
的实现。
在 redis.c:180 中存储了 Redis 支持所有的指令及其实现函数:
第二个属性就是指令的具体实现函数,进入该函数即可阅读相应的指令的具体实现。
在调用具体的命令执行函数前,命令就被拆成一个个参数存放到相应的redisClient.argv中了,比如 Redis 命令set aaa "aaa"
会被拆成数组{"set", "aaa", "aaa"}
放在redisClient.argv
中。
Redis 数据库的真身
redisClient
结构体中有一个db
字段,它是 redisDb 类型,这个就是该redisClient
目前选中的数据库,不论是哪种数据类型,都会调用 setKey 函数将自己设置进数据库中:
发现其实就是在往redisDb
的dict
字典中加入 kv,dict
就是 Redis 自己实现的字典结构,其实现类似于高级语言中的 hashmap,可见一个 Redis 数据库本质就是一个大字典,当你创建的不同的数据结构时,本质上都是在往这个大字典中写入 kv。从setKey
的签名可以看出,这个大字典中的每一个 key 和 value 都是robj
类型,这是个什么东西呢?
redisObject
robj
其实是 redisObject 的简称:
类型type
代表了该robj
对用户暴露的类型,就是引言中说的五种类型:
而encoding
代表底层实际使用的数据结构类型,而具体的底层数据结构实现存储在ptr
字段中。
底层数据结构
底层数据结构是指不对用户暴露,仅仅作为底层实现的一些数据结构,Redis 有如下的底层数据结构:
long
:就是 C 语言中普通的 long 类型,当字符串可以编码成long
类型的数字时,会采用这种结构sds:就是 Redis 中的字符串类型所有的 key 的底层数据结构都是它字符串的底层数据结构,根据其内存摆放特点又有两种
raw
:普通的sds
embstr
:内存中位置紧跟在相应的redisObject
后面,可以和redisObject
一起分配与释放dict:Redis 自己实现字典,除了用于实现 Redis 内部的功能外,还用于
hash
和set
的底层数据结构ziplist
:在内存中连续排列的一个列表结构,可以存储字符串或者数字,和别的结构不一样的地方是,在代码中没有具体的结构体来表示,只有一些宏可以从代表ziplist
的 byte 串取得具体属性的值,redis.c:246。是list
,hash
和zset
数据结构的默认实现虽然是一个紧凑的数据结构,但却无法像数组一样随机访问,各种操作的时间复杂度和链表类似,在查询时需要一个一个元素往下走该编码相对比较复杂,网上有很多文章讲解,这里就不专门介绍了list:Redis 自己实现的一个双向链表,可用于
list
的底层数据结构intset:整数集合,其实就是个从小到大排列的整数数组,如果
set
中所有的元素都是数字的话,可以用于set
的底层数据结构skiplist:跳表,可以和
dict
一起用于zset
的底层数据结构,其中dict
用于按成员取分值,而skiplist
负责按分值取成员。
下面逐一通过图示五种数据结构是如何在上面这 7 种底层数据结构中作选择的。
string
hash
list
set
zset
在使用 ziplist 作为底层数据结构时,score 是以字符串的形式编码在里面,具体为什么要这么做,我也比较困惑,ziplist 本身是支持存数字的。
这个skiplist + dict
的结构其实是 zset 结构体:
其中dict
主要用于支持像zscore
这样的按成员取分值的操作,而zsl
跳跃表主要用于支持像zrange
这样的按照分数取成员的操作。
作者:技乐书香
链接:https://juejin.cn/post/7206260789770059813
来源:稀土掘金
评论