这是一个相当老的问题，但由于有很多观点，我认为有必要提出一个替代方案，在我看来，非常优雅的解决方案。

为了读取树结构，可以使用递归通用表表达式(CTEs)。它提供了一次获取整个树结构的可能性，有关于节点的级别，它的父节点和父节点的子节点顺序的信息。

让我向你展示这在PostgreSQL 9.1中是如何工作的。

Create a structure CREATE TABLE tree ( id int NOT NULL, name varchar(32) NOT NULL, parent_id int NULL, node_order int NOT NULL, CONSTRAINT tree_pk PRIMARY KEY (id), CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) REFERENCES tree (id) NOT DEFERRABLE ); insert into tree values (0, 'ROOT', NULL, 0), (1, 'Node 1', 0, 10), (2, 'Node 1.1', 1, 10), (3, 'Node 2', 0, 20), (4, 'Node 1.1.1', 2, 10), (5, 'Node 2.1', 3, 10), (6, 'Node 1.2', 1, 20); Write a query WITH RECURSIVE tree_search (id, name, level, parent_id, node_order) AS ( SELECT id, name, 0, parent_id, 1 FROM tree WHERE parent_id is NULL UNION ALL SELECT t.id, t.name, ts.level + 1, ts.id, t.node_order FROM tree t, tree_search ts WHERE t.parent_id = ts.id ) SELECT * FROM tree_search WHERE level > 0 ORDER BY level, parent_id, node_order;

以下是调查结果:

     id |    name    | level | parent_id | node_order 
    ----+------------+-------+-----------+------------
      1 | Node 1     |     1 |         0 |         10
      3 | Node 2     |     1 |         0 |         20
      2 | Node 1.1   |     2 |         1 |         10
      6 | Node 1.2   |     2 |         1 |         20
      5 | Node 2.1   |     2 |         3 |         10
      4 | Node 1.1.1 |     3 |         2 |         10
    (6 rows)

树节点按深度排序。在最终输出中，我们将在随后的行中显示它们。

对于每一层，它们都是根据父级中的parent_id和node_order进行排序的。这告诉我们如何在输出链接节点中将它们按此顺序呈现给父节点。

有了这样的结构，用HTML制作一个真正漂亮的演示就不难了。

递归cte可用于PostgreSQL, IBM DB2, MS SQL Server, Oracle和SQLite。

如果你想阅读更多关于递归SQL查询的内容，你可以查看你最喜欢的DBMS的文档，或者阅读我关于这个主题的两篇文章:

做它在SQL:递归树遍历 了解SQL递归查询的强大功能

如果您使用嵌套集(有时称为Modified preorder Tree Traversal)，您可以通过一个查询以树顺序提取整个树结构或其中的任何子树，但插入的代价更大，因为您需要管理通过树结构描述有序路径的列。

对于django-mptt，我使用了这样的结构:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

它描述了一个像这样的树(id代表每一项):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

或者，作为一个嵌套的集合图，这使得left和right值的工作方式更加明显:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

如您所见，要获得给定节点的整个子树，按照树的顺序，您只需选择在其left和right值之间具有left和right值的所有行。检索给定节点的祖先树也很简单。

The level column is a bit of denormalisation for convenience more than anything and the tree_id column allows you to restart the lft and rght numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft and rght columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.

为了实际使用这些数据来显示树，我创建了一个tree_item_iterator实用函数，对于每个节点，它应该为您提供足够的信息来生成您想要的任何类型的显示。

更多关于MPTT的信息:

SQL中的树 在数据库中存储分层数据 在MySQL中管理分层数据

从Oracle 9i开始，您可以使用CONNECT BY。

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

从SQL Server 2005开始，您可以使用递归公共表表达式(CTE)。

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

两者都将输出以下结果。

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

有一些很好的解决方案利用了sql索引的内部btree表示。这是基于1998年左右的一些伟大的研究。

下面是一个示例表(在mysql中)。

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

树表示中唯一需要的字段是:

tw:从左到右的DFS预购索引，其中根= 1。 pa:对父节点的引用(使用tw)，根节点为空。 sz:包括节点本身在内的节点分支的大小。 Nc:用作语法糖。它是tw+sz，表示节点的“下一个子”的tw。

下面是一个例子，24个节点填充，按tw排序:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

每个树的结果都是非递归的。 例如，要获取tw='22'节点的父节点列表

的祖先

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

兄弟姐妹和孩子是微不足道的-只需使用pa字段按tw排序。

的后代

例如，根在tw = 17的节点的集合(分支)。

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

额外的笔记

当读取的数量远远大于插入或更新的数量时，这种方法非常有用。

因为树中节点的插入、移动或更新需要调整树，所以在开始操作之前必须锁定表。

插入/删除成本很高，因为tw索引和sz(分支大小)值需要在插入点之后的所有节点上更新，并且需要分别对所有祖先节点更新。

分支移动涉及到将分支的tw值移出范围，因此在移动分支时禁用外键约束也是必要的。移动一个分支需要四个查询:

把树枝移出范围。 填补它留下的缺口。(剩下的树现在是正常化的)。 打开它要去的地方的缺口。 移动树枝到它的新位置。

调整树查询

树中间隙的打开/关闭是创建/更新/删除方法使用的一个重要子函数，因此我将它包含在这里。

我们需要两个参数——一个标志表示是缩小还是扩大，另一个是节点的tw索引。因此，例如tw=18(分支大小为5)。让我们假设我们正在缩小(删除tw) -这意味着我们在下面的例子的更新中使用'-'而不是'+'。

我们首先使用一个(稍微改变的)祖先函数来更新sz值。

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

然后我们需要为那些tw高于要移除的分支调整tw。

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

然后我们需要调整那些pa的tw比要移除的分支高的父类。

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

假设你知道根元素是0，下面是输出到文本的伪代码:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

如果元素是按树顺序排列的，如你的例子所示，你可以使用以下Python示例:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

这样做的目的是维护一个表示树中当前位置的堆栈。对于表中的每个元素，它弹出堆栈元素(关闭匹配的div)，直到找到当前项的父元素。然后它输出该节点的开始并将其推入堆栈。

如果希望使用缩进而不是嵌套元素输出树，可以简单地跳过print语句来打印div，并在每个项之前打印等于堆栈大小的若干倍的空格。例如，在Python中:

print "  " * len(stack)

您还可以轻松地使用此方法构造一组嵌套的列表或字典。

编辑:我从你的澄清中看到，这些名称并不是节点路径。这就提出了另一种方法:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

这将构造一个元组数组树(!)。Idx[0]表示树的根。数组中的每个元素都是一个二元组，由节点本身及其所有子元素的列表组成。构造后，可以保留idx[0]并丢弃idx，除非您希望通过节点的ID访问节点。