树数据结构的数据库结构

Question

在数据库中实现可自定义(意味着具有未知级别的树结构)树数据结构的最佳方法是什么？

在使用带有外键的表之前,我已经完成了这一次.

你能看到其他什么实现,这种实现是否有意义？

Answer 1

你提到最常用的,即邻接列表:https: //blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets

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

Joe Celko写了一本关于这个主题的书,这是一个很好的参考,从一般的SQL角度来看(在上面的嵌套集文章链接中提到).

此外,Itzik Ben-Gann在其"Inside Microsoft SQL Server 2005:T-SQL查询"一书中对最常见的选项有了很好的概述.

选择模型时要考虑的主要事项是:

1)结构变化的频率 - 树的实际结构变化的频率.某些模型提供更好的结构更新特性.但是,将结构更改与其他数据更改分开很重要.例如,您可能想要为公司的组织结构图建模.有些人会将此建模为邻接列表,使用员工ID将员工链接到他们的主管.这通常是次优的方法.通常更好的方法是将组织结构与员工本身分开建模,并将员工维护为结构的属性.这样,当员工离开公司时,组织结构本身不需要改变,只需要与离开的员工的关联.

2)树是重写还是读重 - 一些结构在读取结构时工作得很好,但在写入结构时会产生额外的开销.

3)您需要从结构中获得哪些类型的信息 - 某些结构擅长提供有关结构的某些信息.示例包括查找节点及其所有子节点,查找节点及其所有父节点,查找满足特定条件的子节点数等.您需要知道结构中需要哪些信息以确定最适合的结构您的需求.

Answer 2

看看在MySQL中管理分层数据.它讨论了在关系数据库中存储和管理分层(树状)数据的两种方法.

第一种方法是邻接列表模型,这是您实质上描述的:拥有引用表本身的外键.虽然这种方法很简单,但对于某些查询来说效率非常低,例如构建整个树.

本文讨论的第二种方法是嵌套集模型.这种方法更有效,更灵活.有关详细说明和示例查询,请参阅文章.

Answer 3

如果必须使用Relational DataBase来组织树数据结构,那么Postgresql有一个很酷的ltree模块,它提供数据类型来表示存储在分层树状结构中的数据标签.你可以从那里得到这个想法.(有关更多信息,请参阅:http://www.postgresql.org/docs/9.0/static/ltree.html)

通常,LDAP用于组织层次结构中的记录.