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

我将尝试回答你的问题，但我将从一些可能看起来奇怪的东西开始:如果你对Redis内部不感兴趣，你不应该在意关于数据类型是如何内部实现的。原因很简单:对于每一个Redis操作，你都会在文档中找到时间复杂度，如果你有一组操作和时间复杂度，你唯一需要的是一些关于内存使用的线索(因为我们做了许多优化，这些优化可能会根据数据而变化，获得这些数据的最佳方法是做一些琐碎的现实测试)。

但既然你问了，这里是每个Redis数据类型的底层实现。

• 字符串是使用C动态字符串库实现的，因此我们不需要(渐进地说)为追加操作中的分配付费。这样我们就有O(N)个追加，而不是二次行为。
• 列表是用链表实现的。
• 集和散列是用哈希表实现的。
• 排序集是用跳跃表(一种特殊类型的平衡树)实现的。

但是，当列表、集合和排序集的项数量和最大值的大小较小时，则使用不同的、更紧凑的编码。这种编码因不同类型而不同，但有一个特点，即它是一个紧凑的数据团，通常强制对每个操作进行O(N)扫描。因为我们只对小对象使用这种格式，所以这不是问题;扫描一个小的O(N) blob是缓存无关，所以实际上它是非常快的，当有太多的元素时，编码会自动切换到本机编码(链表，哈希等等)。

但是你的问题不仅仅是关于内部，你的观点是用什么类型来完成什么?。

字符串

这是所有类型的基类型。它是四种类型之一，但也是复杂类型的基类型，因为List是字符串的列表，Set是字符串的集合，等等。

在所有想要存储HTML页面的明显场景中，Redis字符串都是一个好主意，但当你想避免转换已经编码的数据时也是如此。例如，如果你有JSON或MessagePack，你可以将对象存储为字符串。在Redis 2.6中，你甚至可以使用Lua脚本操作这种对象服务器端。

字符串的另一个有趣的用法是位图，通常是字节的随机访问数组，因为Redis导出命令来访问字节的随机范围，甚至单个位。例如，检查这篇很好的博客文章:使用Redis快速简单的实时度量。

列表

当你可能只接触到列表的极端情况时，列表是很好的:接近尾部或接近头部。列表不太适合分页，因为随机访问很慢O(N)。 因此，列表的良好用途是普通队列和堆栈，或者使用具有相同源和目标的RPOPLPUSH来处理循环中的项，以“旋转”一圈项

当我们只想创建一个有上限的N项集合时，列表也很好，其中通常只访问顶部或底部的项，或者当N很小时。

集

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

集合也可以很好地表示关系，例如，“用户X的朋友是谁?”等等。但是其他好的数据结构是我们会看到的排序集。

集支持复杂的操作，如交叉，并，等等，所以这是一个很好的数据结构使用Redis在“计算”的方式，当你有数据，你想要对数据执行转换，以获得一些输出。

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

散列

哈希是表示对象的完美数据结构，由字段和值组成。还可以使用HINCRBY对哈希字段进行原子增量。当你有用户、博客文章或其他类型的项对象时，如果你不想使用自己的编码，比如JSON或类似的，哈希可能是一种方法。

然而，请记住，Redis对小散列进行了非常有效的编码，你可以要求Redis以非常快的方式原子地GET, SET或增加单个字段。

哈希还可以使用引用来表示链接的数据结构。例如，检查lamernews.com的注释实现。

排序集

排序集是只有除列表之外的其他数据结构才能维护有序的元素。你可以用排序集做很多很酷的事情。例如，你可以在你的web应用程序中有各种各样的上面的东西列表。排名靠前的用户，排名靠前的文章，排名靠前的等等，但是一个Redis实例每秒将支持大量的插入和获取Top -elements操作。

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

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

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

结论

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

抱歉有语法错误，现在是午夜，太累了，没有时间看这篇文章;)

大多数时候，你不需要理解Redis使用的底层数据结构。但是一些知识可以帮助你做出CPU v/s内存的权衡。它还可以帮助您以有效的方式对数据建模。

