如何在数据库中表示树状结构 [英] How to represent a tree like structure in a 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)

在 db 中表示数据的天真方法是具有两个表的关系数据库:节点和边.也就是说，节点表将有节点 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 问题的回答中:将平面表解析为树的最有效/最优雅的方法是什么? 我将此解决方案称为闭包表".

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 的分层数据.我证明了使用正确的索引(取决于您需要运行的查询)，闭包表设计可以具有非常好的性能，即使是在大量边(在我的演示中大约 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 反模式:避免数据库编程的陷阱中介绍了该设计.

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