如何在SQL中表示数据树？

Question

我正在写一个从Tree和TreeNode组合而成的数据树结构。树将包含数据的根级和*操作。 我正在使用一个用户界面库来呈现树窗口窗体中我可以将树绑定到TreeView。

我需要将这个树和节点保存在数据库中。 什么将是最好的方式来保存树和获得以下功能：

1. 直观的实施。
2. 简单的绑定。将很容易从树移动到DB结构和回（如果有）

我有2个想法。首先是将数据序列化成表格中的单行数据。 第二个是保存在表格中，但是当移动到数据实体时，我将丢失已更改节点上的表上的行状态。

任何想法？

Answer 1

这取决于你将如何查询和更新数据。如果您将所有数据存储在一行中，则基本上只有一个单元，您无法重写所有数据而无法查询或部分更新。

如果你想将每个元素作为一行存储，你应该首先阅读Managing Hierarchical Data in MySQL（特定于MySQL，但也适用于其他许多数据库）。

如果您只访问整个树，则邻接列表模型会很难在不使用递归查询的情况下检索根下的所有节点。如果添加一个连接到头部的额外列，那么您可以执行SELECT * WHERE head_id = @id并将整棵树放在一个非递归查询中，但它会使数据库非标准化。

某些数据库具有自定义扩展功能，可以更容易地存储和检索角色数据，例如Oracle拥有CONNECT BY。

Answer 2

最简单的实现是邻接表结构：

id parent_id data 

然而，一些数据库，特别是MySQL，在处理这个模型的一些问题，因为它需要运行哪些MySQL没有递归查询的能力。

另一种模式是嵌套集合：

id lft rgt data 

其中lft和rgt是定义层次任意值（任何孩子的lft，rgt应在任何父母的lft，rgt）

这不需要递归查询，但它更难以维护。

但是，在MySQL这可以改进使用SPATIAL abitilies。

请参阅以下文章在我的博客：

• Adjacency list vs. nested sets: PostgreSQL
• Adjacency list vs. nested sets: SQL Server
• Adjacency list vs. nested sets: Oracle
• Adjacency list vs. nested sets: MySQL

进行更详细的解释。

Answer 3

类似于表“节点”，其中每个节点行包含父节点id（除普通节点数据外）。对于根，父项是NULL。

当然，这使得查找孩子更费时，但这样一来，实际的数据库将会非常简单。

Answer 4

我书签这slidshare有关SQL-反模式，其中讨论了几个备选方案：http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed

从那里是使用封闭表（它在幻灯片中解释）的建议。

下面是总结（幻灯片77）：

    | Query Child | Query Subtree | Modify Tree | Ref. Integrity 
Adjacency List | Easy  |  Hard  | Easy  |  Yes 
Path Enumeration | Easy  |  Easy  | Hard  |  No 
Nested Sets  | Hard  |  Easy  | Hard  |  No 
Closure Table  | Easy  |  Easy  | Easy  |  Yes 

Answer 5

最好的办法，我觉得确实是给每个节点ID和PARENT_ID，其中父ID是父节点的ID。这有几个好处

1. 当你想更新一个节点时，你只需要重写那个节点的数据。
2. 当您只想查询某个节点时，您可以准确获得所需的信息，从而减少数据库连接的开销
3. 许多编程语言都具有将mysql数据转换为XML或json的功能，将使使用api打开您的应用程序更容易。

Answer 6

我很惊讶，没有人提到物化路径解决方案，这可能是使用标准SQL中树的最快方式。

在此方法中，树中的每个节点都有一列路径，其中存储从根节点到节点的完整路径。这涉及非常简单和快速的查询。

看一看示例表节点：

+---------+-------+ 
| node_id | path | 
+---------+-------+ 
| 0  |  | 
| 1  | 1  | 
| 2  | 2  | 
| 3  | 3  | 
| 4  | 1.4 | 
| 5  | 2.5 | 
| 6  | 2.6 | 
| 7  | 2.6.7 | 
| 8  | 2.6.8 | 
| 9  | 2.6.9 | 
+---------+-------+ 

为了得到节点的孩子X，您可以编写以下查询：

SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%') 

请介意，那列路径应该被索引，以便快速执行LIKE claus即

Answer 7

如果您使用的是PostgreSQL，您可以使用ltree，这是一个实现树数据结构的contrib扩展中的包（默认情况下为）。

从docs：

CREATE TABLE test (path ltree); 
INSERT INTO test VALUES ('Top'); 
INSERT INTO test VALUES ('Top.Science'); 
INSERT INTO test VALUES ('Top.Science.Astronomy'); 
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics'); 
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology'); 
INSERT INTO test VALUES ('Top.Hobbies'); 
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy'); 
INSERT INTO test VALUES ('Top.Collections'); 
INSERT INTO test VALUES ('Top.Collections.Pictures'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts'); 
CREATE INDEX path_gist_idx ON test USING GIST (path); 
CREATE INDEX path_idx ON test USING BTREE (path); 

你可以做这样的查询：

ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science'; 
       path 
------------------------------------ 
Top.Science 
Top.Science.Astronomy 
Top.Science.Astronomy.Astrophysics 
Top.Science.Astronomy.Cosmology 
(4 rows)