在内部，Redis使用以下数据结构:

1. 字符串
2. 字典
3. 双链表
4. 跳跃表
5. 邮政编码列表
6. Int集
7. Zip地图(自Redis 2.6起已弃用，支持Zip列表)

要找到特定键使用的编码，使用命令object encoding <key>。

1. 字符串

在Redis中，字符串被称为简单动态字符串，或SDS。它是char *上的一个较小的包装器，允许您将字符串的长度和空闲字节数作为前缀存储。

因为字符串的长度被存储，所以strlen是一个O(1)操作。此外，因为长度是已知的，Redis字符串是二进制安全的。字符串包含null字符是完全合法的。

字符串是Redis中最通用的数据结构。字符串是以下类型的所有:

1. 可以存储文本的字符串。参见集和得到命令。
2. 可以存储二进制数据的字节数组。
3. 可以存储数字的long。参见增加， 12月， INCRBY和DECRBY命令。
4. 一个数组(chars， ints， longs或任何其他数据类型)，可以允许有效的随机访问。参见SETRANGE和GETRANGE命令。
5. 允许你设置或获取单个位的位数组。参见SETBIT和GETBIT命令。
6. 可用于构建其他数据结构的内存块。这在内部用于构建ziplist和intset，它们是用于少量元素的紧凑、内存高效的数据结构。下文将详细介绍。

2. 字典

Redis使用字典来实现以下功能:

1. 将键映射到其关联值，其中值可以是字符串、散列、集合、排序集合或列表。
2. 将密钥映射到其到期时间戳。
3. 实现Hash、Set和Sorted Set数据类型。
4. 将Redis命令映射到处理这些命令的函数。
5. 将Redis键映射到被该键阻塞的客户端列表。看到BLPOP。

Redis字典是使用哈希表实现的。我将不解释实现，只解释Redis的具体内容:

1. 字典使用一个名为dictType的结构来扩展哈希表的行为。该结构具有函数指针，因此以下操作是可扩展的:a)哈希函数，b)键比较，c)键析构函数，和d)值析构函数。
2. 字典使用murmurhash2。(之前他们使用了Djb2哈希函数, seed=5381，但后来使用了哈希函数被换成了低语。参见这个问题用于解释djb2哈希算法)。
3. Redis使用增量哈希，也称为增量调整。字典有两个哈希表。每当字典为感动了时，就会有一个桶从第一个(较小的)哈希表迁移到第二个哈希表。这样，Redis就避免了昂贵的调整大小操作。

Set数据结构使用Dictionary来保证没有重复项。Sorted Set使用字典将一个元素映射到它的分数，这就是为什么ZSCORE是一个O(1)操作。

3.双链表

list数据类型是使用双链表实现的。Redis的实现直接来自于算法教科书。唯一的变化是Redis将长度存储在列表数据结构中。这确保LLEN具有O(1)复杂度。

4. 跳跃表

Redis使用跳跃表作为排序集的底层数据结构。维基百科有一个很好的介绍。William Pugh的论文跳跃表:平衡树的概率替代方案有更多细节。

排序集同时使用跳过表和字典。字典存储每个元素的分数。

Redis的跳跃列表实现在以下方面与标准实现不同:

1. Redis允许重复得分。如果两个节点有相同的分数，它们将根据辞典编纂的顺序进行排序。
2. 每个节点在0级有一个后向指针。这允许您以分数的相反顺序遍历元素。

5. 邮政编码列表

Zip List类似于双链表，只是它不使用指针并内联存储数据。

双链表中的每个节点都有3个指针——一个前向指针、一个后向指针和一个用于引用存储在该节点上的数据的指针。指针需要内存(64位系统需要8个字节)，因此对于小列表，双链表的效率非常低。

Zip列表在Redis字符串中按顺序存储元素。每个元素都有一个小的头部，存储元素的长度和数据类型，下一个元素的偏移量和上一个元素的偏移量。这些偏移量替换向前指针和向后指针。由于数据是内联存储的，因此不需要数据指针。

