关系数据库中存储层次数据的选项

技术背景

在关系数据库中存储层次数据是一个常见的需求，例如组织架构、产品分类等。然而，关系数据库的表格结构与层次数据的树形结构存在一定的不匹配，因此需要采用一些特殊的方法来存储和查询层次数据。

实现步骤

邻接列表模型 + 嵌套集模型

原理：使用邻接列表维护层次结构，使用嵌套集进行查询。邻接列表通过 parent 列记录每个节点的父节点，嵌套集通过 lft 和 rgt 列记录每个节点在树中的左右边界。
操作方法
- 查询所有子节点：查询 parent 列。
- 查询所有后代节点：查询 lft 在父节点的 lft 和 rgt 之间的节点。
- 查询所有祖先节点：查询 lft 小于当前节点的 lft 且 rgt 大于当前节点的 rgt 的节点，并按 parent 排序。
代码示例

-- 创建示例表
CREATE TABLE categories (
    category_id INT,
    name VARCHAR(255),
    parent INT,
    lft INT,
    rgt INT
);

-- 插入示例数据
INSERT INTO categories (category_id, name, parent, lft, rgt) VALUES
(1, 'ELECTRONICS', NULL, 1, 20),
(2, 'TELEVISIONS', 1, 2, 9),
(3, 'TUBE', 2, 3, 4),
(4, 'LCD', 2, 5, 6),
(5, 'PLASMA', 2, 7, 8),
(6, 'PORTABLE ELECTRONICS', 1, 10, 19),
(7, 'MP3 PLAYERS', 6, 11, 14),
(8, 'FLASH', 7, 12, 13),
(9, 'CD PLAYERS', 6, 15, 16),
(10, '2 WAY RADIOS', 6, 17, 18);

-- 查询所有子节点
SELECT * FROM categories WHERE parent = 1;

-- 查询所有后代节点
SELECT * FROM categories WHERE lft BETWEEN 2 AND 9;

-- 查询所有祖先节点
SELECT * FROM categories WHERE lft < 5 AND rgt > 6 ORDER BY parent;

优缺点：优点是插入新节点容易，查询速度较快；缺点是插入新节点时需要更新 lft 和 rgt 列，性能较差，不适合频繁插入或删除数据的场景。

多谱系列模型

原理：为每个谱系级别创建一个列，记录每个节点的所有祖先节点，直到根节点。低于当前节点级别的列设置为 0 或 NULL。
操作方法：可以通过简单的查询语句完成各种操作，如查询祖先节点、后代节点等。
代码示例

-- 创建示例表
CREATE TABLE taxons (
    TaxonId SMALLINT,
    ClassId SMALLINT,
    OrderId SMALLINT,
    FamilyId SMALLINT,
    GenusId SMALLINT,
    Name VARCHAR(150)
);

-- 插入示例数据
INSERT INTO taxons (TaxonId, ClassId, OrderId, FamilyId, GenusId, Name) VALUES
(254, 0, 0, 0, 0, 'Aves'),
(255, 254, 0, 0, 0, 'Gaviiformes'),
(256, 254, 255, 0, 0, 'Gaviidae'),
(257, 254, 255, 256, 0, 'Gavia'),
(258, 254, 255, 256, 257, 'Gavia stellata'),
(259, 254, 255, 256, 257, 'Gavia arctica'),
(260, 254, 255, 256, 257, 'Gavia immer'),
(261, 254, 255, 256, 257, 'Gavia adamsii'),
(262, 254, 0, 0, 0, 'Podicipediformes'),
(263, 254, 262, 0, 0, 'Podicipedidae'),
(264, 254, 262, 263, 0, 'Tachybaptus');

-- 查询所有祖先节点
SELECT * FROM taxons WHERE TaxonId = 258;

优缺点：优点是操作简单，查询效率高；缺点是层次深度有固定限制，内部节点的插入、删除和移动操作代价较高。

HierarchyId 数据类型和公共表表达式

原理：Microsoft SQL Server 2008 引入了 HierarchyId 数据类型和公共表表达式（CTE），用于处理层次数据。HierarchyId 数据类型可以表示树中的任意节点，CTE 可以递归查询层次数据。
操作方法：可以使用 HierarchyId 数据类型存储节点的层次信息，使用 CTE 进行递归查询。
代码示例

-- 创建示例表
CREATE TABLE Employees (
    EmployeeID INT,
    Name NVARCHAR(50),
    Path HierarchyId
);

-- 插入示例数据
INSERT INTO Employees (EmployeeID, Name, Path) VALUES
(1, 'CEO', '/'),
(2, 'Manager1', '/1/'),
(3, 'Employee1', '/1/1/'),
(4, 'Employee2', '/1/2/'),
(5, 'Manager2', '/2/'),
(6, 'Employee3', '/2/1/');

