专注WEB开发 分享经验,沉淀知识

redis数据类型底层结构的归纳与总结

 作者:chenxing  时间:2022-03-10 23:19  评论:

redis有5大基本的数据类型和3个拓展类型。和他们的底层数据结构。

redis有5大基本的数据类型和3个拓展类型。和他们的底层数据结构。

redis 5大基本数据类型:

  • string
  • hash
  • list
  • sort set
  • set

redis 3个拓展类型:

  • GEO
  • HyperLogLog
  • BitMap

redis 6大底层数据结构

  • 简单的动态字符串
  • 双选链表
  • 压缩列表
  • 跳表
  • 哈希表
  • 整数数组

除了string外使用简单的动态字符串外,其他的四个类型都由两个数据结构实现。

我们来看下他们的映射关系:

  • string->简单的动态字符串
  • list->双向链表、压缩列表
  • hash->压缩列表、哈希表
  • sort set-> 压缩列表、跳表
  • set->哈希表和整数数组

string数据结构(简单的动态字符串:sds)

直接看下sds的数据结构:

struct sdshdr {
    //元素长度
    int len;
    //未使用长度
    int free;
    //保存元素
    char buf[];
}

list数据结构

压缩列表存储满足条件 list保存的字符串对象元素长度小于64字节 list保存的对象元素数量小于512个 其他双向链表

Hash数据结构

压缩列表存储满足条件 hash保持对象的键和值的长度小于64字节 hash保存对象的键值对数量小于512个 其他的哈希表存储

sort set数据结构

压缩列表存储满足条件 sort set 保存对象的元素长度小于64字节 sort set 保存底下的元素个数小于128个 其他的跳表存储

这里有两个疑问:

  1. 压缩列表如何存储key/value 也就是sore 和 member的映射关系?
  2. 跳表是如何存储key/value,索引是如何组织的

压缩列表是第一位置存储key,下一个位置存储value,依次类推。所以这里的个数会发现默认值配置 了128个而不是512(虽然这些配置是可以在redis.conf中进行修改)。

跳表存储:跳表(skiplist:构建索引) + 哈希表(dict:存储key/value)组合模式。每一个entry元素以sore值构建组织跳表索引,dict构建 key/value的存储。

set数据结构

整数数组(intset)的存储满足的条件: set存储对象的元素为int的类型 set存储对象的元素元素个数小于512 其他的用哈希表保存

这里有个疑问: 我们set元素并不是key/value形式,用哈希表怎么存? set中哈希表存储方式:key为set的值,value为null。 关于intset: intset这里值得注意的是intset存储是有序的,内部通过二分法实现元素的查找

typedef struct intset {
    //编码方式
    uint32_t encoding;

    //集合包含的元素数量
    uint32_t length;

    //保存元素的数组
    int8_t contents[];

} intset;

总结:知道的redis各个数据类型应用的数据结构,我们就知道很多操作的时间复杂度。这个对redis一些优化理解有很多的帮助。比如zsort使用的是跳表,跳表的查询和修改的时间复杂度O(logN)那么对应zsort读写炒作时间复杂度也就是O(logN)。还有这里有很多颠覆认知的东西,比如sort set和set从字面上看好像类型,但是从数据结构上看两个是天差地别就和java和javascript一样毫无关系,还有set使用哈希表作为数据结构也是我们难以想象的,至少在不知道这些数据结构之前。

除特别注明外,本站所有文章均为作者原创。 或分享自己的编程经验,或探讨工作中的问题,或聊以人生趣事。 转载请注明出处来自 http://www.qiusuoweb.com/140.html

发布评论

 提交评论
有人回复时邮件通知我

 评论(0)

站长头像
chenxing(PHP攻城狮)

运营天数

总访问量

文章数量

-

-

-

交流群:157451741

新浪微博:草莽兴

 近期文章

个人博客图片免费存放解决方案

 2022-03-21 00:16  92

MySQL中的MVCC总结

 2022-03-19 03:00  94

什么才是高级工程师的第一技能

 2022-03-16 22:04  71

 最新评论

 诚心: 09月29日 23:01
学到了
来源: 如何一次性推送百万级别的消息
 Nick: 04月14日 12:26
网上的资料还是太老,都只是取一个元素,解决了一大难题
来源: redis set集合取出一组数据并删除
 skywalker: 11月03日 18:21
简洁明了
来源: mysql 获取某个日期的前一天或后一天
 lisheng: 05月09日 19:26
兴哥牛B加油哈兴哥成功的道路上你又进了一步 哈哈
来源: 一年时间又回到这里
 心态炸裂: 03月24日 10:54
No3.blindcomfirm 多了一个l,望改正!!!
来源: 微信小程序获取input值的总结
 666666: 11月08日 13:49
66666
来源: 一年时间又回到这里