假设您有一个存储有序树层次结构的平面表:
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",不暗示命名结构,这只是为了使其可读.
我已经发布了自己的解决方案,所以你们可以把它拉成碎片.
现在MySQL 8.0即将发布,所有流行的SQL数据库都将支持标准语法中的递归查询.
WITH RECURSIVE MyTree AS (
SELECT * FROM MyTable WHERE ParentId IS NULL
UNION ALL
SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;
我在2017年的演示文稿Recursive Query Throwdown中测试了MySQL 8.0中的递归查询.
以下是我2008年的原始答案:
有几种方法可以在关系数据库中存储树形结构数据.您在示例中显示的内容使用两种方法:
邻接列表("父"列)和
路径枚举(名称列中的虚线数字).
另一种解决方案称为嵌套集,它也可以存储在同一个表中.阅读Joe Celko的" SQL for Treesies中的树和层次结构 ",了解有关这些设计的更多信息.
我通常更喜欢名为Closure Table(又名"Adjacency Relation")的设计,用于存储树形结构数据.它需要另一个表,但是查询树很容易.
我在我的演示文稿中使用SQL和PHP覆盖了层次数据的模型,并在我的书" SQL反模式:避免数据库编程的陷阱"中介绍了闭包表.
CREATE TABLE ClosureTable ( ancestor_id INT NOT NULL REFERENCES FlatTable(id), descendant_id INT NOT NULL REFERENCES FlatTable(id), PRIMARY KEY (ancestor_id, descendant_id) );
将所有路径存储在Closure Table中,其中存在从一个节点到另一个节点的直接祖先.为每个节点包含一行以引用自身.例如,使用您在问题中显示的数据集:
INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES (1,1), (1,2), (1,4), (1,6), (2,2), (2,4), (3,3), (3,5), (4,4), (5,5), (6,6);
现在你可以从节点1开始得到一棵树,如下所示:
SELECT f.* FROM FlatTable f JOIN ClosureTable a ON (f.id = a.descendant_id) WHERE a.ancestor_id = 1;
输出(在MySQL客户端中)如下所示:
+----+ | id | +----+ | 1 | | 2 | | 4 | | 6 | +----+
换句话说,节点3和5被排除,因为它们是单独层次结构的一部分,而不是从节点1下降.
回复:关于直接子女(或直系亲属)的电子满意评论.您可以在其中添加" path_length"列,ClosureTable以便更容易专门查询直接子项或父项(或任何其他距离).
INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES (1,1,0), (1,2,1), (1,4,2), (1,6,1), (2,2,0), (2,4,1), (3,3,0), (3,5,1), (4,4,0), (5,5,0), (6,6,0);
然后,您可以在搜索中添加一个术语,用于查询给定节点的直接子节点.这些path_length是1的后代.
SELECT f.* FROM FlatTable f JOIN ClosureTable a ON (f.id = a.descendant_id) WHERE a.ancestor_id = 1 AND path_length = 1; +----+ | id | +----+ | 2 | | 6 | +----+
来自@ashraf的评论:"如何按名称排序整棵树？"
这是一个示例查询,用于返回作为节点1后代的所有节点,将它们连接到包含其他节点属性(如name名称)的FlatTable ,并按名称排序.
SELECT f.name FROM FlatTable f JOIN ClosureTable a ON (f.id = a.descendant_id) WHERE a.ancestor_id = 1 ORDER BY f.name;
来自@Nate的评论:
SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs FROM FlatTable f JOIN ClosureTable a ON (f.id = a.descendant_id) JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) WHERE a.ancestor_id = 1 GROUP BY a.descendant_id ORDER BY f.name +------------+-------------+ | name | breadcrumbs | +------------+-------------+ | Node 1 | 1 | | Node 1.1 | 1,2 | | Node 1.1.1 | 1,2,4 | | Node 1.2 | 1,6 | +------------+-------------+
用户今天建议编辑.SO主持人批准了编辑,但我正在撤消它.
编辑建议上面最后一个查询中的ORDER BY应该是ORDER BY b.path_length, f.name,可能是为了确保排序与层次结构匹配.但这不起作用,因为它会在"节点1.2"之后命令"节点1.1.1".
如果您希望排序以合理的方式匹配层次结构,那么这是可能的,但不是简单地按路径长度排序.例如,请参阅我对MySQL Closure Table分层数据库的回答- 如何以正确的顺序提取信息.
如果使用嵌套集(有时称为修改的预订树遍历),您可以使用单个查询以树顺序提取整个树结构或其中的任何子树,但代价是插入更昂贵,因为您需要管理通过树结构描述有序路径的列.
对于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
或者,作为嵌套的集合图,它使得lft和rght值的工作方式更加明显:
__________________________________________________________________________ | 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 | |________________________________| |________________________________| | |__________________________________________________________________________|
如您所见,要以树的顺序获取给定节点的整个子树,您只需选择其值lft和rght值之间的所有行lft和rght值.检索给定节点的祖先树也很简单.
该level柱是为了方便起见比什么都有点denormalisation和tree_id列允许您重新启动lft和rght编号为每个顶级节点,从而降低受插入,移动和删除的列数,作为lft和rght列必须是在进行这些操作时进行相应调整,以便产生或缩小差距.当我试图围绕每个操作所需的查询时,我做了一些开发笔记.
在实际处理这些数据以显示树的方面,我创建了一个tree_item_iterator实用程序函数,对于每个节点,它应该为您提供足够的信息来生成您想要的任何类型的显示.
有关更多信息MPTT:
SQL中的树
在数据库中存储分层数据
在MySQL中管理分层数据
这是一个相当古老的问题,但由于它有很多观点,我认为值得提出一个替代方案,并且在我看来非常优雅的解决方案.
为了读取树结构,您可以使用递归公用表表达式(CTE).它提供了一次获取整个树结构的可能性,具有关于节点级别,其父节点和父节点的子节点内的顺序的信息.
让我告诉你这在PostgreSQL 9.1中是如何工作的.
创建一个结构
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);
写一个查询
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中使用.
如果您想阅读有关递归SQL查询的更多信息,可以查看您喜欢的DBMS的文档,或阅读我的两篇文章,内容涉及此主题:
在SQL中执行:递归树遍历
了解SQL递归查询的强大功能
从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'
比尔的答案非常好,这个答案增加了一些东西,这使我希望SO支持线程答案.
无论如何,我想支持树结构和Order属性.我在每个节点中包含一个属性,称为在原始问题中执行leftSibling相同的Order操作(维护从左到右的顺序).
mysql> desc nodes ; +-------------+--------------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+--------------+------+-----+---------+----------------+ | id | int(11) | NO | PRI | NULL | auto_increment | | name | varchar(255) | YES | | NULL | | | leftSibling | int(11) | NO | | 0 | | +-------------+--------------+------+-----+---------+----------------+ 3 rows in set (0.00 sec) mysql> desc adjacencies; +------------+---------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +------------+---------+------+-----+---------+----------------+ | relationId | int(11) | NO | PRI | NULL | auto_increment | | parent | int(11) | NO | | NULL | | | child | int(11) | NO | | NULL | | | pathLen | int(11) | NO | | NULL | | +------------+---------+------+-----+---------+----------------+ 4 rows in set (0.00 sec)
我的博客上有更多细节和SQL代码.
谢谢Bill,你的回答有助于入门!
鉴于选择,我将使用对象.我为每个记录创建一个对象,其中每个对象都有一个children集合,并将它们全部存储在一个关联数组(/ hashtable)中,其中Id是关键字.并通过该系列闪电战,将孩子们加入相关的儿童田地.简单.
但是因为你通过限制使用一些好的OOP而没有乐趣,我可能会根据以下内容进行迭代:
function PrintLine(int pID, int level)
foreach record where ParentID == pID
print level*tabs + record-data
PrintLine(record.ID, level + 1)
PrintLine(0, 0)
编辑:这类似于其他一些条目,但我认为它稍微清晰一些.我要补充一点:这是非常SQL密集型的.这很讨厌.如果您有选择,请转到OOP路线.
这是迅速写的,既不漂亮,也没有有效的(加上它autoboxes很多,之间的转换int和Integer很讨厌!),但它的作品.
它可能会破坏规则,因为我正在创建自己的对象但是嘿,我这样做是为了转移实际工作:)
这也假设在开始构建节点之前,resultSet/table被完全读入某种结构,如果你有数十万行,这将不是最好的解决方案.
public class Node {
private Node parent = null;
private List children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List> input) {
// maps id of a node to it's Node object
Map nodeMap = new HashMap();
// maps id of a node to the id of it's parent
Map childParentMap = new HashMap();
// create special 'root' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("\t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List> resultSet = new ArrayList>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map newMap(String id, String name, String parentId) {
Map row = new HashMap();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
京公网安备 11010802040832号 | 京ICP备19059560号-6 