如何在db中表示树状结构 [英] How to represent a tree like structure in a db

问题描述

我开始一个项目，我在设计阶段：也就是说，我还没有决定使用哪个db框架。我将有代码创建一个森林像结构。也就是说，许多树，其中每棵树是标准的：节点和边。代码创建这些树后，我想将它们保存在db中。 （然后最终拉出它们）

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)

在数据库中表示数据的朴素方法是一个关系数据库，有两个表：节点和边。也就是说，节点表将具有节点id，节点数据等。并且边表将是节点id到节点id的映射。

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中的blob更好？在这种情况下应该使用哪种类型的数据库？请评论速度/可扩展性。

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.

感谢

推荐答案

我展示了一个类似于您的节点;边缘表，在我的回答StackOverflow问题：将平面表解析成树的最有效/优雅的方法是什么？我称这个解决方案为Closure Table。

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".

我在SQL中做了关于存储和使用树的不同方法的演示，使用SQL和PHP的分层数据模型。我演示了使用正确的索引（取决于你需要运行的查询），Closure Table设计可以有非常好的性能，即使是在大集合的边缘（在我的演示中大约500K边缘）。

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反模式：避免数据库编程的缺陷。

I also covered the design in my book, SQL Antipatterns: Avoiding the Pitfalls of Database Programming.

这篇关于如何在db中表示树状结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！