Zip列表用于存储小列表、排序集和散列。排序集被平摊成类似[element1, score1, element2, score2, element3, score3]的列表并存储在Zip list中。哈希被平铺成一个列表，如[key1, value1, key2, value2]等。

使用Zip列表，您可以在CPU和内存之间进行权衡。Zip列表是内存高效的，但它们比链表(或哈希表/跳跃表)使用更多的CPU。在zip列表中查找一个元素是O(n)。插入新元素需要重新分配内存。正因为如此，Redis只对小列表、散列和排序集使用这种编码。你可以通过改变redis.conf中<datatype>-max-ziplist-entries和<datatype>-max-ziplist-value>的值来调整这种行为。更多信息见Redis内存优化，章节“小聚合数据类型的特殊编码”。

c .关于ziplist的评论是优秀的，你可以完全理解这个数据结构，而不需要阅读代码。

6. Int集

整型集是“排序整型数组”的花哨名称。

在Redis中，集合通常使用哈希表实现。对于小的集合，哈希表在内存方面是低效的。当集合仅由整数组成时，数组通常更有效。

Int Set是一个已排序的整数数组。要查找一个元素，使用二分搜索算法。这有一个O(log N)的复杂度。向这个数组中添加新的整数可能需要重新分配内存，这对于大的整数数组来说是非常昂贵的。

作为进一步的内存优化，Int集有3种不同整数大小的变体:16位、32位和64位。Redis非常聪明，可以根据元素的大小使用正确的变体。当添加一个新元素并且超出当前大小时，Redis会自动将其迁移到下一个大小。如果添加了一个字符串，Redis会自动将Int集转换为基于常规哈希表的集合。

Int集是CPU和内存之间的权衡。Int集是非常有效的内存，对于小集，它们比哈希表更快。但是在一定数量的元素之后，O(log N)的检索时间和重新分配内存的成本变得太多了。通过实验，发现切换到常规哈希表的最佳阈值为512。但是，您可以根据应用程序的需要提高这个阈值(降低它没有意义)。参见redis.conf中的set-max-intset-entries。

7. Zip地图

Zip map是扁平的字典，存储在列表中。它们非常类似于Zip列表。

自Redis 2.6以来，Zip map已弃用，小散列存储在Zip列表中。要了解关于这种编码的更多信息，请参考zipmap.c中的注释。

Redis存储指向值的键。键可以是任意大小合理的二进制值(为了可读性和调试目的，建议使用短ASCII字符串)。值是Redis的五种原生数据类型之一。

1.strings -一个最大512 MB的二进制安全字节序列

2.哈希-键值对的集合

3.列表——字符串的插入顺序集合

4.集合——没有顺序的唯一字符串的集合

5.排序集-由用户定义评分排序的唯一字符串的集合

字符串

Redis字符串是一个字节序列。

Redis中的字符串是二进制安全的(意味着它们有一个已知的长度，而不是由任何特殊的终止字符决定的)，所以你可以在一个字符串中存储最多512兆字节的任何东西。

字符串是标准的“键值存储”;的概念。你有一个指向值的键，其中键和值都是文本或二进制字符串。

有关字符串的所有可能操作，请参见 http://redis.io/commands/#string < / p >

散列

Redis哈希是键值对的集合。

Redis哈希包含许多键值对，其中每个键和值都是一个字符串。Redis哈希不直接支持复杂值(这意味着，你不能让一个哈希字段有一个列表或集合或其他哈希值)，但你可以使用哈希字段指向其他顶级复杂值。您可以对哈希字段值执行的唯一特殊操作是数字内容的原子增量/减量。

你可以用两种方式来考虑Redis哈希:一种直接的对象表示，一种紧凑地存储许多小值的方式。

直接对象表示很容易理解。对象有一个名称(散列的键)和一组带值的内部键。请看下面的例子。

