小编典典

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

redis

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

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

所以,我读过Redis列表实际上是用链表实现的。但对于其他类型,我无法挖掘任何信息。此外,如果有人偶然发现了这个问题,并且没有对修改或访问不同数据结构的利弊进行高级总结,他们也会有一个完整的列表,说明何时最好地使用特定类型进行引用。

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


阅读 265

收藏
2021-12-29

共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 以非常快的方式原子地 GET、SET 或递增单个字段。

散列也可以用来表示链接的数据结构,使用引用。例如检查 lamernews.com 评论的实现。

排序集

排序集是除列表之外唯一用于维护有序元素的其他数据结构。你可以用排序集做一些很酷的事情。例如,您可以在您的 Web 应用程序中拥有各种Top Something列表。按分数排名最高的用户,按页面浏览量排名最高的帖子,无论什么排名最高,但单个 Redis 实例将支持每秒大量的插入和获取顶部元素的操作。

排序集与常规集一样,可用于描述关系,但它们也允许您对项目列表进行分页并记住顺序。例如,如果我记得用户 X 的朋友有一个排序的集合,我可以很容易地按照接受的友谊顺序记住他们。

排序集适用于优先队列。

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

2021-12-29