-- 查询所有后代节点
WITH RecursiveCTE AS (
    SELECT EmployeeID, Name, Path
    FROM Employees
    WHERE Path = '/1/'
    UNION ALL
    SELECT e.EmployeeID, e.Name, e.Path
    FROM Employees e
    JOIN RecursiveCTE r ON e.Path.IsDescendantOf(r.Path) = 1
)
SELECT * FROM RecursiveCTE;

优缺点：优点是 SQL Server 原生支持，查询方便；缺点是仅适用于 SQL Server 数据库。

数组实现的谱系列或物化路径

原理：如果数据库支持数组，可以将谱系列或物化路径实现为父节点 ID 的数组。例如，在 PostgreSQL 中，可以使用数组和集合运算符查询层次数据，并使用 GIN 索引提高性能。
操作方法：将每个节点的所有祖先节点 ID 存储在一个数组中，使用集合运算符进行查询。
代码示例

-- 创建示例表
CREATE TABLE categories (
    id INT,
    name VARCHAR(255),
    path INTEGER[]
);

-- 插入示例数据
INSERT INTO categories (id, name, path) VALUES
(1, 'ELECTRONICS', ARRAY[1]),
(2, 'TELEVISIONS', ARRAY[1, 2]),
(3, 'TUBE', ARRAY[1, 2, 3]);

-- 查询所有后代节点
SELECT * FROM categories WHERE path @> ARRAY[1, 2];

优缺点：优点是查询简单，性能较好；缺点是需要数据库支持数组类型。

闭包表

原理：闭包表通过记录所有节点之间的祖先 - 后代关系来存储层次数据。闭包表通常包含三列：ANCESTOR_ID、DESCENDANT_ID 和 DEPTH。
操作方法：使用触发器和存储过程维护闭包表，查询时通过连接闭包表和原始表获取所需信息。
代码示例

-- 创建示例表
CREATE TABLE nomenclature (
    id INT,
    name VARCHAR(255),
    parent_id INT
);

CREATE TABLE nom_helper (
    ancestor_id INT,
    descendant_id INT,
    depth INT
);

-- 创建触发器
CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $$
DECLARE
    old_parent INTEGER;
    new_parent INTEGER;
    id_nom INTEGER;
    txt_name TEXT;
BEGIN
    -- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
    -- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
    -- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
        EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
            SELECT $1.id,$1.id,0 UNION ALL
            SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE
        -- EXECUTE does not support conditional statements inside
        EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
        IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
            EXECUTE '
            -- prevent cycles in the tree
            UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
                || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
                || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
            -- first remove edges between all old parents of node and its descendants
            DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
                (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
                AND ancestor_id IN
                (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
            -- then add edges for all new parents ...
            INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
                SELECT child_id,ancestor_id,d_c+d_a FROM
                (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
                CROSS JOIN
                (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
                || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
        END IF;
    END IF;
    RETURN NULL;
END;
$$;

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('nomenclature', 'nom_helper', 'parent_id');

-- 重建闭包表
CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
        INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
            WITH RECURSIVE tree AS
            (
                SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
                UNION ALL 
                SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
                JOIN tree ON child_id = ' || fld_parent || '
            )
            SELECT * FROM tree;';
END;
$$;

-- 查询所有后代节点
SELECT nomenclature.*,depth FROM nom_helper LEFT JOIN nomenclature ON descendant_id = nomenclature.id WHERE ancestor_id = 1 AND depth <> 0;

优缺点：优点是查询简单，适用于频繁查询的场景；缺点是插入和删除操作需要维护闭包表，性能较差。

最佳实践

根据具体需求选择合适的存储方法。如果需要频繁插入和删除数据，邻接列表模型可能更适合；如果需要频繁查询后代节点，嵌套集模型或闭包表可能更合适。
使用索引提高查询性能。例如，在嵌套集模型中，可以为 lft 和 rgt 列创建索引；在闭包表中，可以为 ANCESTOR_ID 和 DESCENDANT_ID 列创建索引。
定期维护数据，避免数据冗余和不一致。例如，在使用闭包表时，定期重建闭包表以确保数据的一致性。

常见问题

插入和删除操作性能问题：某些存储方法（如嵌套集模型和闭包表）在插入和删除数据时需要更新大量的记录，导致性能下降。可以通过优化算法、使用存储过程或触发器等方式提高性能。
层次深度限制问题：多谱系列模型有固定的层次深度限制，无法处理深度较大的层次数据。可以考虑使用其他方法，如闭包表或 HierarchyId 数据类型。
数据一致性问题：在使用多种存储方法时，需要确保数据的一致性。例如，在使用邻接列表模型和嵌套集模型时，插入新节点时需要同时更新 parent 列和 lft、rgt 列。可以使用存储过程或触发器来保证数据的一致性。

数据库开发 > 层次数据存储

#SQL #数据库开发 #PostgreSQL #Microsoft SQL Server #层次数据存储

关系数据库中存储层次数据的选项

https://119291.xyz/posts/options-for-storing-hierarchical-data-in-relational-database/

作者

发布于

2025年5月29日

许可协议

在 Android 应用中打开网页的方法上一篇

Python print函数输出刷新方法下一篇