使用散列存储许多小值是一种聪明的Redis海量数据存储技术。当一个哈希只有少量的字段(~100)时，Redis会优化整个哈希的存储和访问效率。Redis的小哈希存储优化提出了一个有趣的行为:拥有100个哈希，每个哈希有100个内部键和值，比拥有10,000个顶级键指向字符串值更有效。使用Redis哈希以这种方式优化数据存储确实需要额外的编程开销来跟踪数据的最终位置，但如果你的数据存储主要是基于字符串的，使用这个奇怪的技巧可以节省大量的内存开销。

对于哈希值的所有可能操作，请参见散列文件

列表

Redis列表就像链表一样。

可以从列表的头部或尾部向列表插入、删除和遍历列表。

当您需要按照插入值的顺序维护值时，请使用列表。(如果你需要的话，Redis确实给了你插入到任意列表位置的选项，但是如果你插入的位置远离你的起始位置，你的插入性能会降低。)

Redis列表通常用作生产者/消费者队列。向列表中插入项，然后从列表中弹出项。如果用户试图从一个没有元素的列表中弹出，会发生什么?你可以让Redis等待一个元素出现，并在它被添加时立即返回给你。这将Redis变成一个实时消息队列/事件/作业/任务/通知系统。

您可以从列表的任意一端原子地删除元素，从而使任何列表都可以被视为堆栈或队列。

您还可以通过在每次插入后将列表修剪为特定大小来维护固定长度的列表(有上限的集合)。

对于列表上所有可能的操作，请参见列出了文档 . xml

集

Redis集合是集合。

Redis集合包含唯一的无序Redis字符串，其中每个字符串在一个集合中只存在一次。如果你将相同的元素添加到一个集合十次，它只会显示一次。集合非常适合惰性地确保某些东西至少存在一次，而不用担心重复元素的积累和浪费空间。您可以随心所欲地多次添加相同的字符串，而不需要检查它是否已经存在。

集合可以快速地检查、插入和删除集合中的成员。

集合具有高效的集合操作，正如您所期望的那样。你可以同时取多个集合的并集、交集和差集。结果可以返回给调用者，也可以存储在一个新的集合中以供以后使用。

集合有恒定的时间访问成员检查(不像列表)，Redis甚至有方便的随机成员删除和返回(“从集合中弹出一个随机元素”)或随机成员返回而不替换(“给我30个随机的唯一用户”)或替换(“给我7张卡片，但每次选择后，把卡片放回去，这样它就可以再次采样”)。

对于集合上所有可能的操作，请参见设置文档。

排序集

Redis排序集是用户定义的排序集。

为简单起见，您可以将已排序的集合看作具有唯一元素的二叉树。(Redis排序集实际上是跳跃表。)元素的排序顺序由每个元素的得分定义。

排序的集合仍然是集合。元素在一个集合中只能出现一次。为了唯一性，元素是由它的字符串内容定义的。插入元素“apple”;排序得分为3，然后插入元素"apple"排序得分500的结果在一个元素“苹果”;在你的排序集中有500的排序分数。集合仅基于数据而不是基于(Score, Data)对是唯一的。

确保您的数据模型依赖于字符串内容，而不是元素的唯一性得分。分数允许重复(甚至为零)，但是最后一次，set元素在每个排序的set中只能存在一次。例如，如果您试图将每个用户登录的历史记录存储为一个排序集，方法是将得分作为登录的历元，将值作为用户id，那么您最终将只存储所有用户的最后一次登录历元。你的集合会增长到你的用户群的大小，而不是你想要的用户群*登录的大小。

元素与分数一起添加到您的集合中。您可以随时更新任何元素的分数，只需再次添加一个新分数的元素。分数由浮点双精度精度表示，因此可以在需要时指定高精度时间戳的粒度。多个元素可能具有相同的分数。

可以用几种不同的方式检索元素。由于所有内容都已排序，因此可以从最低值开始请求元素。您可以请求从最高分开始的元素(“反过来”)。您可以根据元素的排序分数按自然顺序或倒序请求它们。

对于排序集的所有可能的操作，请参见Sorted设置文档。