如何高效地将平面表解析为嵌套树结构？

将扁平表高效解析为树状结构

简介

将表示树形层次结构的扁平表高效转换为嵌套结构，可以使用多种方法实现。本文探讨了一种使用基本数据结构的极简方案，并考虑了用于优化树形表示的替代数据库存储方法。

解析的极简方法

假设一个表包含以下数据：

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

将此表解析为树形结构：

1. 创建字典：将每个节点的 Id 映射到其对应的数据。

2. 识别根节点：根节点是没有 ParentId 的节点。

3. 构建树：通过递归创建子节点并将其添加到相应的父节点来构建树。

   • 对于每个非根节点，使用其 ParentId 在字典中查找其父节点。
   • 将节点添加为父节点的子节点。

4. 排序子节点：根据子节点的 Order 对每个节点的子节点进行排序。

此方法的伪代码：

<code>创建字典(table)
def 获取根节点():
    根节点 = []
    对于 id, 节点 in 字典.items():
        如果 节点['ParentId'] == 0:
            根节点.append(节点)
    返回 根节点

def 构建树(根节点):
    对于 根节点 in 根节点:
        子节点 = []
        对于 id, 节点 in 字典.items():
            如果 节点['ParentId'] == 根节点['Id']:
                子节点.append(节点)
        子节点.sort(key=lambda x: x['Order'])
        根节点['children'] = 子节点
        构建树(子节点)

def 打印树(根节点):
    对于 根节点 in 根节点:
        打印(根节点['Name'])
        如果 'children' in 根节点:
            打印树(根节点['children'])</code>

SQL 中树形结构的替代存储方法

闭包表：

在关系数据库中存储树形结构的另一种方法是使用闭包表，其中包含一个单独的表，该表包含祖先节点 ID 和后代节点 ID 列。这允许轻松查询关系。

使用闭包表的查询：

<code>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</code>

嵌套集：

嵌套集涉及在单个表中存储树中每个节点的位置信息。此方法允许对给定级别或子树中的节点进行高效的基于范围的查询。

结论

虽然提供的示例使用扁平表作为输入，但所提出的方法非常适用于不同的数据结构和存储方法。通过使用适当的技术，您可以高效地解析树形层次结构，并确保数据完整性和易于访问。

以上是如何高效地将平面表解析为嵌套树结构？的详细内容。更多信息请关注PHP中文网其他相关文章！