假设你有一个扁平的表,存储一个有序的树层次结构:
Id Name ParentId Order
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
这是一个图表,我们有[id] Name。根节点0是虚构的。
[0] ROOT
/ \
[1] Node 1 [3] Node 2
/ \ \
[2] Node 1.1 [6] Node 1.2 [5] Node 2.1
/
[4] Node 1.1.1
您将使用什么极简的方法将其输出到HTML(或文本,就此而言),作为一个正确有序、正确缩进的树?
进一步假设您只有基本的数据结构(数组和hashmap),没有带有父/子引用的花哨对象,没有ORM,没有框架,只有您的两只手。该表表示为一个结果集,可以随机访问。
伪代码或简单的英语是可以的,这纯粹是一个概念问题。
附加问题:在RDBMS中是否存在从根本上更好的方法来存储这样的树结构?
编辑和添加
回答一位评论者(Mark Bessey)的问题:根节点是不必要的,因为无论如何它都不会显示。ParentId = 0是表示“这些是顶级”的惯例。Order列定义了具有相同父节点的节点如何排序。
我所说的“结果集”可以被描绘成一个hashmap数组(继续使用这个术语)。因为我的例子本来就应该在那里。有些答案是额外的,首先构建它,但这没关系。
树可以任意深。每个节点可以有N个子节点。不过,我脑子里并没有“数百万条”树。
不要把我选择的节点命名(“节点1.1.1”)误认为是可以依赖的。节点也可以被称为“Frank”或“Bob”,没有隐含的命名结构,这只是为了让它更具可读性。
我已经发布了我自己的解决方案,所以你们可以把它拆成碎片。
要扩展Bill的SQL解决方案,基本上可以使用平面数组来实现相同的功能。此外,如果你的字符串都有相同的长度,你的最大子代数是已知的(比如在一个二叉树中),你可以使用一个单一的字符串(字符数组)。如果你有任意数量的孩子,事情就会变得复杂一些……我必须检查我的旧笔记,看看能做些什么。
然后,牺牲一点内存,特别是如果你的树是稀疏的和/或不平衡的,你可以,通过一些索引数学,通过存储你的树随机访问所有的字符串,宽度优先在数组中,就像这样(对于二叉树):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
你知道弦的长度,你知道
我现在在工作,所以不能花太多时间在上面,但有兴趣,我可以获取一些代码来做到这一点。
我们过去用它来搜索由DNA密码子组成的二叉树,一个构建树的过程,然后我们将其平铺以搜索文本模式,当找到时,尽管索引数学(从上面反向),我们将节点找回…非常快速和有效,我们的树很少有空节点,但我们可以在一瞬间搜索千兆字节的数据。
如果您使用嵌套集(有时称为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中管理分层数据