文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Redis数据结构SortedSet的底层原理解析

2022-07-13 17:00

关注

概述

一些常用命令

存储的时候我们可以发现,是有一个score(分数)的,这个就是用来排序的字段。

实现

先说结论,SortedSet底层,根据配置会在不同的时候选用两种不同的数据结构zset,或ziplist进行存储:

首先,我们来看几个参数:

zset-max-ziplist-entries 128
zset-max-ziplist-value 64
if (
    field-value对的数量 > ziplist.entries.size ||
    任意一个filed或value长度 > zset-max-ziplist-value
) {
    // 使用 zset 进行存储
} else {
    // 使用 ziplist 进行存储

zset的结构如下:

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset

可以发现,是由字典+跳跃表实现的。

而跳表则是排序的关键

跳跃表

先上图:

Redis数据结构SortedSet的底层原理解析

我们知道,链表的检索效率是非常低的,如果要拿到100条数据中间的数据,则需要遍历50个数据才行,为了解决这个问题,跳表应运而生

如上图,就是常规的跳表,会在原有的数据上加上若干层,指向当前层的下一个节点。

跳表的插入

Redis数据结构SortedSet的底层原理解析

如上图所示:其实每个节点的层数是随机的,而且新插入一个节点不会影响其它节点的层数。因此,插入操作只需要修改插入节点前后的指针,而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上,这是skiplist跳表的一个很重要的特性,这让它在插入性能上明显优于平衡树的方案。

如下图,假如我们需要查询23,查询的路径如下。

Redis数据结构SortedSet的底层原理解析

事实上,在插入之前也要先经历一个类似的查找过程,在确定插入位置后,再完成插入操作。

这也是SortedSet实现排序的原理。

压缩列表

压缩列表 ziplist 是为 Redis 节约内存而开发的。

压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点 (entry),每个节点可以保存 一个字节数组 或者 一个整数值 。

Redis数据结构SortedSet的底层原理解析

1、zl bytes:用于记录整个压缩列表占用的内存字节数

2、zl tail:记录要列表尾节点距离压缩列表的起始地址有多少字节

3、zl len:记录了压缩列表包含的节点数量。

4、entryX:要说列表包含的各个节点

5、zl end:用于标记压缩列表的末端

压缩列表是一种为了节约内存而开发的顺序型数据结构

压缩列表被用作列表键和哈希键的底层实现之一

压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值

添加新节点到压缩列表,可能会引发连锁更新操作。

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-数据库
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