树是表示层次结构的方法之一，因此可用于许多问题域。本文通过一个简单问题域中的示例，讨论了在RDBMS中表示树的四种最受欢迎的方法。

以树状结构表示和存储数据是软件开发中的常见问题：

• XML / Markup语法解析器（例如Apache Xerces和Xalan XSLt）使用树；
• PDF使用以下树结构：根节点->目录节点->页面节点->子页面节点。通常，PDF文件在内存中表示为平衡树。
• 多种科学和游戏应用程序使用决策树，概率树，行为树；Flare可视化库（http://flare.prefuse.org/）充分利用了生成树，经纪人在决定是否投标合同时也使用树木。

树是表示层次结构的方法之一，因此可用于许多问题域：

• 计算机科学中的二叉树，
• 生物学中的系统树
• 商业中的庞氏骗局，
• 项目管理中的任务分解树，
• 树用于建模多级关系，例如“上级-下级”，“祖先-后代”，“整个-部分”，“一般-特定”。

本文讨论了在关系数据库中存储树的四种最流行的方法。作为示例，我们将使用建筑材料目录（图1）和Postgres 9.6 RDBMS。

图1.建筑物资目录

图论使用术语“树”来表示非循环连接图，而术语“林”用于任意非循环图（可能是断开的）。本文讨论的方法可以应用于存储树木和森林而不会失去一般性。

1.邻接表

图论中的邻接表是一种通过存储每个顶点的邻居列表（即相邻顶点）来表示图的方法。对于树，可以仅存储父节点，然后每个列表都包含一个值，该值可以与顶点一起存储在数据库中。这是最流行的表示形式之一，也是最直观的表示形式：表仅具有对自身的引用（图2）。然后，根节点NULL的父节点包含一个空值（）。

图2.邻接表实现

此方法的主要数据选择操作要求DBMS支持递归查询。PostgreSQL支持这种类型的查询，但是对于不支持DBMS的用户，可能需要通过使用临时表和存储过程来执行选择。以下是一些查询示例。

获取给定节点的子树：

WITH RECURSIVE sub_category(code, name, parent_code, level) AS (
	SELECT code, name, parent_code, 1 FROM goods_category WHERE code=1 /* id of the given node */
	UNION ALL 
	SELECT c.code, c.name, c.parent_code, level+1
	FROM goods_category c, sub_category sc
	WHERE c.parent_code = sc.code  
)
SELECT code, name, parent_code, level FROM sub_category;

从根到给定节点的路径：

WITH RECURSIVE sub_category(code, name, parent_code, level) AS (
	SELECT code, name, parent_code, 1 FROM goods_category WHERE code=5 /* id of the given node */
	UNION ALL 
	SELECT c.code, c.name, c.parent_code, level+1
	FROM goods_category c, sub_category sc
	WHERE c.code = sc.parent_code  
)
SELECT code, name, parent_code, (SELECT max(level) FROM sub_category) - level AS distance FROM sub_category;

检查Cement节点（代码= 5）是否为Construction Material / Fixtures（代码= 1）的后代：

WITH RECURSIVE sub_category(code, name, parent_code, level) AS (
	SELECT code, name, parent_code, 1 FROM goods_category WHERE code=5 /* id of the checked node */
	UNION ALL 
	SELECT c.code, c.name, c.parent_code, level+1
	FROM goods_category c, sub_category sc
	WHERE c.code = sc.parent_code  
) 
SELECT CASE WHEN exists(SELECT 1 FROM sub_category WHERE code=2 /* code of the subtree root */)
	THEN 'true' 
	ELSE 'false' 
	END

这种方法的***优点***包括：

• 数据的直观表示（元组(code, parent_code)直接对应于树的边缘）；
• 没有数据冗余，也不需要非参照完整性约束（除非您需要DBMS级约束来防止循环）；
• 树木可以有任意深度；
• 快速，简单的插入，移动和删除操作，因为它们不会影响任何其他节点。

的***缺点***是：

• 该方法需要递归以便选择节点的后代或祖先，定义节点的深度，并找出后代的数量。如果DBMS不支持特定功能，则无法有效地实现这些操作。对于无法进行递归或不可行的情况，可以通过使用一个递归来实现此方法的某些优点。

2.子集

也称为Closure table或Bridge table。

该方法将树表示为嵌套的子集：根节点包含所有深度为1的节点，它们依次包含深度为2的节点，依此类推（图3）。

图3.将树表示为嵌套子集

Subsets方法需要两个表：第一个表包含所有子集（表goods_category，图4），第二个表包含子集的包含事实，以及相应的深度级别（表subset，图4）。

图4.子集实现

结果，对于树中的每个节点，该subset表包含的记录数等于该节点的深度级别。因此，记录数随着算术级数的增长而增加，但是普通查询变得比以前的方法更简单，更快。

获取给定节点的子树：

SELECT name, set_code, subset_code, level FROM subset s
    LEFT JOIN goods_category c ON c.code = s.set_code
