Redis使用的基础数据结构是什么？
我试图在一个明确的列表中回答两个问题：
所以，我读过Redis列表实际上是用链表实现的。 但对于其他类型，我无法挖掘任何信息。 另外，如果有人偶然发现了这个问题，并没有对修改或访问不同数据结构的优缺点进行高级总结，那么他们也会有一个完整的列表， 以便最好地使用特定类型来引用。
具体来说，我想要概述所有类型：字符串，列表，集合，zset和散列。
哦，到目前为止，我已经看过这些文章，其中包括：
我会尽量回答你的问题，但是我会先从一些看起来很奇怪的事情开始：如果你对Redis内部没有兴趣，你不应该关心数据类型是如何在内部实现的。 这是一个简单的原因：对于每个Redis操作，您都会发现文档中的时间复杂性，并且如果您有一组操作和时间复杂性，则您需要的唯一其他内容就是关于内存使用情况的一些线索（因为我们做了许多优化，这些优化可能会根据数据而有所不同，获得这些数字的最佳方法是进行一些微不足道的实际测试）。
但是，既然你问了，这是每个Redis数据类型的底层实现。
但是，当列表，集合和有序集合的项目数量和最大值的大小很小时，会使用不同的，更紧凑的编码。 这种编码对于不同的类型有所不同，但具有的特征是它是一个紧凑的数据块，通常会对每个操作强制进行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应用程序中包含各种Top Something列表。 顶级用户评分，顶级页面浏览量，顶级用户，但是单个Redis实例将支持每秒插入和get-top-elements操作数量。
与常规集合一样，排序集合可用于描述关系，但它们还允许您对项目列表进行分页并记住排序。 例如，如果我记住用户X的朋友与一个有序集合，我可以按照接受的友谊的顺序轻松地记住他们。
排序集适合优先队列。
排序集就像更强大的列表，其中从列表中间插入，删除或获取范围总是很快。 但他们使用更多的内存，并且是O（log（N））数据结构。
结论
我希望我在这篇文章中提供了一些信息，但是从http://github.com/antirez/lamernews下载lamernews的源代码并理解它的工作原理会好得多。 来自Redis的许多数据结构在Lamer News中使用，并且有许多关于如何使用来解决特定任务的线索。
对不起，语法错别字，现在是午夜，太累了查看帖子;）
大多数情况下，您不需要了解Redis使用的基础数据结构。 但有一点知识可以帮助您使CPU v / s内存取而代之。 它还可以帮助您以高效的方式建模您的数据。
在内部，Redis使用以下数据结构：
要查找特定密钥使用的object encoding <key> ，请使用命令object encoding <key> 。
1.字符串
在Redis中，字符串被称为简单动态字符串或SDS。 它是一个小char *封装，它允许您将字符串的长度和可用字节数作为前缀存储。
由于字符串的长度存储，strlen是O（1）操作。 另外，由于长度是已知的，Redis字符串是二进制安全的。 包含空字符的字符串是完全合法的。
字符串是Redis中最通用的数据结构。 字符串是以下所有内容：
long可以存储数字。 请参阅INCR，DECR，INCRBY和DECRBY命令。 chars ， ints ， longs ints或任何其他数据类型）。 请参阅SETRANGE和GETRANGE命令。 2.字典
Redis使用以下字典：
Redis字典是使用哈希表实现的。 我不会解释实现，而只是解释Redis的具体事情：
dictType的结构来扩展哈希表的行为。 这个结构有函数指针，所以下面的操作是可扩展的：a）散列函数，b）键比较，c）键析构函数，以及d）值析构函数。 Set数据结构使用Dictionary来保证没有重复。 Sorted Set使用字典将元素映射到其分数，这就是为什么ZSCORE是O（1）操作的原因。
3.双向链接列表
list数据类型是使用双重链接列表实现的。 Redis的实施是直接从算法教科书。 唯一的变化是Redis将这个长度存储在列表数据结构中。 这确保了LLEN具有O（1）的复杂性。
4.跳过列表
Redis使用跳过列表作为排序集合的基础数据结构。 维基百科有一个很好的介绍。 William Pugh的论文Skip Lists：平衡树的概率选择有更多细节。
排序集使用跳过列表和词典。 字典存储每个元素的分数。
Redis的Skip List实现与标准实现有以下不同之处：
5.邮编列表
一个Zip列表就像一个双向链表，除了它不使用指针并将数据存入内联。
双向链表中的每个节点都有3个指针 - 一个前向指针，一个后向指针和一个指向存储在该节点的数据的指针。 指针需要内存（64位系统上的8个字节），所以对于小列表，双向链表的效率非常低。
Zip List按顺序将元素存储在Redis字符串中。 每个元素都有一个小头，它存储元素的长度和数据类型，下一个元素的偏移量和前一个元素的偏移量。 这些偏移量取代了前向和后向指针。 由于数据以内联方式存储，因此我们不需要数据指针。
Zip列表用于存储小列表，排序集合和散列。 排序集合被平化为一个列表，如[element1, score1, element2, score2, element3, score3]并存储在Zip列表中。 哈希被平化为一个列表，如[key1, value1, key2, value2]等。
通过Zip列表，您可以在CPU和内存之间进行权衡。 Zip列表的内存效率很高，但它们使用的CPU比链表（或哈希表/跳过列表）多。 在zip列表中查找元素是O（n）。 插入一个新元素需要重新分配内存。 因此，Redis仅将此编码用于小列表，哈希和有序集合。 您可以通过在<datatype>-max-ziplist-entries更改<datatype>-max-ziplist-entries和<datatype>-max-ziplist-value>的值来调整此行为。 有关更多信息，请参阅Redis内存优化，“小型聚合数据类型的特殊编码”部分。
关于ziplist.c的评论非常好，你可以完全理解这个数据结构，而不必阅读代码。
6. Int集
Int集是“Sorted Integer Arrays”的奇特名称。
在Redis中，集合通常使用散列表来实现。 对于小集合，散列表是无效的记忆智能。 当该集合仅由整数组成时，数组通常更高效。
一个整数集是一个整数排序的数组。 为了找到使用二分搜索算法的元素。 这具有O（logN）的复杂度。 向这个数组添加新的整数可能需要重新分配内存，这对于大整数数组可能会变得很昂贵。
作为进一步的内存优化，Int Sets有3种不同的整数大小：16位，32位和64位。 Redis足够聪明，可以根据元素的大小使用正确的变体。 当添加新元素并超过当前大小时，Redis会自动将其迁移到下一个大小。 如果添加了一个字符串，Redis会自动将Int集合转换为基于常规哈希表的集合。
Int集是CPU和内存之间的折中。 Int集具有极高的内存效率，对于小集，它们比散列表更快。 但是在一定数量的元素之后，O（log N）检索时间和重新分配内存的代价变得太大了。 根据实验，找到切换到常规哈希表的最佳阈值为512.但是，您可以根据您的应用程序的需要增加此阈值（降低它没有意义）。 请参阅set-max-intset-entries 。
7. Zip地图
Zip地图是字典压扁并存储在列表中。 它们与Zip列表非常相似。
自Redis 2.6开始，Zip Maps已被弃用，并且小型哈希存储在Zip列表中。 要了解更多关于此编码的信息，请参阅zipmap.c中的注释。
Redis存储指向值的键。 密钥可以是任何达到合理大小的二进制值（为便于阅读和调试，建议使用短的ASCII字符串）。 值是五种本地Redis数据类型之一。
1.strings - 一个高达512 MB的二进制安全字节序列
2.哈希 - 一组键值对
3.lists - 一个插入顺序的字符串集合
4.sets - 一组没有排序的独特字符串
5.sorted sets - 由用户定义的评分排序的唯一字符串集合
字符串
Redis字符串是一个字节序列。
Redis中的字符串是二进制安全的（意思是它们的长度不是由任何特殊的终止字符决定的），所以你可以在一个字符串中存储512兆字节的内容。
字符串是cannonical“关键价值商店”的概念。 您有一个指向值的键，其中键和值都是文本或二进制字符串。
有关字符串的所有可能操作，请参阅http://redis.io/commands/#string
哈希
Redis哈希是键值对的集合。
Redis哈希包含许多键值对，其中每个键和值都是一个字符串。 Redis哈希不直接支持复杂值（也就是说，您不能让哈希字段具有列表或集合或其他哈希值），但是您可以使用哈希字段来指向其他顶级复杂值。 您可以对散列字段值执行的唯一特殊操作是数字内容的原子增量/减量。
您可以通过两种方式来思考Redis哈希：作为直接对象表示和作为一种紧凑存储许多小值的方式。
直接对象表示很容易理解。 对象有一个名称（哈希键）和一组带有值的内部键。 请看下面的例子，以及一个例子。
使用散列存储很多小值是一种聪明的Redis海量数据存储技术。 当散列具有少量字段（〜100）时，Redis会优化整个散列的存储和访问效率。 Redis的小散列存储优化引发了一个有趣的行为：使用100个内部键和值分别具有100个散列而不是具有10,000个指向字符串值的顶级键的效率更高。 使用Redis哈希来优化您的数据存储这种方式确实需要额外的编程开销来跟踪数据的结束位置，但如果您的数据存储主要基于字符串，则可以使用这个奇怪的技巧节省大量内存开销。
有关散列的所有可能操作，请参阅散列文档
清单
Redis列表就像链接列表一样。
您可以从列表的首部或尾部插入，删除和遍历列表。
当您需要按照插入顺序维护值时使用列表。 （如果需要，Redis会给你选择插入任意列表位置的选项，但是如果远离你的开始位置，插入性能会降低。）
Redis列表通常用作生产者/消费者队列。 将项目插入列表中，然后从列表中弹出项目。 如果您的消费者尝试从没有元素的列表中弹出，会发生什么？ 您可以要求Redis等待元素出现，并在添加元素后立即将其返回给您。 这将Redis转变为实时消息队列/事件/作业/任务/通知系统。
你可以原子地移除列表的任何一端的元素，使任何列表被视为栈或队列。
您还可以在每次插入后将列表修剪为特定大小，以维护固定长度列表（限定集合）。
有关列表中的所有可能操作，请参阅列表文档
集
Redis集合就是集合。
Redis集合包含唯一的无序Redis字符串，其中每个字符串仅在每个集合中存在一次。 如果您将相同元素添加到集合中十次，则它只会显示一次。 集合非常适合懒惰地确保至少存在一次，而不用担心重复的元素累积和浪费空间。 您可以根据需要多次添加相同的字符串，而无需检查它是否已经存在。
集合对会员检查，插入和删除集合中的成员都很快。
正如您所期望的那样，集合具有高效的集合操作。 您可以一次取多个集合的并集，交集和差异。 结果可以返回给调用者，也可以将结果存储在新的集合中供以后使用。
集合对会员资格检查具有恒定的时间访问权限（与列表不同），并且Redis甚至可以方便地随机移除成员并返回（“从集合中弹出一个随机元素”）或随机成员返回而无需替换（“给我30个随机独立用户“）或更换（”给我7张卡，但每次选择后，将卡放回原位，以便可能再次采样“）。
对于所有可能的操作集，请参阅集文档。
排序集
Redis排序集是用户定义的排序集。
为了简单起见，您可以将有序集合看作具有唯一元素的二叉树。 （Redis排序集实际上是跳过列表。）元素的排序顺序由每个元素的分数定义。
排序集仍然是集合。 元素只能在一组中出现一次。 为了唯一性目的，元素由其字符串内容定义。 将排序分数为3的元素“apple”插入，然后将排序分数为500的元素“apple”插入，得到排序集合中排序分数为500的一个元素“apple”。 集合仅基于数据而不唯一，不基于（分数，数据）对。
确保你的数据模型依赖于字符串的内容，而不是元素的唯一性分数。 分数可以重复（甚至为零），但最后一次，set元素只能在每个有序集合中存在一次。 例如，如果您尝试将每个用户登录的历史记录存储为已排序的集合，并将分数设置为登录的时间和用户标识的值，则最终只会为所有用户保存上次登录时间。 您的设置将随着您的用户基数的增加而变大，而不是您希望的用户基数*登录的大小。
元素添加到您的设置与分数。 您可以随时更新任何元素的分数，只需再添加一个新分数即可。 分数由浮点双精度表示，因此您可以根据需要指定高精度时间戳的粒度。 多个元素可能具有相同的分数。
您可以通过几种不同的方式检索元素。 由于一切都已排序，因此您可以要求从最低分数开始的元素。 您可以要求从最高分数开始的元素（“反向”）。 您可以按照自然顺序或相反顺序通过排序得分来询问元素。
对于排序集合上的所有可能操作，请参阅排序集文档。
链接地址: http://www.djcxy.com/p/26955.html上一篇: What are the underlying data structures used for Redis?
下一篇: data structure and algorithm for table allocations in restaurant?