如何在SQL数据库中存储树

Question

我必须在数据库中存储一棵树,那么最好的方法是什么？显示您使用的方法并命名其优缺点.(我使用的是SQL Server 2005)

Answer 1

我发现SQL反模式中的讨论非常有用,因为它还关注每个实现的缺点.

此外,本演示文稿中的幻灯片48-77 重申了分析.

最重要的是,没有通用树这样的东西,也没有SQL树的银弹.您将不得不问自己关于数据,如何选择,修改,分支移动等等,并根据这些答案实施合适的解决方案.

Answer 2

长话短说：

• 邻接列表非常适合查找上一级或下一级，并能够编辑中间的节点。
• 路径枚举允许您具有无限的深度并快速遍历，但使编辑中间的节点变得困难。
• 闭包表允许无限深度遍历并编辑中间节点，但需要更多空间并且开发更复杂。

在数据库中存储树或分层结构有三种基本解决方案。

1. 邻接表：存储每个节点的父节点
2. 路径枚举：在文本中存储每个节点的完整路径
3. 关闭表：创建一个包含所有祖先/后代关系的附加表

每个解决方案都有优点和缺点：

	邻接表	路径枚举	关闭表
仓储费用	低：O(n)	低：O(n)	高：O(n 2 )
找到第一个孩子	简单/快速	简单/快速	简单/快速
找到所有孩子	硬/慢	简单/中等	简单/快速
寻找直系父母	简单/快速	简单/快速	简单/快速
查找整个路径	硬/中	简单/快速	简单/快速
添加孩子	简单/快速	简单/快速	简单/快速
修改父级	简单/快速	硬/慢	简单/快速
容易矛盾吗？	不	是的	不
开发复杂度	简单的	简单的	难的

1. 邻接表

CREATE TABLE family_tree_adjacency_list (
  PersonId int,
  Name varchar(255),
  ParentId int 

人员ID	姓名	父ID
1	约翰	无效的
2	简	1
3	标记	2
4	玛丽	2
5	贝丝	4

这是SQL中最简单的树结构。易于创建，易于概念化。由于树中的每个节点只有一个父节点，因此您只需存储每个节点的父节点即可存储整个树。任何具有NULL父节点的节点都是顶级节点。如果您不需要查找节点的顶级祖先或底层后代，这可能是一个很好的结构。

优点：

• 只需要一张桌子，无需额外的存储空间。
• 可以轻松找到任何节点的直接子节点或父节点 ( SELECT * FROM family_tree WHERE parent_id = 47)。
• 添加更多孩子很容易
• 如果需要修改树中间的节点以更改其父节点，则无需进行其他更改。

缺点：

• 你不可能在所有深度找到所有的孩子。如果您使用树进行分类，则必须进行递归编程来查找所有子级，或者对后代总数设置限制。这是复杂且缓慢的。
• 您找不到顶级父级。如果您需要遍历树一直到顶部，则需要使用递归编程（或对可以深入的字段数量设置限制）。

2. 路径枚举

CREATE TABLE family_tree_path_enumeration (
  PersonId int,
  Name varchar(255),
  Path varchar(255)
)

人员ID	姓名	小路
1	约翰	1
2	简	1/2
3	标记	1/2/3
4	玛丽	1/2/4
5	贝丝	1/2/4/5

这是一个很好的折衷结构。不要过度设计您的解决方案！该解决方案易于实现、易于概念化，并且通常速度相当快。要查找特定节点的所有子节点，您需要使用LIKE通配符%，这比=，但对于大多数情况来说通常没问题。该解决方案唯一真正的缺点是编辑表格。重新组织中间树节点是一项非常复杂的工作，因此如果您经常这样做，请不要使用路径枚举。

优点：

• 存储成本仍然较低
• 快速搜索孩子和家长，甚至一直到顶部，无论有多少层。
• 轻松添加孩子
• 易于开发

缺点：

• 修改父级需要查找所有子级并编辑每个子级路径，这将是一项昂贵的操作。如果这是一项常见任务，请不要使用路径枚举。弄乱还可能导致数据库内出现矛盾
• 查找节点的所有子节点稍微慢一些，因为它使用LIKE %. 这可能会对一个巨大的数据库产生影响。

-- find all sub-children of #1
SELECT * from family_tree_path_enumeration WHERE Path like '%1%

3. 关闭表

CREATE TABLE family_tree_closure_table (
  PersonId int,
  Name varchar(255)
)

CREATE TABLE family_tree_relationships (
  AncestorId int,
  DescendantId int,
  Depth int  -- this is a helper field to make our lives easier when finding parents and children
)

人员ID	姓名
1	约翰
2	简
3	标记
4	玛丽
5	贝丝

祖先ID	后代ID	深度
1	2	1
2	3	1
1	3	2
2	4	1
1	4	2
4	5	1
2	4	2
1	4	3

这个解决方案有点复杂，但即使对于大型数据集它也会很快，并且仍然允许修改而不会遇到问题。这里的缺点是开发稍微复杂一些，并且可以使用指数级更多的存储空间（尽管在实践中通常情况并非如此）。如果您需要查找顶部祖先和底部后代，并且还需要定期编辑树，那么这可能是一个很好的结构。

优点：

• 可扩展且快速
• 可以快速找到整个父路径，或者所有后代节点
• 轻松添加孩子
• 稍微轻松地修改中间节点（根据您正在做的事情，您可能需要修改后代的深度）

缺点：

• 开发复杂（需要 2 个单独的表）
• 使用更多空间（需要 2 个单独的桌子）
• 您可能过度设计了您的解决方案！

结论

每个表都有其权衡。如果您想要一个易于重组且易于找到某一级别的父母或孩子的简单解决方案，那么简单的邻接列表会很好。如果您需要查找完整路径（向上或向下），但不需要经常编辑表中间的节点，则路径枚举表会更好。如果您需要查找类别中的所有节点，但还需要能够编辑中间的节点，那么您可能需要使用闭包表。

Answer 3

嗯，最简单的方法是让一条记录有一个 ParentID 列，这样它就知道哪个记录是它的父记录。这是一个非常标准的做法。例如，在线商店可能具有产品类别的层次结构。每个类别都有一个 ParentID。示例：服装数据库中的“牛仔裤”类别可能将“裤子”作为父类别。如果你想要一个记录表明哪些是它的孩子，这有点困难，除非你限制孩子的数量。如果你想要一个二叉树，你可以有 LeftChildID 和 RightChildID 列。如果您允许任意数量的子项，则可以有一个子项列，其中 ID 以逗号分隔（例如1,4,72,19) 但这会使查询变得相当困难。如果您的数据库允许列中的数组类型，您可能可以使用数组而不是分隔字符串，这很容易查询 - 但我不确定 MS SQL Server 是否支持。

除此之外，这取决于您正在建模的数据类型，以及您计划对这棵树执行的操作类型。

Answer 4

试试这个:SQL Server 2005中的层次结构(树)