树数据结构的数据库结构 [英] Database Structure for Tree Data Structure

问题描述

在数据库中实现可定制的（意思是具有未知数量级别）树数据结构的最佳方式是什么？

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?

推荐答案

你提到最常用的方法，即Adjacency List：
https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25 / hierarchys-convert-adjacency-list-to-nested-sets

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

还有其他模型，包括物化路径和嵌套集：
http://communities.bmc.com/communities/docs/DOC-9902

There are other models as well, including materialized path and nested sets: http://communities.bmc.com/communities/docs/DOC-9902

Joe Celko撰写了一本关于这个主题的书，从一般的SQL角度来看是一个很好的参考（在上面的嵌套集合文章链接中提到）。

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

此外，Itzik Ben-Gann对他的书Inside Microsoft SQL Server 2005：T-SQL Querying中最常见的选项进行了很好的概述。

Also, Itzik Ben-Gann has a good overview of the most common options in his book "Inside Microsoft SQL Server 2005: T-SQL Querying".

选择模型时要考虑的主要问题是：

The main things to consider when choosing a model are:

1）结构变化的频率 - 实际结构的频率的树变化。一些型号提供更好的结构更新特性。然而，重要的是将结构更改与其他数据更改分开。例如，您可能需要为公司的组织结构图建模。有些人会将其建模为邻接列表，使用员工ID将员工链接到其主管。这通常是一个次优的方法。通常工作更好的方法是将组织结构与员工本身分开，并将员工作为结构的属性进行维护。这样一来，当员工离开公司时，组织结构本身就不需要改变，只是与员工离开的关系。

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.

2）是树写重或读重 - 某些结构在阅读结构时工作得很好，但在写入结构时会产生额外的开销。

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.

3）什么类型的信息您需要从结构中获得 - 某些结构在提供某些关于结构的信息方面表现优异。示例包括查找节点及其所有子节点，查找节点及其所有父节点，查找满足某些条件的子节点数量等。您需要知道从结构中需要哪些信息来确定最适合的结构你的需要。

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.

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