假设您有一个存储有序树层次结构的平面表:
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(或文本,就此而言)作为正确排序,正确缩进的树？
进一步假设你只有基本的数据结构(数组和散列图),没有带有父/子引用的花哨对象,没有ORM,没有框架,只有你的双手.该表表示为结果集,可以随机访问.
伪代码或普通英语是可以的,这纯粹是一个概念性的问题.
额外问题:在RDBMS中存储这样的树结构是否有根本更好的方法？
编辑和补充
回答一个评论者(Mark Bessey的)问题:根节点不是必需的,因为它永远不会被显示.ParentId = 0是表示"这些是顶级"的惯例.Order列定义了如何对具有相同父节点的节点进行排序.
我所谈到的"结果集"可以被描绘成一组哈希图(保留在该术语中).因为我的例子意味着已经存在.有些答案会加倍努力并首先构建它,但那没关系.
树可以任意深.每个节点可以有N个子节点.不过,我并没有考虑到"数百万条目".
不要将我选择的节点命名('Node 1.1.1')误认为是依赖的东西.节点同样可以称为"Frank"或"Bob",不暗示命名结构,这只是为了使其可读. …
我想在SQL表中表示"hi","hello","goodbye","good day","howdy"(带有该顺序)列表:
pk | i | val
------------
1 | 0 | hi
0 | 2 | hello
2 | 3 | goodbye
3 | 4 | good day
5 | 6 | howdy
'pk'是主键列.无视其价值观.
'i'是定义'val'列中值的顺序的"索引".它仅用于建立顺序,而值则不重要.
我遇到的问题是在维护订单的同时将值插入列表中.例如,如果我想插入"嘿"并且我希望它出现在 "你好"和"再见"之间,那么我必须改变"再见"和"美好的一天"的"i"值(但最好不要"你好"为新入场腾出空间".
那么,是否有一个标准的SQL模式来进行移位操作,但只移位必要的元素？(注意,一个简单的"UPDATE表SET i = i + 1 WHERE i> = 3"不起作用,因为它违反了'i'上的唯一性约束,并且它也不必要地更新了"howdy"行.)
或者,有没有更好的方式来表示有序列表？我想你可以让'i'成为一个浮点值并在它们之间选择值,但是当没有这样的值时你必须有一个单独的重新平衡操作.
或者,是否有一些标准算法用于在任意其他字符串之间生成字符串值,如果我要使'i'为varchar？
或者我应该将其表示为链接列表？我正在避免这种情况,因为我也希望能够执行SELECT .. ORDER BY以按顺序获取所有元素.