WHERE subset_code = 1 /* the subtree root */
ORDER BY level;

从根到给定节点的路径：

SELECT name, set_code, subset_code, level FROM subset s
    LEFT JOIN goods_category c ON c.code = s.subset_code
WHERE set_code = 3 /* the give node */
ORDER BY level;

检查“块”节点（代码= 3）是否为“建筑材料/夹具”（代码= 1）的后代：

SELECT CASE 
    WHEN exists(SELECT 1 FROM subset 
                WHERE set_code = 3 AND subset_code = 1)
	THEN 'true' 
	ELSE 'false' 
	END

为了保持完整性，移动和插入操作需要实现触发器，该触发器将更新所有关联的记录。

Subsets方法的主要优点\是支持快速，简单，非递归的树操作：子树选择，祖先选择，节点深度级别的计算和后代数量。

缺点\包括：

• 相对不直观的数据表示（由于间接后代之间的冗余引用而变得复杂）；
• 数据冗余；
• 数据完整性需要触发器；
• 移动和插入操作比邻接列表方法更为复杂。插入需要为每个后代节点附加记录，而移动节点需要更新其后代和祖先的记录。

3.嵌套集

此方法的思想是存储树的前缀遍历。在此首先访问树的根，然后按前缀顺序访问左子树的所有节点，然后再次按前缀顺序访问右子树的节点。遍历的顺序存储在两个附加字段中：left_key和right_key。该left_key字段包含进入子树之前的遍历步骤数，而right_key包含离开子树之前的遍历步骤数。结果，对于每个节点，其后代的节点号在节点号之间，而与它们的深度级别无关。此属性允许编写查询而无需采用递归。

图5嵌套集的实现

获取给定节点的子树：

WITH root AS (SELECT left_key, right_key FROM goods_category WHERE code=2 /* id of the node */)
SELECT * FROM goods_category
    WHERE left_key >= (SELECT left_key FROM root) 
        AND right_key <= (SELECT right_key FROM root)
ORDER BY level;

从根到给定节点的路径：

WITH node AS (SELECT left_key, right_key FROM goods_category WHERE code=8 /* id of the node */)
SELECT * FROM goods_category
    WHERE left_key <= (SELECT left_key FROM node) 
        AND right_key >= (SELECT right_key FROM node)
ORDER BY level;

检查“块”节点是否是“建筑材料/夹具”节点的后代：

SELECT CASE 
    WHEN exists(SELECT 1 from goods_category AS gc1, goods_category gc2 
        WHERE gc1.code = 1 
            AND gc2.code = 3 
            AND gc1.left_key <= gc2.left_key 
            AND gc1.right_key >= gc2.right_key)
    THEN 'true'
    ELSE 'false'
END

此方法的优点\是，它允许快速而简单的操作来选择节点的祖先，后代，其计数和深度级别，而无需递归。

方法的主要缺点是在插入或移动节点时必须重新分配遍历顺序。例如，为了将一个节点添加到最底层，有必要将所有节点的left_keyandright_key字段更新为其“ right and above”，这可能需要重新遍历整个树。可以通过分配给减少更新的数量left_key和right_key具有间隔，例如值10 000和200 000代替的1和20。这将允许插入节点而无需对其他节点重新编号。另一种方法是对left_key和的值使用实数right_key。

4.物化路径

也称为沿袭列

此方法的想法是显式存储从根开始的整个路径作为节点的主键（图6）。物化路径是表示树的一种优雅方式：每个节点都有一个直观的标识符，其中的各个部分都有明确定义的语义。此属性对于通用分类非常重要，包括国际疾病分类（ICD），科学论文中使用的通用小数分类（UDC），PACS（物理和天文学分类方案）。此方法的查询很简洁，但并不总是有效的，因为它们涉及子字符串匹配。

图6物化路径实现

获取给定节点的子树：

SELECT * FROM goods_category WHERE path LIKE '1.1%' ORDER BY path

从根到给定节点的路径：

SELECT * FROM goods_category WHERE '1.1.3' LIKE path||'%' ORDER BY path

检查“水泥”节点是否为“建筑材料/夹具”节点的后代：

SELECT CASE 
    WHEN exists(SELECT 1 FROM goods_category AS gc1, goods_category AS gc2
        WHERE gc1.name = 'Construction Material/Fixtures' 	
            AND gc2.name = 'Cement' 
            AND gc2.path LIKE gc1.path||'%')
    THEN 'true'
    ELSE 'false'
END

对于事先知道级别数和每个级别上的节点数的情况，可以通过使用带有严格定义的零填充小数位组的数字标识符来避免使用显式分隔符。这种方法被用于许多分类中，包括OKATO，NAICS。

也可以将单独的列用于层次结构的各个级别（多个谱系列）：这将消除使用子字符串匹配的必要性。

物化路径方法的优点是数据的直观表示以及某些常见查询的简单性。

该方法的缺点包括复杂的插入，移动和删除操作，完整性约束的简单实现以及由于需要进行子字符串匹配而导致的查询效率低下。在使用数字标识符方法的情况下，另一个可能的缺点是深度级别的数量有限。

