小编典典

Redis的底层数据结构是什么?

redis

我试图在一个明确的列表中回答两个问题:

  1. Redis的底层数据结构是什么?
  2. 每种类型的主要优点/缺点/用例是什么?

因此,我读过Redis列表实际上是用链接列表实现的。但是对于其他类型,我无法提取任何信息。同样,如果有人偶然发现了这个问题,而又对修改或访问不同数据结构的优缺点没有一个高层次的总结,那么他们将有完整的清单,列出
何时可以最佳地使用特定类型 进行引用。

具体来说,我希望概述所有类型:字符串,列表,集合,zset和哈希。

到目前为止,我已经看过这些文章,其中包括:


阅读 577

收藏
2020-06-20

共1个答案

小编典典

我将尝试回答您的问题,但首先我会从一开始可能看起来很奇怪的事情开始:如果您对Redis内部不感兴趣, 则不必在意
内部如何实现数据类型。原因很简单:对于每个Redis操作,您都会在文档中找到时间复杂度,并且,如果您拥有一组操作和时间复杂度,则唯一需要做的就是了解内存使用情况的一些线索(而且我们会根据数据进行很多优化,获取这些数据的最佳方法是进行一些琐碎的实际测试。

但是,正如您所问的那样,这是每种Redis数据类型的基础实现。

  • 字符串 是使用C动态字符串库实现的,因此我们无需为附加操作中的分配支付费用(渐近而言)。这样,例如,我们有O(N)个附加项,而不是具有二次行为。
  • 列表 通过链接列表实现。
  • 散列 与哈希表来实现。
  • 排序集 通过跳过列表(平衡树的一种特殊类型)实现。

但是,如果列表,集合和排序集合的项目数少且最大值大,则使用不同的,更紧凑的编码。对于不同的类型,此编码有所不同,但是其特征在于它是一个紧凑的数据块,经常对每个操作强制执行O(N)扫描。由于我们仅将这种格式用于小对象,因此这不是问题。扫描一个小的O(N)Blob可以
忽略高速缓存, 因此从实践上讲它是非常快的,并且当元素过多时,编码会自动切换到本机编码(链接列表,哈希等)。

但是您的问题不仅仅在于内部,而是您 要使用哪种类型来完成任务?

弦乐

这是所有类型的基本类型。它是四种类型之一,也是复杂类型的基本类型,因为List是字符串列表,Set是一组字符串,依此类推。

在要存储HTML页面的所有显而易见的情况下,以及在避免转换已编码数据的情况下,Redis字符串都是一个好主意。因此,例如,如果您具有JSON或MessagePack,则可以将对象存储为字符串。在Redis
2.6中,您甚至可以使用Lua脚本来操纵这种对象服务器端。

字符串的另一种有趣用法是位图,通常是字节的随机访问数组,因为Redis导出命令以访问字节的随机范围甚至单个位。例如,查看以下优秀博客文章:使用Redis的Fast
Easy实时指标

清单

当您可能只触摸列表的极端时(靠近尾巴或靠近头部),列表是不错的选择。列表不是很好的分页内容,因为随机访问速度很慢,O(N)。因此,列表的良好用法是普通队列和堆栈,或者使用具有相同源和目标的RPOPLPUSH在循环中处理项目以“旋转”项目环。

当我们只想创建N个项目的封顶集合时, 通常 我们只访问顶部或底部项目,或者当N小时,列表也很好。

套装

集合是无序的数据集合,因此每次您拥有一个项目集合时它们都很好,并且以非常快速的方式检查集合的存在或大小非常重要。关于集的另一件很酷的事情是支持偷看或弹出随机元素(SRANDMEMBER和SPOP命令)。

集合也可以很好地表示关系,例如“用户X的朋友是什么?” 等等。但是,正如我们将看到的,用于这种东西的其他好的数据结构是排序集。

集合支持复杂的操作,例如交集,并集等,因此,当您有数据并且想要对该数据执行转换以获得一些输出时,这是一种以“计算”方式使用Redis的良好数据结构。

小集合以非常有效的方式编码。

散列

散列是代表由字段和值组成的对象的理想数据结构。散列字段也可以使用HINCRBY自动增加。当您有对象(例如用户,博客文章或其他类型的 项目)时
,如果您不想使用自己的编码(例如JSON或类似格式),则很可能需要使用哈希。

但是,请记住,Redis非常有效地编码了小哈希,并且您可以要求Redis以非常快速的方式原子地获取,设置或递增各个字段。

哈希还可以用于使用引用来表示链接的数据结构。例如,查看lamernews.com评论的实现。

排序集

除列表外, 排序集是 唯一其他可维护有序元素的数据结构 。您可以使用排序集来做很多很酷的事情。例如,您可以在Web应用程序中拥有各种 Top
Something
列表。按分数排名最高的用户,按浏览量排名的最高帖子,排名最高的东西,但是一个Redis实例将支持每秒大量的插入和get-top-
elements操作。

像常规集一样,已排序的集可用于描述关系,但是它们也允许您分页项目列表并记住排序。例如,如果我记得带有排序集的用户X的朋友,我可以轻松地按照接受的朋友的顺序记住他们。

排序集适合于优先级队列。

排序集就像更强大的列表一样,从列表中间插入,删除或获取范围总是非常快。但是它们使用更多的内存,并且是O(log(N))数据结构。

结论

我希望我在这篇文章中提供了一些信息,但是从http://github.com/antirez/lamernews下载lamernews的源代码并了解其工作原理要好得多。Lamer
News内部使用了Redis的许多数据结构,并且有很多线索可以用来解决给定的任务。

抱歉语法错误,在这里是午夜,又太累了,无法阅读这篇文章;)

2020-06-20