什么是用于Redis的底层数据结构？ [英] What are the underlying data structures used for Redis?
问题描述
我试图回答一个明确的列表中有两个问题：
I'm trying to answer two questions in a definitive list:
- 什么是用于Redis的底层数据结构？
- 什么是主要优势/劣势/用例为每种类型的？
所以，我读过的Redis的名单实际上是用链表实现的。但对于其他类型的，我不能挖的任何信息。此外，如果有人偶然发现这个问题，并没有足够的优点和修改或访问不同的数据结构的利弊高水平的总结，他们就会有时，最好使用特定类型引用为好。
So, I've read the Redis lists are actually implemented with linked lists. But for other types, I'm not able to dig up any information. Also, if someone were to stumble upon this question and not have a high level summary of the pros and cons of modifying or accessing different data structures, they'd have a complete list of when to best use specific types to reference as well.
具体而言，我正在寻找勾勒出所有类型：字符串，列表，集，zset和散列
Specifically, I'm looking to outline all types: string, list, set, zset and hash.
呵呵，我已经看了这些文章，除其他外，到目前为止：
Oh, I've looked at these article, among others, so far:
- http://redis.io/topics/data-types
- http://redis.io/topics/data-types-intro
- http://redis.io/topics/faq
- http://redis.io/topics/data-types
- http://redis.io/topics/data-types-intro
- http://redis.io/topics/faq
推荐答案
我会尽力回答你的问题，但我将开始与一些可能看起来很奇怪，在第一：如果你不感兴趣，Redis的内部，你< STRONG>不应该关心关于数据类型是如何在内部实现。这是一个简单的道理：每Redis的操作，你会发现文档中的时间复杂度，如果你有一组操作的时间复杂度，你唯一需要的另一件事是一些关于内存使用情况的线索（因为我们这样做可能会因数据各不相同许多优化，以获得后者的数字最好的办法是做一些琐碎的现实世界的测试）。
I'll try to answer your question, but I'll start with something that may look strange at first: if you are not interested in Redis internals you should not care about how data types are implemented internally. This is for a simple reason: for every Redis operation you'll find the time complexity in the documentation and, if you have the set of operations and the time complexity, the only other thing you need is some clue about memory usage (and because we do many optimizations that may vary depending on data, the best way to get these latter figures are doing a few trivial real world tests).
不过既然你问，这里是每一个Redis的数据类型的底层实现。
But since you asked, here is the underlying implementation of every Redis data type.
- 字符串正在使用C动态字符串库中实现，使我们不支付（渐进地说）在追加操作的分配。通过这种方式，我们有O（N）追加，而无需二次行为，例如，
- 列表与链表实现的。
- 设置和散列与哈希表来实现。
- 排序集与跳表<实施/一>（一种特殊类型的平衡树）。
- Strings are implemented using a C dynamic string library so that we don't pay (asymptotically speaking) for allocations in append operations. This way we have O(N) appends, for instance, instead of having quadratic behavior.
- Lists are implemented with linked lists.
- Sets and Hashes are implemented with hash tables.
- Sorted sets are implemented with skip lists (a peculiar type of balanced trees).
但是，当列表，集合，和排序集都是小项目的数量和最大值的大小，不同的，更紧凑的编码。此编码不同对于不同类型的，但具有如下特征：它是数据的简洁斑点经常迫使O（N）扫描每个操作。因为我们使用这种格式只为小物件，这不是一个问题;扫描一个小的O（N）BLOB是缓存无视的所以实际上来说这是非常快的，当有太多的元素编码自动切换到本地编码（链表，哈希，等等类推）。
But when lists, sets, and sorted sets are small in number of items and size of the largest values, a different, much more compact encoding is used. This encoding differs for different types, but has the feature that it is a compact blob of data that often forces an O(N) scan for every operation. Since we use this format only for small objects this is not an issue; scanning a small O(N) blob is cache oblivious so practically speaking it is very fast, and when there are too many elements the encoding is automatically switched to the native encoding (linked list, hash, and so forth).
但你的问题是不是真的只是内部，你的观点是的什么类型的使用来完成什么？的。
But your question was not really just about internals, your point was What type to use to accomplish what?.
这是所有类型的基本类型。它是四种类型中的一种，但也是复杂类型的基本类型，因为一个列表是字符串的列表，一个集是一组字符串，等等。
This is the base type of all the types. It's one of the four types but is also the base type of the complex types, because a List is a list of strings, a Set is a set of strings, and so forth.
一个Redis的字符串是所有要存储一个HTML页面里明显的情况下是一个好主意，而且当你想避免转换您已连接codeD数据。因此，举例来说，如果你有JSON或MessagePack你可能只是存储对象的字符串。在Redis的2.6，你甚至可以操纵这种类型的对象服务器端使用Lua脚本。
A Redis string is a good idea in all the obvious scenarios where you want to store an HTML page, but also when you want to avoid converting your already encoded data. So for instance, if you have JSON or MessagePack you may just store objects as strings. In Redis 2.6 you can even manipulate this kind of object server side using Lua scripts.
的字符串的另一个有趣的用途是位图，并以字节为一般的随机存取阵列中，由于Redis的出口的命令来访问随机范围的字节，或甚至单个比特。例如检查这一良好的博客文章：快速方便实时指标使用Redis的。
Another interesting usage of strings is bitmaps, and in general random access arrays of bytes, since Redis exports commands to access random ranges of bytes, or even single bits. For instance check this good blog post: Fast Easy real time metrics using Redis.
列表是不错的，当你很可能会接触到只有列表的极端：尾附近，或靠近头部。列表是不是很好分页的东西，因为随机访问速度很慢，O（N）。 所以列出的良好的用途是使用RPOPLPUSH具有相同的源和目的地为旋转的项目的环平原队列和堆栈，或在一个循环处理项目
Lists are good when you are likely to touch only the extremes of the list: near tail, or near head. Lists are not very good to paginate stuff, because random access is slow, O(N). So good uses of lists are plain queues and stacks, or processing items in a loop using RPOPLPUSH with same source and destination to "rotate" a ring of items.
列表都还不错，当我们只想创建N个项目，其中的一般的访问，我们就在顶部或底部的项目，或当N是一个小的上限集合。
Lists are also good when we want just to create a capped collection of N items where usually we access just the top or bottom items, or when N is small.
设定是一个无序的数据收集，所以他们是很好的，每次有项目的集合时间，这是非常重要的一个非常快速的方式来检查是否存在或集合的大小。关于套另一个很酷的事情是偷看或弹出随机元素（SRANDMEMBER和SPOP命令）的支持。
Sets are an unordered data collection, so they are good every time you have a collection of items and it is very important to check for existence or size of the collection in a very fast way. Another cool thing about sets is support for peeking or popping random elements (SRANDMEMBER and SPOP commands).
设定都还不错，重新present关系，如什么是朋友用户X？等等。但其他好的数据结构的这种东西的顺序设定，我们将拭目以待。
Sets are also good to represent relations, e.g., "What are friends of user X?" and so forth. But other good data structures for this kind of stuff are sorted sets as we'll see.
设定支持诸如十字路口，工会等复杂的操作，所以这是一个很好的数据结构里的计算的方式使用Redis的，当你有数据，并要对这些数据进行转换，以获得一些输出
Sets support complex operations like intersections, unions, and so forth, so this is a good data structure for using Redis in a "computational" manner, when you have data and you want to perform transformations on that data to obtain some output.
小套都设有codeD在一个非常有效的方式。
Small sets are encoded in a very efficient way.
哈希是完美的数据结构来重新present的对象，领域和值组成。哈希值的字段也可以使用HINCRBY被原子递增。当你有对象，如用户，博客文章，或者一些其他类型的项目的，哈希很可能要走的路，如果你不想使用自己的编码像JSON或类似的。
Hashes are the perfect data structure to represent objects, composed of fields and values. Fields of hashes can also be atomically incremented using HINCRBY. When you have objects such as users, blog posts, or some other kind of item, hashes are likely the way to go if you don't want to use your own encoding like JSON or similar.
但是，请记住，小的散列连接codeD非常有效地Redis的，你可以问Redis的原子地获取，设置或增加在一个非常快时尚的各个字段。
However, keep in mind that small hashes are encoded very efficiently by Redis, and you can ask Redis to atomically GET, SET or increment individual fields in a very fast fashion.
散列也可以用来重新present联的数据结构，使用参考。例如检查lamernews.com实施意见。
Hashes can also be used to represent linked data structures, using references. For instance check the lamernews.com implementation of comments.
排序集是唯一的其他数据结构，除了列表，以维持有序元素的。你可以做一些很酷的东西与排序集。例如，你可以有各种热门的东西列表中的Web应用程序。顶级用户可以通过得分，顶帖浏览量，上什么，而是一个Redis的实例将支持吨插入并获得顶元素操作每秒。
Sorted sets are the only other data structures, besides lists, to maintain ordered elements. You can do a number of cool stuff with sorted sets. For instance, you can have all kinds of Top Something lists in your web application. Top users by score, top posts by pageviews, top whatever, but a single Redis instance will support tons of insertion and get-top-elements operations per second.
有序集合，像普通套，可以用来描述关系，但他们也让你分页的项目清单，并记住顺序。举例来说，如果我没有记错的朋友用户X的一个有序集合，我可以很容易地记住他们，为接受的友谊。
Sorted sets, like regular sets, can be used to describe relations, but they also allow you to paginate the list of items and to remember the ordering. For instance, if I remember friends of user X with a sorted set I can easily remember them in order of accepted friendship.
排序集有利于优先级队列。
Sorted sets are good for priority queues.
排序集一样更强大的列表，其中插入，删除，或从列表中的中间得到的范围总是很快。但是，他们使用更多的内存，并且是O（日志（N））的数据结构。
Sorted sets are like more powerful lists where inserting, removing, or getting ranges from the the middle of the list is always fast. But they use more memory, and are O(log(N)) data structures.
我希望我提供在这篇文章中一些信息，但它远远不如从 HTTP下载lamernews源$ C $ C： //github.com/antirez/lamernews 并了解它是如何工作的。从Redis的许多数据结构被用于内部拉默新闻，并且有将要使用什么解决给定的任务多线索。
I hope that I provided some info in this post, but it is far better to download the source code of lamernews from http://github.com/antirez/lamernews and understand how it works. Many data structures from Redis are used inside Lamer News, and there are many clues about what to use to solve a given task.
抱歉语法拼写错误，这是午夜时分这里累得审查后;）
Sorry for grammar typos, it's midnight here and too tired to review the post ;)
这篇关于什么是用于Redis的底层数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