4.1。PostgreSQL的Ltree模块

PostgreSQL有一个指定的用于树的ltree模块：它允许以便捷的方式有效地使用Materializedpath方法。该模块实现一种ltree数据类型，用于表示存储在分层树状结构中的数据的标签。提供了用于搜索标签树的广泛工具。

标签包括字母数字字符和下划线，并且每个标签应小于256个字节长（例如L1，42，building_materials）。

从根到特定节点的路径以点分隔的标签序列（例如L1.L2.L3）存储，最大可能长度等于65 Kb，但最好小于2 Kb。文档指出，这不是主要限制，它提供了一个DMOZ目录（http://dmoztools.net/）的示例，该目录的最大标签路径仅为240字节长。

该模块支持两种类型的模板，用于在标签上执行搜索：（lquery用于匹配ltree值的正则表达式）和ltxtquery（全文本ltree搜索模板）。两者之间的主要区别在于，ltxtquery匹配单词的方式与其在标签路径中的位置无关。

让我们看看如何使用ltree在示例树上执行常见操作。

首先，我们设置模块，创建表并用数据填充它。

CREATE EXTENSION "ltree";

CREATE TABLE goods_category_ltree (path ltree, name text);

INSERT INTO goods_category_ltree (path, name) VALUES
    ('construction_materials', 'Construction Material/Fixtures'),
    ('construction_materials.glass', 'Glass & Facade'),
    ('construction_materials.building_materials', 'Building Material'),
    ('construction_materials.roofing', 'Roofing & Cladding'),
    ('construction_materials.glass.blocks', 'Blocks'),
    ('construction_materials.glass.bricks', 'Bricks'),
    ('construction_materials.glass.cement', 'Cement'),
    ('construction_materials.building_materials.home_glazing', 'Home Glazing'),
    ('construction_materials.roofing.metal_sheet', 'Metal Roofing Sheet'),
    ('construction_materials.roofing.pvc_sheet', 'PVC Roofing Sheet');

获取给定节点的子树：

SELECT * FROM goods_category_ltree WHERE path @> (SELECT path FROM goods_category_ltree WHERE name = 'Blocks');

要么

SELECT path, name FROM goods_category_ltree WHERE path ~ 'construction_materials.glass.*';

从根到给定节点的路径：

SELECT * FROM goods_category_ltree WHERE path <@ (SELECT path FROM goods_category_ltree WHERE name = 'Construction Material/Fixtures');

检查“水泥”节点是否为“建筑材料/夹具”节点的后代：

SELECT CASE WHEN exists(SELECT 1 FROM goods_category_ltree 
    WHERE (
        SELECT path FROM goods_category_ltree WHERE name = 'Construction material/ Fixtures'
    ) @> (SELECT path FROM goods_category_ltree WHERE name = 'Cement'))
THEN 'true'
ELSE 'false'    
END

确定路径中标签的数量（深度级别）：

SELECT path, nlevel(path) FROM goods_category_ltree WHERE name ='Blocks';

结论

我们讨论了四种在关系数据库中存储树状结构的最流行方法。每种方法都有其优点和缺点。

在这四种方法中，只有邻接表方法可以避免冗余，并且不需要非参照完整性约束。插入和移动操作不会影响数据库中的其他记录。但是，大多数查询至少需要某种类型的递归。

其他三个方法不需要对其查询进行递归，但是如果不更新其他关联节点，则无法执行插入和移动操作。物化路径和嵌套集方法有可能的优化，仅解决了它们的一些局限性。

下图使用绿色示意性地表示对于所讨论的每种树存储方法，实际在关系数据库中存储了哪些数据。

邻接表	子集

嵌套集	物化路径

对于“邻接列表”和“物化路径”方法，存储的数据直接反映域的初始结构。对于子集方法，其结构由于祖先和后代之间的附加自反和传递连接而变得复杂。嵌套集方法的存储数据仅与初始结构间接相关。

	邻接表	子集	嵌套集	物化路径
树深度与子树搜索时间的相关性	重要的：每一个新的深度级别都会增加另一个递归 SELECT	中等	适中，可以为left_key和创建索引right_key	有效（子字符串匹配）。使用ltree模块可能会加快操作速度，因为它支持多种索引类型（B-tree和GiST超过ltree值）
节点插入	简单：不影响其他记录	复杂：需要将该节点添加到两个表中，以及每个后代节点的新记录	复杂：需要“在右侧和上方”更新所有节点	复杂：需要更新所有后代节点
节点移动	简单：不影响其他记录	复杂：需要更新该节点的祖先和后代的记录	复杂：需要“在右侧和上方”更新所有节点	复杂：需要更新后代和祖先节点
节点删除	简单，层叠	简单，级联	简单	复杂的子字符串匹配
冗余	没有	是	是	是
非参照完整性约束	并不需要	需要	需要	需要

翻译自 https://bitworks.software/en/2017-10-20-storing-trees-in-rdbms.html