SQL 树数据结构的数据库结构
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/935098/
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
Database Structure for Tree Data Structure
提问by CodeMonkey1313
What would be the best way to implement a customizable (meaning, a tree structure with an unknown number of level) tree data structure in a database?
在数据库中实现可定制的（意思是，具有未知级别数的树结构）树数据结构的最佳方法是什么？
I've done this once before using a table with a foreign key to itself.
在使用带有外键的表之前，我已经这样做过一次。
What other implementations could you see, and does this implementation make sense?
你还能看到哪些其他实现，这个实现有意义吗？
采纳答案by JeremyDWill
You mention the most commonly implemented, which is Adjacency List: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets
您提到了最常用的实现，即邻接列表：https: //blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets
There are other models as well, including materialized path and nested sets: http://communities.bmc.com/communities/docs/DOC-9902
还有其他模型，包括物化路径和嵌套集：http: //communities.bmc.com/communities/docs/DOC-9902
Joe Celko has written a book on this subject, which is a good reference from a general SQL perspective (it is mentioned in the nested set article link above).
Joe Celko 写了一本关于这个主题的书，从一般 SQL 的角度来看，这是一个很好的参考（在上面的嵌套集文章链接中提到过）。
Also, Itzik Ben-Gann has a good overview of the most common options in his book "Inside Microsoft SQL Server 2005: T-SQL Querying".
此外，Itzik Ben-Gann 在他的书“Inside Microsoft SQL Server 2005：T-SQL Querying”中对最常见的选项进行了很好的概述。
The main things to consider when choosing a model are:
选择模型时要考虑的主要事项是：
1) Frequency of structure change - how frequently does the actual structure of the tree change. Some models provide better structure update characteristics. It is important to separate structure changes from other data changes however. For example, you may want to model a company's organizational chart. Some people will model this as an adjacency list, using the employee ID to link an employee to their supervisor. This is usually a sub-optimal approach. An approach that often works better is to model the org structure separate from employees themselves, and maintain the employee as an attribute of the structure. This way, when an employee leaves the company, the organizational structure itself does not need to be changes, just the association with the employee that left.
1) 结构变化的频率——树的实际结构变化的频率。一些模型提供更好的结构更新特性。然而，将结构更改与其他数据更改分开是很重要的。例如，您可能想要为公司的组织结构图建模。有些人会将其建模为邻接列表，使用员工 ID 将员工与其主管联系起来。这通常是次优方法。通常效果更好的方法是将组织结构与员工本身分开建模，并将员工作为结构的一个属性进行维护。这样，当员工离开公司时，组织结构本身不需要发生变化，只需与离职员工的关联即可。
2) Is the tree write-heavy or read-heavy - some structures work very well when reading the structure, but incur additional overhead when writing to the structure.
2) 树是写重读还是重读——一些结构在读取结构时工作得很好，但在写入结构时会产生额外的开销。
3) What types of information do you need to obtain from the structure - some structures excel at providing certain kinds of information about the structure. Examples include finding a node and all its children, finding a node and all its parents, finding the count of child nodes meeting certain conditions, etc. You need to know what information will be needed from the structure to determine the structure that will best fit your needs.
3) 你需要从结构中获取什么类型的信息——一些结构擅长提供关于结构的某些类型的信息。示例包括查找节点及其所有子节点、查找节点及其所有父节点、查找满足特定条件的子节点数等。您需要知道从结构中需要哪些信息来确定最适合的结构您的需求。
回答by Ayman Hourieh
Have a look at Managing Hierarchical Data in MySQL. It discusses two approaches for storing and managing hierarchical (tree-like) data in a relational database.
看看在 MySQL中管理分层数据。它讨论了在关系数据库中存储和管理分层（树状）数据的两种方法。
The first approach is the adjacency list model, which is what you essentially describe: having a foreign key that refers to the table itself. While this approach is simple, it can be very inefficient for certain queries, like building the whole tree.
第一种方法是邻接表模型，这就是您本质上所描述的：拥有一个引用表本身的外键。虽然这种方法很简单，但对于某些查询（例如构建整个树）来说效率可能非常低。
The second approach discussed in the article is the nested set model. This approach is far more efficient and flexible. Refer to the article for detailed explanation and example queries.
文章中讨论的第二种方法是嵌套集模型。这种方法更加有效和灵活。有关详细说明和示例查询，请参阅文章。
回答by yurilo
If you have to use Relational DataBase to organize tree data structure then Postgresql has cool ltree module that provides data type for representing labels of data stored in a hierarchical tree-like structure. You can get the idea from there.(For more information see: http://www.postgresql.org/docs/9.0/static/ltree.html)
如果您必须使用关系数据库来组织树数据结构，那么 Postgresql 有很酷的 ltree 模块，它提供数据类型来表示存储在分层树状结构中的数据标签。你可以从那里得到这个想法。（有关更多信息，请参见：http: //www.postgresql.org/docs/9.0/static/ltree.html）
In common LDAP is used to organize records in hierarchical structure.
通常，LDAP 用于按层次结构组织记录。
回答by Darshan
Fantastic collection of ready to use functions which can be used with the adjacency list model to make life simpler.
即用型函数的奇妙集合，可与邻接列表模型一起使用，使生活更简单。
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
回答by Aaron Daniels
Having a table with a foreign key to itself does make sense to me.
拥有一张带有外键的表对我来说确实有意义。
You can then use a common table expression in SQL or the connect by prior statement in Oracle to build your tree.
然后，您可以使用 SQL 中的公共表表达式或 Oracle 中的 connect by 先前语句来构建树。
回答by emzero
回答by Alex
If anyone using MS SQL Server 2008 and higherlands on this question: SQL Server 2008 and higher has a new "hierarchyId" feature designed specifically for this task.
如果任何使用MS SQL Server 2008 及更高版本的人遇到此问题：SQL Server 2008 及更高版本具有专门为此任务设计的新“hierarchyId”功能。
More info at https://docs.microsoft.com/en-us/sql/relational-databases/hierarchical-data-sql-server
更多信息请访问https://docs.microsoft.com/en-us/sql/relational-databases/hierarchical-data-sql-server
