database 如何在数据库中表示树状结构
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6567385/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to represent a tree like structure in a db
提问by Guy
I'm starting a project and I'm in the designing phase: I.e., I haven't decided yet on which db framework I'm going to use. I'm going to have code that creates a "forest" like structure. That is, many trees, where each tree is a standard: nodes and edges. After the code creates these trees I want to save them in the db. (and then pull them out eventually)
我正在开始一个项目，我正处于设计阶段：即，我还没有决定要使用哪个数据库框架。我将拥有创建类似“森林”结构的代码。也就是说，许多树，其中每棵树都是一个标准：节点和边。在代码创建这些树后，我想将它们保存在数据库中。（然后最终将它们拉出）
The naive approach to representing the data in the db is a relational db with two tables: nodes and edges. That is, the nodes table will have a node id, node data, etc.. And the edges table will be a mapping of node id to node id.
在 db 中表示数据的天真方法是具有两个表的关系数据库：节点和边。也就是说，节点表将有节点 id、节点数据等。而边表将是节点 id 到节点 id 的映射。
Is there a better approach? Or given the (limited) assumptions I'm giving this is the best approach? How about if we add an assumption that the trees are relatively small - is it better to save the whole tree as a blob in the db? Which type of db should I use in that case? Please comment on speed/scalability.
有没有更好的方法？或者考虑到我给出的（有限的）假设，这是最好的方法？如果我们添加一个假设，即树相对较小 - 将整棵树保存为 db 中的 blob 会更好吗？在这种情况下我应该使用哪种类型的数据库？请评论速度/可扩展性。
Thanks
谢谢
采纳答案by Bill Karwin
I showed a solution similar to your nodes & edges tables, in my answer to the StackOverflow question: What is the most efficient/elegant way to parse a flat table into a tree?I call this solution "Closure Table".
在我对 StackOverflow 问题的回答中，我展示了一个类似于您的节点和边表的解决方案：将平面表解析为树的最有效/最优雅的方法是什么？我称这个解决方案为“Closure Table”。
I did a presentation on different methods of storing and using trees in SQL, Models for Hierarchical Data with SQL and PHP. I demonstrated that with the right indexes (depending on the queries you need to run), the Closure Table design can have very good performance, even over large collections of edges (about 500K edges in my demo).
我做了一个关于在 SQL 中存储和使用树的不同方法、使用SQL 和 PHP 的分层数据模型的演示。我证明了使用正确的索引（取决于您需要运行的查询），闭包表设计可以具有非常好的性能，即使是在大的边集合上（在我的演示中大约有 500K 边）。
I also covered the design in my book, SQL Antipatterns: Avoiding the Pitfalls of Database Programming.
我还在我的《SQL 反模式：避免数据库编程的陷阱》一书中介绍了该设计。
回答by eric
Be sure to use some sort of low level-coding for the entity being treed to prevent looping. The entity might be a part, subject, folder, etc.
确保对正在树状化的实体使用某种低级编码以防止循环。实体可能是部件、主题、文件夹等。
With an Entity file and and Entity-Xref file you can loop through one of say two relationships between the two files, a parent and a child relation.
使用 Entity 文件和 Entity-Xref 文件，您可以遍历两个文件之间的两个关系之一，即父关系和子关系。
A level is the level an entity found in a tree. A low-level-code for the entity is the lowest level an entity is found in any tree anywhere. Check to make sure the low level code of the entity you want to make a child is less than or equal to prevent a loop. after adding an entity as a child it will become at least one level lower.
级别是实体在树中找到的级别。实体的低级代码是实体在任何位置的任何树中找到的最低级别。检查以确保要创建子项的实体的低级代码小于或等于以防止循环。将实体添加为子实体后，它将至少降低一级。
